Xenomai  3.1-devel
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 
45 struct __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 
56 struct __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  */
65 typedef int __AVL_T(avlh_cmp_t)(const struct __AVL_T(avlh) *const,
66  const struct __AVL_T(avlh) *const);
67 
68 typedef struct __AVL_T(avlh) *
69 __AVL_T(avl_search_t)(const struct __AVL_T(avl) *,
70  const struct __AVL_T(avlh) *, int *, int);
71 
72 typedef int __AVL_T(avlh_prn_t)(char *, size_t,
73  const struct __AVL_T(avlh) *const);
74 
75 struct __AVL_T(avl_searchops) {
76  __AVL_T(avl_search_t) *search;
77  __AVL_T(avlh_cmp_t) *cmp;
78 };
79 
80 struct __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 
103 static inline struct shavlh *
104 shavlh_link(const struct shavl *const avl,
105  const struct shavlh *const holder, unsigned int dir)
106 {
107  return (void *)avl + holder->link[avl_type2index(dir)].offset;
108 }
109 
110 static inline void
111 shavlh_set_link(struct shavl *const avl, struct shavlh *lhs,
112  int dir, struct shavlh *rhs)
113 {
114  lhs->link[avl_type2index(dir)].offset = (void *)rhs - (void *)avl;
115 }
116 
117 static inline
118 struct shavlh *shavl_end(const struct shavl *const avl, int dir)
119 {
120  return (void *)avl + avl->end[avl_type2index(dir)].offset;
121 }
122 
123 static inline void
124 shavl_set_end(struct shavl *const avl, int dir, struct shavlh *holder)
125 {
126  avl->end[avl_type2index(dir)].offset = (void *)holder - (void *)avl;
127 }
128 
129 #define shavl_count(avl) ((avl)->count)
130 #define shavl_height(avl) ((avl)->height)
131 #define shavl_anchor(avl) (&(avl)->anchor)
132 
133 #define shavlh_up(avl, holder) \
134  shavlh_link((avl), (holder), AVL_UP)
135 #define shavlh_left(avl, holder) \
136  shavlh_link((avl), (holder), AVL_LEFT)
137 #define shavlh_right(avl, holder) \
138  shavlh_link((avl), (holder), AVL_RIGHT)
139 
140 #define shavlh_thr_tst(avl, holder, side) \
141  (shavlh_link(avl, holder, side) == NULL)
142 #define shavlh_child(avl, holder, side) \
143  (shavlh_link((avl),(holder),(side)))
144 #define shavlh_has_child(avl, holder, side) \
145  (!shavlh_thr_tst(avl, holder, side))
146 
147 #define shavl_top(avl) (shavlh_right(avl, shavl_anchor(avl)))
148 #define shavl_head(avl) (shavl_end((avl), AVL_LEFT))
149 #define shavl_tail(avl) (shavl_end((avl), AVL_RIGHT))
150 
151 /*
152  * Search a node in a pshared AVL, return its parent if it could not
153  * be found.
154  */
155 #define DECLARE_SHAVL_SEARCH(__search_fn, __cmp) \
156  struct shavlh *__search_fn(const struct shavl *const avl, \
157  const struct shavlh *const node, \
158  int *const pdelta, int dir) \
159  { \
160  int delta = AVL_RIGHT; \
161  struct shavlh *holder = shavl_top(avl), *next; \
162  \
163  if (holder == NULL) \
164  goto done; \
165  \
166  for (;;) { \
167  delta = __cmp(node, holder); \
168  /* \
169  * Handle duplicates keys here, according to \
170  * "dir", if dir is: \
171  * - AVL_LEFT, the leftmost node is returned, \
172  * - AVL_RIGHT, the rightmost node is returned, \
173  * - 0, the first match is returned. \
174  */ \
175  if (!(delta ?: dir)) \
176  break; \
177  next = shavlh_child(avl, holder, delta ?: dir); \
178  if (next == NULL) \
179  break; \
180  holder = next; \
181  } \
182  \
183  done: \
184  *pdelta = delta; \
185  return holder; \
186  }
187 
188 #else /* !AVL_PSHARED */
189 
190 #define avlh_link(avl, holder, dir) ((holder)->link[avl_type2index(dir)].ptr)
191 
192 #define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)].ptr)
193 
194 static inline void
195 avlh_set_link(struct avl *const avl, struct avlh *lhs, int dir, struct avlh *rhs)
196 {
197  avlh_link(avl, lhs, dir) = rhs;
198 }
199 
200 static inline void
201 avl_set_end(struct avl *const avl, int dir, struct avlh *holder)
202 {
203  avl_end(avl, dir) = holder;
204 }
205 
206 #define avl_count(avl) ((avl)->count)
207 #define avl_height(avl) ((avl)->height)
208 #define avl_anchor(avl) (&(avl)->anchor)
209 
210 #define avlh_up(avl, holder) avlh_link((avl), (holder), AVL_UP)
211 #define avlh_left(avl, holder) avlh_link((avl), (holder), AVL_LEFT)
212 #define avlh_right(avl, holder) avlh_link((avl), (holder), AVL_RIGHT)
213 
214 #define avlh_thr_tst(avl, holder, side) (avlh_link(avl, holder, side) == NULL)
215 #define avlh_child(avl, holder, side) (avlh_link((avl),(holder),(side)))
216 #define avlh_has_child(avl, holder, side) (!avlh_thr_tst(avl, holder, side))
217 
218 #define avl_top(avl) (avlh_right(avl, avl_anchor(avl)))
219 #define avl_head(avl) (avl_end((avl), AVL_LEFT))
220 #define avl_tail(avl) (avl_end((avl), AVL_RIGHT))
221 
222 /*
223  * Search a node in a private AVL, return its parent if it could not
224  * be found.
225  */
226 #define DECLARE_AVL_SEARCH(__search_fn, __cmp) \
227  struct avlh *__search_fn(const struct avl *const avl, \
228  const struct avlh *const node, \
229  int *const pdelta, int dir) \
230  { \
231  int delta = AVL_RIGHT; \
232  struct avlh *holder = avl_top(avl), *next; \
233  \
234  if (holder == NULL) \
235  goto done; \
236  \
237  for (;;) { \
238  delta = __cmp(node, holder); \
239  /* \
240  * Handle duplicates keys here, according to \
241  * "dir", if dir is: \
242  * - AVL_LEFT, the leftmost node is returned, \
243  * - AVL_RIGHT, the rightmost node is returned, \
244  * - 0, the first match is returned. \
245  */ \
246  if (!(delta ?: dir)) \
247  break; \
248  next = avlh_child(avl, holder, delta ?: dir); \
249  if (next == NULL) \
250  break; \
251  holder = next; \
252  } \
253  \
254  done: \
255  *pdelta = delta; \
256  return holder; \
257  }
258 
259 #endif /* !AVL_PSHARED */
260 
261 /*
262  * From "Bit twiddling hacks", returns v < 0 ? -1 : (v > 0 ? 1 : 0)
263  */
264 #define avl_sign(v) \
265  ({ \
266  typeof(v) _v = (v); \
267  ((_v) > 0) - ((_v) < 0); \
268  })
269 
270 /*
271  * Variation on the same theme.
272  */
273 #define avl_cmp_sign(l, r) \
274  ({ \
275  typeof(l) _l = (l); \
276  typeof(r) _r = (r); \
277  (_l > _r) - (_l < _r); \
278  })
279 
280 static inline struct __AVL_T(avlh) *
281 __AVL(search_inner)(const struct __AVL_T(avl) *const avl,
282  const struct __AVL_T(avlh) *n, int *delta,
283  const struct __AVL_T(avl_searchops) *ops)
284 {
285  return ops->search(avl, n, delta, 0);
286 }
287 
288 static inline
289 struct __AVL_T(avlh) *__AVL(gettop)(const struct __AVL_T(avl) *const avl)
290 {
291  return __AVL(top)(avl);
292 }
293 
294 static inline
295 struct __AVL_T(avlh) *__AVL(gethead)(const struct __AVL_T(avl) *const avl)
296 {
297  return __AVL(head)(avl);
298 }
299 
300 static inline
301 struct __AVL_T(avlh) *__AVL(gettail)(const struct __AVL_T(avl) *const avl)
302 {
303  return __AVL(tail)(avl);
304 }
305 
306 static inline
307 unsigned int __AVL(getcount)(const struct __AVL_T(avl) *const avl)
308 {
309  return __AVL(count)(avl);
310 }
311 
312 struct __AVL_T(avlh) *__AVL(inorder)(const struct __AVL_T(avl) *const avl,
313  struct __AVL_T(avlh) *holder,
314  const int dir);
315 
316 struct __AVL_T(avlh) *__AVL(postorder)(const struct __AVL_T(avl) *const avl,
317  struct __AVL_T(avlh) *const holder,
318  const int dir);
319 
320 struct __AVL_T(avlh) *__AVL(preorder)(const struct __AVL_T(avl) *const avl,
321  struct __AVL_T(avlh) *holder,
322  const int dir);
323 
324 static inline struct __AVL_T(avlh) *
325 __AVL(next)(const struct __AVL_T(avl) *const avl,
326  struct __AVL_T(avlh) *const holder)
327 {
328  return __AVL(inorder)(avl, holder, AVL_RIGHT);
329 }
330 
331 static inline struct __AVL_T(avlh) *
332 __AVL(prev)(const struct __AVL_T(avl) *const avl,
333  struct __AVL_T(avlh) *const holder)
334 {
335  return __AVL(inorder)(avl, holder, AVL_LEFT);
336 }
337 
338 static inline struct __AVL_T(avlh) *
339 __AVL(postorder_next)(const struct __AVL_T(avl) *const avl,
340  struct __AVL_T(avlh) *const holder)
341 {
342  return __AVL(postorder)(avl, holder, AVL_RIGHT);
343 }
344 
345 static inline struct __AVL_T(avlh) *
346 __AVL(postorder_prev)(const struct __AVL_T(avl) *const avl,
347  struct __AVL_T(avlh) *const holder)
348 {
349  return __AVL(postorder)(avl, holder, AVL_LEFT);
350 }
351 
352 static inline struct __AVL_T(avlh) *
353 __AVL(preorder_next)(const struct __AVL_T(avl) *const avl,
354  struct __AVL_T(avlh) *const holder)
355 {
356  return __AVL(preorder)(avl, holder, AVL_RIGHT);
357 }
358 
359 static inline struct __AVL_T(avlh) *
360 __AVL(preorder_prev)(const struct __AVL_T(avl) *const avl,
361  struct __AVL_T(avlh) *const holder)
362 {
363  return __AVL(preorder)(avl, holder, AVL_LEFT);
364 }
365 
366 static inline void __AVLH(init)(struct __AVL_T(avlh) *const holder)
367 {
368  holder->balance = 0;
369  holder->type = 0;
370 }
371 
372 static inline struct __AVL_T(avlh) *
373 __AVL(search)(const struct __AVL_T(avl) *const avl,
374  const struct __AVL_T(avlh) *node,
375  const struct __AVL_T(avl_searchops) *ops)
376 {
377  struct __AVL_T(avlh) *holder;
378  int delta;
379 
380  holder = __AVL(search_inner)(avl, node, &delta, ops);
381  if (!delta)
382  return holder;
383 
384  return NULL;
385 }
386 
387 static inline struct __AVL_T(avlh) *
388 __AVL(search_nearest)(const struct __AVL_T(avl) *const avl,
389  const struct __AVL_T(avlh) *node, int dir,
390  const struct __AVL_T(avl_searchops) *ops)
391 {
392  struct __AVL_T(avlh) *holder;
393  int delta;
394 
395  holder = __AVL(search_inner)(avl, node, &delta, ops);
396  if (!holder || delta != dir)
397  return holder;
398 
399  return __AVL(inorder)(avl, holder, dir);
400 }
401 
402 static inline struct __AVL_T(avlh) *
403 __AVL(search_le)(const struct __AVL_T(avl) *const avl,
404  const struct __AVL_T(avlh) *node,
405  const struct __AVL_T(avl_searchops) *ops)
406 {
407  return __AVL(search_nearest)(avl, node, AVL_LEFT, ops);
408 }
409 
410 static inline struct __AVL_T(avlh) *
411 __AVL(search_ge)(const struct __AVL_T(avl) *const avl,
412  const struct __AVL_T(avlh) *node,
413  const struct __AVL_T(avl_searchops) *ops)
414 {
415  return __AVL(search_nearest)(avl, node, AVL_RIGHT, ops);
416 }
417 
418 static inline struct __AVL_T(avlh) *
419 __AVL(search_multi)(const struct __AVL_T(avl) *const avl,
420  const struct __AVL_T(avlh) *node, int dir,
421  const struct __AVL_T(avl_searchops) *ops)
422 {
423  struct __AVL_T(avlh) *holder;
424  int delta;
425 
426  holder = ops->search(avl, node, &delta, dir);
427  if (!delta)
428  return holder;
429 
430  if (!holder)
431  return NULL;
432 
433  return __AVL(inorder)(avl, holder, -dir);
434 }
435 
436 static inline struct __AVL_T(avlh) *
437 __AVL(search_first)(const struct __AVL_T(avl) *const avl,
438  const struct __AVL_T(avlh) *node,
439  const struct __AVL_T(avl_searchops) *ops)
440 {
441  return __AVL(search_multi)(avl, node, AVL_LEFT, ops);
442 }
443 
444 static inline struct __AVL_T(avlh) *
445 __AVL(search_last)(const struct __AVL_T(avl) *const avl,
446  const struct __AVL_T(avlh) *node,
447  const struct __AVL_T(avl_searchops) *ops)
448 {
449  return __AVL(search_multi)(avl, node, AVL_RIGHT, ops);
450 }
451 
452 #ifdef __cplusplus
453 extern "C" {
454 #endif /* __cplusplus */
455 
456 void __AVL(init)(struct __AVL_T(avl) *const avl);
457 
458 void __AVL(destroy)(struct __AVL_T(avl) *const avl);
459 
460 int __AVL(insert)(struct __AVL_T(avl) *const avl,
461  struct __AVL_T(avlh) *const holder,
462  const struct __AVL_T(avl_searchops) *ops);
463 
464 int __AVL(insert_front)(struct __AVL_T(avl) *avl,
465  struct __AVL_T(avlh) *holder,
466  const struct __AVL_T(avl_searchops) *ops);
467 
468 int __AVL(insert_back)(struct __AVL_T(avl) *avl,
469  struct __AVL_T(avlh) *holder,
470  const struct __AVL_T(avl_searchops) *ops);
471 
472 int __AVL(insert_at)(struct __AVL_T(avl) *const avl,
473  struct __AVL_T(avlh) *parent, int dir,
474  struct __AVL_T(avlh) *child);
475 
476 int __AVL(prepend)(struct __AVL_T(avl) *const avl,
477  struct __AVL_T(avlh) *const holder,
478  const struct __AVL_T(avl_searchops) *ops);
479 
480 int __AVL(append)(struct __AVL_T(avl) *const avl,
481  struct __AVL_T(avlh) *const holder,
482  const struct __AVL_T(avl_searchops) *ops);
483 
484 int __AVL(delete)(struct __AVL_T(avl) *const avl,
485  struct __AVL_T(avlh) *node);
486 
487 int __AVL(replace)(struct __AVL_T(avl) *avl,
488  struct __AVL_T(avlh) *oldh,
489  struct __AVL_T(avlh) *newh,
490  const struct __AVL_T(avl_searchops) *ops);
491 
492 struct __AVL_T(avlh) *__AVL(update)(struct __AVL_T(avl) *const avl,
493  struct __AVL_T(avlh) *const holder,
494  const struct __AVL_T(avl_searchops) *ops);
495 
496 struct __AVL_T(avlh) *__AVL(set)(struct __AVL_T(avl) *const avl,
497  struct __AVL_T(avlh) *const holder,
498  const struct __AVL_T(avl_searchops) *ops);
499 
500 void __AVL(clear)(struct __AVL_T(avl) *const avl,
501  void (*destruct)(struct __AVL_T(avlh) *));
502 
503 int __AVL(check)(const struct __AVL_T(avl) *avl,
504  const struct __AVL_T(avl_searchops) *ops);
505 
506 void __AVL(dump)(FILE *file, const struct __AVL_T(avl) *const avl,
507  __AVL_T(avlh_prn_t) *prn, unsigned int indent,
508  unsigned int len);
509 
510 #ifdef __cplusplus
511 }
512 #endif /* __cplusplus */
513 
514 #undef __AVL
515 #undef __AVLH
516 #undef __AVL_T
517 
518 #endif /* !_BOILERPLATE_AVL_INNER_H */