176613Sru/* $NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $ */ 276613Sru 376613Sru/* 476613Sru * Copyright (c) 2001 Christopher G. Demetriou 576613Sru * All rights reserved. 676613Sru * 776613Sru * Redistribution and use in source and binary forms, with or without 876613Sru * modification, are permitted provided that the following conditions 976613Sru * are met: 1076613Sru * 1. Redistributions of source code must retain the above copyright 1176613Sru * notice, this list of conditions and the following disclaimer. 1276613Sru * 2. Redistributions in binary form must reproduce the above copyright 1376613Sru * notice, this list of conditions and the following disclaimer in the 1476613Sru * documentation and/or other materials provided with the distribution. 1576613Sru * 3. All advertising materials mentioning features or use of this software 1676613Sru * must display the following acknowledgement: 1776613Sru * This product includes software developed for the 1876613Sru * NetBSD Project. See http://www.netbsd.org/ for 1976613Sru * information about NetBSD. 2076613Sru * 4. The name of the author may not be used to endorse or promote products 2176613Sru * derived from this software without specific prior written permission. 2276613Sru * 2376613Sru * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 2476613Sru * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 2576613Sru * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 2676613Sru * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 2776613Sru * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2876613Sru * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2976613Sru * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3076613Sru * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3176613Sru * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 3276613Sru * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3376613Sru * 3476613Sru * <<Id: LICENSE,v 1.2 2000/06/14 15:57:33 cgd Exp>> 3576613Sru */ 3676613Sru 3776613Sru/* 3876613Sru * hcreate() / hsearch() / hdestroy() 3976613Sru * 4076613Sru * SysV/XPG4 hash table functions. 4176613Sru * 4276613Sru * Implementation done based on NetBSD manual page and Solaris manual page, 4376613Sru * plus my own personal experience about how they're supposed to work. 4476613Sru * 4576613Sru * I tried to look at Knuth (as cited by the Solaris manual page), but 4676613Sru * nobody had a copy in the office, so... 4776613Sru */ 4876613Sru 4976613Sru#include <sys/cdefs.h> 5092986Sobrien#if 0 5176613Sru#if defined(LIBC_SCCS) && !defined(lint) 5276613Sru__RCSID("$NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $"); 5376613Sru#endif /* LIBC_SCCS and not lint */ 5492986Sobrien#endif 5592986Sobrien__FBSDID("$FreeBSD$"); 5676613Sru 5776613Sru#include <sys/types.h> 5876613Sru#include <sys/queue.h> 5976613Sru#include <errno.h> 6076613Sru#include <search.h> 6176613Sru#include <stdlib.h> 6276613Sru#include <string.h> 6376613Sru 6476613Sru/* 6576613Sru * DO NOT MAKE THIS STRUCTURE LARGER THAN 32 BYTES (4 ptrs on 64-bit 6676613Sru * ptr machine) without adjusting MAX_BUCKETS_LG2 below. 6776613Sru */ 6876613Srustruct internal_entry { 6976613Sru SLIST_ENTRY(internal_entry) link; 7076613Sru ENTRY ent; 7176613Sru}; 7276613SruSLIST_HEAD(internal_head, internal_entry); 7376613Sru 7476613Sru#define MIN_BUCKETS_LG2 4 7576613Sru#define MIN_BUCKETS (1 << MIN_BUCKETS_LG2) 7676613Sru 7776613Sru/* 7876613Sru * max * sizeof internal_entry must fit into size_t. 7976613Sru * assumes internal_entry is <= 32 (2^5) bytes. 8076613Sru */ 8176613Sru#define MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5) 8276613Sru#define MAX_BUCKETS ((size_t)1 << MAX_BUCKETS_LG2) 8376613Sru 8476613Sru/* Default hash function, from db/hash/hash_func.c */ 8576613Sruextern u_int32_t (*__default_hash)(const void *, size_t); 8676613Sru 8776613Srustatic struct internal_head *htable; 8876613Srustatic size_t htablesize; 8976613Sru 9076613Sruint 9176613Sruhcreate(size_t nel) 9276613Sru{ 9376613Sru size_t idx; 9476613Sru unsigned int p2; 9576613Sru 96180323Sdanger /* Make sure this is not called when a table already exists. */ 9776613Sru if (htable != NULL) { 9876613Sru errno = EINVAL; 9976613Sru return 0; 10076613Sru } 10176613Sru 10276613Sru /* If nel is too small, make it min sized. */ 10376613Sru if (nel < MIN_BUCKETS) 10476613Sru nel = MIN_BUCKETS; 10576613Sru 106180323Sdanger /* If it is too large, cap it. */ 10776613Sru if (nel > MAX_BUCKETS) 10876613Sru nel = MAX_BUCKETS; 10976613Sru 110180323Sdanger /* If it is not a power of two in size, round up. */ 11176613Sru if ((nel & (nel - 1)) != 0) { 11276613Sru for (p2 = 0; nel != 0; p2++) 11376613Sru nel >>= 1; 11476613Sru nel = 1 << p2; 11576613Sru } 11676613Sru 11776613Sru /* Allocate the table. */ 11876613Sru htablesize = nel; 11976613Sru htable = malloc(htablesize * sizeof htable[0]); 12076613Sru if (htable == NULL) { 12176613Sru errno = ENOMEM; 12276613Sru return 0; 12376613Sru } 12476613Sru 12576613Sru /* Initialize it. */ 12676613Sru for (idx = 0; idx < htablesize; idx++) 12776613Sru SLIST_INIT(&htable[idx]); 12876613Sru 12976613Sru return 1; 13076613Sru} 13176613Sru 13276613Sruvoid 13376613Sruhdestroy(void) 13476613Sru{ 13576613Sru struct internal_entry *ie; 13676613Sru size_t idx; 13776613Sru 13876613Sru if (htable == NULL) 13976613Sru return; 14076613Sru 14176613Sru for (idx = 0; idx < htablesize; idx++) { 14276613Sru while (!SLIST_EMPTY(&htable[idx])) { 14376613Sru ie = SLIST_FIRST(&htable[idx]); 14476613Sru SLIST_REMOVE_HEAD(&htable[idx], link); 14576613Sru free(ie->ent.key); 14676613Sru free(ie); 14776613Sru } 14876613Sru } 14976613Sru free(htable); 15076613Sru htable = NULL; 15176613Sru} 15276613Sru 15376613SruENTRY * 15476613Sruhsearch(ENTRY item, ACTION action) 15576613Sru{ 15676613Sru struct internal_head *head; 15776613Sru struct internal_entry *ie; 15876613Sru uint32_t hashval; 15976613Sru size_t len; 16076613Sru 16176613Sru len = strlen(item.key); 16276613Sru hashval = (*__default_hash)(item.key, len); 16376613Sru 16476613Sru head = &htable[hashval & (htablesize - 1)]; 16576613Sru ie = SLIST_FIRST(head); 16676613Sru while (ie != NULL) { 16776613Sru if (strcmp(ie->ent.key, item.key) == 0) 16876613Sru break; 16976613Sru ie = SLIST_NEXT(ie, link); 17076613Sru } 17176613Sru 17276613Sru if (ie != NULL) 17376613Sru return &ie->ent; 17476613Sru else if (action == FIND) 17576613Sru return NULL; 17676613Sru 17776613Sru ie = malloc(sizeof *ie); 17876613Sru if (ie == NULL) 17976613Sru return NULL; 18076613Sru ie->ent.key = item.key; 18176613Sru ie->ent.data = item.data; 18276613Sru 18376613Sru SLIST_INSERT_HEAD(head, ie, link); 18476613Sru return &ie->ent; 18576613Sru} 186