X-Git-Url: https://git.saurik.com/apple/libc.git/blobdiff_plain/224c70764cab4e0e39a26aaf3ad3016552f62f55..511daa4c8e95ca3a9f4a918942d9350855df1da0:/stdlib/hcreate-fbsd.c diff --git a/stdlib/hcreate-fbsd.c b/stdlib/hcreate-fbsd.c deleted file mode 100644 index 6ab33e5..0000000 --- a/stdlib/hcreate-fbsd.c +++ /dev/null @@ -1,185 +0,0 @@ -/* $NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $ */ - -/* - * Copyright (c) 2001 Christopher G. Demetriou - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions - * are met: - * 1. Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * 2. Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed for the - * NetBSD Project. See http://www.netbsd.org/ for - * information about NetBSD. - * 4. The name of the author may not be used to endorse or promote products - * derived from this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. - * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT - * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF - * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * <> - */ - -/* - * hcreate() / hsearch() / hdestroy() - * - * SysV/XPG4 hash table functions. - * - * Implementation done based on NetBSD manual page and Solaris manual page, - * plus my own personal experience about how they're supposed to work. - * - * I tried to look at Knuth (as cited by the Solaris manual page), but - * nobody had a copy in the office, so... - */ - -#include -#if 0 -#if defined(LIBC_SCCS) && !defined(lint) -__RCSID("$NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $"); -#endif /* LIBC_SCCS and not lint */ -#endif -__FBSDID("$FreeBSD: src/lib/libc/stdlib/hcreate.c,v 1.3 2002/06/27 13:18:27 deischen Exp $"); - -#include -#include -#include -#include -#include -#include - -/* - * DO NOT MAKE THIS STRUCTURE LARGER THAN 32 BYTES (4 ptrs on 64-bit - * ptr machine) without adjusting MAX_BUCKETS_LG2 below. - */ -struct internal_entry { - SLIST_ENTRY(internal_entry) link; - ENTRY ent; -}; -SLIST_HEAD(internal_head, internal_entry); - -#define MIN_BUCKETS_LG2 4 -#define MIN_BUCKETS (1 << MIN_BUCKETS_LG2) - -/* - * max * sizeof internal_entry must fit into size_t. - * assumes internal_entry is <= 32 (2^5) bytes. - */ -#define MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5) -#define MAX_BUCKETS ((size_t)1 << MAX_BUCKETS_LG2) - -/* Default hash function, from db/hash/hash_func.c */ -extern u_int32_t (*__default_hash)(const void *, size_t); - -static struct internal_head *htable; -static size_t htablesize; - -int -hcreate(size_t nel) -{ - size_t idx; - unsigned int p2; - - /* Make sure this this isn't called when a table already exists. */ - if (htable != NULL) { - errno = EINVAL; - return 0; - } - - /* If nel is too small, make it min sized. */ - if (nel < MIN_BUCKETS) - nel = MIN_BUCKETS; - - /* If it's too large, cap it. */ - if (nel > MAX_BUCKETS) - nel = MAX_BUCKETS; - - /* If it's is not a power of two in size, round up. */ - if ((nel & (nel - 1)) != 0) { - for (p2 = 0; nel != 0; p2++) - nel >>= 1; - nel = 1 << p2; - } - - /* Allocate the table. */ - htablesize = nel; - htable = malloc(htablesize * sizeof htable[0]); - if (htable == NULL) { - errno = ENOMEM; - return 0; - } - - /* Initialize it. */ - for (idx = 0; idx < htablesize; idx++) - SLIST_INIT(&htable[idx]); - - return 1; -} - -void -hdestroy(void) -{ - struct internal_entry *ie; - size_t idx; - - if (htable == NULL) - return; - - for (idx = 0; idx < htablesize; idx++) { - while (!SLIST_EMPTY(&htable[idx])) { - ie = SLIST_FIRST(&htable[idx]); - SLIST_REMOVE_HEAD(&htable[idx], link); - free(ie->ent.key); - free(ie); - } - } - free(htable); - htable = NULL; -} - -ENTRY * -hsearch(ENTRY item, ACTION action) -{ - struct internal_head *head; - struct internal_entry *ie; - uint32_t hashval; - size_t len; - - len = strlen(item.key); - hashval = (*__default_hash)(item.key, len); - - head = &htable[hashval & (htablesize - 1)]; - ie = SLIST_FIRST(head); - while (ie != NULL) { - if (strcmp(ie->ent.key, item.key) == 0) - break; - ie = SLIST_NEXT(ie, link); - } - - if (ie != NULL) - return &ie->ent; - else if (action == FIND) - return NULL; - - ie = malloc(sizeof *ie); - if (ie == NULL) - return NULL; - ie->ent.key = item.key; - ie->ent.data = item.data; - - SLIST_INSERT_HEAD(head, ie, link); - return &ie->ent; -} diff --git a/stdlib/hcreate-fbsd.c b/stdlib/hcreate-fbsd.c new file mode 120000 index 0000000..b06b592 --- /dev/null +++ b/stdlib/hcreate-fbsd.c @@ -0,0 +1 @@ +./hcreate.c \ No newline at end of file