hipack-dict.c 6.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266
  1. /*
  2. * hipack-dict.c
  3. * Copyright (C) 2015 Adrian Perez <aperez@igalia.com>
  4. *
  5. * Distributed under terms of the MIT license.
  6. */
  7. #include "hipack.h"
  8. #include <stdlib.h>
  9. #include <string.h>
  10. #ifndef HIPACK_DICT_DEFAULT_SIZE
  11. #define HIPACK_DICT_DEFAULT_SIZE 16
  12. #endif /* !HIPACK_DICT_DEFAULT_SIZE */
  13. #ifndef HIPACK_DICT_RESIZE_FACTOR
  14. #define HIPACK_DICT_RESIZE_FACTOR 3
  15. #endif /* !HIPACK_DICT_RESIZE_FACTOR */
  16. #ifndef HIPACK_DICT_COUNT_TO_SIZE_RATIO
  17. #define HIPACK_DICT_COUNT_TO_SIZE_RATIO 1.2
  18. #endif /* !HIPACK_DICT_COUNT_TO_SIZE_RATIO */
  19. struct hipack_dict_node {
  20. hipack_value_t value;
  21. hipack_string_t *key;
  22. hipack_dict_node_t *next;
  23. hipack_dict_node_t *next_node;
  24. hipack_dict_node_t *prev_node;
  25. };
  26. static inline hipack_dict_node_t*
  27. make_node (hipack_string_t *key,
  28. const hipack_value_t *value)
  29. {
  30. assert (key->size);
  31. hipack_dict_node_t *node =
  32. hipack_alloc_bzero (sizeof (hipack_dict_node_t));
  33. memcpy (&node->value, value, sizeof (hipack_value_t));
  34. node->key = key;
  35. return node;
  36. }
  37. static inline void
  38. free_node (hipack_dict_node_t *node)
  39. {
  40. hipack_string_free (node->key);
  41. hipack_value_free (&node->value);
  42. hipack_alloc_free (node);
  43. }
  44. static void
  45. free_all_nodes (hipack_dict_t *dict)
  46. {
  47. hipack_dict_node_t *next;
  48. for (hipack_dict_node_t *node = dict->first; node; node = next) {
  49. next = node->next_node;
  50. free_node (node);
  51. }
  52. }
  53. static inline void
  54. rehash (hipack_dict_t *dict)
  55. {
  56. for (hipack_dict_node_t *node = dict->first; node; node = node->next_node)
  57. node->next = NULL;
  58. dict->size *= HIPACK_DICT_RESIZE_FACTOR;
  59. dict->nodes = hipack_alloc_array (dict->nodes,
  60. sizeof (hipack_dict_node_t*),
  61. dict->size);
  62. memset (dict->nodes, 0, sizeof (hipack_dict_node_t*) * dict->size);
  63. for (hipack_dict_node_t *node = dict->first; node; node = node->next_node) {
  64. uint32_t hash_val = hipack_string_hash (node->key) % dict->size;
  65. hipack_dict_node_t *n = dict->nodes[hash_val];
  66. if (!n) {
  67. dict->nodes[hash_val] = node;
  68. } else {
  69. for (;; n = n->next) {
  70. if (!n->next) {
  71. n->next = node;
  72. break;
  73. }
  74. }
  75. }
  76. }
  77. }
  78. hipack_dict_t*
  79. hipack_dict_new (void)
  80. {
  81. hipack_dict_t *dict = hipack_alloc_bzero (sizeof (hipack_dict_t));
  82. dict->size = HIPACK_DICT_DEFAULT_SIZE;
  83. dict->nodes = hipack_alloc_array (NULL,
  84. sizeof (hipack_dict_node_t*),
  85. dict->size);
  86. memset (dict->nodes, 0, sizeof (hipack_dict_node_t*) * dict->size);
  87. return dict;
  88. }
  89. void
  90. hipack_dict_free (hipack_dict_t *dict)
  91. {
  92. if (dict) {
  93. free_all_nodes (dict);
  94. hipack_alloc_free (dict->nodes);
  95. hipack_alloc_free (dict);
  96. }
  97. }
  98. void
  99. hipack_dict_set (hipack_dict_t *dict,
  100. const hipack_string_t *key,
  101. const hipack_value_t *value)
  102. {
  103. hipack_string_t *key_copy = hipack_string_copy (key);
  104. hipack_dict_set_adopt_key (dict, &key_copy, value);
  105. }
  106. void hipack_dict_set_adopt_key (hipack_dict_t *dict,
  107. hipack_string_t **key,
  108. const hipack_value_t *value)
  109. {
  110. assert (dict);
  111. assert (key);
  112. assert (*key);
  113. assert (value);
  114. uint32_t hash_val = hipack_string_hash (*key) % dict->size;
  115. hipack_dict_node_t *node = dict->nodes[hash_val];
  116. for (; node; node = node->next) {
  117. if (hipack_string_equal (node->key, *key)) {
  118. hipack_value_free (&node->value);
  119. memcpy (&node->value, value, sizeof (hipack_value_t));
  120. hipack_string_free (*key);
  121. *key = NULL;
  122. return;
  123. }
  124. }
  125. node = make_node (*key, value);
  126. *key = NULL;
  127. if (dict->nodes[hash_val]) {
  128. node->next = dict->nodes[hash_val];
  129. }
  130. dict->nodes[hash_val] = node;
  131. node->next_node = dict->first;
  132. if (dict->first) {
  133. dict->first->prev_node = node;
  134. }
  135. dict->first = node;
  136. dict->count++;
  137. if (dict->count > (dict->size * HIPACK_DICT_COUNT_TO_SIZE_RATIO)) {
  138. rehash (dict);
  139. }
  140. }
  141. hipack_value_t*
  142. hipack_dict_get (const hipack_dict_t *dict,
  143. const hipack_string_t *key)
  144. {
  145. assert (dict);
  146. assert (key);
  147. uint32_t hash_val = hipack_string_hash (key) % dict->size;
  148. hipack_dict_node_t *node = dict->nodes[hash_val];
  149. if (node) {
  150. if (hipack_string_equal (key, node->key)) {
  151. return &node->value;
  152. }
  153. hipack_dict_node_t *last_node = node;
  154. node = node->next;
  155. while (node) {
  156. if (hipack_string_equal (key, node->key)) {
  157. last_node->next = node->next;
  158. node->next = dict->nodes[hash_val];
  159. dict->nodes[hash_val] = node;
  160. return &node->value;
  161. }
  162. last_node = node;
  163. node = node->next;
  164. }
  165. }
  166. return NULL;
  167. }
  168. void
  169. hipack_dict_del (hipack_dict_t *dict,
  170. const hipack_string_t *key)
  171. {
  172. assert (dict);
  173. assert (key);
  174. uint32_t hash_val = hipack_string_hash (key) % dict->size;
  175. for (hipack_dict_node_t *node = dict->nodes[hash_val]; node; node = node->next) {
  176. if (hipack_string_equal (node->key, key)) {
  177. hipack_dict_node_t *prev_node = node->prev_node;
  178. hipack_dict_node_t *next_node = node->next_node;
  179. if (prev_node) prev_node->next_node = next_node;
  180. else dict->first = next_node;
  181. if (next_node) next_node->prev_node = prev_node;
  182. dict->nodes[hash_val] = node->next;
  183. dict->count--;
  184. free_node (node);
  185. return;
  186. }
  187. }
  188. }
  189. hipack_value_t*
  190. hipack_dict_first (const hipack_dict_t *dict,
  191. const hipack_string_t **key)
  192. {
  193. assert (dict);
  194. assert (key);
  195. if (dict->first) {
  196. *key = dict->first->key;
  197. return (hipack_value_t*) dict->first;
  198. } else {
  199. *key = NULL;
  200. return NULL;
  201. }
  202. }
  203. hipack_value_t*
  204. hipack_dict_next (hipack_value_t *value,
  205. const hipack_string_t **key)
  206. {
  207. assert (value);
  208. assert (key);
  209. hipack_dict_node_t *node = (hipack_dict_node_t*) value;
  210. if (node->next_node) {
  211. *key = node->next_node->key;
  212. return (hipack_value_t*) node->next_node;
  213. } else {
  214. *key = NULL;
  215. return NULL;
  216. }
  217. }