| /* This Source Code Form is subject to the terms of the Mozilla Public |
| * License, v. 2.0. If a copy of the MPL was not distributed with this |
| * file, You can obtain one at http://mozilla.org/MPL/2.0/. |
| * |
| * Copyright 2018 (c) Julius Pfrommer |
| */ |
| |
| #ifndef ZIPTREE_H_ |
| #define ZIPTREE_H_ |
| |
| #ifdef __cplusplus |
| extern "C" { |
| #endif |
| |
| /* Reusable zip tree implementation. The style is inspired by the BSD |
| * sys/queue.h linked list definition. |
| * |
| * Zip trees were developed in: Tarjan, R. E., Levy, C. C., and Timmel, S. "Zip |
| * Trees." arXiv preprint arXiv:1806.06726 (2018). |
| * |
| * The ZIP_ENTRY definitions are to be contained in the tree entries themselves. |
| * Use ZIP_PROTTYPE to define the signature of the zip tree and ZIP_IMPL (in a |
| * .c compilation unit) for the method implementations. |
| * |
| * Zip trees are a probabilistic data structure. Entries are assigned a |
| * (nonzero) rank k with probability 1/2^{k+1}. This header file does not assume |
| * a specific random number generator. So the rank must be given when an entry |
| * is inserted. A fast way (with a single call to a pseudo random generator) to |
| * compute the rank is with ZIP_FFS32(random()). The ZIP_FFS32 returns the least |
| * significant nonzero bit of a 32bit number. */ |
| |
| #define ZIP_HEAD(name, type) \ |
| struct name { \ |
| struct type *zip_root; \ |
| } |
| |
| #define ZIP_INIT(head) do { (head)->zip_root = NULL; } while (0) |
| #define ZIP_ROOT(head) (head)->zip_root |
| #define ZIP_EMPTY(head) (ZIP_ROOT(head) == NULL) |
| |
| #define ZIP_ENTRY(type) \ |
| struct { \ |
| struct type *zip_left; \ |
| struct type *zip_right; \ |
| unsigned char rank; \ |
| } |
| |
| #define ZIP_LEFT(elm, field) (elm)->field.zip_left |
| #define ZIP_RIGHT(elm, field) (elm)->field.zip_right |
| #define ZIP_RANK(elm, field) (elm)->field.rank |
| |
| /* Shortcuts */ |
| #define ZIP_INSERT(name, head, elm, rank) name##_ZIP_INSERT(head, elm, rank) |
| #define ZIP_REMOVE(name, head, elm) name##_ZIP_REMOVE(head, elm) |
| #define ZIP_FIND(name, head, key) name##_ZIP_FIND(head, key) |
| #define ZIP_MIN(name, head) name##_ZIP_MIN(head) |
| #define ZIP_MAX(name, head) name##_ZIP_MAX(head) |
| #define ZIP_ITER(name, head, cb, d) name##_ZIP_ITER(head, cb, d) |
| |
| /* Zip tree method prototypes */ |
| #define ZIP_PROTTYPE(name, type, keytype) \ |
| void name##_ZIP_INSERT(struct name *head, struct type *elm, unsigned char rank); \ |
| void name##_ZIP_REMOVE(struct name *head, struct type *elm); \ |
| struct type *name##_ZIP_FIND(struct name *head, const keytype *key); \ |
| struct type *name##_ZIP_MIN(struct name *head); \ |
| struct type *name##_ZIP_MAX(struct name *head); \ |
| typedef void (*name##_cb)(struct type *elm, void *data); \ |
| void name##_ZIP_ITER(struct name *head, name##_cb cb, void *data); \ |
| |
| /* The comparison method "cmp" defined for every zip tree has the signature |
| * |
| * enum ZIP_CMP cmpDateTime(const keytype *a, const keytype *b); |
| * |
| * The entries need an absolute ordering. So ZIP_CMP_EQ must only be returned if |
| * a and b point to the same memory. (E.g. assured by unique identifiers.) */ |
| enum ZIP_CMP { |
| ZIP_CMP_LESS = -1, |
| ZIP_CMP_EQ = 0, |
| ZIP_CMP_MORE = 1 |
| }; |
| |
| /* Find the position of the first bit in an unsigned 32bit integer */ |
| #ifdef _MSC_VER |
| static __inline |
| #else |
| static inline |
| #endif |
| unsigned char |
| ZIP_FFS32(unsigned int v) { |
| unsigned int t = 1; |
| unsigned char r = 1; |
| if(v == 0) return 0; |
| while((v & t) == 0) { |
| t = t << 1; r++; |
| } |
| return r; |
| } |
| |
| /* Zip tree method implementations */ |
| #define ZIP_IMPL(name, type, field, keytype, keyfield, cmp) \ |
| static struct type * \ |
| __##name##_ZIP_INSERT(struct type *root, struct type *elm) { \ |
| if(!root) { \ |
| ZIP_LEFT(elm, field) = NULL; \ |
| ZIP_RIGHT(elm, field) = NULL; \ |
| return elm; \ |
| } \ |
| if((cmp)(&(elm)->keyfield, &(root)->keyfield) == ZIP_CMP_LESS) { \ |
| if(__##name##_ZIP_INSERT(ZIP_LEFT(root, field), elm) == elm) { \ |
| if(ZIP_RANK(elm, field) < ZIP_RANK(root, field)) { \ |
| ZIP_LEFT(root, field) = elm; \ |
| } else { \ |
| ZIP_LEFT(root, field) = ZIP_RIGHT(elm, field); \ |
| ZIP_RIGHT(elm, field) = root; \ |
| return elm; \ |
| } \ |
| } \ |
| } else { \ |
| if(__##name##_ZIP_INSERT(ZIP_RIGHT(root, field), elm) == elm) { \ |
| if(ZIP_RANK(elm, field) <= ZIP_RANK(root, field)) { \ |
| ZIP_RIGHT(root, field) = elm; \ |
| } else { \ |
| ZIP_RIGHT(root, field) = ZIP_LEFT(elm, field); \ |
| ZIP_LEFT(elm, field) = root; \ |
| return elm; \ |
| } \ |
| } \ |
| } \ |
| return root; \ |
| } \ |
| \ |
| void \ |
| name##_ZIP_INSERT(struct name *head, struct type *elm, \ |
| unsigned char rank) { \ |
| ZIP_RANK(elm, field) = rank; \ |
| ZIP_ROOT(head) = __##name##_ZIP_INSERT(ZIP_ROOT(head), elm); \ |
| } \ |
| \ |
| static struct type * \ |
| __##name##ZIP(struct type *x, struct type *y) { \ |
| if(!x) return y; \ |
| if(!y) return x; \ |
| if(ZIP_RANK(x, field) < ZIP_RANK(y, field)) { \ |
| ZIP_LEFT(y, field) = __##name##ZIP(x, ZIP_LEFT(y, field)); \ |
| return y; \ |
| } \ |
| ZIP_RIGHT(x, field) = __##name##ZIP(ZIP_RIGHT(x, field), y); \ |
| return x; \ |
| } \ |
| \ |
| static struct type * \ |
| __##name##_ZIP_REMOVE(struct type *root, struct type *elm) { \ |
| if(root == elm) \ |
| return __##name##ZIP(ZIP_LEFT(root, field), \ |
| ZIP_RIGHT(root, field)); \ |
| enum ZIP_CMP eq = (cmp)(&(elm)->keyfield, &(root)->keyfield); \ |
| if(eq == ZIP_CMP_LESS) { \ |
| struct type *left = ZIP_LEFT(root, field); \ |
| if(elm == left) \ |
| ZIP_LEFT(root, field) = \ |
| __##name##ZIP(ZIP_LEFT(left, field), \ |
| ZIP_RIGHT(left, field)); \ |
| else \ |
| __##name##_ZIP_REMOVE(left, elm); \ |
| } else { \ |
| struct type *right = ZIP_RIGHT(root, field); \ |
| if(elm == right) \ |
| ZIP_RIGHT(root, field) = \ |
| __##name##ZIP(ZIP_LEFT(right, field), \ |
| ZIP_RIGHT(right, field)); \ |
| else \ |
| __##name##_ZIP_REMOVE(right, elm); \ |
| } \ |
| return root; \ |
| } \ |
| \ |
| void \ |
| name##_ZIP_REMOVE(struct name *head, struct type *elm) { \ |
| ZIP_ROOT(head) = __##name##_ZIP_REMOVE(ZIP_ROOT(head), elm); \ |
| } \ |
| \ |
| static struct type * \ |
| __##name##_ZIP_FIND(struct type *root, const keytype *key) { \ |
| if(!root) \ |
| return NULL; \ |
| enum ZIP_CMP eq = (cmp)(key, &(root)->keyfield); \ |
| if(eq == ZIP_CMP_EQ) { \ |
| return root; \ |
| } \ |
| if(eq == ZIP_CMP_LESS) { \ |
| return __##name##_ZIP_FIND(ZIP_LEFT(root, field), key); \ |
| } \ |
| return __##name##_ZIP_FIND(ZIP_RIGHT(root, field), key); \ |
| } \ |
| \ |
| struct type * \ |
| name##_ZIP_FIND(struct name *head, const keytype *key) { \ |
| return __##name##_ZIP_FIND(ZIP_ROOT(head), key); \ |
| } \ |
| \ |
| struct type * \ |
| name##_ZIP_MIN(struct name *head) { \ |
| struct type *cur = ZIP_ROOT(head); \ |
| if(!cur) return NULL; \ |
| while(ZIP_LEFT(cur, field)) { \ |
| cur = ZIP_LEFT(cur, field); \ |
| } \ |
| return cur; \ |
| } \ |
| \ |
| struct type * \ |
| name##_ZIP_MAX(struct name *head) { \ |
| struct type *cur = ZIP_ROOT(head); \ |
| if(!cur) return NULL; \ |
| while(ZIP_RIGHT(cur, field)) { \ |
| cur = ZIP_RIGHT(cur, field); \ |
| } \ |
| return cur; \ |
| } \ |
| \ |
| static void \ |
| __##name##_ZIP_ITER(struct type *elm, name##_cb cb, void *data) { \ |
| if(!elm) \ |
| return; \ |
| __##name##_ZIP_ITER(ZIP_LEFT(elm, field), cb, data); \ |
| __##name##_ZIP_ITER(ZIP_RIGHT(elm, field), cb, data); \ |
| cb(elm, data); \ |
| } \ |
| \ |
| void \ |
| name##_ZIP_ITER(struct name *head, name##_cb cb, void *data) { \ |
| __##name##_ZIP_ITER(ZIP_ROOT(head), cb, data); \ |
| } |
| |
| #ifdef __cplusplus |
| } /* extern "C" */ |
| #endif |
| |
| #endif /* ZIPTREE_H_ */ |
