[BACK]Return to hcreate.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / lib / libc / stdlib

Annotation of src/lib/libc/stdlib/hcreate.c, Revision 1.4

1.4     ! salo        1: /* $NetBSD: hcreate.c,v 1.3 2001/02/21 16:31:01 lukem Exp $ */
1.1       cgd         2:
                      3: /*
                      4:  * Copyright (c) 2001 Christopher G. Demetriou
                      5:  * All rights reserved.
                      6:  *
                      7:  * Redistribution and use in source and binary forms, with or without
                      8:  * modification, are permitted provided that the following conditions
                      9:  * are met:
                     10:  * 1. Redistributions of source code must retain the above copyright
                     11:  *    notice, this list of conditions and the following disclaimer.
                     12:  * 2. Redistributions in binary form must reproduce the above copyright
                     13:  *    notice, this list of conditions and the following disclaimer in the
                     14:  *    documentation and/or other materials provided with the distribution.
                     15:  * 3. All advertising materials mentioning features or use of this software
                     16:  *    must display the following acknowledgement:
                     17:  *          This product includes software developed for the
1.4     ! salo       18:  *          NetBSD Project.  See http://www.NetBSD.org/ for
1.1       cgd        19:  *          information about NetBSD.
                     20:  * 4. The name of the author may not be used to endorse or promote products
                     21:  *    derived from this software without specific prior written permission.
                     22:  *
                     23:  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
                     24:  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
                     25:  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
                     26:  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
                     27:  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
                     28:  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
                     29:  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
                     30:  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
                     31:  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
                     32:  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
                     33:  *
                     34:  * <<Id: LICENSE,v 1.2 2000/06/14 15:57:33 cgd Exp>>
                     35:  */
                     36:
                     37: /*
                     38:  * hcreate() / hsearch() / hdestroy()
                     39:  *
                     40:  * SysV/XPG4 hash table functions.
                     41:  *
                     42:  * Implementation done based on NetBSD manual page and Solaris manual page,
                     43:  * plus my own personal experience about how they're supposed to work.
                     44:  *
                     45:  * I tried to look at Knuth (as cited by the Solaris manual page), but
                     46:  * nobody had a copy in the office, so...
                     47:  */
                     48:
                     49: #include <sys/cdefs.h>
                     50: #if defined(LIBC_SCCS) && !defined(lint)
1.4     ! salo       51: __RCSID("$NetBSD: hcreate.c,v 1.3 2001/02/21 16:31:01 lukem Exp $");
1.1       cgd        52: #endif /* LIBC_SCCS and not lint */
                     53:
                     54: #if !defined(lint)
                     55: __COPYRIGHT(
                     56: "@(#) Copyright (c) 2001 Christopher G. Demetriou.  All rights reserved.\n");
                     57: #endif /* not lint */
                     58:
                     59: #include "namespace.h"
                     60: #include <assert.h>
                     61: #include <errno.h>
                     62: #include <inttypes.h>
                     63: #include <search.h>
                     64: #include <stdlib.h>
                     65: #include <string.h>
                     66: #include <sys/queue.h>
                     67:
                     68: /*
                     69:  * DO NOT MAKE THIS STRUCTURE LARGER THAN 32 BYTES (4 ptrs on 64-bit
                     70:  * ptr machine) without adjusting MAX_BUCKETS_LG2 below.
                     71:  */
                     72: struct internal_entry {
                     73:        SLIST_ENTRY(internal_entry) link;
                     74:        ENTRY ent;
                     75: };
                     76: SLIST_HEAD(internal_head, internal_entry);
                     77:
                     78: #define        MIN_BUCKETS_LG2 4
                     79: #define        MIN_BUCKETS     (1 << MIN_BUCKETS_LG2)
                     80:
                     81: /*
                     82:  * max * sizeof internal_entry must fit into size_t.
                     83:  * assumes internal_entry is <= 32 (2^5) bytes.
                     84:  */
                     85: #define        MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5)
1.2       ross       86: #define        MAX_BUCKETS     ((size_t)1 << MAX_BUCKETS_LG2)
1.1       cgd        87:
                     88: /* Default hash function, from db/hash/hash_func.c */
                     89: extern u_int32_t (*__default_hash)(const void *, size_t);
                     90:
                     91: static struct internal_head *htable;
                     92: static size_t htablesize;
                     93:
                     94: int
                     95: hcreate(size_t nel)
                     96: {
                     97:        size_t idx;
                     98:        unsigned int p2;
                     99:
                    100:        /* Make sure this this isn't called when a table already exists. */
                    101:        _DIAGASSERT(htable == NULL);
                    102:        if (htable != NULL) {
                    103:                errno = EINVAL;
                    104:                return 0;
                    105:        }
                    106:
                    107:        /* If nel is too small, make it min sized. */
                    108:        if (nel < MIN_BUCKETS)
                    109:                nel = MIN_BUCKETS;
                    110:
                    111:        /* If it's too large, cap it. */
                    112:        if (nel > MAX_BUCKETS)
                    113:                nel = MAX_BUCKETS;
                    114:
                    115:        /* If it's is not a power of two in size, round up. */
                    116:        if ((nel & (nel - 1)) != 0) {
                    117:                for (p2 = 0; nel != 0; p2++)
                    118:                        nel >>= 1;
                    119:                _DIAGASSERT(p2 <= MAX_BUCKETS_LG2);
                    120:                nel = 1 << p2;
                    121:        }
                    122:
                    123:        /* Allocate the table. */
                    124:        htablesize = nel;
                    125:        htable = malloc(htablesize * sizeof htable[0]);
                    126:        if (htable == NULL) {
                    127:                errno = ENOMEM;
                    128:                return 0;
                    129:        }
                    130:
                    131:        /* Initialize it. */
                    132:        for (idx = 0; idx < htablesize; idx++)
                    133:                SLIST_INIT(&htable[idx]);
                    134:
                    135:        return 1;
                    136: }
                    137:
                    138: void
                    139: hdestroy(void)
                    140: {
                    141:        struct internal_entry *ie;
                    142:        size_t idx;
                    143:
                    144:        _DIAGASSERT(htable != NULL);
                    145:        if (htable == NULL)
                    146:                return;
                    147:
                    148:        for (idx = 0; idx < htablesize; idx++) {
                    149:                while (!SLIST_EMPTY(&htable[idx])) {
                    150:                        ie = SLIST_FIRST(&htable[idx]);
                    151:                        SLIST_REMOVE_HEAD(&htable[idx], link);
                    152:                        free(ie->ent.key);
                    153:                        free(ie);
                    154:                }
                    155:        }
                    156:        free(htable);
                    157:        htable = NULL;
                    158: }
                    159:
                    160: ENTRY *
                    161: hsearch(ENTRY item, ACTION action)
                    162: {
                    163:        struct internal_head *head;
                    164:        struct internal_entry *ie;
                    165:        uint32_t hashval;
                    166:        size_t len;
                    167:
                    168:        _DIAGASSERT(htable != NULL);
1.3       lukem     169:        _DIAGASSERT(item.key != NULL);
                    170:        _DIAGASSERT(action == ENTER || action == FIND);
1.1       cgd       171:
                    172:        len = strlen(item.key);
                    173:        hashval = (*__default_hash)(item.key, len);
                    174:
                    175:        head = &htable[hashval & (htablesize - 1)];
                    176:        ie = SLIST_FIRST(head);
                    177:        while (ie != NULL) {
                    178:                if (strcmp(ie->ent.key, item.key) == 0)
                    179:                        break;
                    180:                ie = SLIST_NEXT(ie, link);
                    181:        }
                    182:
                    183:        if (ie != NULL)
                    184:                return &ie->ent;
                    185:        else if (action == FIND)
                    186:                return NULL;
                    187:
                    188:        ie = malloc(sizeof *ie);
                    189:        if (ie == NULL)
                    190:                return NULL;
                    191:        ie->ent.key = item.key;
                    192:        ie->ent.data = item.data;
                    193:
                    194:        SLIST_INSERT_HEAD(head, ie, link);
                    195:        return &ie->ent;
                    196: }

CVSweb <webmaster@jp.NetBSD.org>