hash.c 6.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260
  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. assert ((size & (size-1)) == 0);
  31. hash = XMALLOC (MTYPE_HASH, sizeof (struct hash));
  32. hash->index = XCALLOC (MTYPE_HASH_INDEX,
  33. sizeof (struct hash_backet *) * size);
  34. hash->size = size;
  35. hash->no_expand = 0;
  36. hash->hash_key = hash_key;
  37. hash->hash_cmp = hash_cmp;
  38. hash->count = 0;
  39. return hash;
  40. }
  41. /* Allocate a new hash with default hash size. */
  42. struct hash *
  43. hash_create (unsigned int (*hash_key) (void *),
  44. int (*hash_cmp) (const void *, const void *))
  45. {
  46. return hash_create_size (HASH_INITIAL_SIZE, hash_key, hash_cmp);
  47. }
  48. /* Utility function for hash_get(). When this function is specified
  49. as alloc_func, return arugment as it is. This function is used for
  50. intern already allocated value. */
  51. void *
  52. hash_alloc_intern (void *arg)
  53. {
  54. return arg;
  55. }
  56. /* Expand hash if the chain length exceeds the threshold. */
  57. static void hash_expand (struct hash *hash)
  58. {
  59. unsigned int i, new_size, losers;
  60. struct hash_backet *hb, *hbnext, **new_index;
  61. new_size = hash->size * 2;
  62. new_index = XCALLOC(MTYPE_HASH_INDEX, sizeof(struct hash_backet *) * new_size);
  63. if (new_index == NULL)
  64. return;
  65. for (i = 0; i < hash->size; i++)
  66. for (hb = hash->index[i]; hb; hb = hbnext)
  67. {
  68. unsigned int h = hb->key & (new_size - 1);
  69. hbnext = hb->next;
  70. hb->next = new_index[h];
  71. new_index[h] = hb;
  72. }
  73. /* Switch to new table */
  74. XFREE(MTYPE_HASH_INDEX, hash->index);
  75. hash->size = new_size;
  76. hash->index = new_index;
  77. /* Ideally, new index should have chains half as long as the original.
  78. If expansion didn't help, then not worth expanding again,
  79. the problem is the hash function. */
  80. losers = 0;
  81. for (i = 0; i < hash->size; i++)
  82. {
  83. unsigned int len = 0;
  84. for (hb = hash->index[i]; hb; hb = hb->next)
  85. {
  86. if (++len > HASH_THRESHOLD/2)
  87. ++losers;
  88. if (len >= HASH_THRESHOLD)
  89. hash->no_expand = 1;
  90. }
  91. }
  92. if (losers > hash->count / 2)
  93. hash->no_expand = 1;
  94. }
  95. /* Lookup and return hash backet in hash. If there is no
  96. corresponding hash backet and alloc_func is specified, create new
  97. hash backet. */
  98. void *
  99. hash_get (struct hash *hash, void *data, void * (*alloc_func) (void *))
  100. {
  101. unsigned int key;
  102. unsigned int index;
  103. void *newdata;
  104. unsigned int len;
  105. struct hash_backet *backet;
  106. key = (*hash->hash_key) (data);
  107. index = key & (hash->size - 1);
  108. len = 0;
  109. for (backet = hash->index[index]; backet != NULL; backet = backet->next)
  110. {
  111. if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
  112. return backet->data;
  113. ++len;
  114. }
  115. if (alloc_func)
  116. {
  117. newdata = (*alloc_func) (data);
  118. if (newdata == NULL)
  119. return NULL;
  120. if (len > HASH_THRESHOLD && !hash->no_expand)
  121. {
  122. hash_expand (hash);
  123. index = key & (hash->size - 1);
  124. }
  125. backet = XMALLOC (MTYPE_HASH_BACKET, sizeof (struct hash_backet));
  126. backet->data = newdata;
  127. backet->key = key;
  128. backet->next = hash->index[index];
  129. hash->index[index] = backet;
  130. hash->count++;
  131. return backet->data;
  132. }
  133. return NULL;
  134. }
  135. /* Hash lookup. */
  136. void *
  137. hash_lookup (struct hash *hash, void *data)
  138. {
  139. return hash_get (hash, data, NULL);
  140. }
  141. /* Simple Bernstein hash which is simple and fast for common case */
  142. unsigned int string_hash_make (const char *str)
  143. {
  144. unsigned int hash = 0;
  145. while (*str)
  146. hash = (hash * 33) ^ (unsigned int) *str++;
  147. return hash;
  148. }
  149. /* This function release registered value from specified hash. When
  150. release is successfully finished, return the data pointer in the
  151. hash backet. */
  152. void *
  153. hash_release (struct hash *hash, void *data)
  154. {
  155. void *ret;
  156. unsigned int key;
  157. unsigned int index;
  158. struct hash_backet *backet;
  159. struct hash_backet *pp;
  160. key = (*hash->hash_key) (data);
  161. index = key & (hash->size - 1);
  162. for (backet = pp = hash->index[index]; backet; backet = backet->next)
  163. {
  164. if (backet->key == key && (*hash->hash_cmp) (backet->data, data))
  165. {
  166. if (backet == pp)
  167. hash->index[index] = backet->next;
  168. else
  169. pp->next = backet->next;
  170. ret = backet->data;
  171. XFREE (MTYPE_HASH_BACKET, backet);
  172. hash->count--;
  173. return ret;
  174. }
  175. pp = backet;
  176. }
  177. return NULL;
  178. }
  179. /* Iterator function for hash. */
  180. void
  181. hash_iterate (struct hash *hash,
  182. void (*func) (struct hash_backet *, void *), void *arg)
  183. {
  184. unsigned int i;
  185. struct hash_backet *hb;
  186. struct hash_backet *hbnext;
  187. for (i = 0; i < hash->size; i++)
  188. for (hb = hash->index[i]; hb; hb = hbnext)
  189. {
  190. /* get pointer to next hash backet here, in case (*func)
  191. * decides to delete hb by calling hash_release
  192. */
  193. hbnext = hb->next;
  194. (*func) (hb, arg);
  195. }
  196. }
  197. /* Clean up hash. */
  198. void
  199. hash_clean (struct hash *hash, void (*free_func) (void *))
  200. {
  201. unsigned int i;
  202. struct hash_backet *hb;
  203. struct hash_backet *next;
  204. for (i = 0; i < hash->size; i++)
  205. {
  206. for (hb = hash->index[i]; hb; hb = next)
  207. {
  208. next = hb->next;
  209. if (free_func)
  210. (*free_func) (hb->data);
  211. XFREE (MTYPE_HASH_BACKET, hb);
  212. hash->count--;
  213. }
  214. hash->index[i] = NULL;
  215. }
  216. }
  217. /* Free hash memory. You may call hash_clean before call this
  218. function. */
  219. void
  220. hash_free (struct hash *hash)
  221. {
  222. XFREE (MTYPE_HASH_INDEX, hash->index);
  223. XFREE (MTYPE_HASH, hash);
  224. }