Xenomai 3.3.2
Loading...
Searching...
No Matches
avl-inner.h
1/*
2 * Copyright (c) 2015 Gilles Chanteperdrix
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be included
13 * in all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
19 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
20 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
21 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22 */
23#if (!defined(_BOILERPLATE_AVL_INNER_H) && !defined(AVL_PSHARED)) || \
24 (!defined(_BOILERPLATE_AVL_SHARED_INNER_H) && defined(AVL_PSHARED)) /* Yeah, well... */
25
26#if !defined(_BOILERPLATE_AVL_H) && !defined(_BOILERPLATE_SHAVL_H)
27#error "Do not include this file directly. Use <boilerplate/avl.h> or <boilerplate/shavl.h> instead."
28#endif
29
30#include <stddef.h>
31#include <stdio.h>
32
33#ifdef AVL_PSHARED
34#define __AVL(__decl) shavl_ ## __decl
35#define __AVLH(__decl) shavlh_ ## __decl
36#define __AVL_T(__type) sh ## __type
37#define _BOILERPLATE_AVL_SHARED_INNER_H
38#else
39#define __AVL(__decl) avl_ ## __decl
40#define __AVLH(__decl) avlh_ ## __decl
41#define __AVL_T(__type) __type
42#define _BOILERPLATE_AVL_INNER_H
43#endif
44
45struct __AVL_T(avlh) {
46#define AVLH_APP_BITS 28
47 unsigned int flags: AVLH_APP_BITS;
48 int type: 2;
49 int balance: 2;
50 union {
51 ptrdiff_t offset;
52 struct __AVL_T(avlh) *ptr;
53 } link[3];
54};
55
56struct __AVL_T(avl);
57
58/*
59 * Comparison function: should return -1 if left is less than right, 0
60 * if they are equal and 1 if left is greather than right. You can use
61 * the avl_sign function which will convert a difference to -1, 0,
62 * 1. Beware of overflow however. You can also use avl_cmp_sign()
63 * which should not have any such problems.
64 */
65typedef int __AVL_T(avlh_cmp_t)(const struct __AVL_T(avlh) *const,
66 const struct __AVL_T(avlh) *const);
67
68typedef struct __AVL_T(avlh) *
69__AVL_T(avl_search_t)(const struct __AVL_T(avl) *,
70 const struct __AVL_T(avlh) *, int *, int);
71
72typedef int __AVL_T(avlh_prn_t)(char *, size_t,
73 const struct __AVL_T(avlh) *const);
74
75struct __AVL_T(avl_searchops) {
76 __AVL_T(avl_search_t) *search;
77 __AVL_T(avlh_cmp_t) *cmp;
78};
79
80struct __AVL_T(avl) {
81 struct __AVL_T(avlh) anchor;
82 union {
83 ptrdiff_t offset;
84 struct __AVL_T(avlh) *ptr;
85 } end[3];
86 unsigned int count;
87 unsigned int height;
88};
89
90#define AVL_LEFT -1
91#define AVL_UP 0
92#define AVL_RIGHT 1
93/* maps AVL_LEFT to AVL_RIGHT and reciprocally. */
94#define avl_opposite(type) (-(type))
95/* maps AVL_LEFT and AVL_RIGHT to arrays index (or bit positions). */
96#define avl_type2index(type) ((type)+1)
97
98#define AVL_THR_LEFT (1 << avl_type2index(AVL_LEFT))
99#define AVL_THR_RIGHT (1 << avl_type2index(AVL_RIGHT))
100
101#ifdef AVL_PSHARED
102
103static inline struct shavlh *
104shavlh_link(const struct shavl *const avl,
105 const struct shavlh *const holder, unsigned int dir)
106{
107 ptrdiff_t offset = holder->link[avl_type2index(dir)].offset;
108 return offset == (ptrdiff_t)-1 ? NULL : (void *)avl + offset;
109}
110
111static inline void
112shavlh_set_link(struct shavl *const avl, struct shavlh *lhs,
113 int dir, struct shavlh *rhs)
114{
115 ptrdiff_t offset = rhs ? (void *)rhs - (void *)avl : (ptrdiff_t)-1;
116 lhs->link[avl_type2index(dir)].offset = offset;
117}
118
119static inline
120struct shavlh *shavl_end(const struct shavl *const avl, int dir)
121{
122 ptrdiff_t offset = avl->end[avl_type2index(dir)].offset;
123 return offset == (ptrdiff_t)-1 ? NULL : (void *)avl + offset;
124}
125
126static inline void
127shavl_set_end(struct shavl *const avl, int dir, struct shavlh *holder)
128{
129 ptrdiff_t offset = holder ? (void *)holder - (void *)avl : (ptrdiff_t)-1;
130 avl->end[avl_type2index(dir)].offset = offset;
131}
132
133#define shavl_count(avl) ((avl)->count)
134#define shavl_height(avl) ((avl)->height)
135#define shavl_anchor(avl) (&(avl)->anchor)
136
137#define shavlh_up(avl, holder) \
138 shavlh_link((avl), (holder), AVL_UP)
139#define shavlh_left(avl, holder) \
140 shavlh_link((avl), (holder), AVL_LEFT)
141#define shavlh_right(avl, holder) \
142 shavlh_link((avl), (holder), AVL_RIGHT)
143
144#define shavlh_thr_tst(avl, holder, side) \
145 (shavlh_link(avl, holder, side) == NULL)
146#define shavlh_child(avl, holder, side) \
147 (shavlh_link((avl),(holder),(side)))
148#define shavlh_has_child(avl, holder, side) \
149 (!shavlh_thr_tst(avl, holder, side))
150
151#define shavl_top(avl) (shavlh_right(avl, shavl_anchor(avl)))
152#define shavl_head(avl) (shavl_end((avl), AVL_LEFT))
153#define shavl_tail(avl) (shavl_end((avl), AVL_RIGHT))
154
155/*
156 * Search a node in a pshared AVL, return its parent if it could not
157 * be found.
158 */
159#define DECLARE_SHAVL_SEARCH(__search_fn, __cmp) \
160 struct shavlh *__search_fn(const struct shavl *const avl, \
161 const struct shavlh *const node, \
162 int *const pdelta, int dir) \
163 { \
164 int delta = AVL_RIGHT; \
165 struct shavlh *holder = shavl_top(avl), *next; \
166 \
167 if (holder == NULL) \
168 goto done; \
169 \
170 for (;;) { \
171 delta = __cmp(node, holder); \
172 /* \
173 * Handle duplicates keys here, according to \
174 * "dir", if dir is: \
175 * - AVL_LEFT, the leftmost node is returned, \
176 * - AVL_RIGHT, the rightmost node is returned, \
177 * - 0, the first match is returned. \
178 */ \
179 if (!(delta ?: dir)) \
180 break; \
181 next = shavlh_child(avl, holder, delta ?: dir); \
182 if (next == NULL) \
183 break; \
184 holder = next; \
185 } \
186 \
187 done: \
188 *pdelta = delta; \
189 return holder; \
190 }
191
192#else /* !AVL_PSHARED */
193
194#define avlh_link(avl, holder, dir) ((holder)->link[avl_type2index(dir)].ptr)
195
196#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)].ptr)
197
198static inline void
199avlh_set_link(struct avl *const avl, struct avlh *lhs, int dir, struct avlh *rhs)
200{
201 avlh_link(avl, lhs, dir) = rhs;
202}
203
204static inline void
205avl_set_end(struct avl *const avl, int dir, struct avlh *holder)
206{
207 avl_end(avl, dir) = holder;
208}
209
210#define avl_count(avl) ((avl)->count)
211#define avl_height(avl) ((avl)->height)
212#define avl_anchor(avl) (&(avl)->anchor)
213
214#define avlh_up(avl, holder) avlh_link((avl), (holder), AVL_UP)
215#define avlh_left(avl, holder) avlh_link((avl), (holder), AVL_LEFT)
216#define avlh_right(avl, holder) avlh_link((avl), (holder), AVL_RIGHT)
217
218#define avlh_thr_tst(avl, holder, side) (avlh_link(avl, holder, side) == NULL)
219#define avlh_child(avl, holder, side) (avlh_link((avl),(holder),(side)))
220#define avlh_has_child(avl, holder, side) (!avlh_thr_tst(avl, holder, side))
221
222#define avl_top(avl) (avlh_right(avl, avl_anchor(avl)))
223#define avl_head(avl) (avl_end((avl), AVL_LEFT))
224#define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
225
226/*
227 * Search a node in a private AVL, return its parent if it could not
228 * be found.
229 */
230#define DECLARE_AVL_SEARCH(__search_fn, __cmp) \
231 struct avlh *__search_fn(const struct avl *const avl, \
232 const struct avlh *const node, \
233 int *const pdelta, int dir) \
234 { \
235 int delta = AVL_RIGHT; \
236 struct avlh *holder = avl_top(avl), *next; \
237 \
238 if (holder == NULL) \
239 goto done; \
240 \
241 for (;;) { \
242 delta = __cmp(node, holder); \
243 /* \
244 * Handle duplicates keys here, according to \
245 * "dir", if dir is: \
246 * - AVL_LEFT, the leftmost node is returned, \
247 * - AVL_RIGHT, the rightmost node is returned, \
248 * - 0, the first match is returned. \
249 */ \
250 if (!(delta ?: dir)) \
251 break; \
252 next = avlh_child(avl, holder, delta ?: dir); \
253 if (next == NULL) \
254 break; \
255 holder = next; \
256 } \
257 \
258 done: \
259 *pdelta = delta; \
260 return holder; \
261 }
262
263#endif /* !AVL_PSHARED */
264
265/*
266 * From "Bit twiddling hacks", returns v < 0 ? -1 : (v > 0 ? 1 : 0)
267 */
268#define avl_sign(v) \
269 ({ \
270 typeof(v) _v = (v); \
271 ((_v) > 0) - ((_v) < 0); \
272 })
273
274/*
275 * Variation on the same theme.
276 */
277#define avl_cmp_sign(l, r) \
278 ({ \
279 typeof(l) _l = (l); \
280 typeof(r) _r = (r); \
281 (_l > _r) - (_l < _r); \
282 })
283
284static inline struct __AVL_T(avlh) *
285__AVL(search_inner)(const struct __AVL_T(avl) *const avl,
286 const struct __AVL_T(avlh) *n, int *delta,
287 const struct __AVL_T(avl_searchops) *ops)
288{
289 return ops->search(avl, n, delta, 0);
290}
291
292static inline
293struct __AVL_T(avlh) *__AVL(gettop)(const struct __AVL_T(avl) *const avl)
294{
295 return __AVL(top)(avl);
296}
297
298static inline
299struct __AVL_T(avlh) *__AVL(gethead)(const struct __AVL_T(avl) *const avl)
300{
301 return __AVL(head)(avl);
302}
303
304static inline
305struct __AVL_T(avlh) *__AVL(gettail)(const struct __AVL_T(avl) *const avl)
306{
307 return __AVL(tail)(avl);
308}
309
310static inline
311unsigned int __AVL(getcount)(const struct __AVL_T(avl) *const avl)
312{
313 return __AVL(count)(avl);
314}
315
316struct __AVL_T(avlh) *__AVL(inorder)(const struct __AVL_T(avl) *const avl,
317 struct __AVL_T(avlh) *holder,
318 const int dir);
319
320struct __AVL_T(avlh) *__AVL(postorder)(const struct __AVL_T(avl) *const avl,
321 struct __AVL_T(avlh) *const holder,
322 const int dir);
323
324struct __AVL_T(avlh) *__AVL(preorder)(const struct __AVL_T(avl) *const avl,
325 struct __AVL_T(avlh) *holder,
326 const int dir);
327
328static inline struct __AVL_T(avlh) *
329__AVL(next)(const struct __AVL_T(avl) *const avl,
330 struct __AVL_T(avlh) *const holder)
331{
332 return __AVL(inorder)(avl, holder, AVL_RIGHT);
333}
334
335static inline struct __AVL_T(avlh) *
336__AVL(prev)(const struct __AVL_T(avl) *const avl,
337 struct __AVL_T(avlh) *const holder)
338{
339 return __AVL(inorder)(avl, holder, AVL_LEFT);
340}
341
342static inline struct __AVL_T(avlh) *
343__AVL(postorder_next)(const struct __AVL_T(avl) *const avl,
344 struct __AVL_T(avlh) *const holder)
345{
346 return __AVL(postorder)(avl, holder, AVL_RIGHT);
347}
348
349static inline struct __AVL_T(avlh) *
350__AVL(postorder_prev)(const struct __AVL_T(avl) *const avl,
351 struct __AVL_T(avlh) *const holder)
352{
353 return __AVL(postorder)(avl, holder, AVL_LEFT);
354}
355
356static inline struct __AVL_T(avlh) *
357__AVL(preorder_next)(const struct __AVL_T(avl) *const avl,
358 struct __AVL_T(avlh) *const holder)
359{
360 return __AVL(preorder)(avl, holder, AVL_RIGHT);
361}
362
363static inline struct __AVL_T(avlh) *
364__AVL(preorder_prev)(const struct __AVL_T(avl) *const avl,
365 struct __AVL_T(avlh) *const holder)
366{
367 return __AVL(preorder)(avl, holder, AVL_LEFT);
368}
369
370static inline void __AVLH(init)(struct __AVL_T(avlh) *const holder)
371{
372 holder->balance = 0;
373 holder->type = 0;
374}
375
376static inline struct __AVL_T(avlh) *
377__AVL(search)(const struct __AVL_T(avl) *const avl,
378 const struct __AVL_T(avlh) *node,
379 const struct __AVL_T(avl_searchops) *ops)
380{
381 struct __AVL_T(avlh) *holder;
382 int delta;
383
384 holder = __AVL(search_inner)(avl, node, &delta, ops);
385 if (!delta)
386 return holder;
387
388 return NULL;
389}
390
391static inline struct __AVL_T(avlh) *
392__AVL(search_nearest)(const struct __AVL_T(avl) *const avl,
393 const struct __AVL_T(avlh) *node, int dir,
394 const struct __AVL_T(avl_searchops) *ops)
395{
396 struct __AVL_T(avlh) *holder;
397 int delta;
398
399 holder = __AVL(search_inner)(avl, node, &delta, ops);
400 if (!holder || delta != dir)
401 return holder;
402
403 return __AVL(inorder)(avl, holder, dir);
404}
405
406static inline struct __AVL_T(avlh) *
407__AVL(search_le)(const struct __AVL_T(avl) *const avl,
408 const struct __AVL_T(avlh) *node,
409 const struct __AVL_T(avl_searchops) *ops)
410{
411 return __AVL(search_nearest)(avl, node, AVL_LEFT, ops);
412}
413
414static inline struct __AVL_T(avlh) *
415__AVL(search_ge)(const struct __AVL_T(avl) *const avl,
416 const struct __AVL_T(avlh) *node,
417 const struct __AVL_T(avl_searchops) *ops)
418{
419 return __AVL(search_nearest)(avl, node, AVL_RIGHT, ops);
420}
421
422static inline struct __AVL_T(avlh) *
423__AVL(search_multi)(const struct __AVL_T(avl) *const avl,
424 const struct __AVL_T(avlh) *node, int dir,
425 const struct __AVL_T(avl_searchops) *ops)
426{
427 struct __AVL_T(avlh) *holder;
428 int delta;
429
430 holder = ops->search(avl, node, &delta, dir);
431 if (!delta)
432 return holder;
433
434 if (!holder)
435 return NULL;
436
437 return __AVL(inorder)(avl, holder, -dir);
438}
439
440static inline struct __AVL_T(avlh) *
441__AVL(search_first)(const struct __AVL_T(avl) *const avl,
442 const struct __AVL_T(avlh) *node,
443 const struct __AVL_T(avl_searchops) *ops)
444{
445 return __AVL(search_multi)(avl, node, AVL_LEFT, ops);
446}
447
448static inline struct __AVL_T(avlh) *
449__AVL(search_last)(const struct __AVL_T(avl) *const avl,
450 const struct __AVL_T(avlh) *node,
451 const struct __AVL_T(avl_searchops) *ops)
452{
453 return __AVL(search_multi)(avl, node, AVL_RIGHT, ops);
454}
455
456#ifdef __cplusplus
457extern "C" {
458#endif /* __cplusplus */
459
460void __AVL(init)(struct __AVL_T(avl) *const avl);
461
462void __AVL(destroy)(struct __AVL_T(avl) *const avl);
463
464int __AVL(insert)(struct __AVL_T(avl) *const avl,
465 struct __AVL_T(avlh) *const holder,
466 const struct __AVL_T(avl_searchops) *ops);
467
468int __AVL(insert_front)(struct __AVL_T(avl) *avl,
469 struct __AVL_T(avlh) *holder,
470 const struct __AVL_T(avl_searchops) *ops);
471
472int __AVL(insert_back)(struct __AVL_T(avl) *avl,
473 struct __AVL_T(avlh) *holder,
474 const struct __AVL_T(avl_searchops) *ops);
475
476int __AVL(insert_at)(struct __AVL_T(avl) *const avl,
477 struct __AVL_T(avlh) *parent, int dir,
478 struct __AVL_T(avlh) *child);
479
480int __AVL(prepend)(struct __AVL_T(avl) *const avl,
481 struct __AVL_T(avlh) *const holder,
482 const struct __AVL_T(avl_searchops) *ops);
483
484int __AVL(append)(struct __AVL_T(avl) *const avl,
485 struct __AVL_T(avlh) *const holder,
486 const struct __AVL_T(avl_searchops) *ops);
487
488int __AVL(delete)(struct __AVL_T(avl) *const avl,
489 struct __AVL_T(avlh) *node);
490
491int __AVL(replace)(struct __AVL_T(avl) *avl,
492 struct __AVL_T(avlh) *oldh,
493 struct __AVL_T(avlh) *newh,
494 const struct __AVL_T(avl_searchops) *ops);
495
496struct __AVL_T(avlh) *__AVL(update)(struct __AVL_T(avl) *const avl,
497 struct __AVL_T(avlh) *const holder,
498 const struct __AVL_T(avl_searchops) *ops);
499
500struct __AVL_T(avlh) *__AVL(set)(struct __AVL_T(avl) *const avl,
501 struct __AVL_T(avlh) *const holder,
502 const struct __AVL_T(avl_searchops) *ops);
503
504void __AVL(clear)(struct __AVL_T(avl) *const avl,
505 void (*destruct)(struct __AVL_T(avlh) *));
506
507int __AVL(check)(const struct __AVL_T(avl) *avl,
508 const struct __AVL_T(avl_searchops) *ops);
509
510void __AVL(dump)(FILE *file, const struct __AVL_T(avl) *const avl,
511 __AVL_T(avlh_prn_t) *prn, unsigned int indent,
512 unsigned int len);
513
514#ifdef __cplusplus
515}
516#endif /* __cplusplus */
517
518#undef __AVL
519#undef __AVLH
520#undef __AVL_T
521
522#endif /* !_BOILERPLATE_AVL_INNER_H */