hash.c 6.2 KB

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