Return to hash.c CVS log

Up to [The Machine Emulator] / tme / libtme

Annotation of tme/libtme/hash.c, revision 1.1

1.1     ! root        1: /* $Id: hash.c,v 1.2 2003/09/01 14:24:08 fredette Exp $ */
        !             2: 
        !             3: /* libtme/hash.c - hash table support: */
        !             4: 
        !             5: /*
        !             6:  * Copyright (c) 2003 Matt Fredette
        !             7:  * All rights reserved.
        !             8:  *
        !             9:  * Redistribution and use in source and binary forms, with or without
        !            10:  * modification, are permitted provided that the following conditions
        !            11:  * are met:
        !            12:  * 1. Redistributions of source code must retain the above copyright
        !            13:  *    notice, this list of conditions and the following disclaimer.
        !            14:  * 2. Redistributions in binary form must reproduce the above copyright
        !            15:  *    notice, this list of conditions and the following disclaimer in the
        !            16:  *    documentation and/or other materials provided with the distribution.
        !            17:  * 3. All advertising materials mentioning features or use of this software
        !            18:  *    must display the following acknowledgement:
        !            19:  *      This product includes software developed by Matt Fredette.
        !            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
        !            25:  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
        !            26:  * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
        !            27:  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
        !            28:  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
        !            29:  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
        !            30:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
        !            31:  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
        !            32:  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
        !            33:  * POSSIBILITY OF SUCH DAMAGE.
        !            34:  */
        !            35: 
        !            36: #include <tme/common.h>
        !            37: _TME_RCSID("$Id: hash.c,v 1.2 2003/09/01 14:24:08 fredette Exp $");
        !            38: 
        !            39: /* includes: */
        !            40: #include <tme/hash.h>
        !            41: 
        !            42: /* our hash table size array: */
        !            43: static unsigned long _tme_hash_sizes[] = {
        !            44:   2,
        !            45:   3,
        !            46:   5,
        !            47:   7,
        !            48:   11,
        !            49:   17,
        !            50:   37,
        !            51:   83,
        !            52:   281,
        !            53:   421,
        !            54:   631,
        !            55:   947,
        !            56:   2131,
        !            57:   7193,
        !            58:   10789,
        !            59:   16183,
        !            60:   81929,
        !            61:   414763,
        !            62:   933217,
        !            63:   10629917,
        !            64:   35875969,
        !            65:   80720929,
        !            66: };
        !            67: 
        !            68: /* this allocates and returns a new hash: */
        !            69: tme_hash_t
        !            70: tme_hash_new(tme_hash_func_t hash_func,
        !            71:             tme_compare_func_t compare_func,
        !            72:             tme_hash_data_t value_null)
        !            73: {
        !            74:   tme_hash_t hash;
        !            75: 
        !            76:   hash = tme_new0(struct _tme_hash, 1);
        !            77:   hash->_tme_hash_size = _tme_hash_sizes[0];
        !            78:   hash->_tme_hash_table = 
        !            79:     tme_new0(struct _tme_hash_bucket *,
        !            80:             hash->_tme_hash_size);
        !            81:   hash->_tme_hash_count = 0;
        !            82:   hash->_tme_hash_hash = hash_func;
        !            83:   hash->_tme_hash_compare = compare_func;
        !            84:   hash->_tme_hash_null = value_null;
        !            85:   return (hash);
        !            86: }
        !            87: 
        !            88: /* this destroys a hash: */
        !            89: void
        !            90: tme_hash_destroy(tme_hash_t hash)
        !            91: {
        !            92:   struct _tme_hash_bucket *bucket, *bucket_next;
        !            93:   unsigned long bucket_i;
        !            94: 
        !            95:   /* free all of the buckets in the hash table: */
        !            96:   for (bucket_i = 0;
        !            97:        bucket_i < hash->_tme_hash_size;
        !            98:        bucket_i++) {
        !            99:     for (bucket = hash->_tme_hash_table[bucket_i];
        !           100:         bucket != NULL;
        !           101:         bucket = bucket_next) {
        !           102:       bucket_next = bucket->_tme_hash_bucket_next;
        !           103:       tme_free(bucket);
        !           104:     }
        !           105:   }
        !           106:   tme_free(hash->_tme_hash_table);
        !           107:   tme_free(hash);
        !           108: }
        !           109: 
        !           110: /* this does an internal lookup in a hash table: */
        !           111: static struct _tme_hash_bucket *
        !           112: _tme_hash_lookup_internal(tme_hash_t hash,
        !           113:                          tme_hash_data_t key,
        !           114:                          struct _tme_hash_bucket ***__bucket)
        !           115: {
        !           116:   unsigned long bucket_i;
        !           117:   struct _tme_hash_bucket **_bucket, *bucket;
        !           118:   
        !           119:   /* hash the key: */
        !           120:   bucket_i = (*hash->_tme_hash_hash)(key) % hash->_tme_hash_size;
        !           121: 
        !           122:   /* walk the chain of buckets: */
        !           123:   for (_bucket = hash->_tme_hash_table + bucket_i;
        !           124:        (bucket = *_bucket) != NULL;
        !           125:        _bucket = &bucket->_tme_hash_bucket_next) {
        !           126:     
        !           127:     /* compare the key in this bucket with the lookup key.
        !           128:        if it succeeds, return the bucket: */
        !           129:     if ((*hash->_tme_hash_compare)(key, bucket->_tme_hash_bucket_key)) {
        !           130:       if (__bucket != NULL) {
        !           131:        *__bucket = _bucket;
        !           132:       }
        !           133:       return (bucket);
        !           134:     }
        !           135:   }
        !           136: 
        !           137:   /* the lookup failed.  return where the bucket might be inserted: */
        !           138:   if (__bucket != NULL) {
        !           139:     *__bucket = _bucket;
        !           140:   }
        !           141:   return (NULL);
        !           142: }
        !           143: 
        !           144: /* this inserts a value into a hash table: */
        !           145: void
        !           146: tme_hash_insert(tme_hash_t hash,
        !           147:                tme_hash_data_t key,
        !           148:                tme_hash_data_t value)
        !           149: {
        !           150:   struct _tme_hash_bucket *bucket, *bucket_next, **_bucket;
        !           151:   struct _tme_hash hash_new;
        !           152:   int size_i;
        !           153:   unsigned long bucket_i;
        !           154: 
        !           155:   /* if this key is not already present in the hash table: */
        !           156:   bucket = _tme_hash_lookup_internal(hash, key, &_bucket);
        !           157:   if (bucket == NULL) {
        !           158: 
        !           159:     /* if we need to resize this hash table: */
        !           160:     if ((hash->_tme_hash_count * 2) > hash->_tme_hash_size) {
        !           161: 
        !           162:       /* make a copy of the top of the hash: */
        !           163:       hash_new = *hash;
        !           164: 
        !           165:       /* set the new size of the hash: */
        !           166:       hash_new._tme_hash_size = hash->_tme_hash_count * 2;
        !           167:       for (size_i = 0;
        !           168:           _tme_hash_sizes[size_i] < hash_new._tme_hash_size;
        !           169:           size_i++) {
        !           170:        if (size_i + 1 == TME_ARRAY_ELS(_tme_hash_sizes)) {
        !           171:          abort();
        !           172:        }
        !           173:       }
        !           174:       hash_new._tme_hash_size = _tme_hash_sizes[size_i];
        !           175: 
        !           176:       /* allocate the new hash table: */
        !           177:       hash_new._tme_hash_table = 
        !           178:        tme_new0(struct _tme_hash_bucket *,
        !           179:                 hash_new._tme_hash_size);
        !           180: 
        !           181:       /* move everything from the old hash table into the new: */
        !           182:       for (bucket_i = 0;
        !           183:           bucket_i < hash->_tme_hash_size;
        !           184:           bucket_i++) {
        !           185:        for (bucket = hash->_tme_hash_table[bucket_i];
        !           186:             bucket != NULL;
        !           187:             bucket = bucket_next) {
        !           188:          bucket_next = bucket->_tme_hash_bucket_next;
        !           189:          _tme_hash_lookup_internal(&hash_new,
        !           190:                                    bucket->_tme_hash_bucket_key,
        !           191:                                    &_bucket);
        !           192:          bucket->_tme_hash_bucket_next = *_bucket;
        !           193:          *_bucket = bucket;
        !           194:        }
        !           195:       }
        !           196: 
        !           197:       /* free the old hash table: */
        !           198:       tme_free(hash->_tme_hash_table);
        !           199: 
        !           200:       /* set the new top of the hash: */
        !           201:       *hash = hash_new;
        !           202:     
        !           203:       /* do the internal lookup again: */
        !           204:       _tme_hash_lookup_internal(hash, key, &_bucket);
        !           205:     }
        !           206: 
        !           207:     /* create the new bucket and link it in: */
        !           208:     bucket = tme_new(struct _tme_hash_bucket, 1);
        !           209:     bucket->_tme_hash_bucket_next = *_bucket;
        !           210:     *_bucket = bucket;
        !           211: 
        !           212:     /* increment the number of keys in the hash: */
        !           213:     hash->_tme_hash_count++;
        !           214:   }
        !           215: 
        !           216:   /* set the key and value in the bucket: */
        !           217:   bucket->_tme_hash_bucket_key = key;
        !           218:   bucket->_tme_hash_bucket_value = value;
        !           219: }
        !           220: 
        !           221: /* this looks up a key in the hash: */
        !           222: tme_hash_data_t
        !           223: tme_hash_lookup(tme_hash_t hash,
        !           224:                tme_hash_data_t key)
        !           225: {
        !           226:   struct _tme_hash_bucket *bucket;
        !           227: 
        !           228:   bucket = _tme_hash_lookup_internal(hash, key, NULL);
        !           229:   return (bucket != NULL
        !           230:          ? bucket->_tme_hash_bucket_value
        !           231:          : hash->_tme_hash_null);
        !           232: }
        !           233: 
        !           234: /* this removes a key in the hash: */
        !           235: void
        !           236: tme_hash_remove(tme_hash_t hash,
        !           237:                tme_hash_data_t key)
        !           238: {
        !           239:   struct _tme_hash_bucket *bucket, **_bucket;
        !           240: 
        !           241:   bucket = _tme_hash_lookup_internal(hash, key, &_bucket);
        !           242:   if (bucket != NULL) {
        !           243:     *_bucket = bucket->_tme_hash_bucket_next;
        !           244:     tme_free(bucket);
        !           245:     hash->_tme_hash_count--;
        !           246:   }
        !           247: }
        !           248: 
        !           249: /* this calls a function for each key and value in the hash: */
        !           250: void
        !           251: tme_hash_foreach(tme_hash_t hash,
        !           252:                 tme_foreach_func_t func,
        !           253:                 void *private)
        !           254: {
        !           255:   struct _tme_hash_bucket *bucket;
        !           256:   unsigned long bucket_i;
        !           257: 
        !           258:   /* walk all of the buckets in the hash table: */
        !           259:   for (bucket_i = 0;
        !           260:        bucket_i < hash->_tme_hash_size;
        !           261:        bucket_i++) {
        !           262:     for (bucket = hash->_tme_hash_table[bucket_i];
        !           263:         bucket != NULL;
        !           264:         bucket = bucket->_tme_hash_bucket_next) {
        !           265:       (*func)(bucket->_tme_hash_bucket_key,
        !           266:              bucket->_tme_hash_bucket_value,
        !           267:              private);
        !           268:     }
        !           269:   }
        !           270: }
        !           271: 
        !           272: /* this calls a function for each key and value in the hash.
        !           273:    if the function returns TRUE the entry is removed: */
        !           274: unsigned long
        !           275: tme_hash_foreach_remove(tme_hash_t hash,
        !           276:                        tme_foreach_remove_func_t func,
        !           277:                        void *private)
        !           278: {
        !           279:   struct _tme_hash_bucket **_bucket, *bucket;
        !           280:   unsigned long bucket_i, count;
        !           281: 
        !           282:   /* walk all of the buckets in the hash table: */
        !           283:   count = 0;
        !           284:   for (bucket_i = 0;
        !           285:        bucket_i < hash->_tme_hash_size;
        !           286:        bucket_i++) {
        !           287:     for (_bucket = &hash->_tme_hash_table[bucket_i];
        !           288:         (bucket = *_bucket) != NULL; ) {
        !           289:       if ((*func)(bucket->_tme_hash_bucket_key,
        !           290:                  bucket->_tme_hash_bucket_value,
        !           291:                  private)) {
        !           292:        *_bucket = bucket->_tme_hash_bucket_next;
        !           293:        tme_free(bucket);
        !           294:        hash->_tme_hash_count--;
        !           295:        count++;
        !           296:       }
        !           297:       else {
        !           298:        _bucket = &bucket->_tme_hash_bucket_next;
        !           299:       }
        !           300:     }
        !           301:   }
        !           302:   return (count);
        !           303: }
        !           304: 
        !           305: /* this hashes a direct value: */
        !           306: unsigned long
        !           307: tme_direct_hash(tme_hash_data_t key)
        !           308: {
        !           309:   return ((unsigned long) key);
        !           310: }
        !           311: 
        !           312: /* this compares two direct values: */
        !           313: int
        !           314: tme_direct_compare(tme_hash_data_t key0,
        !           315:                   tme_hash_data_t key1)
        !           316: {
        !           317:   return (key0 == key1);
        !           318: }
        !           319: 
        !           320: /* this hashes a string value: */
        !           321: unsigned long
        !           322: tme_string_hash(tme_hash_data_t key)
        !           323: {
        !           324:   /* this is cribbed from the Dragon book: */
        !           325:   const char *p;
        !           326:   char c;
        !           327:   unsigned long h, g;
        !           328: 
        !           329:   p = (const char *) key;
        !           330:   h = 0;
        !           331: 
        !           332:   for (; (c = *(p++)) != '\0'; ) {
        !           333:     h = (h << 4) + c;
        !           334:     g = (h & 0xf0000000);
        !           335:     if (g) {
        !           336:       h = h ^ (g >> 24);
        !           337:       h = h ^ g;
        !           338:     }
        !           339:   }
        !           340: 
        !           341:   return (h);
        !           342: }
        !           343: 
        !           344: /* this compares two string values: */
        !           345: int
        !           346: tme_string_compare(tme_hash_data_t key0,
        !           347:                   tme_hash_data_t key1)
        !           348: {
        !           349:   return (!strcmp((const char *) key0, (const char *) key1));
        !           350: }
        !           351: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.