Annotation of embedaddon/quagga/lib/hash.c, revision 1.1
1.1 ! misho 1: /* Hash routine.
! 2: * Copyright (C) 1998 Kunihiro Ishiguro
! 3: *
! 4: * This file is part of GNU Zebra.
! 5: *
! 6: * GNU Zebra is free software; you can redistribute it and/or modify
! 7: * it under the terms of the GNU General Public License as published
! 8: * by the Free Software Foundation; either version 2, or (at your
! 9: * option) any later version.
! 10: *
! 11: * GNU Zebra is distributed in the hope that it will be useful, but
! 12: * WITHOUT ANY WARRANTY; without even the implied warranty of
! 13: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
! 14: * General Public License for more details.
! 15: *
! 16: * You should have received a copy of the GNU General Public License
! 17: * along with GNU Zebra; see the file COPYING. If not, write to the
! 18: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
! 19: * Boston, MA 02111-1307, USA.
! 20: */
! 21:
! 22: #include <zebra.h>
! 23:
! 24: #include "hash.h"
! 25: #include "memory.h"
! 26:
! 27: /* Allocate a new hash. */
! 28: struct hash *
! 29: hash_create_size (unsigned int size, unsigned int (*hash_key) (void *),
! 30: int (*hash_cmp) (const void *, const void *))
! 31: {
! 32: struct hash *hash;
! 33:
! 34: hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
! 35: hash->index = XCALLOC (MTYPE_HASH_INDEX,
! 36: sizeof (struct hash_backet *) * size);
! 37: hash->size = size;
! 38: hash->hash_key = hash_key;
! 39: hash->hash_cmp = hash_cmp;
! 40: hash->count = 0;
! 41:
! 42: return hash;
! 43: }
! 44:
! 45: /* Allocate a new hash with default hash size. */
! 46: struct hash *
! 47: hash_create (unsigned int (*hash_key) (void *),
! 48: int (*hash_cmp) (const void *, const void *))
! 49: {
! 50: return hash_create_size (HASHTABSIZE, hash_key, hash_cmp);
! 51: }
! 52:
! 53: /* Utility function for hash_get(). When this function is specified
! 54: as alloc_func, return arugment as it is. This function is used for
! 55: intern already allocated value. */
! 56: void *
! 57: hash_alloc_intern (void *arg)
! 58: {
! 59: return arg;
! 60: }
! 61:
! 62: /* Lookup and return hash backet in hash. If there is no
! 63: corresponding hash backet and alloc_func is specified, create new
! 64: hash backet. */
! 65: void *
! 66: hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *))
! 67: {
! 68: unsigned int key;
! 69: unsigned int index;
! 70: void *newdata;
! 71: struct hash_backet *backet;
! 72:
! 73: key = (*hash->hash_key) (data);
! 74: index = key % hash->size;
! 75:
! 76: for (backet = hash->index[index]; backet != NULL; backet = backet->next)
! 77: if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
! 78: return backet->data;
! 79:
! 80: if (alloc_func)
! 81: {
! 82: newdata = (*alloc_func) (data);
! 83: if (newdata == NULL)
! 84: return NULL;
! 85:
! 86: backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
! 87: backet->data = newdata;
! 88: backet->key = key;
! 89: backet->next = hash->index[index];
! 90: hash->index[index] = backet;
! 91: hash->count++;
! 92: return backet->data;
! 93: }
! 94: return NULL;
! 95: }
! 96:
! 97: /* Hash lookup. */
! 98: void *
! 99: hash_lookup (struct hash *hash, void *data)
! 100: {
! 101: return hash_get (hash, data, NULL);
! 102: }
! 103:
! 104: /* Simple Bernstein hash which is simple and fast for common case */
! 105: unsigned int string_hash_make (const char *str)
! 106: {
! 107: unsigned int hash = 0;
! 108:
! 109: while (*str)
! 110: hash = (hash * 33) ^ (unsigned int) *str++;
! 111:
! 112: return hash;
! 113: }
! 114:
! 115: /* This function release registered value from specified hash. When
! 116: release is successfully finished, return the data pointer in the
! 117: hash backet. */
! 118: void *
! 119: hash_release (struct hash *hash, void *data)
! 120: {
! 121: void *ret;
! 122: unsigned int key;
! 123: unsigned int index;
! 124: struct hash_backet *backet;
! 125: struct hash_backet *pp;
! 126:
! 127: key = (*hash->hash_key) (data);
! 128: index = key % hash->size;
! 129:
! 130: for (backet = pp = hash->index[index]; backet; backet = backet->next)
! 131: {
! 132: if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
! 133: {
! 134: if (backet == pp)
! 135: hash->index[index] = backet->next;
! 136: else
! 137: pp->next = backet->next;
! 138:
! 139: ret = backet->data;
! 140: XFREE (MTYPE_HASH_BACKET, backet);
! 141: hash->count--;
! 142: return ret;
! 143: }
! 144: pp = backet;
! 145: }
! 146: return NULL;
! 147: }
! 148:
! 149: /* Iterator function for hash. */
! 150: void
! 151: hash_iterate (struct hash *hash,
! 152: void (*func) (struct hash_backet *, void *), void *arg)
! 153: {
! 154: unsigned int i;
! 155: struct hash_backet *hb;
! 156: struct hash_backet *hbnext;
! 157:
! 158: for (i = 0; i < hash->size; i++)
! 159: for (hb = hash->index[i]; hb; hb = hbnext)
! 160: {
! 161: /* get pointer to next hash backet here, in case (*func)
! 162: * decides to delete hb by calling hash_release
! 163: */
! 164: hbnext = hb->next;
! 165: (*func) (hb, arg);
! 166: }
! 167: }
! 168:
! 169: /* Clean up hash. */
! 170: void
! 171: hash_clean (struct hash *hash, void (*free_func) (void *))
! 172: {
! 173: unsigned int i;
! 174: struct hash_backet *hb;
! 175: struct hash_backet *next;
! 176:
! 177: for (i = 0; i < hash->size; i++)
! 178: {
! 179: for (hb = hash->index[i]; hb; hb = next)
! 180: {
! 181: next = hb->next;
! 182:
! 183: if (free_func)
! 184: (*free_func) (hb->data);
! 185:
! 186: XFREE (MTYPE_HASH_BACKET, hb);
! 187: hash->count--;
! 188: }
! 189: hash->index[i] = NULL;
! 190: }
! 191: }
! 192:
! 193: /* Free hash memory. You may call hash_clean before call this
! 194: function. */
! 195: void
! 196: hash_free (struct hash *hash)
! 197: {
! 198: XFREE (MTYPE_HASH_INDEX, hash->index);
! 199: XFREE (MTYPE_HASH, hash);
! 200: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / lib