Return to hash.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / lib

quagga

    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: }