14# define ZIP_INLINE __inline
16# define ZIP_INLINE inline
20#if defined(__GNUC__) || defined(__clang__)
21# define ZIP_UNUSED __attribute__((unused))
41#define ZIP_HEAD(name, type) \
46#define ZIP_ENTRY(type) \
61#define ZIP_INIT(head) do { (head)->root = NULL; } while (0)
62#define ZIP_ROOT(head) (head)->root
63#define ZIP_LEFT(elm, field) (elm)->field.left
64#define ZIP_RIGHT(elm, field) (elm)->field.right
65#define ZIP_RANK(elm, field) (elm)->field.rank
73 unsigned short keyoffset,
void *root,
void *elm);
77 unsigned short keyoffset,
void *root,
void *elm);
81 unsigned short keyoffset,
void *root,
86 void *context,
void *elm);
88void *
__ZIP_MIN(
unsigned short fieldoffset,
void *elm);
89void *
__ZIP_MAX(
unsigned short fieldoffset,
void *elm);
103#define ZIP_INSERT(name, head, elm, rank) name##_ZIP_INSERT(head, elm, rank)
104#define ZIP_REMOVE(name, head, elm) name##_ZIP_REMOVE(head, elm)
105#define ZIP_FIND(name, head, key) name##_ZIP_FIND(head, key)
106#define ZIP_MIN(name, head) name##_ZIP_MIN(head)
107#define ZIP_MAX(name, head) name##_ZIP_MAX(head)
108#define ZIP_ITER(name, head, cb, d) name##_ZIP_ITER(head, cb, d)
110#define ZIP_FUNCTIONS(name, type, field, keytype, keyfield, cmp) \
111ZIP_UNUSED static ZIP_INLINE void \
112name##_ZIP_INSERT(struct name *head, struct type *elm, \
114 ZIP_RANK(elm, field) = __ZIP_FFS32(r); \
115 ZIP_ROOT(head) = (struct type*) \
116 __ZIP_INSERT(cmp, offsetof(struct type, field), \
117 offsetof(struct type, keyfield), \
118 ZIP_ROOT(head), elm); \
121ZIP_UNUSED static ZIP_INLINE void \
122name##_ZIP_REMOVE(struct name *head, struct type *elm) { \
123 ZIP_ROOT(head) = (struct type*) \
124 __ZIP_REMOVE(cmp, offsetof(struct type, field), \
125 offsetof(struct type, keyfield), \
126 ZIP_ROOT(head), elm); \
129ZIP_UNUSED static ZIP_INLINE struct type * \
130name##_ZIP_FIND(struct name *head, const keytype *key) { \
131 return (struct type*)__ZIP_FIND(cmp, offsetof(struct type, field), \
132 offsetof(struct type, keyfield), \
133 ZIP_ROOT(head), key); \
136ZIP_UNUSED static ZIP_INLINE struct type * \
137name##_ZIP_MIN(struct name *head) { \
138 return (struct type *)__ZIP_MIN(offsetof(struct type, field), \
142ZIP_UNUSED static ZIP_INLINE struct type * \
143name##_ZIP_MAX(struct name *head) { \
144 return (struct type *)__ZIP_MAX(offsetof(struct type, field), \
148typedef void (*name##_cb)(struct type *elm, void *context); \
150ZIP_UNUSED static ZIP_INLINE void \
151name##_ZIP_ITER(struct name *head, name##_cb cb, void *context) { \
152 __ZIP_ITER(offsetof(struct type, field), (__zip_iter_cb)cb, \
153 context, ZIP_ROOT(head)); \
unsigned char __ZIP_FFS32(unsigned int v)
Zip trees are a probabilistic data structure.
void(* __zip_iter_cb)(void *elm, void *context)
Internal definitions.
void * __ZIP_MAX(unsigned short fieldoffset, void *elm)
void * __ZIP_FIND(zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *root, const void *key)
void * __ZIP_INSERT(zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *root, void *elm)
enum ZIP_CMP(* zip_cmp_cb)(const void *key1, const void *key2)
void * __ZIP_REMOVE(zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *root, void *elm)
void * __ZIP_MIN(unsigned short fieldoffset, void *elm)
void __ZIP_ITER(unsigned short fieldoffset, __zip_iter_cb cb, void *context, void *elm)