An emulator, assembler, and disassembler for the Sega Game Gear
25개 이상의 토픽을 선택하실 수 없습니다. Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

hash_table.c 4.3 KiB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152
  1. /* Copyright (C) 2014-2015 Ben Kurtovic <ben.kurtovic@gmail.com>
  2. Released under the terms of the MIT License. See LICENSE for details. */
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include "hash_table.h"
  6. #include "../util.h"
  7. #define INITIAL_BUCKETS 127
  8. #define GET_FIELD_(obj, offset, type) (*((type*) (((char*) obj) + offset)))
  9. #define NODE_KEY(tab, node) GET_FIELD_(node, tab->key_offset, char*)
  10. #define NEXT_NODE(tab, node) GET_FIELD_(node, tab->next_offset, HashNode*)
  11. /* Internal structs */
  12. struct HashNode {
  13. char *key;
  14. HashNode *next;
  15. };
  16. /*
  17. Hash a string key into a hash table bucket index.
  18. This uses the djb2 algorithm: http://www.cse.yorku.ca/~oz/hash.html
  19. */
  20. static inline size_t hash_key(
  21. const HashTable *table, const char *key, ssize_t size)
  22. {
  23. size_t hash = 5381;
  24. while ((size < 0 || size-- > 0) && *key)
  25. hash = ((hash << 5) + hash) + *(key++);
  26. return hash % table->buckets;
  27. }
  28. /*
  29. Return true if the two key strings are equal, or false if they aren't.
  30. */
  31. static inline bool keyeq(const char *s1, const char *s2, ssize_t size)
  32. {
  33. return !(size >= 0 ? strncmp(s1, s2, size) : strcmp(s1, s2));
  34. }
  35. /*
  36. Create and return a new HashTable.
  37. These HashTables are designed to be generic, a sort of poor-man's C++
  38. template. They can store any kind of node data as long as they are structs
  39. with a char* field (for the node key), and a pointer to its own type (to
  40. implement separate chaining).
  41. key_offset is the (byte) offset of the key field, and next_offset is the
  42. offset of the self-pointer. The callback function is called on a node when
  43. it is removed from the table. Typically, it should free() the node's
  44. members and then free() the node itself.
  45. The hash_table_NEW macro can be used to call this function more easily.
  46. */
  47. HashTable* hash_table_new(
  48. size_t key_offset, size_t next_offset, HashFreeCallback callback)
  49. {
  50. HashTable *table = cr_malloc(sizeof(HashTable));
  51. table->nodes = cr_calloc(INITIAL_BUCKETS, sizeof(HashNode*));
  52. table->buckets = INITIAL_BUCKETS;
  53. table->key_offset = key_offset;
  54. table->next_offset = next_offset;
  55. table->free = callback;
  56. return table;
  57. }
  58. /*
  59. Deallocate a HashTable. This function does nothing if the table is NULL.
  60. */
  61. void hash_table_free(HashTable *table)
  62. {
  63. if (!table)
  64. return;
  65. for (size_t bucket = 0; bucket < table->buckets; bucket++) {
  66. HashNode *node = table->nodes[bucket];
  67. while (node) {
  68. HashNode *temp = NEXT_NODE(table, node);
  69. table->free(node);
  70. node = temp;
  71. }
  72. }
  73. free(table);
  74. }
  75. /*
  76. Search for a key in the hash table.
  77. Return the corresponding node on success and NULL on failure.
  78. If the key is null-terminated, pass size as -1.
  79. */
  80. const HashNode* hash_table_find(
  81. const HashTable *table, const char *key, ssize_t size)
  82. {
  83. HashNode *node = table->nodes[hash_key(table, key, size)];
  84. while (node) {
  85. if (keyeq(key, NODE_KEY(table, node), size))
  86. return node;
  87. node = NEXT_NODE(table, node);
  88. }
  89. return NULL;
  90. }
  91. /*
  92. Insert a node into the table.
  93. This doesn't prevent inserting duplicate keys. If a duplicate key is
  94. inserted, the table acts like a stack; the new one will shadow the old one,
  95. and hash_table_remove() will remove the most-recently inserted key to
  96. reveal the second-most recent.
  97. */
  98. void hash_table_insert(HashTable *table, HashNode *node)
  99. {
  100. size_t index = hash_key(table, NODE_KEY(table, node), -1);
  101. NEXT_NODE(table, node) = table->nodes[index];
  102. table->nodes[index] = node;
  103. }
  104. /*
  105. (Try to) remove a node with the given key from the table.
  106. Return true if the node was removed, or false if it was not found.
  107. If the key is null-terminated, pass size as -1.
  108. */
  109. bool hash_table_remove(HashTable *table, const char *key, ssize_t size)
  110. {
  111. size_t index = hash_key(table, key, size);
  112. HashNode *node = table->nodes[index], *prev = NULL, *next;
  113. while (node) {
  114. next = NEXT_NODE(table, node);
  115. if (keyeq(key, NODE_KEY(table, node), size)) {
  116. if (prev)
  117. NEXT_NODE(table, prev) = next;
  118. else
  119. table->nodes[index] = next;
  120. table->free(node);
  121. return true;
  122. }
  123. prev = node;
  124. node = next;
  125. }
  126. return false;
  127. }