1
0

Map.h 7.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231
  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 <http://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. // Get the last 4 bytes of the key by default.
  40. static inline uint32_t Map_FUNCTION(hash)(Map_KEY_TYPE* key)
  41. {
  42. return ((uint32_t*)key)[(sizeof(Map_KEY_TYPE) / 4) - 1];
  43. }
  44. #endif
  45. static inline int Map_FUNCTION(compare)(Map_KEY_TYPE* keyA, Map_KEY_TYPE* keyB);
  46. #ifndef Map_USE_COMPARATOR
  47. // Get the last 4 bytes of the key by default.
  48. static inline int Map_FUNCTION(compare)(Map_KEY_TYPE* keyA, Map_KEY_TYPE* keyB)
  49. {
  50. return Bits_memcmp(keyA, keyB, sizeof(Map_KEY_TYPE));
  51. }
  52. #endif
  53. #endif
  54. struct Map_CONTEXT
  55. {
  56. #ifdef Map_ENABLE_KEYS
  57. uint32_t* hashCodes;
  58. Map_KEY_TYPE* keys;
  59. #endif
  60. #ifdef Map_ENABLE_HANDLES
  61. uint32_t* handles;
  62. uint32_t nextHandle;
  63. #endif
  64. Map_VALUE_TYPE* values;
  65. uint32_t count;
  66. uint32_t capacity;
  67. struct Allocator* allocator;
  68. };
  69. static inline struct Map_CONTEXT* Map_FUNCTION(new)(struct Allocator* allocator)
  70. {
  71. return Allocator_clone(allocator, (&(struct Map_CONTEXT) {
  72. .allocator = allocator
  73. }));
  74. }
  75. /**
  76. * This is a very hot loop,
  77. * a large amount of code relies on this being fast so it is a good target for optimization.
  78. */
  79. #ifdef Map_ENABLE_KEYS
  80. static inline int Map_FUNCTION(indexForKey)(Map_KEY_TYPE* key, struct Map_CONTEXT* map)
  81. {
  82. uint32_t hashCode = (Map_FUNCTION(hash)(key));
  83. for (uint32_t i = 0; i < map->count; i++) {
  84. if (map->hashCodes[i] == hashCode
  85. && Map_FUNCTION(compare)(key, &map->keys[i]) == 0)
  86. {
  87. return i;
  88. }
  89. }
  90. return -1;
  91. }
  92. #endif
  93. #ifdef Map_ENABLE_HANDLES
  94. static inline int Map_FUNCTION(indexForHandle)(uint32_t handle, struct Map_CONTEXT* map)
  95. {
  96. uint32_t base = 0;
  97. for (uint32_t bufferLen = map->count; bufferLen != 0; bufferLen /= 2) {
  98. uint32_t currentHandle = map->handles[base + (bufferLen / 2)];
  99. if (handle >= currentHandle) {
  100. if (currentHandle == handle) {
  101. return base + (bufferLen / 2);
  102. }
  103. base += (bufferLen / 2) + 1;
  104. bufferLen--;
  105. }
  106. }
  107. return -1;
  108. }
  109. #endif
  110. /**
  111. * @param key the key of the entry to remove.
  112. * @param map the map to remove from.
  113. * @return 0 if the entry is removed, -1 if it could not be found.
  114. */
  115. static inline int Map_FUNCTION(remove)(int index, struct Map_CONTEXT* map)
  116. {
  117. if (index >= 0 && index < (int) map->count - 1) {
  118. #ifdef Map_ENABLE_HANDLES
  119. // If we use handels then we need to keep the map sorted.
  120. #ifdef Map_ENABLE_KEYS
  121. Bits_memmove(&map->hashCodes[index],
  122. &map->hashCodes[index + 1],
  123. (map->count - index - 1) * sizeof(uint32_t));
  124. Bits_memmove(&map->keys[index],
  125. &map->keys[index + 1],
  126. (map->count - index - 1) * sizeof(Map_KEY_TYPE));
  127. #endif
  128. Bits_memmove(&map->handles[index],
  129. &map->handles[index + 1],
  130. (map->count - index - 1) * sizeof(uint32_t));
  131. Bits_memmove(&map->values[index],
  132. &map->values[index + 1],
  133. (map->count - index - 1) * sizeof(Map_VALUE_TYPE));
  134. map->count--;
  135. #else
  136. // No handles, we can just fold the top entry down on one to remove.
  137. map->count--;
  138. map->hashCodes[index] = map->hashCodes[map->count];
  139. Bits_memcpyConst(&map->keys[index], &map->keys[map->count], sizeof(Map_KEY_TYPE));
  140. Bits_memcpyConst(&map->values[index], &map->values[map->count], sizeof(Map_VALUE_TYPE));
  141. #endif
  142. return 0;
  143. } else if (index == (int) map->count - 1) {
  144. map->count--;
  145. return 0;
  146. }
  147. return -1;
  148. }
  149. #ifdef Map_ENABLE_KEYS
  150. static inline int Map_FUNCTION(put)(Map_KEY_TYPE* key,
  151. Map_VALUE_TYPE* value,
  152. struct Map_CONTEXT* map)
  153. #else
  154. static inline int Map_FUNCTION(put)(Map_VALUE_TYPE* value,
  155. struct Map_CONTEXT* map)
  156. #endif
  157. {
  158. if (map->count == map->capacity) {
  159. #ifdef Map_ENABLE_KEYS
  160. map->hashCodes = Allocator_realloc(map->allocator,
  161. map->hashCodes,
  162. sizeof(uint32_t) * (map->count + 10));
  163. map->keys = Allocator_realloc(map->allocator,
  164. map->keys,
  165. sizeof(Map_KEY_TYPE) * (map->count + 10));
  166. #endif
  167. #ifdef Map_ENABLE_HANDLES
  168. map->handles = Allocator_realloc(map->allocator,
  169. map->handles,
  170. sizeof(uint32_t) * (map->count + 10));
  171. #endif
  172. map->values = Allocator_realloc(map->allocator,
  173. map->values,
  174. sizeof(Map_VALUE_TYPE) * (map->count + 10));
  175. map->capacity += 10;
  176. }
  177. int i = -1;
  178. #ifdef Map_ENABLE_KEYS
  179. i = Map_FUNCTION(indexForKey)(key, map);
  180. #endif
  181. if (i < 0) {
  182. i = map->count;
  183. map->count++;
  184. #ifdef Map_ENABLE_HANDLES
  185. map->handles[i] = map->nextHandle++;
  186. #endif
  187. #ifdef Map_ENABLE_KEYS
  188. map->hashCodes[i] = (Map_FUNCTION(hash)(key));
  189. Bits_memcpyConst(&map->keys[i], key, sizeof(Map_KEY_TYPE));
  190. #endif
  191. }
  192. Bits_memcpyConst(&map->values[i], value, sizeof(Map_VALUE_TYPE));
  193. return i;
  194. }
  195. #undef Map
  196. #undef Map_Entry
  197. #undef Map_FUNCTION
  198. #undef Map_USE_HASH
  199. #undef Map_NAME
  200. #undef Map_VALUE_TYPE
  201. #undef Map_ENABLE_HANDLES
  202. #undef Map_KEY_TYPE
  203. #undef Map_ENABLE_KEYS