hash.c 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200
  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. #include <zebra.h>
  22. #include "hash.h"
  23. #include "memory.h"
  24. /* Allocate a new hash. */
  25. struct hash *
  26. hash_create_size (unsigned int size, unsigned int (*hash_key) (void *),
  27. int (*hash_cmp) (const void *, const void *))
  28. {
  29. struct hash *hash;
  30. hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
  31. hash->index = XCALLOC (MTYPE_HASH_INDEX,
  32. sizeof (struct hash_backet *) * size);
  33. hash->size = size;
  34. hash->hash_key = hash_key;
  35. hash->hash_cmp = hash_cmp;
  36. hash->count = 0;
  37. return hash;
  38. }
  39. /* Allocate a new hash with default hash size. */
  40. struct hash *
  41. hash_create (unsigned int (*hash_key) (void *),
  42. int (*hash_cmp) (const void *, const void *))
  43. {
  44. return hash_create_size (HASHTABSIZE, hash_key, hash_cmp);
  45. }
  46. /* Utility function for hash_get(). When this function is specified
  47. as alloc_func, return arugment as it is. This function is used for
  48. intern already allocated value. */
  49. void *
  50. hash_alloc_intern (void *arg)
  51. {
  52. return arg;
  53. }
  54. /* Lookup and return hash backet in hash. If there is no
  55. corresponding hash backet and alloc_func is specified, create new
  56. hash backet. */
  57. void *
  58. hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *))
  59. {
  60. unsigned int key;
  61. unsigned int index;
  62. void *newdata;
  63. struct hash_backet *backet;
  64. key = (*hash->hash_key) (data);
  65. index = key % hash->size;
  66. for (backet = hash->index[index]; backet != NULL; backet = backet->next)
  67. if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
  68. return backet->data;
  69. if (alloc_func)
  70. {
  71. newdata = (*alloc_func) (data);
  72. if (newdata == NULL)
  73. return NULL;
  74. backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
  75. backet->data = newdata;
  76. backet->key = key;
  77. backet->next = hash->index[index];
  78. hash->index[index] = backet;
  79. hash->count++;
  80. return backet->data;
  81. }
  82. return NULL;
  83. }
  84. /* Hash lookup. */
  85. void *
  86. hash_lookup (struct hash *hash, void *data)
  87. {
  88. return hash_get (hash, data, NULL);
  89. }
  90. /* Simple Bernstein hash which is simple and fast for common case */
  91. unsigned int string_hash_make (const char *str)
  92. {
  93. unsigned int hash = 0;
  94. while (*str)
  95. hash = (hash * 33) ^ (unsigned int) *str++;
  96. return hash;
  97. }
  98. /* This function release registered value from specified hash. When
  99. release is successfully finished, return the data pointer in the
  100. hash backet. */
  101. void *
  102. hash_release (struct hash *hash, void *data)
  103. {
  104. void *ret;
  105. unsigned int key;
  106. unsigned int index;
  107. struct hash_backet *backet;
  108. struct hash_backet *pp;
  109. key = (*hash->hash_key) (data);
  110. index = key % hash->size;
  111. for (backet = pp = hash->index[index]; backet; backet = backet->next)
  112. {
  113. if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
  114. {
  115. if (backet == pp)
  116. hash->index[index] = backet->next;
  117. else
  118. pp->next = backet->next;
  119. ret = backet->data;
  120. XFREE (MTYPE_HASH_BACKET, backet);
  121. hash->count--;
  122. return ret;
  123. }
  124. pp = backet;
  125. }
  126. return NULL;
  127. }
  128. /* Iterator function for hash. */
  129. void
  130. hash_iterate (struct hash *hash,
  131. void (*func) (struct hash_backet *, void *), void *arg)
  132. {
  133. unsigned int i;
  134. struct hash_backet *hb;
  135. struct hash_backet *hbnext;
  136. for (i = 0; i < hash->size; i++)
  137. for (hb = hash->index[i]; hb; hb = hbnext)
  138. {
  139. /* get pointer to next hash backet here, in case (*func)
  140. * decides to delete hb by calling hash_release
  141. */
  142. hbnext = hb->next;
  143. (*func) (hb, arg);
  144. }
  145. }
  146. /* Clean up hash. */
  147. void
  148. hash_clean (struct hash *hash, void (*free_func) (void *))
  149. {
  150. unsigned int i;
  151. struct hash_backet *hb;
  152. struct hash_backet *next;
  153. for (i = 0; i < hash->size; i++)
  154. {
  155. for (hb = hash->index[i]; hb; hb = next)
  156. {
  157. next = hb->next;
  158. if (free_func)
  159. (*free_func) (hb->data);
  160. XFREE (MTYPE_HASH_BACKET, hb);
  161. hash->count--;
  162. }
  163. hash->index[i] = NULL;
  164. }
  165. }
  166. /* Free hash memory. You may call hash_clean before call this
  167. function. */
  168. void
  169. hash_free (struct hash *hash)
  170. {
  171. XFREE (MTYPE_HASH_INDEX, hash->index);
  172. XFREE (MTYPE_HASH, hash);
  173. }