Page MenuHomeFreeBSD
Files F149805343

D20324.id58596.diff
No OneTemporary
Actions

D20324.id58596.diff
View Options

Index: share/man/man3/Makefile
===================================================================
--- share/man/man3/Makefile
+++ share/man/man3/Makefile
@@ -175,7 +175,42 @@
timeradd.3 timespecclear.3 \
timeradd.3 timespecisset.3 \
timeradd.3 timespeccmp.3
-MLINKS+= tree.3 RB_EMPTY.3 \
+MLINKS+= tree.3 ARB8_ENTRY.3 \
+ tree.3 ARB16_ENTRY.3 \
+ tree.3 ARB32_ENTRY.3 \
+ tree.3 ARB8_HEAD.3 \
+ tree.3 ARB16_HEAD.3 \
+ tree.3 ARB32_HEAD.3 \
+ tree.3 ARB_INITIALIZER.3 \
+ tree.3 ARB_ROOT.3 \
+ tree.3 ARB_EMPTY.3 \
+ tree.3 ARB_FULL.3 \
+ tree.3 ARB_CURNODES.3 \
+ tree.3 ARB_MAXNODES.3 \
+ tree.3 ARB_NEXT.3 \
+ tree.3 ARB_PREV.3 \
+ tree.3 ARB_MIN.3 \
+ tree.3 ARB_MAX.3 \
+ tree.3 ARB_FIND.3 \
+ tree.3 ARB_NFIND.3 \
+ tree.3 ARB_LEFT.3 \
+ tree.3 ARB_LEFTIDX.3 \
+ tree.3 ARB_RIGHT.3 \
+ tree.3 ARB_RIGHTIDX.3 \
+ tree.3 ARB_PARENT.3 \
+ tree.3 ARB_PARENTIDX.3 \
+ tree.3 ARB_GETFREE.3 \
+ tree.3 ARB_FREEIDX.3 \
+ tree.3 ARB_FOREACH.3 \
+ tree.3 ARB_FOREACH_FROM.3 \
+ tree.3 ARB_FOREACH_SAFE.3 \
+ tree.3 ARB_FOREACH_REVERSE.3 \
+ tree.3 ARB_FOREACH_REVERSE_FROM.3 \
+ tree.3 ARB_FOREACH_REVERSE_SAFE.3 \
+ tree.3 ARB_INIT.3 \
+ tree.3 ARB_INSERT.3 \
+ tree.3 ARB_REMOVE.3 \
+ tree.3 RB_EMPTY.3 \
tree.3 RB_ENTRY.3 \
tree.3 RB_FIND.3 \
tree.3 RB_FOREACH.3 \
Index: share/man/man3/tree.3
===================================================================
--- share/man/man3/tree.3
+++ share/man/man3/tree.3
@@ -95,7 +95,64 @@
.Nm RB_FOREACH_REVERSE_SAFE ,
.Nm RB_INIT ,
.Nm RB_INSERT ,
-.Nm RB_REMOVE
+.Nm RB_REMOVE ,
+.Nm ARB_PROTOTYPE ,
+.Nm ARB_PROTOTYPE_STATIC ,
+.Nm ARB_PROTOTYPE_INSERT ,
+.Nm ARB_PROTOTYPE_INSERT_COLOR ,
+.Nm ARB_PROTOTYPE_REMOVE ,
+.Nm ARB_PROTOTYPE_REMOVE_COLOR ,
+.Nm ARB_PROTOTYPE_FIND ,
+.Nm ARB_PROTOTYPE_NFIND ,
+.Nm ARB_PROTOTYPE_NEXT ,
+.Nm ARB_PROTOTYPE_PREV ,
+.Nm ARB_PROTOTYPE_MINMAX ,
+.Nm ARB_GENERATE ,
+.Nm ARB_GENERATE_STATIC ,
+.Nm ARB_GENERATE_INSERT ,
+.Nm ARB_GENERATE_INSERT_COLOR ,
+.Nm ARB_GENERATE_REMOVE ,
+.Nm ARB_GENERATE_REMOVE_COLOR ,
+.Nm ARB_GENERATE_FIND ,
+.Nm ARB_GENERATE_NFIND ,
+.Nm ARB_GENERATE_NEXT ,
+.Nm ARB_GENERATE_PREV ,
+.Nm ARB_GENERATE_MINMAX ,
+.Nm ARB8_ENTRY ,
+.Nm ARB16_ENTRY ,
+.Nm ARB32_ENTRY ,
+.Nm ARB8_HEAD ,
+.Nm ARB16_HEAD ,
+.Nm ARB32_HEAD ,
+.Nm ARB_INITIALIZER ,
+.Nm ARB_ROOT ,
+.Nm ARB_EMPTY ,
+.Nm ARB_FULL ,
+.Nm ARB_CURNODES ,
+.Nm ARB_MAXNODES ,
+.Nm ARB_NEXT ,
+.Nm ARB_PREV ,
+.Nm ARB_MIN ,
+.Nm ARB_MAX ,
+.Nm ARB_FIND ,
+.Nm ARB_NFIND ,
+.Nm ARB_LEFT ,
+.Nm ARB_LEFTIDX ,
+.Nm ARB_RIGHT ,
+.Nm ARB_RIGHTIDX ,
+.Nm ARB_PARENT ,
+.Nm ARB_PARENTIDX ,
+.Nm ARB_GETFREE ,
+.Nm ARB_FREEIDX ,
+.Nm ARB_FOREACH ,
+.Nm ARB_FOREACH_FROM ,
+.Nm ARB_FOREACH_SAFE ,
+.Nm ARB_FOREACH_REVERSE ,
+.Nm ARB_FOREACH_REVERSE_FROM ,
+.Nm ARB_FOREACH_REVERSE_SAFE ,
+.Nm ARB_INIT ,
+.Nm ARB_INSERT ,
+.Nm ARB_REMOVE
.Nd "implementations of splay and red-black trees"
.Sh SYNOPSIS
.In sys/tree.h
@@ -127,75 +184,104 @@
.Fn SPLAY_INSERT NAME "SPLAY_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
.Fn SPLAY_REMOVE NAME "SPLAY_HEAD *head" "struct TYPE *elm"
-.Fn RB_PROTOTYPE NAME TYPE FIELD CMP
-.Fn RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
-.Fn RB_PROTOTYPE_INSERT NAME TYPE ATTR
-.Fn RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
-.Fn RB_PROTOTYPE_REMOVE NAME TYPE ATTR
-.Fn RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
-.Fn RB_PROTOTYPE_FIND NAME TYPE ATTR
-.Fn RB_PROTOTYPE_NFIND NAME TYPE ATTR
-.Fn RB_PROTOTYPE_NEXT NAME TYPE ATTR
-.Fn RB_PROTOTYPE_PREV NAME TYPE ATTR
-.Fn RB_PROTOTYPE_MINMAX NAME TYPE ATTR
-.Fn RB_GENERATE NAME TYPE FIELD CMP
-.Fn RB_GENERATE_STATIC NAME TYPE FIELD CMP
-.Fn RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
-.Fn RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
-.Fn RB_GENERATE_REMOVE NAME TYPE FIELD ATTR
-.Fn RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
-.Fn RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
-.Fn RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
-.Fn RB_GENERATE_NEXT NAME TYPE FIELD ATTR
-.Fn RB_GENERATE_PREV NAME TYPE FIELD ATTR
-.Fn RB_GENERATE_MINMAX NAME TYPE FIELD ATTR
+.Fn (A)RB_PROTOTYPE NAME TYPE FIELD CMP
+.Fn (A)RB_PROTOTYPE_STATIC NAME TYPE FIELD CMP
+.Fn (A)RB_PROTOTYPE_INSERT NAME TYPE ATTR
+.Fn (A)RB_PROTOTYPE_INSERT_COLOR NAME TYPE ATTR
+.Fn (A)RB_PROTOTYPE_REMOVE NAME TYPE ATTR
+.Fn (A)RB_PROTOTYPE_REMOVE_COLOR NAME TYPE ATTR
+.Fn (A)RB_PROTOTYPE_FIND NAME TYPE ATTR
+.Fn (A)RB_PROTOTYPE_NFIND NAME TYPE ATTR
+.Fn (A)RB_PROTOTYPE_NEXT NAME TYPE ATTR
+.Fn (A)RB_PROTOTYPE_PREV NAME TYPE ATTR
+.Fn (A)RB_PROTOTYPE_MINMAX NAME TYPE ATTR
+.Fn (A)RB_GENERATE NAME TYPE FIELD CMP
+.Fn (A)RB_GENERATE_STATIC NAME TYPE FIELD CMP
+.Fn (A)RB_GENERATE_INSERT NAME TYPE FIELD CMP ATTR
+.Fn (A)RB_GENERATE_INSERT_COLOR NAME TYPE FIELD ATTR
+.Fn (A)RB_GENERATE_REMOVE NAME TYPE FIELD ATTR
+.Fn (A)RB_GENERATE_REMOVE_COLOR NAME TYPE FIELD ATTR
+.Fn (A)RB_GENERATE_FIND NAME TYPE FIELD CMP ATTR
+.Fn (A)RB_GENERATE_NFIND NAME TYPE FIELD CMP ATTR
+.Fn (A)RB_GENERATE_NEXT NAME TYPE FIELD ATTR
+.Fn (A)RB_GENERATE_PREV NAME TYPE FIELD ATTR
+.Fn (A)RB_GENERATE_MINMAX NAME TYPE FIELD ATTR
.Fn RB_ENTRY TYPE
.Fn RB_HEAD HEADNAME TYPE
.Fn RB_INITIALIZER "RB_HEAD *head"
+.Fn ARB<8|16|32>_ENTRY
+.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
+.Fn ARB_INITIALIZER "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
.Ft "struct TYPE *"
-.Fn RB_ROOT "RB_HEAD *head"
+.Fn (A)RB_ROOT "(A)RB_HEAD *head"
.Ft "bool"
-.Fn RB_EMPTY "RB_HEAD *head"
+.Fn (A)RB_EMPTY "(A)RB_HEAD *head"
+.Ft "bool"
+.Fn ARB_FULL "ARB_HEAD *head"
+.Ft "int<8|16|32>_t"
+.Fn ARB_CURNODES "ARB_HEAD *head"
+.Ft "int<8|16|32>_t"
+.Fn ARB_MAXNODES "ARB_HEAD *head"
.Ft "struct TYPE *"
-.Fn RB_NEXT NAME "RB_HEAD *head" "struct TYPE *elm"
+.Fn (A)RB_NEXT NAME "(A)RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
-.Fn RB_PREV NAME "RB_HEAD *head" "struct TYPE *elm"
+.Fn (A)RB_PREV NAME "(A)RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
-.Fn RB_MIN NAME "RB_HEAD *head"
+.Fn (A)RB_MIN NAME "(A)RB_HEAD *head"
.Ft "struct TYPE *"
-.Fn RB_MAX NAME "RB_HEAD *head"
+.Fn (A)RB_MAX NAME "(A)RB_HEAD *head"
.Ft "struct TYPE *"
-.Fn RB_FIND NAME "RB_HEAD *head" "struct TYPE *elm"
+.Fn (A)RB_FIND NAME "(A)RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
-.Fn RB_NFIND NAME "RB_HEAD *head" "struct TYPE *elm"
+.Fn (A)RB_NFIND NAME "(A)RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
-.Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
+.Fn (A)RB_LEFT "struct TYPE *elm" "(A)RB_ENTRY NAME"
+.Ft "int<8|16|32>_t"
+.Fn ARB_LEFTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
.Ft "struct TYPE *"
-.Fn RB_RIGHT "struct TYPE *elm" "RB_ENTRY NAME"
+.Fn (A)RB_RIGHT "struct TYPE *elm" "(A)RB_ENTRY NAME"
+.Ft "int<8|16|32>_t"
+.Fn ARB_RIGHTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
.Ft "struct TYPE *"
-.Fn RB_PARENT "struct TYPE *elm" "RB_ENTRY NAME"
-.Fn RB_FOREACH VARNAME NAME "RB_HEAD *head"
-.Fn RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
-.Fn RB_FOREACH_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
-.Fn RB_FOREACH_REVERSE VARNAME NAME "RB_HEAD *head"
-.Fn RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
-.Fn RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "RB_HEAD *head" "TEMP_VARNAME"
+.Fn (A)RB_PARENT "struct TYPE *elm" "(A)RB_ENTRY NAME"
+.Ft "int<8|16|32>_t"
+.Fn ARB_PARENTIDX "struct TYPE *elm" "ARB_ENTRY NAME"
+.Ft "struct TYPE *"
+.Fn ARB_GETFREE "ARB_HEAD *head"
+.Ft "int<8|16|32>_t"
+.Fn ARB_FREEIDX "ARB_HEAD *head"
+.Fn (A)RB_FOREACH VARNAME NAME "(A)RB_HEAD *head"
+.Fn (A)RB_FOREACH_FROM "VARNAME" "NAME" "POS_VARNAME"
+.Fn (A)RB_FOREACH_SAFE "VARNAME" "NAME" "(A)RB_HEAD *head" "TEMP_VARNAME"
+.Fn (A)RB_FOREACH_REVERSE VARNAME NAME "(A)RB_HEAD *head"
+.Fn (A)RB_FOREACH_REVERSE_FROM "VARNAME" "NAME" "POS_VARNAME"
+.Fn (A)RB_FOREACH_REVERSE_SAFE "VARNAME" "NAME" "(A)RB_HEAD *head" "TEMP_VARNAME"
.Ft void
.Fn RB_INIT "RB_HEAD *head"
+.Ft void
+.Fn ARB_INIT "ARB_HEAD *head" "int<8|16|32>_t maxnodes"
.Ft "struct TYPE *"
-.Fn RB_INSERT NAME "RB_HEAD *head" "struct TYPE *elm"
+.Fn (A)RB_INSERT NAME "(A)RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
-.Fn RB_REMOVE NAME "RB_HEAD *head" "struct TYPE *elm"
+.Fn (A)RB_REMOVE NAME "(A)RB_HEAD *head" "struct TYPE *elm"
.Sh DESCRIPTION
-These macros define data structures for different types of trees:
-splay trees and red-black trees.
+These macros define data structures for three different types of trees:
+splay trees (macros with the
+.Dv SPLAY_
+prefix), red-black trees (the
+.Dv RB_
+prefix), and array-based red-black trees (the
+.Dv ARB_
+prefix).
+The last one use a single, continuous chunk of memory, and are useful
+e.g., when the tree needs to be trasferred between userspace and kernel.
.Pp
In the macro definitions,
.Fa TYPE
is the name tag of a user defined structure that must contain a field of type
.Vt SPLAY_ENTRY ,
or
-.Vt RB_ENTRY ,
+.Vt Po A Pc Ns RB_ENTRY ,
named
.Fa ENTRYNAME .
The argument
@@ -204,21 +290,21 @@
using the macros
.Fn SPLAY_HEAD ,
or
-.Fn RB_HEAD .
+.Fn (A)RB_HEAD .
The argument
.Fa NAME
has to be a unique name prefix for every tree that is defined.
.Pp
The function prototypes are declared with
.Fn SPLAY_PROTOTYPE ,
-.Fn RB_PROTOTYPE ,
+.Fn (A)RB_PROTOTYPE ,
or
-.Fn RB_PROTOTYPE_STATIC .
+.Fn (A)RB_PROTOTYPE_STATIC .
The function bodies are generated with
.Fn SPLAY_GENERATE ,
-.Fn RB_GENERATE ,
+.Fn (A)RB_GENERATE ,
or
-.Fn RB_GENERATE_STATIC .
+.Fn (A)RB_GENERATE_STATIC .
See the examples below for further explanation of how these macros are used.
.Sh SPLAY TREES
A splay tree is a self-organizing data structure.
@@ -376,15 +462,30 @@
The maximum height of a red-black tree is
.Fn 2lg "n + 1" .
.Pp
+.Fn RB_*
+variant trees link an arbitrary number of individually allocated entries
+together using memory pointers.
+.Fn ARB_*
+variant trees require entries to be allocated as an array, and uses array
+indices to link entries together.
+The maximum number of
+.Fn ARB_*
+tree entries is therefore constrained by the minimum of array size and choice of
+signed integer data type used to store array indices.
+.Pp
A red-black tree is headed by a structure defined by the
-.Fn RB_HEAD
+.Fn (A)RB_HEAD
macro.
A
-structure is declared as follows:
+structure is declared with either of the following:
.Bd -ragged -offset indent
.Fn RB_HEAD HEADNAME TYPE
.Va head ;
.Ed
+.Bd -ragged -offset indent
+.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
+.Va head ;
+.Ed
.Pp
where
.Fa HEADNAME
@@ -393,14 +494,33 @@
is the type of the elements to be inserted into the tree.
.Pp
The
-.Fn RB_ENTRY
+.Fn ARB_HEAD
+variant includes a suffix denoting the signed integer data type size
+.Pq in bits
+used to store array indices.
+For example,
+.Fn ARB_HEAD8
+creates a red-black tree head strucutre with 8-bit signed array indices capable
+of indexing up to 128 entries.
+.Pp
+The
+.Fn (A)RB_ENTRY
macro declares a structure that allows elements to be connected in the tree.
+Similarly to the
+.Fn ARB<8|16|32>_HEAD
+macro, the
+.Fn ARB_ENTRY
+variant includes a suffix denoting the signed integer data type size
+.Pq in bits
+used to store array indices.
+Entries should use the same number of bits as the tree head structure they will
+be linked into.
.Pp
In order to use the functions that manipulate the tree structure,
their prototypes need to be declared with the
-.Fn RB_PROTOTYPE
+.Fn (A)RB_PROTOTYPE
or
-.Fn RB_PROTOTYPE_STATIC
+.Fn (A)RB_PROTOTYPE_STATIC
macro,
where
.Fa NAME
@@ -412,18 +532,18 @@
The
.Fa FIELD
argument is the name of the element defined by
-.Fn RB_ENTRY .
+.Fn (A)RB_ENTRY .
Individual prototypes can be declared with
-.Fn RB_PROTOTYPE_INSERT ,
-.Fn RB_PROTOTYPE_INSERT_COLOR ,
-.Fn RB_PROTOTYPE_REMOVE ,
-.Fn RB_PROTOTYPE_REMOVE_COLOR ,
-.Fn RB_PROTOTYPE_FIND ,
-.Fn RB_PROTOTYPE_NFIND ,
-.Fn RB_PROTOTYPE_NEXT ,
-.Fn RB_PROTOTYPE_PREV ,
+.Fn (A)RB_PROTOTYPE_INSERT ,
+.Fn (A)RB_PROTOTYPE_INSERT_COLOR ,
+.Fn (A)RB_PROTOTYPE_REMOVE ,
+.Fn (A)RB_PROTOTYPE_REMOVE_COLOR ,
+.Fn (A)RB_PROTOTYPE_FIND ,
+.Fn (A)RB_PROTOTYPE_NFIND ,
+.Fn (A)RB_PROTOTYPE_NEXT ,
+.Fn (A)RB_PROTOTYPE_PREV ,
and
-.Fn RB_PROTOTYPE_MINMAX
+.Fn (A)RB_PROTOTYPE_MINMAX
in case not all functions are required.
The individual prototype macros expect
.Fa NAME ,
@@ -438,26 +558,26 @@
for static functions.
.Pp
The function bodies are generated with the
-.Fn RB_GENERATE
+.Fn (A)RB_GENERATE
or
-.Fn RB_GENERATE_STATIC
+.Fn (A)RB_GENERATE_STATIC
macro.
These macros take the same arguments as the
-.Fn RB_PROTOTYPE
+.Fn (A)RB_PROTOTYPE
and
-.Fn RB_PROTOTYPE_STATIC
+.Fn (A)RB_PROTOTYPE_STATIC
macros, but should be used only once.
As an alternative individual function bodies are generated with the
-.Fn RB_GENERATE_INSERT ,
-.Fn RB_GENERATE_INSERT_COLOR ,
-.Fn RB_GENERATE_REMOVE ,
-.Fn RB_GENERATE_REMOVE_COLOR ,
-.Fn RB_GENERATE_FIND ,
-.Fn RB_GENERATE_NFIND ,
-.Fn RB_GENERATE_NEXT ,
-.Fn RB_GENERATE_PREV ,
+.Fn (A)RB_GENERATE_INSERT ,
+.Fn (A)RB_GENERATE_INSERT_COLOR ,
+.Fn (A)RB_GENERATE_REMOVE ,
+.Fn (A)RB_GENERATE_REMOVE_COLOR ,
+.Fn (A)RB_GENERATE_FIND ,
+.Fn (A)RB_GENERATE_NFIND ,
+.Fn (A)RB_GENERATE_NEXT ,
+.Fn (A)RB_GENERATE_PREV ,
and
-.Fn RB_GENERATE_MINMAX
+.Fn (A)RB_GENERATE_MINMAX
macros.
.Pp
Finally,
@@ -475,37 +595,47 @@
function defines the order of the tree elements.
.Pp
The
-.Fn RB_INIT
+.Fn (A)RB_INIT
macro initializes the tree referenced by
-.Fa head .
+.Fa head ,
+with the
+.Fn ARB_INIT
+variant also taking the array length
+.Fa maxnodes .
.Pp
The red-black tree can also be initialized statically by using the
-.Fn RB_INITIALIZER
-macro like this:
+.Fn (A)RB_INITIALIZER
+macro like either:
.Bd -ragged -offset indent
.Fn RB_HEAD HEADNAME TYPE
.Va head
=
.Fn RB_INITIALIZER &head ;
.Ed
+.Bd -ragged -offset indent
+.Fn ARB<8|16|32>_HEAD HEADNAME TYPE
+.Va head
+=
+.Fn ARB_INITIALIZER &head maxnodes ;
+.Ed
.Pp
The
-.Fn RB_INSERT
+.Fn (A)RB_INSERT
macro inserts the new element
.Fa elm
into the tree.
.Pp
The
-.Fn RB_REMOVE
+.Fn (A)RB_REMOVE
macro removes the element
.Fa elm
from the tree pointed by
.Fa head .
.Pp
The
-.Fn RB_FIND
+.Fn (A)RB_FIND
and
-.Fn RB_NFIND
+.Fn (A)RB_NFIND
macros can be used to find a particular element in the tree.
.Bd -literal -offset indent
struct TYPE find, *res;
@@ -514,29 +644,29 @@
.Ed
.Pp
The
-.Fn RB_ROOT ,
-.Fn RB_MIN ,
-.Fn RB_MAX ,
-.Fn RB_NEXT ,
+.Fn (A)RB_ROOT ,
+.Fn (A)RB_MIN ,
+.Fn (A)RB_MAX ,
+.Fn (A)RB_NEXT ,
and
-.Fn RB_PREV
+.Fn (A)RB_PREV
macros can be used to traverse the tree:
.Pp
.Dl "for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))"
.Pp
Or, for simplicity, one can use the
-.Fn RB_FOREACH
+.Fn (A)RB_FOREACH
or
-.Fn RB_FOREACH_REVERSE
+.Fn (A)RB_FOREACH_REVERSE
macro:
.Bd -ragged -offset indent
.Fn RB_FOREACH np NAME head
.Ed
.Pp
The macros
-.Fn RB_FOREACH_SAFE
+.Fn (A)RB_FOREACH_SAFE
and
-.Fn RB_FOREACH_REVERSE_SAFE
+.Fn (A)RB_FOREACH_REVERSE_SAFE
traverse the tree referenced by head
in a forward or reverse direction respectively,
assigning each element in turn to np.
@@ -546,9 +676,9 @@
without interfering with the traversal.
.Pp
Both
-.Fn RB_FOREACH_FROM
+.Fn (A)RB_FOREACH_FROM
and
-.Fn RB_FOREACH_REVERSE_FROM
+.Fn (A)RB_FOREACH_REVERSE_FROM
may be used to continue an interrupted traversal
in a forward or reverse direction respectively.
The head pointer is not required.
@@ -557,8 +687,24 @@
and will be overwritten to provide safe traversal.
.Pp
The
-.Fn RB_EMPTY
+.Fn (A)RB_EMPTY
macro should be used to check whether a red-black tree is empty.
+.Pp
+Given that ARB trees have an intrinsic upper bound on the number of entries,
+some ARB-specific additional macros are defined.
+The
+.Fn ARB_FULL
+macro returns a boolean indicating whether the current number of tree entries
+equals the tree's maximum.
+The
+.Fn ARB_CURNODES
+and
+.Fn ARB_MAXNODES
+macros return the current and maximum number of entries respectively.
+The
+.Fn ARB_GETFREE
+macro returns a pointer to the next free entry in the array of entries, ready to
+be linked into the tree.
.Sh EXAMPLES
The following example demonstrates how to declare a red-black tree
holding integers.
@@ -658,7 +804,7 @@
.Ed
.Pp
Both
-.Fn RB_INSERT
+.Fn (A)RB_INSERT
and
.Fn SPLAY_INSERT
return
@@ -667,7 +813,7 @@
return a pointer to the element with the colliding key.
.Pp
Accordingly,
-.Fn RB_REMOVE
+.Fn (A)RB_REMOVE
and
.Fn SPLAY_REMOVE
return the pointer to the removed element otherwise they return
Index: sys/sys/tree.h
===================================================================
--- sys/sys/tree.h
+++ sys/sys/tree.h
@@ -393,7 +393,8 @@
RB_PROTOTYPE_NFIND(name, type, attr); \
RB_PROTOTYPE_NEXT(name, type, attr); \
RB_PROTOTYPE_PREV(name, type, attr); \
- RB_PROTOTYPE_MINMAX(name, type, attr);
+ RB_PROTOTYPE_MINMAX(name, type, attr); \
+ RB_PROTOTYPE_REBALANCE(name, type, attr);
#define RB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
attr void name##_RB_INSERT_COLOR(struct name *, struct type *)
#define RB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
@@ -412,6 +413,8 @@
attr struct type *name##_RB_PREV(struct type *)
#define RB_PROTOTYPE_MINMAX(name, type, attr) \
attr struct type *name##_RB_MINMAX(struct name *, int)
+#define RB_PROTOTYPE_REBALANCE(name, type, attr) \
+ attr struct type *name##_RB_REBALANCE(struct name *, struct type *)
/* Main rb operation.
* Moves node close to the key of elm to top
@@ -429,7 +432,8 @@
RB_GENERATE_NFIND(name, type, field, cmp, attr) \
RB_GENERATE_NEXT(name, type, field, attr) \
RB_GENERATE_PREV(name, type, field, attr) \
- RB_GENERATE_MINMAX(name, type, field, attr)
+ RB_GENERATE_MINMAX(name, type, field, attr) \
+ RB_GENERATE_REBALANCE(name, type, field, cmp, attr)
#define RB_GENERATE_INSERT_COLOR(name, type, field, attr) \
attr void \
@@ -758,6 +762,22 @@
return (parent); \
}
+#define RB_GENERATE_REBALANCE(name, type, field, cmp, attr) \
+attr struct type * \
+name##_RB_REBALANCE(struct name *head, struct type *elm) \
+{ \
+ struct type *cmpelm; \
+ if (((cmpelm = RB_PREV(name, head, elm)) != NULL && \
+ (cmp)(cmpelm, elm) >= 0) || \
+ ((cmpelm = RB_NEXT(name, head, elm)) != NULL && \
+ (cmp)(elm, cmpelm) >= 0)) { \
+ /* XXXLAS: Remove/insert is heavy handed. */ \
+ RB_REMOVE(name, head, elm); \
+ return (RB_INSERT(name, head, elm)); \
+ } \
+ return (NULL); \
+} \
+
#define RB_NEGINF -1
#define RB_INF 1
@@ -769,6 +789,7 @@
#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_REBALANCE(name, x, y) name##_RB_REBALANCE(x, y)
#define RB_FOREACH(x, name, head) \
for ((x) = RB_MIN(name, head); \
@@ -799,5 +820,738 @@
for ((x) = RB_MAX(name, head); \
((x) != NULL) && ((y) = name##_RB_PREV(x), (x) != NULL); \
(x) = (y))
+
+/* Array-based red-black trees. */
+
+#define ARB_NULLIDX -1
+#define ARB_NULLCOL -1
+
+#define ARB_HEAD(name, type, idxbits) \
+struct name { \
+ int##idxbits##_t arb_curnodes; \
+ int##idxbits##_t arb_maxnodes; \
+ int##idxbits##_t arb_root_idx; \
+ int##idxbits##_t arb_free_idx; \
+ int##idxbits##_t arb_min_idx; \
+ int##idxbits##_t arb_max_idx; \
+ struct type arb_nodes[]; \
+}
+#define ARB8_HEAD(name, type) ARB_HEAD(name, type, 8)
+#define ARB16_HEAD(name, type) ARB_HEAD(name, type, 16)
+#define ARB32_HEAD(name, type) ARB_HEAD(name, type, 32)
+
+#define ARB_INITIALIZER(name, maxn) \
+ ((struct name){ 0, maxn, ARB_NULLIDX, ARB_NULLIDX, \
+ ARB_NULLIDX, ARB_NULLIDX })
+
+#define ARB_INIT(x, field, head, maxn) \
+ (head)->arb_curnodes = 0; \
+ (head)->arb_maxnodes = (maxn); \
+ (head)->arb_root_idx = (head)->arb_free_idx = \
+ (head)->arb_min_idx = (head)->arb_max_idx = ARB_NULLIDX; \
+ /* The ARB_RETURNFREE() puts all entries on the free list. */ \
+ ARB_ARRFOREACH_REVWCOND(x, field, head, \
+ ARB_RETURNFREE(head, x, field))
+
+#define ARB_ENTRY(idxbits) \
+struct { \
+ int##idxbits##_t arbe_parent_idx; \
+ int##idxbits##_t arbe_left_idx; \
+ int##idxbits##_t arbe_right_idx; \
+ int8_t arbe_color; \
+}
+#define ARB8_ENTRY() ARB_ENTRY(8)
+#define ARB16_ENTRY() ARB_ENTRY(16)
+#define ARB32_ENTRY() ARB_ENTRY(32)
+
+#define ARB_ENTRYINIT(elm, field) do { \
+ (elm)->field.arbe_parent_idx = \
+ (elm)->field.arbe_left_idx = \
+ (elm)->field.arbe_right_idx = ARB_NULLIDX; \
+ (elm)->field.arbe_color = ARB_NULLCOL; \
+} while (/*CONSTCOND*/ 0)
+
+#define ARB_ELMTYPE(head) __typeof(&(head)->arb_nodes[0])
+#define ARB_NODES(head) (head)->arb_nodes
+#define ARB_MAXNODES(head) (head)->arb_maxnodes
+#define ARB_CURNODES(head) (head)->arb_curnodes
+#define ARB_EMPTY(head) ((head)->arb_curnodes == 0)
+#define ARB_FULL(head) ((head)->arb_curnodes >= (head)->arb_maxnodes)
+#define ARB_CNODE(head, idx) \
+ ((((intptr_t)(idx) <= ARB_NULLIDX) || ((idx) >= ARB_MAXNODES(head))) ? \
+ NULL : ((const ARB_ELMTYPE(head))(ARB_NODES(head) + (idx))))
+#define ARB_NODE(head, idx) \
+ (__DECONST(ARB_ELMTYPE(head), ARB_CNODE(head, idx)))
+#define ARB_ROOT(head) ARB_NODE(head, ARB_ROOTIDX(head))
+#define ARB_LEFT(head, elm, field) ARB_NODE(head, ARB_LEFTIDX(elm, field))
+#define ARB_RIGHT(head, elm, field) ARB_NODE(head, ARB_RIGHTIDX(elm, field))
+#define ARB_PARENT(head, elm, field) ARB_NODE(head, ARB_PARENTIDX(elm, field))
+#define ARB_FREEIDX(head) (head)->arb_free_idx
+#define ARB_ROOTIDX(head) (head)->arb_root_idx
+#define ARB_MINIDX(head) (head)->arb_min_idx
+#define ARB_MAXIDX(head) (head)->arb_max_idx
+#define ARB_SELFIDX(head, elm) \
+ ((elm) ? ((intptr_t)((((const uint8_t *)(elm)) - \
+ ((const uint8_t *)ARB_NODES(head))) / sizeof(*(elm)))) : \
+ (intptr_t)ARB_NULLIDX)
+#define ARB_LEFTIDX(elm, field) (elm)->field.arbe_left_idx
+#define ARB_RIGHTIDX(elm, field) (elm)->field.arbe_right_idx
+#define ARB_PARENTIDX(elm, field) (elm)->field.arbe_parent_idx
+#define ARB_COLOR(elm, field) (elm)->field.arbe_color
+#define ARB_PREVFREE(head, elm, field) \
+ ARB_NODE(head, ARB_PREVFREEIDX(elm, field))
+#define ARB_PREVFREEIDX(elm, field) ARB_LEFTIDX(elm, field)
+#define ARB_NEXTFREE(head, elm, field) \
+ ARB_NODE(head, ARB_NEXTFREEIDX(elm, field))
+#define ARB_NEXTFREEIDX(elm, field) ARB_RIGHTIDX(elm, field)
+#define ARB_ISFREE(elm, field) (ARB_COLOR(elm, field) == ARB_NULLCOL)
+
+#define ARB_SET(head, elm, parent, field) do { \
+ ARB_PARENTIDX(elm, field) = \
+ parent ? ARB_SELFIDX(head, parent) : ARB_NULLIDX; \
+ ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(elm, field) = ARB_NULLIDX; \
+ ARB_COLOR(elm, field) = RB_RED; \
+} while (/*CONSTCOND*/ 0)
+
+#define ARB_SET_BLACKRED(black, red, field) do { \
+ ARB_COLOR(black, field) = RB_BLACK; \
+ ARB_COLOR(red, field) = RB_RED; \
+} while (/*CONSTCOND*/ 0)
+
+#ifndef ARB_AUGMENT
+#define ARB_AUGMENT(x) do {} while (0)
+#endif
+
+#define ARB_ROTATE_LEFT(head, elm, tmp, field) do { \
+ __typeof(ARB_RIGHTIDX(elm, field)) _tmpidx; \
+ (tmp) = ARB_RIGHT(head, elm, field); \
+ _tmpidx = ARB_RIGHTIDX(elm, field); \
+ ARB_RIGHTIDX(elm, field) = ARB_LEFTIDX(tmp, field); \
+ if (ARB_RIGHTIDX(elm, field) != ARB_NULLIDX) { \
+ ARB_PARENTIDX(ARB_LEFT(head, tmp, field), field) = \
+ ARB_SELFIDX(head, elm); \
+ } \
+ ARB_AUGMENT(elm); \
+ ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \
+ if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \
+ if (ARB_SELFIDX(head, elm) == \
+ ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \
+ ARB_LEFTIDX(ARB_PARENT(head, elm, field), \
+ field) = _tmpidx; \
+ else \
+ ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \
+ field) = _tmpidx; \
+ } else \
+ ARB_ROOTIDX(head) = _tmpidx; \
+ ARB_LEFTIDX(tmp, field) = ARB_SELFIDX(head, elm); \
+ ARB_PARENTIDX(elm, field) = _tmpidx; \
+ ARB_AUGMENT(tmp); \
+ if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \
+ ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \
+} while (/*CONSTCOND*/ 0)
+
+#define ARB_ROTATE_RIGHT(head, elm, tmp, field) do { \
+ __typeof(ARB_LEFTIDX(elm, field)) _tmpidx; \
+ (tmp) = ARB_LEFT(head, elm, field); \
+ _tmpidx = ARB_LEFTIDX(elm, field); \
+ ARB_LEFTIDX(elm, field) = ARB_RIGHTIDX(tmp, field); \
+ if (ARB_LEFTIDX(elm, field) != ARB_NULLIDX) { \
+ ARB_PARENTIDX(ARB_RIGHT(head, tmp, field), field) = \
+ ARB_SELFIDX(head, elm); \
+ } \
+ ARB_AUGMENT(elm); \
+ ARB_PARENTIDX(tmp, field) = ARB_PARENTIDX(elm, field); \
+ if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) { \
+ if (ARB_SELFIDX(head, elm) == \
+ ARB_LEFTIDX(ARB_PARENT(head, elm, field), field)) \
+ ARB_LEFTIDX(ARB_PARENT(head, elm, field), \
+ field) = _tmpidx; \
+ else \
+ ARB_RIGHTIDX(ARB_PARENT(head, elm, field), \
+ field) = _tmpidx; \
+ } else \
+ ARB_ROOTIDX(head) = _tmpidx; \
+ ARB_RIGHTIDX(tmp, field) = ARB_SELFIDX(head, elm); \
+ ARB_PARENTIDX(elm, field) = _tmpidx; \
+ ARB_AUGMENT(tmp); \
+ if (ARB_PARENTIDX(tmp, field) != ARB_NULLIDX) \
+ ARB_AUGMENT(ARB_PARENT(head, tmp, field)); \
+} while (/*CONSTCOND*/ 0)
+
+#define ARB_RETURNFREE(head, elm, field) \
+({ \
+ ARB_COLOR(elm, field) = ARB_NULLCOL; \
+ ARB_NEXTFREEIDX(elm, field) = ARB_FREEIDX(head); \
+ ARB_FREEIDX(head) = ARB_SELFIDX(head, elm); \
+ elm; \
+})
+
+#define ARB_GETFREEAT(head, field, fidx) \
+({ \
+ __typeof(ARB_NODE(head, 0)) _elm, _prevelm; \
+ int _idx = fidx; \
+ if (ARB_FREEIDX(head) == ARB_NULLIDX && !ARB_FULL(head)) { \
+ /* Populate the free list. */ \
+ ARB_ARRFOREACH_REVERSE(_elm, field, head) { \
+ if (ARB_ISFREE(_elm, field)) \
+ ARB_RETURNFREE(head, _elm, field); \
+ } \
+ } \
+ _elm = _prevelm = ARB_NODE(head, ARB_FREEIDX(head)); \
+ for (; _idx > 0 && _elm != NULL; _idx--, _prevelm = _elm) \
+ _elm = ARB_NODE(head, ARB_NEXTFREEIDX(_elm, field)); \
+ if (_elm) { \
+ if (fidx == 0) \
+ ARB_FREEIDX(head) = \
+ ARB_NEXTFREEIDX(_elm, field); \
+ else \
+ ARB_NEXTFREEIDX(_prevelm, field) = \
+ ARB_NEXTFREEIDX(_elm, field); \
+ } \
+ _elm; \
+})
+#define ARB_GETFREE(head, field) ARB_GETFREEAT(head, field, 0)
+
+/* Generates prototypes and inline functions */
+#define ARB_PROTOTYPE(name, type, field, cmp) \
+ ARB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define ARB_PROTOTYPE_STATIC(name, type, field, cmp) \
+ ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, __unused static)
+#define ARB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+ ARB_PROTOTYPE_INSERT_COLOR(name, type, attr); \
+ ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
+ ARB_PROTOTYPE_INSERT(name, type, attr); \
+ ARB_PROTOTYPE_REMOVE(name, type, attr); \
+ ARB_PROTOTYPE_CFIND(name, type, attr); \
+ ARB_PROTOTYPE_FIND(name, type, attr); \
+ ARB_PROTOTYPE_NFIND(name, type, attr); \
+ ARB_PROTOTYPE_CNEXT(name, type, attr); \
+ ARB_PROTOTYPE_NEXT(name, type, attr); \
+ ARB_PROTOTYPE_CPREV(name, type, attr); \
+ ARB_PROTOTYPE_PREV(name, type, attr); \
+ ARB_PROTOTYPE_CMINMAX(name, type, attr); \
+ ARB_PROTOTYPE_MINMAX(name, type, attr); \
+ ARB_PROTOTYPE_REBALANCE(name, type, attr);
+#define ARB_PROTOTYPE_INSERT_COLOR(name, type, attr) \
+ attr void name##_ARB_INSERT_COLOR(struct name *, struct type *)
+#define ARB_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
+ attr void name##_ARB_REMOVE_COLOR(struct name *, struct type *, struct type *)
+#define ARB_PROTOTYPE_REMOVE(name, type, attr) \
+ attr struct type *name##_ARB_REMOVE(struct name *, struct type *)
+#define ARB_PROTOTYPE_INSERT(name, type, attr) \
+ attr struct type *name##_ARB_INSERT(struct name *, struct type *)
+#define ARB_PROTOTYPE_CFIND(name, type, attr) \
+ attr const struct type *name##_ARB_CFIND(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_FIND(name, type, attr) \
+ attr struct type *name##_ARB_FIND(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_NFIND(name, type, attr) \
+ attr struct type *name##_ARB_NFIND(struct name *, struct type *)
+#define ARB_PROTOTYPE_CNFIND(name, type, attr) \
+ attr const struct type *name##_ARB_CNFIND(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_CNEXT(name, type, attr) \
+ attr const struct type *name##_ARB_CNEXT(const struct name *head,\
+ const struct type *)
+#define ARB_PROTOTYPE_NEXT(name, type, attr) \
+ attr struct type *name##_ARB_NEXT(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_CPREV(name, type, attr) \
+ attr const struct type *name##_ARB_CPREV(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_PREV(name, type, attr) \
+ attr struct type *name##_ARB_PREV(const struct name *, \
+ const struct type *)
+#define ARB_PROTOTYPE_CMINMAX(name, type, attr) \
+ attr const struct type *name##_ARB_CMINMAX(const struct name *, int)
+#define ARB_PROTOTYPE_MINMAX(name, type, attr) \
+ attr struct type *name##_ARB_MINMAX(const struct name *, int)
+#define ARB_PROTOTYPE_REBALANCE(name, type, attr) \
+ attr struct type *name##_ARB_REBALANCE(struct name *, struct type *)
+
+#define ARB_GENERATE(name, type, field, cmp) \
+ ARB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define ARB_GENERATE_STATIC(name, type, field, cmp) \
+ ARB_GENERATE_INTERNAL(name, type, field, cmp, __unused static)
+#define ARB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
+ ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+ ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
+ ARB_GENERATE_INSERT(name, type, field, cmp, attr) \
+ ARB_GENERATE_REMOVE(name, type, field, attr) \
+ ARB_GENERATE_CFIND(name, type, field, cmp, attr) \
+ ARB_GENERATE_FIND(name, type, field, cmp, attr) \
+ ARB_GENERATE_CNEXT(name, type, field, attr) \
+ ARB_GENERATE_NEXT(name, type, field, attr) \
+ ARB_GENERATE_CPREV(name, type, field, attr) \
+ ARB_GENERATE_PREV(name, type, field, attr) \
+ ARB_GENERATE_CMINMAX(name, type, field, attr) \
+ ARB_GENERATE_MINMAX(name, type, field, attr) \
+ ARB_GENERATE_REBALANCE(name, type, field, cmp, attr)
+
+#define ARB_GENERATE_INSERT_COLOR(name, type, field, attr) \
+attr void \
+name##_ARB_INSERT_COLOR(struct name *head, struct type *elm) \
+{ \
+ struct type *parent, *gparent, *tmp; \
+ while ((parent = ARB_PARENT(head, elm, field)) != NULL && \
+ ARB_COLOR(parent, field) == RB_RED) { \
+ gparent = ARB_PARENT(head, parent, field); \
+ if (parent == ARB_LEFT(head, gparent, field)) { \
+ tmp = ARB_RIGHT(head, gparent, field); \
+ if (tmp && ARB_COLOR(tmp, field) == RB_RED) { \
+ ARB_COLOR(tmp, field) = RB_BLACK; \
+ ARB_SET_BLACKRED(parent, gparent, field); \
+ elm = gparent; \
+ continue; \
+ } \
+ if (ARB_RIGHT(head, parent, field) == elm) { \
+ ARB_ROTATE_LEFT(head, parent, tmp, field); \
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ ARB_SET_BLACKRED(parent, gparent, field); \
+ ARB_ROTATE_RIGHT(head, gparent, tmp, field); \
+ } else { \
+ tmp = ARB_LEFT(head, gparent, field); \
+ if (tmp && ARB_COLOR(tmp, field) == RB_RED) { \
+ ARB_COLOR(tmp, field) = RB_BLACK; \
+ ARB_SET_BLACKRED(parent, gparent, field); \
+ elm = gparent; \
+ continue; \
+ } \
+ if (ARB_LEFT(head, parent, field) == elm) { \
+ ARB_ROTATE_RIGHT(head, parent, tmp, field); \
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ ARB_SET_BLACKRED(parent, gparent, field); \
+ ARB_ROTATE_LEFT(head, gparent, tmp, field); \
+ } \
+ } \
+ ARB_COLOR(ARB_ROOT(head), field) = RB_BLACK; \
+}
+
+#define ARB_GENERATE_REMOVE_COLOR(name, type, field, attr) \
+attr void \
+name##_ARB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+{ \
+ struct type *tmp; \
+ while ((elm == NULL || ARB_COLOR(elm, field) == RB_BLACK) && \
+ elm != ARB_ROOT(head)) { \
+ if (ARB_LEFT(head, parent, field) == elm) { \
+ tmp = ARB_RIGHT(head, parent, field); \
+ if (ARB_COLOR(tmp, field) == RB_RED) { \
+ ARB_SET_BLACKRED(tmp, parent, field); \
+ ARB_ROTATE_LEFT(head, parent, tmp, field); \
+ tmp = ARB_RIGHT(head, parent, field); \
+ } \
+ if ((ARB_LEFT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_LEFT(head, tmp, field), field) == RB_BLACK) && \
+ (ARB_RIGHT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == RB_BLACK)) { \
+ ARB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = ARB_PARENT(head, elm, field); \
+ } else { \
+ if (ARB_RIGHT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == RB_BLACK) { \
+ struct type *oleft; \
+ if ((oleft = ARB_LEFT(head, tmp, field)) \
+ != NULL) \
+ ARB_COLOR(oleft, field) = RB_BLACK; \
+ ARB_COLOR(tmp, field) = RB_RED; \
+ ARB_ROTATE_RIGHT(head, tmp, oleft, field); \
+ tmp = ARB_RIGHT(head, parent, field); \
+ } \
+ ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
+ ARB_COLOR(parent, field) = RB_BLACK; \
+ if (ARB_RIGHT(head, tmp, field)) \
+ ARB_COLOR(ARB_RIGHT(head, tmp, field), field) = RB_BLACK; \
+ ARB_ROTATE_LEFT(head, parent, tmp, field); \
+ elm = ARB_ROOT(head); \
+ break; \
+ } \
+ } else { \
+ tmp = ARB_LEFT(head, parent, field); \
+ if (ARB_COLOR(tmp, field) == RB_RED) { \
+ ARB_SET_BLACKRED(tmp, parent, field); \
+ ARB_ROTATE_RIGHT(head, parent, tmp, field); \
+ tmp = ARB_LEFT(head, parent, field); \
+ } \
+ if ((ARB_LEFT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_LEFT(head, tmp, field), field) == RB_BLACK) && \
+ (ARB_RIGHT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_RIGHT(head, tmp, field), field) == RB_BLACK)) { \
+ ARB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = ARB_PARENT(head, elm, field); \
+ } else { \
+ if (ARB_LEFT(head, tmp, field) == NULL || \
+ ARB_COLOR(ARB_LEFT(head, tmp, field), field) == RB_BLACK) { \
+ struct type *oright; \
+ if ((oright = ARB_RIGHT(head, tmp, field)) \
+ != NULL) \
+ ARB_COLOR(oright, field) = RB_BLACK; \
+ ARB_COLOR(tmp, field) = RB_RED; \
+ ARB_ROTATE_LEFT(head, tmp, oright, field); \
+ tmp = ARB_LEFT(head, parent, field); \
+ } \
+ ARB_COLOR(tmp, field) = ARB_COLOR(parent, field); \
+ ARB_COLOR(parent, field) = RB_BLACK; \
+ if (ARB_LEFT(head, tmp, field)) \
+ ARB_COLOR(ARB_LEFT(head, tmp, field), field) = RB_BLACK; \
+ ARB_ROTATE_RIGHT(head, parent, tmp, field); \
+ elm = ARB_ROOT(head); \
+ break; \
+ } \
+ } \
+ } \
+ if (elm) \
+ ARB_COLOR(elm, field) = RB_BLACK; \
+}
+
+#define ARB_GENERATE_REMOVE(name, type, field, attr) \
+attr struct type * \
+name##_ARB_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *child, *parent, *old = elm; \
+ int color; \
+ if (ARB_LEFT(head, elm, field) == NULL) \
+ child = ARB_RIGHT(head, elm, field); \
+ else if (ARB_RIGHT(head, elm, field) == NULL) \
+ child = ARB_LEFT(head, elm, field); \
+ else { \
+ struct type *left; \
+ elm = ARB_RIGHT(head, elm, field); \
+ while ((left = ARB_LEFT(head, elm, field)) != NULL) \
+ elm = left; \
+ child = ARB_RIGHT(head, elm, field); \
+ parent = ARB_PARENT(head, elm, field); \
+ color = ARB_COLOR(elm, field); \
+ if (child) \
+ ARB_PARENTIDX(child, field) = \
+ ARB_SELFIDX(head, parent); \
+ if (parent) { \
+ if (ARB_LEFT(head, parent, field) == elm) \
+ ARB_LEFTIDX(parent, field) = \
+ ARB_SELFIDX(head, child); \
+ else \
+ ARB_RIGHTIDX(parent, field) = \
+ ARB_SELFIDX(head, child); \
+ ARB_AUGMENT(parent); \
+ } else \
+ ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \
+ if (ARB_PARENT(head, elm, field) == old) \
+ parent = elm; \
+ (elm)->field = (old)->field; \
+ if (ARB_PARENT(head, old, field)) { \
+ if (ARB_LEFT(head, ARB_PARENT(head, old, field), \
+ field) == old) \
+ ARB_LEFTIDX(ARB_PARENT(head, old, field), \
+ field) = ARB_SELFIDX(head, elm); \
+ else \
+ ARB_RIGHTIDX(ARB_PARENT(head, old, field),\
+ field) = ARB_SELFIDX(head, elm); \
+ ARB_AUGMENT(ARB_PARENT(head, old, field)); \
+ } else \
+ ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \
+ ARB_PARENTIDX(ARB_LEFT(head, old, field), field) = \
+ ARB_SELFIDX(head, elm); \
+ if (ARB_RIGHT(head, old, field)) \
+ ARB_PARENTIDX(ARB_RIGHT(head, old, field), \
+ field) = ARB_SELFIDX(head, elm); \
+ if (parent) { \
+ left = parent; \
+ do { \
+ RB_AUGMENT(left); \
+ } while ((left = ARB_PARENT(head, left, field)) \
+ != NULL); \
+ } \
+ goto color; \
+ } \
+ parent = ARB_PARENT(head, elm, field); \
+ color = ARB_COLOR(elm, field); \
+ if (child) \
+ ARB_PARENTIDX(child, field) = ARB_SELFIDX(head, parent);\
+ if (parent) { \
+ if (ARB_LEFT(head, parent, field) == elm) \
+ ARB_LEFTIDX(parent, field) = \
+ ARB_SELFIDX(head, child); \
+ else \
+ ARB_RIGHTIDX(parent, field) = \
+ ARB_SELFIDX(head, child); \
+ ARB_AUGMENT(parent); \
+ } else \
+ ARB_ROOTIDX(head) = ARB_SELFIDX(head, child); \
+color: \
+ if (color == RB_BLACK) \
+ name##_ARB_REMOVE_COLOR(head, parent, child); \
+ ARB_CURNODES(head) -= 1; \
+ if (ARB_MINIDX(head) == ARB_SELFIDX(head, old)) \
+ ARB_MINIDX(head) = ARB_PARENTIDX(old, field); \
+ if (ARB_MAXIDX(head) == ARB_SELFIDX(head, old)) \
+ ARB_MAXIDX(head) = ARB_PARENTIDX(old, field); \
+ ARB_RETURNFREE(head, old, field); \
+ return (old); \
+} \
+
+#define ARB_GENERATE_INSERT(name, type, field, cmp, attr) \
+/* Inserts a node into the RB tree */ \
+attr struct type * \
+name##_ARB_INSERT(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp; \
+ struct type *parent = NULL; \
+ int comp = 0; \
+ tmp = ARB_ROOT(head); \
+ while (tmp) { \
+ parent = tmp; \
+ comp = (cmp)(elm, parent); \
+ if (comp < 0) \
+ tmp = ARB_LEFT(head, tmp, field); \
+ else if (comp > 0) \
+ tmp = ARB_RIGHT(head, tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ ARB_SET(head, elm, parent, field); \
+ if (parent != NULL) { \
+ if (comp < 0) \
+ ARB_LEFTIDX(parent, field) = \
+ ARB_SELFIDX(head, elm); \
+ else \
+ ARB_RIGHTIDX(parent, field) = \
+ ARB_SELFIDX(head, elm); \
+ ARB_AUGMENT(parent); \
+ } else \
+ ARB_ROOTIDX(head) = ARB_SELFIDX(head, elm); \
+ name##_ARB_INSERT_COLOR(head, elm); \
+ ARB_CURNODES(head) += 1; \
+ if (ARB_MINIDX(head) == ARB_NULLIDX || \
+ (ARB_PARENTIDX(elm, field) == ARB_MINIDX(head) && \
+ ARB_LEFTIDX(parent, field) == ARB_SELFIDX(head, elm))) \
+ ARB_MINIDX(head) = ARB_SELFIDX(head, elm); \
+ if (ARB_MAXIDX(head) == ARB_NULLIDX || \
+ (ARB_PARENTIDX(elm, field) == ARB_MAXIDX(head) && \
+ ARB_RIGHTIDX(parent, field) == ARB_SELFIDX(head, elm))) \
+ ARB_MAXIDX(head) = ARB_SELFIDX(head, elm); \
+ return (NULL); \
+}
+
+#define ARB_GENERATE_CFIND(name, type, field, cmp, attr) \
+/* Finds the node with the same key as elm */ \
+attr const struct type * \
+name##_ARB_CFIND(const struct name *head, const struct type *elm) \
+{ \
+ const struct type *tmp = ARB_ROOT(head); \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) \
+ tmp = ARB_LEFT(head, tmp, field); \
+ else if (comp > 0) \
+ tmp = ARB_RIGHT(head, tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (NULL); \
+}
+
+#define ARB_GENERATE_FIND(name, type, field, cmp, attr) \
+attr struct type * \
+name##_ARB_FIND(const struct name *head, const struct type *elm) \
+{ return (__DECONST(struct type *, name##_ARB_CFIND(head, elm))); }
+
+#define ARB_GENERATE_CNFIND(name, type, field, cmp, attr) \
+/* Finds the first node greater than or equal to the search key */ \
+attr const struct type * \
+name##_ARB_CNFIND(const struct name *head, const struct type *elm) \
+{ \
+ const struct type *tmp = ARB_ROOT(head); \
+ const struct type *res = NULL; \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) { \
+ res = tmp; \
+ tmp = ARB_LEFT(head, tmp, field); \
+ } \
+ else if (comp > 0) \
+ tmp = ARB_RIGHT(head, tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (res); \
+}
+
+#define ARB_GENERATE_NFIND(name, type, field, cmp, attr) \
+attr struct type * \
+name##_ARB_NFIND(const struct name *head, const struct type *elm) \
+{ return (__DECONST(struct type *, name##_ARB_CNFIND(head, elm))); }
+
+#define ARB_GENERATE_CNEXT(name, type, field, attr) \
+/* ARGSUSED */ \
+attr const struct type * \
+name##_ARB_CNEXT(const struct name *head, const struct type *elm) \
+{ \
+ if (ARB_RIGHT(head, elm, field)) { \
+ elm = ARB_RIGHT(head, elm, field); \
+ while (ARB_LEFT(head, elm, field)) \
+ elm = ARB_LEFT(head, elm, field); \
+ } else { \
+ if (ARB_PARENT(head, elm, field) && \
+ (elm == ARB_LEFT(head, ARB_PARENT(head, elm, field),\
+ field))) \
+ elm = ARB_PARENT(head, elm, field); \
+ else { \
+ while (ARB_PARENT(head, elm, field) && \
+ (elm == ARB_RIGHT(head, ARB_PARENT(head, \
+ elm, field), field))) \
+ elm = ARB_PARENT(head, elm, field); \
+ elm = ARB_PARENT(head, elm, field); \
+ } \
+ } \
+ return (elm); \
+}
+
+#define ARB_GENERATE_NEXT(name, type, field, attr) \
+attr struct type * \
+name##_ARB_NEXT(const struct name *head, const struct type *elm) \
+{ return (__DECONST(struct type *, name##_ARB_CNEXT(head, elm))); }
+
+#define ARB_GENERATE_CPREV(name, type, field, attr) \
+/* ARGSUSED */ \
+attr const struct type * \
+name##_ARB_CPREV(const struct name *head, const struct type *elm) \
+{ \
+ if (ARB_LEFT(head, elm, field)) { \
+ elm = ARB_LEFT(head, elm, field); \
+ while (ARB_RIGHT(head, elm, field)) \
+ elm = ARB_RIGHT(head, elm, field); \
+ } else { \
+ if (ARB_PARENT(head, elm, field) && \
+ (elm == ARB_RIGHT(head, ARB_PARENT(head, elm, \
+ field), field))) \
+ elm = ARB_PARENT(head, elm, field); \
+ else { \
+ while (ARB_PARENT(head, elm, field) && \
+ (elm == ARB_LEFT(head, ARB_PARENT(head, elm,\
+ field), field))) \
+ elm = ARB_PARENT(head, elm, field); \
+ elm = ARB_PARENT(head, elm, field); \
+ } \
+ } \
+ return (elm); \
+}
+
+#define ARB_GENERATE_PREV(name, type, field, attr) \
+attr struct type * \
+name##_ARB_PREV(const struct name *head, const struct type *elm) \
+{ return (__DECONST(struct type *, name##_ARB_CPREV(head, elm))); }
+
+#define ARB_GENERATE_CMINMAX(name, type, field, attr) \
+attr const struct type * \
+name##_ARB_CMINMAX(const struct name *head, int val) \
+{ \
+ const struct type *tmp = ARB_EMPTY(head) ? NULL : ARB_ROOT(head);\
+ const struct type *parent = NULL; \
+ while (tmp) { \
+ parent = tmp; \
+ if (val < 0) \
+ tmp = ARB_LEFT(head, tmp, field); \
+ else \
+ tmp = ARB_RIGHT(head, tmp, field); \
+ } \
+ return (__DECONST(struct type *, parent)); \
+}
+
+#define ARB_GENERATE_MINMAX(name, type, field, attr) \
+attr struct type * \
+name##_ARB_MINMAX(const struct name *head, int val) \
+{ return (__DECONST(struct type *, name##_ARB_CMINMAX(head, val))); }
+
+#define ARB_GENERATE_REBALANCE(name, type, field, cmp, attr) \
+attr struct type * \
+name##_ARB_REBALANCE(struct name *head, struct type *elm) \
+{ \
+ struct type *cmpelm; \
+ if (((cmpelm = ARB_PREV(name, head, elm)) != NULL && \
+ (cmp)(cmpelm, elm) >= 0) || \
+ ((cmpelm = ARB_NEXT(name, head, elm)) != NULL && \
+ (cmp)(elm, cmpelm) >= 0)) { \
+ /* XXXLAS: Remove/insert is heavy handed. */ \
+ ARB_REMOVE(name, head, elm); \
+ /* Remove puts elm on the free list. */ \
+ elm = ARB_GETFREE(head, field); \
+ return (ARB_INSERT(name, head, elm)); \
+ } \
+ return (NULL); \
+} \
+
+#define ARB_INSERT(name, x, y) name##_ARB_INSERT(x, y)
+#define ARB_REMOVE(name, x, y) name##_ARB_REMOVE(x, y)
+#define ARB_CFIND(name, x, y) name##_ARB_CFIND(x, y)
+#define ARB_FIND(name, x, y) name##_ARB_FIND(x, y)
+#define ARB_CNFIND(name, x, y) name##_ARB_CNFIND(x, y)
+#define ARB_NFIND(name, x, y) name##_ARB_NFIND(x, y)
+#define ARB_CNEXT(name, x, y) name##_ARB_CNEXT(x, y)
+#define ARB_NEXT(name, x, y) name##_ARB_NEXT(x, y)
+#define ARB_CPREV(name, x, y) name##_ARB_CPREV(x, y)
+#define ARB_PREV(name, x, y) name##_ARB_PREV(x, y)
+#define ARB_CMIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \
+ name##_ARB_CMINMAX(x, RB_NEGINF) : ARB_CNODE(x, ARB_MINIDX(x)))
+#define ARB_MIN(name, x) (ARB_MINIDX(x) == ARB_NULLIDX ? \
+ name##_ARB_MINMAX(x, RB_NEGINF) : ARB_NODE(x, ARB_MINIDX(x)))
+#define ARB_CMAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \
+ name##_ARB_CMINMAX(x, RB_INF) : ARB_CNODE(x, ARB_MAXIDX(x)))
+#define ARB_MAX(name, x) (ARB_MAXIDX(x) == ARB_NULLIDX ? \
+ name##_ARB_MINMAX(x, RB_INF) : ARB_NODE(x, ARB_MAXIDX(x)))
+#define ARB_REBALANCE(name, x, y) name##_ARB_REBALANCE(x, y)
+
+#define ARB_FOREACH(x, name, head) \
+ for ((x) = ARB_MIN(name, head); \
+ (x) != NULL; \
+ (x) = name##_ARB_NEXT(head, x))
+
+#define ARB_FOREACH_FROM(x, name, y) \
+ for ((x) = (y); \
+ ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \
+ (x) = (y))
+
+#define ARB_FOREACH_SAFE(x, name, head, y) \
+ for ((x) = ARB_MIN(name, head); \
+ ((x) != NULL) && ((y) = name##_ARB_NEXT(x), (x) != NULL); \
+ (x) = (y))
+
+#define ARB_FOREACH_REVERSE(x, name, head) \
+ for ((x) = ARB_MAX(name, head); \
+ (x) != NULL; \
+ (x) = name##_ARB_PREV(x))
+
+#define ARB_FOREACH_REVERSE_FROM(x, name, y) \
+ for ((x) = (y); \
+ ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \
+ (x) = (y))
+
+#define ARB_FOREACH_REVERSE_SAFE(x, name, head, y) \
+ for ((x) = ARB_MAX(name, head); \
+ ((x) != NULL) && ((y) = name##_ARB_PREV(x), (x) != NULL); \
+ (x) = (y))
+
+#define ARB_ARRFOREACH(x, field, head) \
+ for ((x) = ARB_NODES(head); \
+ ARB_SELFIDX(head, x) < ARB_MAXNODES(head); \
+ (x)++)
+
+#define ARB_ARRFOREACH_REVWCOND(x, field, head, extracond) \
+ for ((x) = ARB_NODES(head) + (ARB_MAXNODES(head) - 1); \
+ (x) >= ARB_NODES(head) && (extracond); \
+ (x)--)
+
+#define ARB_ARRFOREACH_REVERSE(x, field, head) \
+ ARB_ARRFOREACH_REVWCOND(x, field, head, 1)
#endif /* _SYS_TREE_H_ */
Index: tests/sys/sys/Makefile
===================================================================
--- tests/sys/sys/Makefile
+++ tests/sys/sys/Makefile
@@ -2,8 +2,10 @@
TESTSDIR= ${TESTSBASE}/sys/sys
-ATF_TESTS_C= bitstring_test rb_test splay_test
+ATF_TESTS_C= arb_test bitstring_test rb_test splay_test
WARNS?= 5
+
+CFLAGS+= -ggdb
.include <bsd.test.mk>
Index: tests/sys/sys/arb_test.c
===================================================================
--- /dev/null
+++ tests/sys/sys/arb_test.c
@@ -0,0 +1,115 @@
+/* $OpenBSD: rb-test.c,v 1.4 2008/04/13 00:22:17 djm Exp $ */
+/*
+ * Copyright 2019 Edward Tomasz Napierala <trasz@FreeBSD.org>
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote products
+ * derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+#include <sys/types.h>
+
+#include <sys/tree.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <atf-c.h>
+
+struct node {
+ ARB32_ENTRY() next;
+ int key;
+};
+
+ARB32_HEAD(tree, node) *root;
+
+static int
+compare(const struct node *a, const struct node *b)
+{
+ if (a->key < b->key) return (-1);
+ else if (a->key > b->key) return (1);
+ return (0);
+}
+
+ARB_PROTOTYPE(tree, node, next, compare);
+
+ARB_GENERATE(tree, node, next, compare);
+
+#define ITER 150
+#define MIN 5
+#define MAX 5000
+
+ATF_TC_WITHOUT_HEAD(arb_test);
+ATF_TC_BODY(arb_test, tc)
+{
+ struct node *tmp, *ins;
+ int i, max, min;
+
+ max = min = 42; /* pacify gcc */
+
+ root = (struct tree *)calloc(ITER, 128);
+
+ ARB_INIT(tmp, next, root, ITER);
+
+ for (i = 0; i < ITER; i++) {
+ tmp = ARB_GETFREE(root, next);
+ ATF_REQUIRE_MSG(tmp != NULL, "ARB_GETFREE failed");
+ do {
+ tmp->key = arc4random_uniform(MAX-MIN);
+ tmp->key += MIN;
+ } while (ARB_FIND(tree, root, tmp) != NULL);
+ if (i == 0)
+ max = min = tmp->key;
+ else {
+ if (tmp->key > max)
+ max = tmp->key;
+ if (tmp->key < min)
+ min = tmp->key;
+ }
+ ATF_REQUIRE_EQ(NULL, ARB_INSERT(tree, root, tmp));
+ }
+
+ ins = ARB_MIN(tree, root);
+ ATF_REQUIRE_MSG(ins != NULL, "ARB_MIN error");
+ ATF_CHECK_EQ(min, ins->key);
+ tmp = ins;
+ ins = ARB_MAX(tree, root);
+ ATF_REQUIRE_MSG(ins != NULL, "ARB_MAX error");
+ ATF_CHECK_EQ(max, ins->key);
+
+ ATF_CHECK_EQ(tmp, ARB_REMOVE(tree, root, tmp));
+
+ for (i = 0; i < ITER - 1; i++) {
+ tmp = ARB_ROOT(root);
+ ATF_REQUIRE_MSG(tmp != NULL, "ARB_ROOT error");
+ ATF_CHECK_EQ(tmp, ARB_REMOVE(tree, root, tmp));
+ }
+}
+
+ATF_TP_ADD_TCS(tp)
+{
+
+ ATF_TP_ADD_TC(tp, arb_test);
+
+ return (atf_no_error());
+}

File Metadata

Mime Type
text/plain
Expires
Sat, Mar 28, 6:02 AM (1 h, 39 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
30460060
Default Alt Text
D20324.id58596.diff (50 KB)

Event Timeline