open62541 1.4.15
Open source implementation of OPC UA
Loading...
Searching...
No Matches
ziptree.h
Go to the documentation of this file.
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, 2021-2022 (c) Julius Pfrommer
6 */
7
8#ifndef ZIPTREE_H_
9#define ZIPTREE_H_
10
11#include <stddef.h>
12
13#ifdef _MSC_VER
14# define ZIP_INLINE __inline
15#else
16# define ZIP_INLINE inline
17#endif
18
19#if defined(__GNUC__) || defined(__clang__)
20# define ZIP_UNUSED __attribute__((unused))
21#else
22# define ZIP_UNUSED
23#endif
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29/** Reusable zip tree implementation. The style is inspired by the BSD
30 * sys/queue.h linked list definition.
31 *
32 * Zip trees were developed in: Tarjan, R. E., Levy, C. C., and Timmel, S. "Zip
33 * Trees." arXiv preprint arXiv:1806.06726 (2018). The original definition was
34 * modified in two ways:
35 *
36 * - Multiple elements with the same key can be inserted. These appear adjacent
37 * in the tree. ZIP_FIND will return the topmost of these elements.
38 * - The pointer-value of the elements are used as the rank. This simplifies the
39 * code and is (empirically) faster.
40 *
41 * The ZIP_ENTRY definitions are to be contained in the tree entries themselves.
42 * Use ZIP_FUNCTIONS to define the signature of the zip tree functions. */
43
44#define ZIP_HEAD(name, type) \
45struct name { \
46 struct type *root; \
47}
48
49#define ZIP_ENTRY(type) \
50struct { \
51 struct type *left; \
52 struct type *right; \
53}
54
60
61/** The comparison method "cmp" for a zip tree has the signature.
62 * Provide this to the ZIP_FUNCTIONS macro.
63 *
64 * enum ZIP_CMP cmpMethod(const keytype *a, const keytype *b);
65 */
66typedef enum ZIP_CMP (*zip_cmp_cb)(const void *key1, const void *key2);
67
68#define ZIP_INIT(head) do { (head)->root = NULL; } while (0)
69#define ZIP_ROOT(head) (head)->root
70#define ZIP_LEFT(elm, field) (elm)->field.left
71#define ZIP_RIGHT(elm, field) (elm)->field.right
72#define ZIP_INSERT(name, head, elm) name##_ZIP_INSERT(head, elm)
73#define ZIP_FIND(name, head, key) name##_ZIP_FIND(head, key)
74#define ZIP_MIN(name, head) name##_ZIP_MIN(head)
75#define ZIP_MAX(name, head) name##_ZIP_MAX(head)
76
77/** Returns the element if it was found in the tree. Returns NULL otherwise. */
78#define ZIP_REMOVE(name, head, elm) name##_ZIP_REMOVE(head, elm)
79
80/** Split (_UNZIP) and merge (_ZIP) trees. _UNZIP splits at the key and moves
81 * elements <= into the left output (right otherwise). */
82#define ZIP_ZIP(name, left, right) name##_ZIP_ZIP(left, right)
83#define ZIP_UNZIP(name, head, key, left, right) \
84 name##_ZIP_UNZIP(head, key, left, right)
85
86/** ZIP_ITER uses in-order traversal of the tree (in the order of the keys). The
87 * memory if a node is not accessed by ZIP_ITER after the callback has been
88 * executed for it. So a tree can be cleaned by calling free on each node from
89 * within the iteration callback.
90 *
91 * ZIP_ITER returns a void pointer. The first callback to return non-NULL aborts
92 * the iteration. This pointer is then returned. */
93typedef void * (*zip_iter_cb)(void *context, void *elm);
94#define ZIP_ITER(name, head, cb, ctx) name##_ZIP_ITER(head, cb, ctx)
95
96/** Same as _ITER, but only visits elements with the given key */
97#define ZIP_ITER_KEY(name, head, key, cb, ctx) name##_ZIP_ITER_KEY(head, key, cb, ctx)
98
99/** Macro to generate typed ziptree methods */
100#define ZIP_FUNCTIONS(name, type, field, keytype, keyfield, cmp) \
101 \
102ZIP_UNUSED static ZIP_INLINE void \
103name##_ZIP_INSERT(struct name *head, struct type *el) { \
104 __ZIP_INSERT(head, (zip_cmp_cb)cmp, offsetof(struct type, field), \
105 offsetof(struct type, keyfield), el); \
106} \
107 \
108ZIP_UNUSED static ZIP_INLINE struct type * \
109name##_ZIP_REMOVE(struct name *head, struct type *elm) { \
110 return (struct type*) \
111 __ZIP_REMOVE(head, (zip_cmp_cb)cmp, \
112 offsetof(struct type, field), \
113 offsetof(struct type, keyfield), elm); \
114} \
115 \
116ZIP_UNUSED static ZIP_INLINE struct type * \
117name##_ZIP_FIND(struct name *head, const keytype *key) { \
118 struct type *cur = ZIP_ROOT(head); \
119 while(cur) { \
120 enum ZIP_CMP eq = cmp(key, &cur->keyfield); \
121 if(eq == ZIP_CMP_EQ) \
122 break; \
123 if(eq == ZIP_CMP_LESS) \
124 cur = ZIP_LEFT(cur, field); \
125 else \
126 cur = ZIP_RIGHT(cur, field); \
127 } \
128 return cur; \
129} \
130 \
131ZIP_UNUSED static ZIP_INLINE struct type * \
132name##_ZIP_MIN(struct name *head) { \
133 struct type *cur = ZIP_ROOT(head); \
134 if(!cur) \
135 return NULL; \
136 while(ZIP_LEFT(cur, field)) { \
137 cur = ZIP_LEFT(cur, field); \
138 } \
139 return cur; \
140} \
141 \
142ZIP_UNUSED static ZIP_INLINE struct type * \
143name##_ZIP_MAX(struct name *head) { \
144 struct type *cur = ZIP_ROOT(head); \
145 if(!cur) \
146 return NULL; \
147 while(ZIP_RIGHT(cur, field)) { \
148 cur = ZIP_RIGHT(cur, field); \
149 } \
150 return cur; \
151} \
152 \
153typedef void * (*name##_cb)(void *context, struct type *elm); \
154 \
155ZIP_UNUSED static ZIP_INLINE void * \
156name##_ZIP_ITER(struct name *head, name##_cb cb, void *context) { \
157 return __ZIP_ITER(offsetof(struct type, field), (zip_iter_cb)cb, \
158 context, ZIP_ROOT(head)); \
159} \
160 \
161ZIP_UNUSED static ZIP_INLINE void * \
162name##_ZIP_ITER_KEY(struct name *head, const keytype *key, \
163 name##_cb cb, void *context) { \
164 return __ZIP_ITER_KEY((zip_cmp_cb)cmp, offsetof(struct type, field), \
165 offsetof(struct type, keyfield), key, \
166 (zip_iter_cb)cb, context, ZIP_ROOT(head)); \
167} \
168 \
169ZIP_UNUSED static ZIP_INLINE struct type * \
170name##_ZIP_ZIP(struct type *left, struct type *right) { \
171 return (struct type*) \
172 __ZIP_ZIP(offsetof(struct type, field), left, right); \
173} \
174 \
175ZIP_UNUSED static ZIP_INLINE void \
176name##_ZIP_UNZIP(struct name *head, const keytype *key, \
177 struct name *left, struct name *right) { \
178 __ZIP_UNZIP((zip_cmp_cb)cmp, offsetof(struct type, field), \
179 offsetof(struct type, keyfield), key, \
180 head, left, right); \
181}
182
183/** Internal definitions. Don't use directly. */
184
185void
186__ZIP_INSERT(void *h, zip_cmp_cb cmp, unsigned short fieldoffset,
187 unsigned short keyoffset, void *elm);
188
189void *
190__ZIP_REMOVE(void *h, zip_cmp_cb cmp, unsigned short fieldoffset,
191 unsigned short keyoffset, void *elm);
192
193void *
194__ZIP_ITER(unsigned short fieldoffset, zip_iter_cb cb,
195 void *context, void *elm);
196
197void *
198__ZIP_ITER_KEY(zip_cmp_cb cmp, unsigned short fieldoffset,
199 unsigned short keyoffset, const void *key,
200 zip_iter_cb cb, void *context, void *elm);
201
202void *
203__ZIP_ZIP(unsigned short fieldoffset, void *left, void *right);
204
205void
206__ZIP_UNZIP(zip_cmp_cb cmp, unsigned short fieldoffset,
207 unsigned short keyoffset, const void *key,
208 void *h, void *l, void *r);
209
210#ifdef __cplusplus
211} /* extern "C" */
212#endif
213
214#endif /* ZIPTREE_H_ */
__ZIP_ITER
void * __ZIP_ITER(unsigned short fieldoffset, zip_iter_cb cb, void *context, void *elm)
ZIP_CMP
ZIP_CMP
Definition ziptree.h:55
ZIP_CMP_LESS
@ ZIP_CMP_LESS
Definition ziptree.h:56
ZIP_CMP_EQ
@ ZIP_CMP_EQ
Definition ziptree.h:57
ZIP_CMP_MORE
@ ZIP_CMP_MORE
Definition ziptree.h:58
zip_cmp_cb
enum ZIP_CMP(* zip_cmp_cb)(const void *key1, const void *key2)
The comparison method "cmp" for a zip tree has the signature.
Definition ziptree.h:66
__ZIP_INSERT
void __ZIP_INSERT(void *h, zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *elm)
Internal definitions.
__ZIP_UNZIP
void __ZIP_UNZIP(zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, const void *key, void *h, void *l, void *r)
__ZIP_ZIP
void * __ZIP_ZIP(unsigned short fieldoffset, void *left, void *right)
__ZIP_ITER_KEY
void * __ZIP_ITER_KEY(zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, const void *key, zip_iter_cb cb, void *context, void *elm)
zip_iter_cb
void *(* zip_iter_cb)(void *context, void *elm)
ZIP_ITER uses in-order traversal of the tree (in the order of the keys).
Definition ziptree.h:93
__ZIP_REMOVE
void * __ZIP_REMOVE(void *h, zip_cmp_cb cmp, unsigned short fieldoffset, unsigned short keyoffset, void *elm)
Generated by doxygen 1.9.8