summaryrefslogtreecommitdiff
path: root/src/tree.h
diff options
context:
space:
mode:
authorMuhammad Moinur Rahman <bofh@FreeBSD.org>2026-01-07 19:19:44 +0100
committerMuhammad Moinur Rahman <bofh@FreeBSD.org>2026-01-07 19:19:44 +0100
commit1dd83cf7e527ff29d734f6a2c8f9b61d39b41d94 (patch)
treeda5185757a055488bdc9cbb7d17077a8f36596a9 /src/tree.h
parent1e2f270469c61337ef7f5f92ab93f691e5d86492 (diff)
Import libucl 0.9.3vendor/libucl/0.9.3vendor/libucl
Diffstat (limited to 'src/tree.h')
-rw-r--r--src/tree.h314
1 files changed, 152 insertions, 162 deletions
diff --git a/src/tree.h b/src/tree.h
index 404b4a867be9..bb5fe46ff6a9 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -43,177 +43,167 @@
#define __tree_h
-#define TREE_DELTA_MAX 1
+#define TREE_DELTA_MAX 1
#ifndef _HU_FUNCTION
-# if defined(__GNUC__) || defined(__clang__)
-# define _HU_FUNCTION(x) __attribute__((__unused__)) x
-# else
-# define _HU_FUNCTION(x) x
-# endif
+#if defined(__GNUC__) || defined(__clang__)
+#define _HU_FUNCTION(x) __attribute__((__unused__)) x
+#else
+#define _HU_FUNCTION(x) x
+#endif
#endif
-#define TREE_ENTRY(type) \
- struct { \
- struct type *avl_left; \
- struct type *avl_right; \
- int avl_height; \
- }
+#define TREE_ENTRY(type) \
+ struct { \
+ struct type *avl_left; \
+ struct type *avl_right; \
+ int avl_height; \
+ }
-#define TREE_HEAD(name, type) \
- struct name { \
- struct type *th_root; \
- int (*th_cmp)(struct type *lhs, struct type *rhs); \
- }
+#define TREE_HEAD(name, type) \
+ struct name { \
+ struct type *th_root; \
+ int (*th_cmp)(struct type * lhs, struct type *rhs); \
+ }
-#define TREE_INITIALIZER(cmp) { 0, cmp }
+#define TREE_INITIALIZER(cmp) {0, cmp}
-#define TREE_DELTA(self, field) \
- (( (((self)->field.avl_left) ? (self)->field.avl_left->field.avl_height : 0)) \
- - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0))
+#define TREE_DELTA(self, field) \
+ (((((self)->field.avl_left) ? (self)->field.avl_left->field.avl_height : 0)) - (((self)->field.avl_right) ? (self)->field.avl_right->field.avl_height : 0))
/* Recursion prevents the following from being defined as macros. */
-#define TREE_DEFINE(node, field) \
- \
- static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node *); \
- \
- static struct node *_HU_FUNCTION(TREE_ROTL_##node##_##field)(struct node *self) \
- { \
- struct node *r= self->field.avl_right; \
- self->field.avl_right= r->field.avl_left; \
- r->field.avl_left= TREE_BALANCE_##node##_##field(self); \
- return TREE_BALANCE_##node##_##field(r); \
- } \
- \
- static struct node *_HU_FUNCTION(TREE_ROTR_##node##_##field)(struct node *self) \
- { \
- struct node *l= self->field.avl_left; \
- self->field.avl_left= l->field.avl_right; \
- l->field.avl_right= TREE_BALANCE_##node##_##field(self); \
- return TREE_BALANCE_##node##_##field(l); \
- } \
- \
- static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node *self) \
- { \
- int delta= TREE_DELTA(self, field); \
- \
- if (delta < -TREE_DELTA_MAX) \
- { \
- if (TREE_DELTA(self->field.avl_right, field) > 0) \
- self->field.avl_right= TREE_ROTR_##node##_##field(self->field.avl_right); \
- return TREE_ROTL_##node##_##field(self); \
- } \
- else if (delta > TREE_DELTA_MAX) \
- { \
- if (TREE_DELTA(self->field.avl_left, field) < 0) \
- self->field.avl_left= TREE_ROTL_##node##_##field(self->field.avl_left); \
- return TREE_ROTR_##node##_##field(self); \
- } \
- self->field.avl_height= 0; \
- if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height)) \
- self->field.avl_height= self->field.avl_left->field.avl_height; \
- if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height)) \
- self->field.avl_height= self->field.avl_right->field.avl_height; \
- self->field.avl_height += 1; \
- return self; \
- } \
- \
- static struct node *_HU_FUNCTION(TREE_INSERT_##node##_##field) \
- (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \
- { \
- if (!self) \
- return elm; \
- if (compare(elm, self) < 0) \
- self->field.avl_left= TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare); \
- else \
- self->field.avl_right= TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare); \
- return TREE_BALANCE_##node##_##field(self); \
- } \
- \
- static struct node *_HU_FUNCTION(TREE_FIND_##node##_##field) \
- (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \
- { \
- if (!self) \
- return 0; \
- if (compare(elm, self) == 0) \
- return self; \
- if (compare(elm, self) < 0) \
- return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \
- else \
- return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \
- } \
- \
- static struct node *_HU_FUNCTION(TREE_MOVE_RIGHT)(struct node *self, struct node *rhs) \
- { \
- if (!self) \
- return rhs; \
- self->field.avl_right= TREE_MOVE_RIGHT(self->field.avl_right, rhs); \
- return TREE_BALANCE_##node##_##field(self); \
- } \
- \
- static struct node *_HU_FUNCTION(TREE_REMOVE_##node##_##field) \
- (struct node *self, struct node *elm, int (*compare)(struct node *lhs, struct node *rhs)) \
- { \
- if (!self) return 0; \
- \
- if (compare(elm, self) == 0) \
- { \
- struct node *tmp= TREE_MOVE_RIGHT(self->field.avl_left, self->field.avl_right); \
- self->field.avl_left= 0; \
- self->field.avl_right= 0; \
- return tmp; \
- } \
- if (compare(elm, self) < 0) \
- self->field.avl_left= TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare); \
- else \
- self->field.avl_right= TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare); \
- return TREE_BALANCE_##node##_##field(self); \
- } \
- \
- static void _HU_FUNCTION(TREE_FORWARD_APPLY_ALL_##node##_##field) \
- (struct node *self, void (*function)(struct node *node, void *data), void *data) \
- { \
- if (self) \
- { \
- TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \
- function(self, data); \
- TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \
- } \
- } \
- \
- static void _HU_FUNCTION(TREE_REVERSE_APPLY_ALL_##node##_##field) \
- (struct node *self, void (*function)(struct node *node, void *data), void *data) \
- { \
- if (self) \
- { \
- TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \
- function(self, data); \
- TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \
- } \
- }
-
-#define TREE_INSERT(head, node, field, elm) \
- ((head)->th_root= TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
-
-#define TREE_FIND(head, node, field, elm) \
- (TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
-
-#define TREE_REMOVE(head, node, field, elm) \
- ((head)->th_root= TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
-
-#define TREE_DEPTH(head, field) \
- ((head)->th_root->field.avl_height)
-
-#define TREE_FORWARD_APPLY(head, node, field, function, data) \
- TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data)
-
-#define TREE_REVERSE_APPLY(head, node, field, function, data) \
- TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data)
-
-#define TREE_INIT(head, cmp) do { \
- (head)->th_root= 0; \
- (head)->th_cmp= (cmp); \
- } while (0)
+#define TREE_DEFINE(node, field) \
+ \
+ static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node *); \
+ \
+ static struct node *_HU_FUNCTION(TREE_ROTL_##node##_##field)(struct node * self) \
+ { \
+ struct node *r = self->field.avl_right; \
+ self->field.avl_right = r->field.avl_left; \
+ r->field.avl_left = TREE_BALANCE_##node##_##field(self); \
+ return TREE_BALANCE_##node##_##field(r); \
+ } \
+ \
+ static struct node *_HU_FUNCTION(TREE_ROTR_##node##_##field)(struct node * self) \
+ { \
+ struct node *l = self->field.avl_left; \
+ self->field.avl_left = l->field.avl_right; \
+ l->field.avl_right = TREE_BALANCE_##node##_##field(self); \
+ return TREE_BALANCE_##node##_##field(l); \
+ } \
+ \
+ static struct node *_HU_FUNCTION(TREE_BALANCE_##node##_##field)(struct node * self) \
+ { \
+ int delta = TREE_DELTA(self, field); \
+ \
+ if (delta < -TREE_DELTA_MAX) { \
+ if (TREE_DELTA(self->field.avl_right, field) > 0) \
+ self->field.avl_right = TREE_ROTR_##node##_##field(self->field.avl_right); \
+ return TREE_ROTL_##node##_##field(self); \
+ } \
+ else if (delta > TREE_DELTA_MAX) { \
+ if (TREE_DELTA(self->field.avl_left, field) < 0) \
+ self->field.avl_left = TREE_ROTL_##node##_##field(self->field.avl_left); \
+ return TREE_ROTR_##node##_##field(self); \
+ } \
+ self->field.avl_height = 0; \
+ if (self->field.avl_left && (self->field.avl_left->field.avl_height > self->field.avl_height)) \
+ self->field.avl_height = self->field.avl_left->field.avl_height; \
+ if (self->field.avl_right && (self->field.avl_right->field.avl_height > self->field.avl_height)) \
+ self->field.avl_height = self->field.avl_right->field.avl_height; \
+ self->field.avl_height += 1; \
+ return self; \
+ } \
+ \
+ static struct node *_HU_FUNCTION(TREE_INSERT_##node##_##field)(struct node * self, struct node * elm, int (*compare)(struct node * lhs, struct node * rhs)) \
+ { \
+ if (!self) \
+ return elm; \
+ if (compare(elm, self) < 0) \
+ self->field.avl_left = TREE_INSERT_##node##_##field(self->field.avl_left, elm, compare); \
+ else \
+ self->field.avl_right = TREE_INSERT_##node##_##field(self->field.avl_right, elm, compare); \
+ return TREE_BALANCE_##node##_##field(self); \
+ } \
+ \
+ static struct node *_HU_FUNCTION(TREE_FIND_##node##_##field)(struct node * self, struct node * elm, int (*compare)(struct node * lhs, struct node * rhs)) \
+ { \
+ if (!self) \
+ return 0; \
+ if (compare(elm, self) == 0) \
+ return self; \
+ if (compare(elm, self) < 0) \
+ return TREE_FIND_##node##_##field(self->field.avl_left, elm, compare); \
+ else \
+ return TREE_FIND_##node##_##field(self->field.avl_right, elm, compare); \
+ } \
+ \
+ static struct node *_HU_FUNCTION(TREE_MOVE_RIGHT)(struct node * self, struct node * rhs) \
+ { \
+ if (!self) \
+ return rhs; \
+ self->field.avl_right = TREE_MOVE_RIGHT(self->field.avl_right, rhs); \
+ return TREE_BALANCE_##node##_##field(self); \
+ } \
+ \
+ static struct node *_HU_FUNCTION(TREE_REMOVE_##node##_##field)(struct node * self, struct node * elm, int (*compare)(struct node * lhs, struct node * rhs)) \
+ { \
+ if (!self) return 0; \
+ \
+ if (compare(elm, self) == 0) { \
+ struct node *tmp = TREE_MOVE_RIGHT(self->field.avl_left, self->field.avl_right); \
+ self->field.avl_left = 0; \
+ self->field.avl_right = 0; \
+ return tmp; \
+ } \
+ if (compare(elm, self) < 0) \
+ self->field.avl_left = TREE_REMOVE_##node##_##field(self->field.avl_left, elm, compare); \
+ else \
+ self->field.avl_right = TREE_REMOVE_##node##_##field(self->field.avl_right, elm, compare); \
+ return TREE_BALANCE_##node##_##field(self); \
+ } \
+ \
+ static void _HU_FUNCTION(TREE_FORWARD_APPLY_ALL_##node##_##field)(struct node * self, void (*function)(struct node * node, void *data), void *data) \
+ { \
+ if (self) { \
+ TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \
+ function(self, data); \
+ TREE_FORWARD_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \
+ } \
+ } \
+ \
+ static void _HU_FUNCTION(TREE_REVERSE_APPLY_ALL_##node##_##field)(struct node * self, void (*function)(struct node * node, void *data), void *data) \
+ { \
+ if (self) { \
+ TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_right, function, data); \
+ function(self, data); \
+ TREE_REVERSE_APPLY_ALL_##node##_##field(self->field.avl_left, function, data); \
+ } \
+ }
+
+#define TREE_INSERT(head, node, field, elm) \
+ ((head)->th_root = TREE_INSERT_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
+
+#define TREE_FIND(head, node, field, elm) \
+ (TREE_FIND_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
+
+#define TREE_REMOVE(head, node, field, elm) \
+ ((head)->th_root = TREE_REMOVE_##node##_##field((head)->th_root, (elm), (head)->th_cmp))
+
+#define TREE_DEPTH(head, field) \
+ ((head)->th_root->field.avl_height)
+
+#define TREE_FORWARD_APPLY(head, node, field, function, data) \
+ TREE_FORWARD_APPLY_ALL_##node##_##field((head)->th_root, function, data)
+
+#define TREE_REVERSE_APPLY(head, node, field, function, data) \
+ TREE_REVERSE_APPLY_ALL_##node##_##field((head)->th_root, function, data)
+
+#define TREE_INIT(head, cmp) \
+ do { \
+ (head)->th_root = 0; \
+ (head)->th_cmp = (cmp); \
+ } while (0)
#endif /* __tree_h */
generated by cgit v1.2.3 (git 2.25.1) at 2026-01-19 11:28:16 +0000