Introduction
Introduction Statistics Contact Development Disclaimer Help
strip down tree.h remove unused code and unused macros - webdump - HTML to plai…
git clone git://git.codemadness.org/webdump
Log
Files
Refs
README
LICENSE
---
commit 589d7d1ed851b5226a4782de8c9f00001f25c599
parent c0d1a46e3d5e9d291cb731bec2f0511553d87b48
Author: Hiltjo Posthuma <[email protected]>
Date: Tue, 19 Sep 2023 20:04:01 +0200
strip down tree.h remove unused code and unused macros
... only RB_INSERT and RB_FIND are used.
Diffstat:
M tree.h | 268 +----------------------------…
1 file changed, 1 insertion(+), 267 deletions(-)
---
diff --git a/tree.h b/tree.h
@@ -114,30 +114,10 @@ struct { …
RB_PARENT(elm, field) = (tmp); \
} while (0)
-/* Generates prototypes and inline functions */
-#define RB_PROTOTYPE(name, type, field, cmp) …
- RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
-#define RB_PROTOTYPE_STATIC(name, type, field, cmp) …
- RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused_…
-#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
-attr void name##_RB_INSERT_COLOR(struct name *, struct type *); …
-attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
-attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
-attr struct type *name##_RB_INSERT(struct name *, struct type *); \
-attr struct type *name##_RB_FIND(struct name *, struct type *); …
-attr struct type *name##_RB_NFIND(struct name *, struct type *); \
-attr struct type *name##_RB_NEXT(struct type *); \
-attr struct type *name##_RB_PREV(struct type *); \
-attr struct type *name##_RB_MINMAX(struct name *, int); …
- \
-
-/* Main rb operation.
- * Moves node close to the key of elm to top
+/* Moves node close to the key of elm to top
*/
#define RB_GENERATE(name, type, field, cmp) …
RB_GENERATE_INTERNAL(name, type, field, cmp,)
-#define RB_GENERATE_STATIC(name, type, field, cmp) …
- RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__…
#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
attr void \
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
@@ -183,145 +163,6 @@ name##_RB_INSERT_COLOR(struct name *head, struct type *el…
RB_COLOR(head->rbh_root, field) = RB_BLACK; \
} \
\
-attr void \
-name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *el…
-{ \
- struct type *tmp; \
- while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
- elm != RB_ROOT(head)) { \
- if (RB_LEFT(parent, field) == elm) { \
- tmp = RB_RIGHT(parent, field); \
- if (RB_COLOR(tmp, field) == RB_RED) { \
- RB_SET_BLACKRED(tmp, parent, field); \
- RB_ROTATE_LEFT(head, parent, tmp, field);\
- tmp = RB_RIGHT(parent, field); \
- } \
- if ((RB_LEFT(tmp, field) == NULL || \
- RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) …
- (RB_RIGHT(tmp, field) == NULL || \
- RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)…
- RB_COLOR(tmp, field) = RB_RED; \
- elm = parent; \
- parent = RB_PARENT(elm, field); …
- } else { \
- if (RB_RIGHT(tmp, field) == NULL || \
- RB_COLOR(RB_RIGHT(tmp, field), field) == R…
- struct type *oleft; \
- if ((oleft = RB_LEFT(tmp, field)))\
- RB_COLOR(oleft, field) = RB_BL…
- RB_COLOR(tmp, field) = RB_RED; \
- RB_ROTATE_RIGHT(head, tmp, oleft, fiel…
- tmp = RB_RIGHT(parent, field); \
- } \
- RB_COLOR(tmp, field) = RB_COLOR(parent, field)…
- RB_COLOR(parent, field) = RB_BLACK; \
- if (RB_RIGHT(tmp, field)) \
- RB_COLOR(RB_RIGHT(tmp, field), field) …
- RB_ROTATE_LEFT(head, parent, tmp, field);\
- elm = RB_ROOT(head); \
- break; \
- } \
- } else { \
- tmp = RB_LEFT(parent, field); \
- if (RB_COLOR(tmp, field) == RB_RED) { \
- RB_SET_BLACKRED(tmp, parent, field); \
- RB_ROTATE_RIGHT(head, parent, tmp, field);\
- tmp = RB_LEFT(parent, field); \
- } \
- if ((RB_LEFT(tmp, field) == NULL || \
- RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) …
- (RB_RIGHT(tmp, field) == NULL || \
- RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)…
- RB_COLOR(tmp, field) = RB_RED; \
- elm = parent; \
- parent = RB_PARENT(elm, field); …
- } else { \
- if (RB_LEFT(tmp, field) == NULL || \
- RB_COLOR(RB_LEFT(tmp, field), field) == RB…
- struct type *oright; \
- if ((oright = RB_RIGHT(tmp, field)))\
- RB_COLOR(oright, field) = RB_B…
- RB_COLOR(tmp, field) = RB_RED; \
- RB_ROTATE_LEFT(head, tmp, oright, fiel…
- tmp = RB_LEFT(parent, field); \
- } \
- RB_COLOR(tmp, field) = RB_COLOR(parent, field)…
- RB_COLOR(parent, field) = RB_BLACK; \
- if (RB_LEFT(tmp, field)) \
- RB_COLOR(RB_LEFT(tmp, field), field) =…
- RB_ROTATE_RIGHT(head, parent, tmp, field);\
- elm = RB_ROOT(head); \
- break; \
- } \
- } \
- } \
- if (elm) \
- RB_COLOR(elm, field) = RB_BLACK; \
-} \
- \
-attr struct type * \
-name##_RB_REMOVE(struct name *head, struct type *elm) \
-{ \
- struct type *child, *parent, *old = elm; \
- int color; \
- if (RB_LEFT(elm, field) == NULL) \
- child = RB_RIGHT(elm, field); \
- else if (RB_RIGHT(elm, field) == NULL) \
- child = RB_LEFT(elm, field); \
- else { \
- struct type *left; \
- elm = RB_RIGHT(elm, field); \
- while ((left = RB_LEFT(elm, field))) \
- elm = left; \
- child = RB_RIGHT(elm, field); \
- parent = RB_PARENT(elm, field); …
- color = RB_COLOR(elm, field); \
- if (child) \
- RB_PARENT(child, field) = parent; \
- if (parent) { \
- if (RB_LEFT(parent, field) == elm) \
- RB_LEFT(parent, field) = child; …
- else \
- RB_RIGHT(parent, field) = child; \
- } else \
- RB_ROOT(head) = child; \
- if (RB_PARENT(elm, field) == old) \
- parent = elm; \
- (elm)->field = (old)->field; \
- if (RB_PARENT(old, field)) { \
- if (RB_LEFT(RB_PARENT(old, field), field) == old)\
- RB_LEFT(RB_PARENT(old, field), field) = elm;\
- else \
- RB_RIGHT(RB_PARENT(old, field), field) = elm;\
- } else \
- RB_ROOT(head) = elm; \
- RB_PARENT(RB_LEFT(old, field), field) = elm; \
- if (RB_RIGHT(old, field)) \
- RB_PARENT(RB_RIGHT(old, field), field) = elm; \
- if (parent) { \
- left = parent; \
- do { \
- } while ((left = RB_PARENT(left, field))); \
- } \
- goto color; \
- } \
- parent = RB_PARENT(elm, field); …
- color = RB_COLOR(elm, field); \
- if (child) \
- RB_PARENT(child, field) = parent; \
- if (parent) { \
- if (RB_LEFT(parent, field) == elm) \
- RB_LEFT(parent, field) = child; …
- else \
- RB_RIGHT(parent, field) = child; \
- } else \
- RB_ROOT(head) = child; \
-color: \
- if (color == RB_BLACK) \
- name##_RB_REMOVE_COLOR(head, parent, child); \
- return (old); \
-} \
- \
/* Inserts a node into the RB tree */ \
attr struct type * \
name##_RB_INSERT(struct name *head, struct type *elm) \
@@ -368,116 +209,9 @@ name##_RB_FIND(struct name *head, struct type *elm) …
return (tmp); \
} \
return (NULL); \
-} \
- \
-/* Finds the first node greater than or equal to the search key */ \
-attr struct type * \
-name##_RB_NFIND(struct name *head, struct type *elm) \
-{ \
- struct type *tmp = RB_ROOT(head); \
- struct type *res = NULL; \
- int comp; \
- while (tmp) { \
- comp = cmp(elm, tmp); \
- if (comp < 0) { …
- res = tmp; \
- tmp = RB_LEFT(tmp, field); \
- } \
- else if (comp > 0) \
- tmp = RB_RIGHT(tmp, field); \
- else \
- return (tmp); \
- } \
- return (res); \
-} \
- \
-attr struct type * \
-name##_RB_NEXT(struct type *elm) \
-{ \
- if (RB_RIGHT(elm, field)) { \
- elm = RB_RIGHT(elm, field); \
- while (RB_LEFT(elm, field)) \
- elm = RB_LEFT(elm, field); \
- } else { \
- if (RB_PARENT(elm, field) && \
- (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
- elm = RB_PARENT(elm, field); \
- else { \
- while (RB_PARENT(elm, field) && …
- (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
- elm = RB_PARENT(elm, field); \
- elm = RB_PARENT(elm, field); \
- } \
- } \
- return (elm); \
-} \
- \
-attr struct type * \
-name##_RB_PREV(struct type *elm) \
-{ \
- if (RB_LEFT(elm, field)) { \
- elm = RB_LEFT(elm, field); \
- while (RB_RIGHT(elm, field)) \
- elm = RB_RIGHT(elm, field); \
- } else { \
- if (RB_PARENT(elm, field) && \
- (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
- elm = RB_PARENT(elm, field); \
- else { \
- while (RB_PARENT(elm, field) && …
- (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
- elm = RB_PARENT(elm, field); \
- elm = RB_PARENT(elm, field); \
- } \
- } \
- return (elm); \
-} \
- \
-attr struct type * \
-name##_RB_MINMAX(struct name *head, int val) \
-{ \
- struct type *tmp = RB_ROOT(head); \
- struct type *parent = NULL; \
- while (tmp) { \
- parent = tmp; \
- if (val < 0) \
- tmp = RB_LEFT(tmp, field); \
- else \
- tmp = RB_RIGHT(tmp, field); \
- } \
- return (parent); \
}
-#define RB_NEGINF -1
-#define RB_INF 1
-
#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
-#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
-#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
-#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
-#define RB_PREV(name, x, y) name##_RB_PREV(y)
-#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
-#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
-
-#define RB_FOREACH(x, name, head) \
- for ((x) = RB_MIN(name, head); \
- (x) != NULL; \
- (x) = name##_RB_NEXT(x))
-
-#define RB_FOREACH_SAFE(x, name, head, y) \
- for ((x) = RB_MIN(name, head); \
- ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
- (x) = (y))
-
-#define RB_FOREACH_REVERSE(x, name, head) \
- for ((x) = RB_MAX(name, head); \
- (x) != NULL; \
- (x) = name##_RB_PREV(x))
-
-#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
- for ((x) = RB_MAX(name, head); \
- ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
- (x) = (y))
#endif /* TREE_H */
You are viewing proxied material from codemadness.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.