17c478bd9Sstevel@tonic-gate /* 27c478bd9Sstevel@tonic-gate * CDDL HEADER START 37c478bd9Sstevel@tonic-gate * 47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the 5*cb5caa98Sdjl * Common Development and Distribution License (the "License"). 6*cb5caa98Sdjl * You may not use this file except in compliance with the License. 77c478bd9Sstevel@tonic-gate * 87c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 97c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 107c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions 117c478bd9Sstevel@tonic-gate * and limitations under the License. 127c478bd9Sstevel@tonic-gate * 137c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 147c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 157c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 167c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 177c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 187c478bd9Sstevel@tonic-gate * 197c478bd9Sstevel@tonic-gate * CDDL HEADER END 207c478bd9Sstevel@tonic-gate */ 217c478bd9Sstevel@tonic-gate /* 22*cb5caa98Sdjl * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 23f166393fSesolom * Use is subject to license terms. 247c478bd9Sstevel@tonic-gate */ 257c478bd9Sstevel@tonic-gate 267c478bd9Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 277c478bd9Sstevel@tonic-gate 287c478bd9Sstevel@tonic-gate #include <stdio.h> 297c478bd9Sstevel@tonic-gate #include <string.h> 307c478bd9Sstevel@tonic-gate #include <stdlib.h> 317c478bd9Sstevel@tonic-gate 32*cb5caa98Sdjl #include "cache.h" 337c478bd9Sstevel@tonic-gate 34*cb5caa98Sdjl nsc_keephot_t * 357c478bd9Sstevel@tonic-gate maken(int n) 367c478bd9Sstevel@tonic-gate { 37*cb5caa98Sdjl nsc_keephot_t *ret; 387c478bd9Sstevel@tonic-gate 39*cb5caa98Sdjl ++n; 40*cb5caa98Sdjl ret = (nsc_keephot_t *)calloc(n, sizeof (nsc_keephot_t)); 41*cb5caa98Sdjl if (ret == NULL) 42*cb5caa98Sdjl return (NULL); 43*cb5caa98Sdjl ret[0].num = n - 1; 447c478bd9Sstevel@tonic-gate return (ret); 457c478bd9Sstevel@tonic-gate } 467c478bd9Sstevel@tonic-gate 47*cb5caa98Sdjl void * 48*cb5caa98Sdjl insertn(nsc_keephot_t *table, uint_t n, void *data) 497c478bd9Sstevel@tonic-gate { 50*cb5caa98Sdjl void *olddata; 51*cb5caa98Sdjl int size, guess, base, last; 527c478bd9Sstevel@tonic-gate 53*cb5caa98Sdjl if (n < 1 || table[1].num > n) { 547c478bd9Sstevel@tonic-gate return (data); 55*cb5caa98Sdjl } 567c478bd9Sstevel@tonic-gate 57*cb5caa98Sdjl size = table[0].num; 58*cb5caa98Sdjl if (table[size].num < n) /* biggest so far */ 597c478bd9Sstevel@tonic-gate guess = size; 607c478bd9Sstevel@tonic-gate else { 617c478bd9Sstevel@tonic-gate base = 1; 627c478bd9Sstevel@tonic-gate last = size; 637c478bd9Sstevel@tonic-gate while (last >= base) { 647c478bd9Sstevel@tonic-gate guess = (last+base)/2; 65*cb5caa98Sdjl if (table[guess].num == n) 667c478bd9Sstevel@tonic-gate goto doit; 67*cb5caa98Sdjl if (table[guess].num > n) 687c478bd9Sstevel@tonic-gate last = guess - 1; 697c478bd9Sstevel@tonic-gate else 707c478bd9Sstevel@tonic-gate base = guess + 1; 717c478bd9Sstevel@tonic-gate } 727c478bd9Sstevel@tonic-gate guess = last; 737c478bd9Sstevel@tonic-gate } 74*cb5caa98Sdjl 757c478bd9Sstevel@tonic-gate doit: 76*cb5caa98Sdjl olddata = table[1].ptr; 77*cb5caa98Sdjl (void) memmove(table + 1, table + 2, 78*cb5caa98Sdjl sizeof (nsc_keephot_t) * (guess-1)); 79*cb5caa98Sdjl table[guess].ptr = data; 80*cb5caa98Sdjl table[guess].num = n; 817c478bd9Sstevel@tonic-gate return (olddata); 827c478bd9Sstevel@tonic-gate } 83