[xiph-commits] r15767 - in trunk/ezstream: . compat/sys
moritz at svn.xiph.org
moritz at svn.xiph.org
Sun Mar 15 03:55:59 PDT 2009
Author: moritz
Date: 2009-03-15 03:55:58 -0700 (Sun, 15 Mar 2009)
New Revision: 15767
Modified:
trunk/ezstream/NEWS
trunk/ezstream/compat/sys/tree.3
trunk/ezstream/compat/sys/tree.h
Log:
Update tree macros. The manual now actually has an acceptable license.
Modified: trunk/ezstream/NEWS
===================================================================
--- trunk/ezstream/NEWS 2009-03-14 16:05:12 UTC (rev 15766)
+++ trunk/ezstream/NEWS 2009-03-15 10:55:58 UTC (rev 15767)
@@ -1,3 +1,11 @@
+Changes in 0.5.4, released on XXXX-XX-XX:
+
+ * sys/compat/tree.*:
+ - [MISC] Update tree macros to a newer version. The manual, shipped for
+ reference, now has a more friendly 2-clause BSD license.
+
+
+
Changes in 0.5.3, released on 2007-12-01:
* src/ezstream.c:
Modified: trunk/ezstream/compat/sys/tree.3
===================================================================
--- trunk/ezstream/compat/sys/tree.3 2009-03-14 16:05:12 UTC (rev 15766)
+++ trunk/ezstream/compat/sys/tree.3 2009-03-15 10:55:58 UTC (rev 15767)
@@ -1,4 +1,4 @@
-.\" $OpenBSD: tree.3,v 1.13 2007/05/31 19:19:48 jmc Exp $
+.\" $OpenBSD: tree.3,v 1.20 2009/01/28 12:22:48 stsp Exp $
.\"/*
.\" * Copyright 2002 Niels Provos <provos at citi.umich.edu>
.\" * All rights reserved.
@@ -11,11 +11,6 @@
.\" * 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. All advertising materials mentioning features or use of this software
-.\" * must display the following acknowledgement:
-.\" * This product includes software developed by Niels Provos.
-.\" * 4. 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
@@ -28,7 +23,7 @@
.\" * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
.\" * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
.\" */
-.Dd $Mdocdate$
+.Dd $Mdocdate: January 28 2009 $
.Dt TREE 3
.Os
.Sh NAME
@@ -50,20 +45,25 @@
.Nm SPLAY_INSERT ,
.Nm SPLAY_REMOVE ,
.Nm RB_PROTOTYPE ,
+.Nm RB_PROTOTYPE_STATIC ,
.Nm RB_GENERATE ,
+.Nm RB_GENERATE_STATIC ,
.Nm RB_ENTRY ,
.Nm RB_HEAD ,
.Nm RB_INITIALIZER ,
.Nm RB_ROOT ,
.Nm RB_EMPTY ,
.Nm RB_NEXT ,
+.Nm RB_PREV ,
.Nm RB_MIN ,
.Nm RB_MAX ,
.Nm RB_FIND ,
+.Nm RB_NFIND ,
.Nm RB_LEFT ,
.Nm RB_RIGHT ,
.Nm RB_PARENT ,
.Nm RB_FOREACH ,
+.Nm RB_FOREACH_REVERSE ,
.Nm RB_INIT ,
.Nm RB_INSERT ,
.Nm RB_REMOVE
@@ -78,7 +78,7 @@
.Ft "struct TYPE *"
.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
.Fn SPLAY_ROOT "SPLAY_HEAD *head"
-.Ft "bool"
+.Ft "int"
.Fn SPLAY_EMPTY "SPLAY_HEAD *head"
.Ft "struct TYPE *"
.Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
@@ -101,29 +101,36 @@
.Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
.Pp
.Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
+.Fn RB_PROTOTYPE_STATIC "NAME" "TYPE" "FIELD" "CMP"
.Fn RB_GENERATE "NAME" "TYPE" "FIELD" "CMP"
+.Fn RB_GENERATE_STATIC "NAME" "TYPE" "FIELD" "CMP"
.Fn RB_ENTRY "TYPE"
.Fn RB_HEAD "HEADNAME" "TYPE"
.Fn RB_INITIALIZER "RB_HEAD *head"
.Ft "struct TYPE *"
.Fn RB_ROOT "RB_HEAD *head"
-.Ft "bool"
+.Ft "int"
.Fn RB_EMPTY "RB_HEAD *head"
.Ft "struct TYPE *"
.Fn RB_NEXT "NAME" "RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
+.Fn RB_PREV "NAME" "RB_HEAD *head" "struct TYPE *elm"
+.Ft "struct TYPE *"
.Fn RB_MIN "NAME" "RB_HEAD *head"
.Ft "struct TYPE *"
.Fn RB_MAX "NAME" "RB_HEAD *head"
.Ft "struct TYPE *"
.Fn RB_FIND "NAME" "RB_HEAD *head" "struct TYPE *elm"
.Ft "struct TYPE *"
+.Fn RB_NFIND "NAME" "RB_HEAD *head" "struct TYPE *elm"
+.Ft "struct TYPE *"
.Fn RB_LEFT "struct TYPE *elm" "RB_ENTRY NAME"
.Ft "struct TYPE *"
.Fn RB_RIGHT "struct TYPE *elm" "RB_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_REVERSE "VARNAME" "NAME" "RB_HEAD *head"
.Ft void
.Fn RB_INIT "RB_HEAD *head"
.Ft "struct TYPE *"
@@ -136,12 +143,12 @@
.Pp
In the macro definitions,
.Fa TYPE
-is the name tag of a user defined structure that must contain a field of type
-.Li SPLAY_ENTRY ,
+is the name tag of a user defined structure that must contain a field named
+.Fa FIELD ,
+of type
+.Li SPLAY_ENTRY
or
-.Li RB_ENTRY ,
-named
-.Fa ENTRYNAME .
+.Li RB_ENTRY .
The argument
.Fa HEADNAME
is the name tag of a user defined structure that must be declared
@@ -153,14 +160,16 @@
.Fa NAME
has to be a unique name prefix for every tree that is defined.
.Pp
-The function prototypes are declared with either
-.Li SPLAY_PROTOTYPE
+The function prototypes are declared with
+.Li SPLAY_PROTOTYPE ,
+.Li RB_PROTOTYPE ,
or
-.Li RB_PROTOTYPE .
-The function bodies are generated with either
-.Li SPLAY_GENERATE
+.Li RB_PROTOTYPE_STATIC .
+The function bodies are generated with
+.Li SPLAY_GENERATE ,
+.Li RB_GENERATE ,
or
-.Li RB_GENERATE .
+.Li 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.
@@ -222,7 +231,7 @@
Finally,
the
.Fa CMP
-argument is the name of a function used to compare trees noded
+argument is the name of a function used to compare trees' nodes
with each other.
The function takes two arguments of type
.Fa "struct TYPE *" .
@@ -328,7 +337,9 @@
In order to use the functions that manipulate the tree structure,
their prototypes need to be declared with the
.Fn RB_PROTOTYPE
-macro,
+or
+.Fn RB_PROTOTYPE_STATIC
+macros,
where
.Fa NAME
is a unique identifier for this particular tree.
@@ -343,15 +354,19 @@
.Pp
The function bodies are generated with the
.Fn RB_GENERATE
-macro.
-It takes the same arguments as the
+or
+.Fn RB_GENERATE_STATIC
+macros.
+These macros take the same arguments as the
.Fn RB_PROTOTYPE
-macro, but should be used only once.
+and
+.Fn RB_PROTOTYPE_STATIC
+macros, but should be used only once.
.Pp
Finally,
the
.Fa CMP
-argument is the name of a function used to compare trees noded
+argument is the name of a function used to compare trees' nodes
with each other.
The function takes two arguments of type
.Fa "struct TYPE *" .
@@ -378,6 +393,11 @@
macro inserts the new element
.Fa elm
into the tree.
+Upon success,
+.Va NULL
+is returned.
+If a matching element already exists in the tree, the insertion is
+aborted, and a pointer to the existing element is returned.
.Pp
The
.Fn RB_REMOVE
@@ -388,7 +408,14 @@
.Pp
The
.Fn RB_FIND
-macro can be used to find a particular element in the tree.
+and
+.Fn RB_NFIND
+macros can be used to find a particular element in the tree.
+.Fn RB_FIND
+finds the node with the same key as
+.Fa elm .
+.Fn RB_NFIND
+finds the first node greater than or equal to the search key.
.Bd -literal -offset indent
struct TYPE find, *res;
find.key = 30;
@@ -399,8 +426,9 @@
.Fn RB_ROOT ,
.Fn RB_MIN ,
.Fn RB_MAX ,
+.Fn RB_NEXT ,
and
-.Fn RB_NEXT
+.Fn RB_PREV
macros can be used to traverse the tree:
.Bd -literal -offset indent
for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))
@@ -408,7 +436,9 @@
.Pp
Or, for simplicity, one can use the
.Fn RB_FOREACH
-macro:
+or
+.Fn RB_FOREACH_REVERSE
+macros:
.Bd -literal -offset indent
RB_FOREACH(np, NAME, &head)
.Ed
@@ -436,7 +466,7 @@
int
intcmp(struct node *e1, struct node *e2)
{
- return (e1->i - e2->i);
+ return (e1->i < e2->i ? -1 : e1->i > e2->i);
}
RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
Modified: trunk/ezstream/compat/sys/tree.h
===================================================================
--- trunk/ezstream/compat/sys/tree.h 2009-03-14 16:05:12 UTC (rev 15766)
+++ trunk/ezstream/compat/sys/tree.h 2009-03-15 10:55:58 UTC (rev 15767)
@@ -1,4 +1,4 @@
-/* $OpenBSD: tree.h,v 1.9 2004/11/24 18:10:42 tdeval Exp $ */
+/* $OpenBSD: tree.h,v 1.11 2008/05/11 22:19:09 millert Exp $ */
/*
* Copyright 2002 Niels Provos <provos at citi.umich.edu>
* All rights reserved.
@@ -373,21 +373,31 @@
} while (0)
/* Generates prototypes and inline functions */
-#define RB_PROTOTYPE(name, type, field, cmp) \
-void name##_RB_INSERT_COLOR(struct name *, struct type *); \
-void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
-struct type *name##_RB_REMOVE(struct name *, struct type *); \
-struct type *name##_RB_INSERT(struct name *, struct type *); \
-struct type *name##_RB_FIND(struct name *, struct type *); \
-struct type *name##_RB_NEXT(struct type *); \
-struct type *name##_RB_MINMAX(struct name *, int); \
+#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) \
+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
*/
-#define RB_GENERATE(name, type, field, cmp) \
-void \
+#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) \
+attr void \
name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
{ \
struct type *parent, *gparent, *tmp; \
@@ -431,7 +441,7 @@
RB_COLOR(head->rbh_root, field) = RB_BLACK; \
} \
\
-void \
+attr void \
name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
{ \
struct type *tmp; \
@@ -507,7 +517,7 @@
RB_COLOR(elm, field) = RB_BLACK; \
} \
\
-struct type * \
+attr struct type * \
name##_RB_REMOVE(struct name *head, struct type *elm) \
{ \
struct type *child, *parent, *old = elm; \
@@ -575,7 +585,7 @@
} \
\
/* Inserts a node into the RB tree */ \
-struct type * \
+attr struct type * \
name##_RB_INSERT(struct name *head, struct type *elm) \
{ \
struct type *tmp; \
@@ -606,7 +616,7 @@
} \
\
/* Finds the node with the same key as elm */ \
-struct type * \
+attr struct type * \
name##_RB_FIND(struct name *head, struct type *elm) \
{ \
struct type *tmp = RB_ROOT(head); \
@@ -623,7 +633,29 @@
return (NULL); \
} \
\
-struct type * \
+/* 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); \
+} \
+ \
+/* ARGSUSED */ \
+attr struct type * \
name##_RB_NEXT(struct type *elm) \
{ \
if (RB_RIGHT(elm, field)) { \
@@ -644,7 +676,29 @@
return (elm); \
} \
\
-struct type * \
+/* ARGSUSED */ \
+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); \
@@ -665,7 +719,9 @@
#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)
@@ -674,4 +730,9 @@
(x) != NULL; \
(x) = name##_RB_NEXT(x))
+#define RB_FOREACH_REVERSE(x, name, head) \
+ for ((x) = RB_MAX(name, head); \
+ (x) != NULL; \
+ (x) = name##_RB_PREV(x))
+
#endif /* _SYS_TREE_H_ */
More information about the commits
mailing list