1
0

Map.h 7.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232
  1. /* vim: set expandtab ts=4 sw=4: */
  2. /*
  3. * You may redistribute this program and/or modify it under the terms of
  4. * the GNU General Public License as published by the Free Software Foundation,
  5. * either version 3 of the License, or (at your option) any later version.
  6. *
  7. * This program is distributed in the hope that it will be useful,
  8. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  10. * GNU General Public License for more details.
  11. *
  12. * You should have received a copy of the GNU General Public License
  13. * along with this program. If not, see <https://www.gnu.org/licenses/>.
  14. */
  15. #ifndef Map_H
  16. #define Map_H
  17. #endif // This header can be used multiple times as long as the name is different.
  18. #include "util/Bits.h"
  19. #if defined(Map_KEY_TYPE)
  20. Assert_compileTime(!(sizeof(Map_KEY_TYPE) % 4));
  21. #define Map_ENABLE_KEYS
  22. #elif !defined(Map_ENABLE_HANDLES)
  23. #error must define Map_KEY_TYPE or Map_ENABLE_HANDLES or both
  24. #endif
  25. #ifndef Map_VALUE_TYPE
  26. #error must define Map_VALUE_TYPE
  27. #endif
  28. #ifndef Map_NAME
  29. #error must give this map type a name by defining Map_NAME
  30. #endif
  31. #define Map_CONTEXT Map_GLUE(Map_, Map_NAME)
  32. #define Map_FUNCTION(name) Map_GLUE(Map_GLUE(Map_GLUE(Map_, Map_NAME),_), name)
  33. #define Map_GLUE(x, y) Map_GLUE2(x, y)
  34. #define Map_GLUE2(x, y) x ## y
  35. #ifdef Map_ENABLE_KEYS
  36. // Hashcode calculator.
  37. static inline uint32_t Map_FUNCTION(hash)(Map_KEY_TYPE* key);
  38. #ifndef Map_USE_HASH
  39. #include "util/Hash.h"
  40. static inline uint32_t Map_FUNCTION(hash)(Map_KEY_TYPE* key)
  41. {
  42. return Hash_compute((uint8_t*)key, sizeof(Map_KEY_TYPE));
  43. }
  44. #endif
  45. static inline int Map_FUNCTION(compare)(Map_KEY_TYPE* keyA, Map_KEY_TYPE* keyB);
  46. #ifndef Map_USE_COMPARATOR
  47. static inline int Map_FUNCTION(compare)(Map_KEY_TYPE* keyA, Map_KEY_TYPE* keyB)
  48. {
  49. return Bits_memcmp(keyA, keyB, sizeof(Map_KEY_TYPE));
  50. }
  51. #endif
  52. #endif
  53. struct Map_CONTEXT
  54. {
  55. #ifdef Map_ENABLE_KEYS
  56. uint32_t* hashCodes;
  57. Map_KEY_TYPE* keys;
  58. #endif
  59. #ifdef Map_ENABLE_HANDLES
  60. uint32_t* handles;
  61. uint32_t nextHandle;
  62. #endif
  63. Map_VALUE_TYPE* values;
  64. uint32_t count;
  65. uint32_t capacity;
  66. struct Allocator* allocator;
  67. };
  68. static inline struct Map_CONTEXT* Map_FUNCTION(new)(struct Allocator* allocator)
  69. {
  70. return Allocator_clone(allocator, (&(struct Map_CONTEXT) {
  71. .allocator = allocator
  72. }));
  73. }
  74. /**
  75. * This is a very hot loop,
  76. * a large amount of code relies on this being fast so it is a good target for optimization.
  77. */
  78. #ifdef Map_ENABLE_KEYS
  79. static inline int Map_FUNCTION(indexForKey)(Map_KEY_TYPE* key, struct Map_CONTEXT* map)
  80. {
  81. uint32_t hashCode = (Map_FUNCTION(hash)(key));
  82. for (uint32_t i = 0; i < map->count; i++) {
  83. if (map->hashCodes[i] == hashCode
  84. && Map_FUNCTION(compare)(key, &map->keys[i]) == 0)
  85. {
  86. return i;
  87. }
  88. }
  89. return -1;
  90. }
  91. #endif
  92. #ifdef Map_ENABLE_HANDLES
  93. static inline int Map_FUNCTION(indexForHandle)(uint32_t handle, struct Map_CONTEXT* map)
  94. {
  95. uint32_t base = 0;
  96. for (uint32_t bufferLen = map->count; bufferLen != 0; bufferLen /= 2) {
  97. uint32_t currentHandle = map->handles[base + (bufferLen / 2)];
  98. if (handle >= currentHandle) {
  99. if (currentHandle == handle) {
  100. return base + (bufferLen / 2);
  101. }
  102. base += (bufferLen / 2) + 1;
  103. bufferLen--;
  104. }
  105. }
  106. return -1;
  107. }
  108. #endif
  109. /**
  110. * @param key the key of the entry to remove.
  111. * @param map the map to remove from.
  112. * @return 0 if the entry is removed, -1 if it could not be found.
  113. */
  114. static inline int Map_FUNCTION(remove)(int index, struct Map_CONTEXT* map)
  115. {
  116. if (index >= 0 && index < (int) map->count - 1) {
  117. #ifdef Map_ENABLE_HANDLES
  118. // If we use handels then we need to keep the map sorted.
  119. #ifdef Map_ENABLE_KEYS
  120. Bits_memmove(&map->hashCodes[index],
  121. &map->hashCodes[index + 1],
  122. (map->count - index - 1) * sizeof(uint32_t));
  123. Bits_memmove(&map->keys[index],
  124. &map->keys[index + 1],
  125. (map->count - index - 1) * sizeof(Map_KEY_TYPE));
  126. #endif
  127. Bits_memmove(&map->handles[index],
  128. &map->handles[index + 1],
  129. (map->count - index - 1) * sizeof(uint32_t));
  130. Bits_memmove(&map->values[index],
  131. &map->values[index + 1],
  132. (map->count - index - 1) * sizeof(Map_VALUE_TYPE));
  133. map->count--;
  134. #else
  135. // No handles, we can just fold the top entry down on one to remove.
  136. map->count--;
  137. map->hashCodes[index] = map->hashCodes[map->count];
  138. Bits_memcpy(&map->keys[index], &map->keys[map->count], sizeof(Map_KEY_TYPE));
  139. Bits_memcpy(&map->values[index], &map->values[map->count], sizeof(Map_VALUE_TYPE));
  140. #endif
  141. return 0;
  142. } else if (index == (int) map->count - 1) {
  143. map->count--;
  144. return 0;
  145. }
  146. return -1;
  147. }
  148. #ifdef Map_ENABLE_KEYS
  149. static inline int Map_FUNCTION(put)(Map_KEY_TYPE* key,
  150. Map_VALUE_TYPE* value,
  151. struct Map_CONTEXT* map)
  152. #else
  153. static inline int Map_FUNCTION(put)(Map_VALUE_TYPE* value,
  154. struct Map_CONTEXT* map)
  155. #endif
  156. {
  157. if (map->count == map->capacity) {
  158. #ifdef Map_ENABLE_KEYS
  159. map->hashCodes = Allocator_realloc(map->allocator,
  160. map->hashCodes,
  161. sizeof(uint32_t) * (map->count + 10));
  162. map->keys = Allocator_realloc(map->allocator,
  163. map->keys,
  164. sizeof(Map_KEY_TYPE) * (map->count + 10));
  165. #endif
  166. #ifdef Map_ENABLE_HANDLES
  167. map->handles = Allocator_realloc(map->allocator,
  168. map->handles,
  169. sizeof(uint32_t) * (map->count + 10));
  170. #endif
  171. map->values = Allocator_realloc(map->allocator,
  172. map->values,
  173. sizeof(Map_VALUE_TYPE) * (map->count + 10));
  174. map->capacity += 10;
  175. }
  176. int i = -1;
  177. #ifdef Map_ENABLE_KEYS
  178. i = Map_FUNCTION(indexForKey)(key, map);
  179. #endif
  180. if (i < 0) {
  181. i = map->count;
  182. map->count++;
  183. #ifdef Map_ENABLE_HANDLES
  184. map->handles[i] = map->nextHandle++;
  185. #endif
  186. #ifdef Map_ENABLE_KEYS
  187. map->hashCodes[i] = (Map_FUNCTION(hash)(key));
  188. Bits_memcpy(&map->keys[i], key, sizeof(Map_KEY_TYPE));
  189. #endif
  190. }
  191. Bits_memcpy(&map->values[i], value, sizeof(Map_VALUE_TYPE));
  192. return i;
  193. }
  194. #undef Map
  195. #undef Map_Entry
  196. #undef Map_FUNCTION
  197. #undef Map_USE_HASH
  198. #undef Map_NAME
  199. #undef Map_VALUE_TYPE
  200. #undef Map_ENABLE_HANDLES
  201. #undef Map_KEY_TYPE
  202. #undef Map_ENABLE_KEYS
  203. #undef Map_USE_COMPARATOR