hashmap.c 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217
  1. /* vim: tabstop=4 shiftwidth=4 noexpandtab
  2. * This file is part of ToaruOS and is released under the terms
  3. * of the NCSA / University of Illinois License - see LICENSE.md
  4. * Copyright (C) 2013-2014 Kevin Lange
  5. */
  6. #include <kernel/list.h>
  7. #include <kernel/hashmap.h>
  8. unsigned int hashmap_string_hash(void * _key) {
  9. unsigned int hash = 0;
  10. char * key = (char *)_key;
  11. int c;
  12. /* This is the so-called "sdbm" hash. It comes from a piece of
  13. * public domain code from a clone of ndbm. */
  14. while ((c = *key++)) {
  15. hash = c + (hash << 6) + (hash << 16) - hash;
  16. }
  17. return hash;
  18. }
  19. int hashmap_string_comp(void * a, void * b) {
  20. return !strcmp(a,b);
  21. }
  22. void * hashmap_string_dupe(void * key) {
  23. return strdup(key);
  24. }
  25. unsigned int hashmap_int_hash(void * key) {
  26. return (unsigned int)key;
  27. }
  28. int hashmap_int_comp(void * a, void * b) {
  29. return (int)a == (int)b;
  30. }
  31. void * hashmap_int_dupe(void * key) {
  32. return key;
  33. }
  34. static void hashmap_int_free(void * ptr) {
  35. return;
  36. }
  37. hashmap_t * hashmap_create(int size) {
  38. hashmap_t * map = malloc(sizeof(hashmap_t));
  39. map->hash_func = &hashmap_string_hash;
  40. map->hash_comp = &hashmap_string_comp;
  41. map->hash_key_dup = &hashmap_string_dupe;
  42. map->hash_key_free = &free;
  43. map->hash_val_free = &free;
  44. map->size = size;
  45. map->entries = malloc(sizeof(hashmap_entry_t *) * size);
  46. memset(map->entries, 0x00, sizeof(hashmap_entry_t *) * size);
  47. return map;
  48. }
  49. hashmap_t * hashmap_create_int(int size) {
  50. hashmap_t * map = malloc(sizeof(hashmap_t));
  51. map->hash_func = &hashmap_int_hash;
  52. map->hash_comp = &hashmap_int_comp;
  53. map->hash_key_dup = &hashmap_int_dupe;
  54. map->hash_key_free = &hashmap_int_free;
  55. map->hash_val_free = &free;
  56. map->size = size;
  57. map->entries = malloc(sizeof(hashmap_entry_t *) * size);
  58. memset(map->entries, 0x00, sizeof(hashmap_entry_t *) * size);
  59. return map;
  60. }
  61. void * hashmap_set(hashmap_t * map, void * key, void * value) {
  62. unsigned int hash = map->hash_func(key) % map->size;
  63. hashmap_entry_t * x = map->entries[hash];
  64. if (!x) {
  65. hashmap_entry_t * e = malloc(sizeof(hashmap_entry_t));
  66. e->key = map->hash_key_dup(key);
  67. e->value = value;
  68. e->next = NULL;
  69. map->entries[hash] = e;
  70. return NULL;
  71. } else {
  72. hashmap_entry_t * p = NULL;
  73. do {
  74. if (map->hash_comp(x->key, key)) {
  75. void * out = x->value;
  76. x->value = value;
  77. return out;
  78. } else {
  79. p = x;
  80. x = x->next;
  81. }
  82. } while (x);
  83. hashmap_entry_t * e = malloc(sizeof(hashmap_entry_t));
  84. e->key = map->hash_key_dup(key);
  85. e->value = value;
  86. e->next = NULL;
  87. p->next = e;
  88. return NULL;
  89. }
  90. }
  91. void * hashmap_get(hashmap_t * map, void * key) {
  92. unsigned int hash = map->hash_func(key) % map->size;
  93. hashmap_entry_t * x = map->entries[hash];
  94. if (!x) {
  95. return NULL;
  96. } else {
  97. do {
  98. if (map->hash_comp(x->key, key)) {
  99. return x->value;
  100. }
  101. x = x->next;
  102. } while (x);
  103. return NULL;
  104. }
  105. }
  106. void * hashmap_remove(hashmap_t * map, void * key) {
  107. unsigned int hash = map->hash_func(key) % map->size;
  108. hashmap_entry_t * x = map->entries[hash];
  109. if (!x) {
  110. return NULL;
  111. } else {
  112. if (map->hash_comp(x->key, key)) {
  113. void * out = x->value;
  114. map->entries[hash] = x->next;
  115. map->hash_key_free(x->key);
  116. map->hash_val_free(x);
  117. return out;
  118. } else {
  119. hashmap_entry_t * p = x;
  120. x = x->next;
  121. do {
  122. if (map->hash_comp(x->key, key)) {
  123. void * out = x->value;
  124. p->next = x->next;
  125. map->hash_key_free(x->key);
  126. map->hash_val_free(x);
  127. return out;
  128. }
  129. p = x;
  130. x = x->next;
  131. } while (x);
  132. }
  133. return NULL;
  134. }
  135. }
  136. int hashmap_has(hashmap_t * map, void * key) {
  137. unsigned int hash = map->hash_func(key) % map->size;
  138. hashmap_entry_t * x = map->entries[hash];
  139. if (!x) {
  140. return 0;
  141. } else {
  142. do {
  143. if (map->hash_comp(x->key, key)) {
  144. return 1;
  145. }
  146. x = x->next;
  147. } while (x);
  148. return 0;
  149. }
  150. }
  151. list_t * hashmap_keys(hashmap_t * map) {
  152. list_t * l = list_create();
  153. for (unsigned int i = 0; i < map->size; ++i) {
  154. hashmap_entry_t * x = map->entries[i];
  155. while (x) {
  156. list_insert(l, x->key);
  157. x = x->next;
  158. }
  159. }
  160. return l;
  161. }
  162. list_t * hashmap_values(hashmap_t * map) {
  163. list_t * l = list_create();
  164. for (unsigned int i = 0; i < map->size; ++i) {
  165. hashmap_entry_t * x = map->entries[i];
  166. while (x) {
  167. list_insert(l, x->value);
  168. x = x->next;
  169. }
  170. }
  171. return l;
  172. }
  173. void hashmap_free(hashmap_t * map) {
  174. for (unsigned int i = 0; i < map->size; ++i) {
  175. hashmap_entry_t * x = map->entries[i], * p;
  176. while (x) {
  177. p = x;
  178. x = x->next;
  179. map->hash_key_free(p->key);
  180. map->hash_val_free(p);
  181. }
  182. }
  183. free(map->entries);
  184. }