diff --git a/util/tree.h b/util/tree.h
index 80d0f53813442514d8861d9a152c34f6c7708c65..8ada42d2f9c1082b1676b652a9d9233583ef0fbf 100644 (file)
--- a/util/tree.h
+++ b/util/tree.h
* Copyright 2002 Niels Provos <provos@citi.umich.edu>
* All rights reserved.
*
+ * Copyright (C) 2013 Texas Instruments Incorporated - http://www.ti.com/
+ * ALL RIGHTS RESERVED
+ *
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* Every operation on a red-black tree is bounded as O(lg n).
* The maximum height of a red-black tree is 2lg (n+1).
*/
+/* Change Log
+ * TI - Added versions of some RB macros that handle caching
+ */
#define SPLAY_HEAD(name, type) \
struct name { \
} 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__)) static)
-#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+#define RB_PROTOTYPE(name, type, field, cmp, inv) \
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp, inv,)
+#define RB_PROTOTYPE_STATIC(name, type, field, cmp, inv) \
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp, inv, __attribute__((__unused__)) static)
+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, inv, 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_NEXT(struct type *); \
attr struct type *name##_RB_PREV(struct type *); \
attr struct type *name##_RB_MINMAX(struct name *, int); \
+attr struct type *name##_RB_NEXT_CACHED(struct type *); \
+attr struct type *name##_RB_MINMAX_CACHED(struct name *, int); \
\
/* Main rb operation.
* 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__)) static)
-#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
+#define RB_GENERATE(name, type, field, cmp, inv) \
+ RB_GENERATE_INTERNAL(name, type, field, cmp, inv,)
+#define RB_GENERATE_STATIC(name, type, field, cmp, inv) \
+ RB_GENERATE_INTERNAL(name, type, field, cmp, inv, __attribute__((__unused__)) static)
+#define RB_GENERATE_INTERNAL(name, type, field, cmp, inv, attr) \
attr void \
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
{ \
tmp = RB_RIGHT(tmp, field); \
} \
return (parent); \
-}
+} \
+ \
+/* ARGSUSED */ \
+attr struct type * \
+name##_RB_NEXT_CACHED(struct type *elm) \
+{ \
+ inv(elm); \
+ if (RB_RIGHT(elm, field)) { \
+ elm = RB_RIGHT(elm, field); \
+ inv(elm); \
+ while (RB_LEFT(elm, field)) { \
+ elm = RB_LEFT(elm, field); \
+ inv(elm); \
+ } \
+ } else { \
+ inv(RB_PARENT(elm, field)); \
+ 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); \
+ inv(RB_PARENT(elm, field)); \
+ } \
+ elm = RB_PARENT(elm, field); \
+ } \
+ } \
+ return (elm); \
+} \
+ \
+attr struct type * \
+name##_RB_MINMAX_CACHED(struct name *head, int val) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ struct type *parent = NULL; \
+ while (tmp) { \
+ parent = tmp; \
+ inv(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_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)
+/* Cache versions */
+#define RB_NEXT_CACHED(name, x, y) name##_RB_NEXT_CACHED(y)
+#define RB_MIN_CACHED(name, x) name##_RB_MINMAX_CACHED(x, RB_NEGINF)
#define RB_FOREACH(x, name, head) \
for ((x) = RB_MIN(name, head); \