ziptree.h 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240
  1. /* This Source Code Form is subject to the terms of the Mozilla Public
  2. * License, v. 2.0. If a copy of the MPL was not distributed with this
  3. * file, You can obtain one at http://mozilla.org/MPL/2.0/.
  4. *
  5. * Copyright 2018 (c) Julius Pfrommer
  6. */
  7. #ifndef ZIPTREE_H_
  8. #define ZIPTREE_H_
  9. #ifdef __cplusplus
  10. extern "C" {
  11. #endif
  12. /* Reusable zip tree implementation. The style is inspired by the BSD
  13. * sys/queue.h linked list definition.
  14. *
  15. * Zip trees were developed in: Tarjan, R. E., Levy, C. C., and Timmel, S. "Zip
  16. * Trees." arXiv preprint arXiv:1806.06726 (2018).
  17. *
  18. * The ZIP_ENTRY definitions are to be contained in the tree entries themselves.
  19. * Use ZIP_PROTTYPE to define the signature of the zip tree and ZIP_IMPL (in a
  20. * .c compilation unit) for the method implementations.
  21. *
  22. * Zip trees are a probabilistic data structure. Entries are assigned a
  23. * (nonzero) rank k with probability 1/2^{k+1}. This header file does not assume
  24. * a specific random number generator. So the rank must be given when an entry
  25. * is inserted. A fast way (with a single call to a pseudo random generator) to
  26. * compute the rank is with ZIP_FFS32(random()). The ZIP_FFS32 returns the least
  27. * significant nonzero bit of a 32bit number. */
  28. #define ZIP_HEAD(name, type) \
  29. struct name { \
  30. struct type *zip_root; \
  31. }
  32. #define ZIP_INIT(head) do { (head)->zip_root = NULL; } while (0)
  33. #define ZIP_ROOT(head) (head)->zip_root
  34. #define ZIP_EMPTY(head) (ZIP_ROOT(head) == NULL)
  35. #define ZIP_ENTRY(type) \
  36. struct { \
  37. struct type *zip_left; \
  38. struct type *zip_right; \
  39. unsigned char rank; \
  40. }
  41. #define ZIP_LEFT(elm, field) (elm)->field.zip_left
  42. #define ZIP_RIGHT(elm, field) (elm)->field.zip_right
  43. #define ZIP_RANK(elm, field) (elm)->field.rank
  44. /* Shortcuts */
  45. #define ZIP_INSERT(name, head, elm, rank) name##_ZIP_INSERT(head, elm, rank)
  46. #define ZIP_REMOVE(name, head, elm) name##_ZIP_REMOVE(head, elm)
  47. #define ZIP_FIND(name, head, key) name##_ZIP_FIND(head, key)
  48. #define ZIP_MIN(name, head) name##_ZIP_MIN(head)
  49. #define ZIP_MAX(name, head) name##_ZIP_MAX(head)
  50. #define ZIP_ITER(name, head, cb, d) name##_ZIP_ITER(head, cb, d)
  51. /* Zip tree method prototypes */
  52. #define ZIP_PROTTYPE(name, type, keytype) \
  53. void name##_ZIP_INSERT(struct name *head, struct type *elm, unsigned char rank); \
  54. void name##_ZIP_REMOVE(struct name *head, struct type *elm); \
  55. struct type *name##_ZIP_FIND(struct name *head, const keytype *key); \
  56. struct type *name##_ZIP_MIN(struct name *head); \
  57. struct type *name##_ZIP_MAX(struct name *head); \
  58. typedef void (*name##_cb)(struct type *elm, void *data); \
  59. void name##_ZIP_ITER(struct name *head, name##_cb cb, void *data); \
  60. /* The comparison method "cmp" defined for every zip tree has the signature
  61. *
  62. * enum ZIP_CMP cmpDateTime(const keytype *a, const keytype *b);
  63. *
  64. * The entries need an absolute ordering. So ZIP_CMP_EQ must only be returned if
  65. * a and b point to the same memory. (E.g. assured by unique identifiers.) */
  66. enum ZIP_CMP {
  67. ZIP_CMP_LESS = -1,
  68. ZIP_CMP_EQ = 0,
  69. ZIP_CMP_MORE = 1
  70. };
  71. /* Find the position of the first bit in an unsigned 32bit integer */
  72. #ifdef _MSC_VER
  73. static __inline
  74. #else
  75. static inline
  76. #endif
  77. unsigned char
  78. ZIP_FFS32(unsigned int v) {
  79. unsigned int t = 1;
  80. unsigned char r = 1;
  81. if(v == 0) return 0;
  82. while((v & t) == 0) {
  83. t = t << 1; r++;
  84. }
  85. return r;
  86. }
  87. /* Zip tree method implementations */
  88. #define ZIP_IMPL(name, type, field, keytype, keyfield, cmp) \
  89. static struct type * \
  90. __##name##_ZIP_INSERT(struct type *root, struct type *elm) { \
  91. if(!root) { \
  92. ZIP_LEFT(elm, field) = NULL; \
  93. ZIP_RIGHT(elm, field) = NULL; \
  94. return elm; \
  95. } \
  96. if((cmp)(&(elm)->keyfield, &(root)->keyfield) == ZIP_CMP_LESS) { \
  97. if(__##name##_ZIP_INSERT(ZIP_LEFT(root, field), elm) == elm) { \
  98. if(ZIP_RANK(elm, field) < ZIP_RANK(root, field)) { \
  99. ZIP_LEFT(root, field) = elm; \
  100. } else { \
  101. ZIP_LEFT(root, field) = ZIP_RIGHT(elm, field); \
  102. ZIP_RIGHT(elm, field) = root; \
  103. return elm; \
  104. } \
  105. } \
  106. } else { \
  107. if(__##name##_ZIP_INSERT(ZIP_RIGHT(root, field), elm) == elm) { \
  108. if(ZIP_RANK(elm, field) <= ZIP_RANK(root, field)) { \
  109. ZIP_RIGHT(root, field) = elm; \
  110. } else { \
  111. ZIP_RIGHT(root, field) = ZIP_LEFT(elm, field); \
  112. ZIP_LEFT(elm, field) = root; \
  113. return elm; \
  114. } \
  115. } \
  116. } \
  117. return root; \
  118. } \
  119. \
  120. void \
  121. name##_ZIP_INSERT(struct name *head, struct type *elm, \
  122. unsigned char rank) { \
  123. ZIP_RANK(elm, field) = rank; \
  124. ZIP_ROOT(head) = __##name##_ZIP_INSERT(ZIP_ROOT(head), elm); \
  125. } \
  126. \
  127. static struct type * \
  128. __##name##ZIP(struct type *x, struct type *y) { \
  129. if(!x) return y; \
  130. if(!y) return x; \
  131. if(ZIP_RANK(x, field) < ZIP_RANK(y, field)) { \
  132. ZIP_LEFT(y, field) = __##name##ZIP(x, ZIP_LEFT(y, field)); \
  133. return y; \
  134. } \
  135. ZIP_RIGHT(x, field) = __##name##ZIP(ZIP_RIGHT(x, field), y); \
  136. return x; \
  137. } \
  138. \
  139. static struct type * \
  140. __##name##_ZIP_REMOVE(struct type *root, struct type *elm) { \
  141. if(root == elm) \
  142. return __##name##ZIP(ZIP_LEFT(root, field), \
  143. ZIP_RIGHT(root, field)); \
  144. enum ZIP_CMP eq = (cmp)(&(elm)->keyfield, &(root)->keyfield); \
  145. if(eq == ZIP_CMP_LESS) { \
  146. struct type *left = ZIP_LEFT(root, field); \
  147. if(elm == left) \
  148. ZIP_LEFT(root, field) = \
  149. __##name##ZIP(ZIP_LEFT(left, field), \
  150. ZIP_RIGHT(left, field)); \
  151. else \
  152. __##name##_ZIP_REMOVE(left, elm); \
  153. } else { \
  154. struct type *right = ZIP_RIGHT(root, field); \
  155. if(elm == right) \
  156. ZIP_RIGHT(root, field) = \
  157. __##name##ZIP(ZIP_LEFT(right, field), \
  158. ZIP_RIGHT(right, field)); \
  159. else \
  160. __##name##_ZIP_REMOVE(right, elm); \
  161. } \
  162. return root; \
  163. } \
  164. \
  165. void \
  166. name##_ZIP_REMOVE(struct name *head, struct type *elm) { \
  167. ZIP_ROOT(head) = __##name##_ZIP_REMOVE(ZIP_ROOT(head), elm); \
  168. } \
  169. \
  170. static struct type * \
  171. __##name##_ZIP_FIND(struct type *root, const keytype *key) { \
  172. if(!root) \
  173. return NULL; \
  174. enum ZIP_CMP eq = (cmp)(key, &(root)->keyfield); \
  175. if(eq == ZIP_CMP_EQ) { \
  176. return root; \
  177. } else if(eq == ZIP_CMP_LESS) { \
  178. return __##name##_ZIP_FIND(ZIP_LEFT(root, field), key); \
  179. } else { \
  180. return __##name##_ZIP_FIND(ZIP_RIGHT(root, field), key); \
  181. } \
  182. } \
  183. \
  184. struct type * \
  185. name##_ZIP_FIND(struct name *head, const keytype *key) { \
  186. return __##name##_ZIP_FIND(ZIP_ROOT(head), key); \
  187. } \
  188. \
  189. struct type * \
  190. name##_ZIP_MIN(struct name *head) { \
  191. struct type *cur = ZIP_ROOT(head); \
  192. if(!cur) return NULL; \
  193. while(ZIP_LEFT(cur, field)) { \
  194. cur = ZIP_LEFT(cur, field); \
  195. } \
  196. return cur; \
  197. } \
  198. \
  199. struct type * \
  200. name##_ZIP_MAX(struct name *head) { \
  201. struct type *cur = ZIP_ROOT(head); \
  202. if(!cur) return NULL; \
  203. while(ZIP_RIGHT(cur, field)) { \
  204. cur = ZIP_RIGHT(cur, field); \
  205. } \
  206. return cur; \
  207. } \
  208. \
  209. static void \
  210. __##name##_ZIP_ITER(struct type *elm, name##_cb cb, void *data) { \
  211. if(!elm) \
  212. return; \
  213. __##name##_ZIP_ITER(ZIP_LEFT(elm, field), cb, data); \
  214. __##name##_ZIP_ITER(ZIP_RIGHT(elm, field), cb, data); \
  215. cb(elm, data); \
  216. } \
  217. \
  218. void \
  219. name##_ZIP_ITER(struct name *head, name##_cb cb, void *data) { \
  220. __##name##_ZIP_ITER(ZIP_ROOT(head), cb, data); \
  221. }
  222. #ifdef __cplusplus
  223. } /* extern "C" */
  224. #endif
  225. #endif /* ZIPTREE_H_ */