[xiph-commits] r13431 - in trunk/ezstream: . compat compat/sys src
moritz at svn.xiph.org
moritz at svn.xiph.org
Thu Aug 2 11:48:26 PDT 2007
Author: moritz
Date: 2007-08-02 11:48:26 -0700 (Thu, 02 Aug 2007)
New Revision: 13431
Added:
trunk/ezstream/compat/
trunk/ezstream/compat/Makefile.am
trunk/ezstream/compat/sys/
trunk/ezstream/compat/sys/Makefile.am
trunk/ezstream/compat/sys/tree.3
trunk/ezstream/compat/sys/tree.h
trunk/ezstream/src/xalloc.c
trunk/ezstream/src/xalloc.h
Modified:
trunk/ezstream/Makefile.am
trunk/ezstream/NEWS
trunk/ezstream/README
trunk/ezstream/configure.in
trunk/ezstream/src/Makefile.am
trunk/ezstream/src/configfile.c
trunk/ezstream/src/ezstream.c
trunk/ezstream/src/metadata.c
trunk/ezstream/src/playlist.c
trunk/ezstream/src/util.c
trunk/ezstream/src/util.h
Log:
Switch to using the (integrated) libxalloc.
Modified: trunk/ezstream/Makefile.am
===================================================================
--- trunk/ezstream/Makefile.am 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/Makefile.am 2007-08-02 18:48:26 UTC (rev 13431)
@@ -1,7 +1,7 @@
AUTOMAKE_OPTIONS = 1.9 foreign
ACLOCAL_AMFLAGS = -I m4
-SUBDIRS = doc examples m4 src win32
+SUBDIRS = compat doc examples m4 src win32
dist_doc_DATA = COPYING NEWS README
Modified: trunk/ezstream/NEWS
===================================================================
--- trunk/ezstream/NEWS 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/NEWS 2007-08-02 18:48:26 UTC (rev 13431)
@@ -1,3 +1,12 @@
+Changes in 0.4.4 (SVN):
+
+ * various:
+ - [MISC] Add new --enable-debug configuration option to the configure
+ script, which enables newly added memory debugging features.
+ (Not interesting for non-developers.)
+
+
+
Changes in 0.4.3, released on 2007-07-24:
* src/ezstream.c:
Modified: trunk/ezstream/README
===================================================================
--- trunk/ezstream/README 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/README 2007-08-02 18:48:26 UTC (rev 13431)
@@ -51,8 +51,10 @@
on a variety of systems. Aside from the standard autoconf options of the
configure script, a couple of additional options are available:
- --enable-examplesdir=DIR example configuration files installation directory
+ --enable-examplesdir=DIR
+ example configuration files installation directory
(default: DATADIR/examples/ezstream)
+ --enable-debug enable memory debugging (default: no)
--with-taglib=PREFIX Prefix where TagLib is installed (default:
autodetect)
--with-ogg=PREFIX Prefix where libogg is installed (optional)
Property changes on: trunk/ezstream/compat
___________________________________________________________________
Name: svn:ignore
+ Makefile.in
Added: trunk/ezstream/compat/Makefile.am
===================================================================
--- trunk/ezstream/compat/Makefile.am (rev 0)
+++ trunk/ezstream/compat/Makefile.am 2007-08-02 18:48:26 UTC (rev 13431)
@@ -0,0 +1,5 @@
+AUTOMAKE_OPTIONS = 1.9 foreign
+
+SUBDIRS = sys
+
+CLEANFILES = *~ *.core core
Property changes on: trunk/ezstream/compat/sys
___________________________________________________________________
Name: svn:ignore
+ Makefile.in
Added: trunk/ezstream/compat/sys/Makefile.am
===================================================================
--- trunk/ezstream/compat/sys/Makefile.am (rev 0)
+++ trunk/ezstream/compat/sys/Makefile.am 2007-08-02 18:48:26 UTC (rev 13431)
@@ -0,0 +1,5 @@
+AUTOMAKE_OPTIONS = 1.9 foreign
+
+EXTRA_DIST = tree.h tree.3
+
+CLEANFILES = *~ *.core core
Added: trunk/ezstream/compat/sys/tree.3
===================================================================
--- trunk/ezstream/compat/sys/tree.3 (rev 0)
+++ trunk/ezstream/compat/sys/tree.3 2007-08-02 18:48:26 UTC (rev 13431)
@@ -0,0 +1,534 @@
+.\" $OpenBSD: tree.3,v 1.13 2007/05/31 19:19:48 jmc Exp $
+.\"/*
+.\" * Copyright 2002 Niels Provos <provos at 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. 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
+.\" * 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.
+.\" */
+.Dd $Mdocdate$
+.Dt TREE 3
+.Os
+.Sh NAME
+.Nm SPLAY_PROTOTYPE ,
+.Nm SPLAY_GENERATE ,
+.Nm SPLAY_ENTRY ,
+.Nm SPLAY_HEAD ,
+.Nm SPLAY_INITIALIZER ,
+.Nm SPLAY_ROOT ,
+.Nm SPLAY_EMPTY ,
+.Nm SPLAY_NEXT ,
+.Nm SPLAY_MIN ,
+.Nm SPLAY_MAX ,
+.Nm SPLAY_FIND ,
+.Nm SPLAY_LEFT ,
+.Nm SPLAY_RIGHT ,
+.Nm SPLAY_FOREACH ,
+.Nm SPLAY_INIT ,
+.Nm SPLAY_INSERT ,
+.Nm SPLAY_REMOVE ,
+.Nm RB_PROTOTYPE ,
+.Nm RB_GENERATE ,
+.Nm RB_ENTRY ,
+.Nm RB_HEAD ,
+.Nm RB_INITIALIZER ,
+.Nm RB_ROOT ,
+.Nm RB_EMPTY ,
+.Nm RB_NEXT ,
+.Nm RB_MIN ,
+.Nm RB_MAX ,
+.Nm RB_FIND ,
+.Nm RB_LEFT ,
+.Nm RB_RIGHT ,
+.Nm RB_PARENT ,
+.Nm RB_FOREACH ,
+.Nm RB_INIT ,
+.Nm RB_INSERT ,
+.Nm RB_REMOVE
+.Nd "implementations of splay and red-black trees"
+.Sh SYNOPSIS
+.Fd #include <sys/tree.h>
+.Pp
+.Fn SPLAY_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
+.Fn SPLAY_GENERATE "NAME" "TYPE" "FIELD" "CMP"
+.Fn SPLAY_ENTRY "TYPE"
+.Fn SPLAY_HEAD "HEADNAME" "TYPE"
+.Ft "struct TYPE *"
+.Fn SPLAY_INITIALIZER "SPLAY_HEAD *head"
+.Fn SPLAY_ROOT "SPLAY_HEAD *head"
+.Ft "bool"
+.Fn SPLAY_EMPTY "SPLAY_HEAD *head"
+.Ft "struct TYPE *"
+.Fn SPLAY_NEXT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
+.Ft "struct TYPE *"
+.Fn SPLAY_MIN "NAME" "SPLAY_HEAD *head"
+.Ft "struct TYPE *"
+.Fn SPLAY_MAX "NAME" "SPLAY_HEAD *head"
+.Ft "struct TYPE *"
+.Fn SPLAY_FIND "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
+.Ft "struct TYPE *"
+.Fn SPLAY_LEFT "struct TYPE *elm" "SPLAY_ENTRY NAME"
+.Ft "struct TYPE *"
+.Fn SPLAY_RIGHT "struct TYPE *elm" "SPLAY_ENTRY NAME"
+.Fn SPLAY_FOREACH "VARNAME" "NAME" "SPLAY_HEAD *head"
+.Ft void
+.Fn SPLAY_INIT "SPLAY_HEAD *head"
+.Ft "struct TYPE *"
+.Fn SPLAY_INSERT "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
+.Ft "struct TYPE *"
+.Fn SPLAY_REMOVE "NAME" "SPLAY_HEAD *head" "struct TYPE *elm"
+.Pp
+.Fn RB_PROTOTYPE "NAME" "TYPE" "FIELD" "CMP"
+.Fn RB_GENERATE "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"
+.Fn RB_EMPTY "RB_HEAD *head"
+.Ft "struct TYPE *"
+.Fn RB_NEXT "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_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"
+.Ft void
+.Fn RB_INIT "RB_HEAD *head"
+.Ft "struct TYPE *"
+.Fn RB_INSERT "NAME" "RB_HEAD *head" "struct TYPE *elm"
+.Ft "struct TYPE *"
+.Fn RB_REMOVE "NAME" "RB_HEAD *head" "struct TYPE *elm"
+.Sh DESCRIPTION
+These macros define data structures for different types of trees:
+splay trees and red-black trees.
+.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 ,
+or
+.Li RB_ENTRY ,
+named
+.Fa ENTRYNAME .
+The argument
+.Fa HEADNAME
+is the name tag of a user defined structure that must be declared
+using the macros
+.Fn SPLAY_HEAD
+or
+.Fn 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 either
+.Li SPLAY_PROTOTYPE
+or
+.Li RB_PROTOTYPE .
+The function bodies are generated with either
+.Li SPLAY_GENERATE
+or
+.Li RB_GENERATE .
+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.
+Every operation on the tree causes a splay to happen.
+The splay moves the requested node to the root of the tree and partly
+rebalances it.
+.Pp
+This has the benefit that request locality causes faster lookups as
+the requested nodes move to the top of the tree.
+On the other hand, every lookup causes memory writes.
+.Pp
+The Balance Theorem bounds the total access time for m operations
+and n inserts on an initially empty tree as O((m + n)lg n).
+The amortized cost for a sequence of m accesses to a splay tree is O(lg n).
+.Pp
+A splay tree is headed by a structure defined by the
+.Fn SPLAY_HEAD
+macro.
+A
+.Fa SPLAY_HEAD
+structure is declared as follows:
+.Bd -literal -offset indent
+SPLAY_HEAD(HEADNAME, TYPE) head;
+.Ed
+.Pp
+where
+.Fa HEADNAME
+is the name of the structure to be defined, and struct
+.Fa TYPE
+is the type of the elements to be inserted into the tree.
+.Pp
+The
+.Fn SPLAY_ENTRY
+macro declares a structure that allows elements to be connected in the tree.
+.Pp
+In order to use the functions that manipulate the tree structure,
+their prototypes need to be declared with the
+.Fn SPLAY_PROTOTYPE
+macro,
+where
+.Fa NAME
+is a unique identifier for this particular tree.
+The
+.Fa TYPE
+argument is the type of the structure that is being managed
+by the tree.
+The
+.Fa FIELD
+argument is the name of the element defined by
+.Fn SPLAY_ENTRY .
+.Pp
+The function bodies are generated with the
+.Fn SPLAY_GENERATE
+macro.
+It takes the same arguments as the
+.Fn SPLAY_PROTOTYPE
+macro, but should be used only once.
+.Pp
+Finally,
+the
+.Fa CMP
+argument is the name of a function used to compare trees noded
+with each other.
+The function takes two arguments of type
+.Fa "struct TYPE *" .
+If the first argument is smaller than the second, the function returns a
+value smaller than zero.
+If they are equal, the function returns zero.
+Otherwise, it should return a value greater than zero.
+The compare function defines the order of the tree elements.
+.Pp
+The
+.Fn SPLAY_INIT
+macro initializes the tree referenced by
+.Fa head .
+.Pp
+The splay tree can also be initialized statically by using the
+.Fn SPLAY_INITIALIZER
+macro like this:
+.Bd -literal -offset indent
+SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(&head);
+.Ed
+.Pp
+The
+.Fn SPLAY_INSERT
+macro inserts the new element
+.Fa elm
+into the tree.
+.Pp
+The
+.Fn SPLAY_REMOVE
+macro removes the element
+.Fa elm
+from the tree pointed by
+.Fa head .
+.Pp
+The
+.Fn SPLAY_FIND
+macro can be used to find a particular element in the tree.
+.Bd -literal -offset indent
+struct TYPE find, *res;
+find.key = 30;
+res = SPLAY_FIND(NAME, &head, &find);
+.Ed
+.Pp
+The
+.Fn SPLAY_ROOT ,
+.Fn SPLAY_MIN ,
+.Fn SPLAY_MAX ,
+and
+.Fn SPLAY_NEXT
+macros can be used to traverse the tree:
+.Bd -literal -offset indent
+for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
+.Ed
+.Pp
+Or, for simplicity, one can use the
+.Fn SPLAY_FOREACH
+macro:
+.Bd -literal -offset indent
+SPLAY_FOREACH(np, NAME, &head)
+.Ed
+.Pp
+The
+.Fn SPLAY_EMPTY
+macro should be used to check whether a splay tree is empty.
+.Sh RED-BLACK TREES
+A red-black tree is a binary search tree with the node color as an
+extra attribute.
+It fulfills a set of conditions:
+.Pp
+.Bl -enum -compact -offset indent
+.It
+every search path from the root to a leaf consists of the same number of
+black nodes,
+.It
+each red node (except for the root) has a black parent,
+.It
+each leaf node is black.
+.El
+.Pp
+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).
+.Pp
+A red-black tree is headed by a structure defined by the
+.Fn RB_HEAD
+macro.
+A
+.Fa RB_HEAD
+structure is declared as follows:
+.Bd -literal -offset indent
+RB_HEAD(HEADNAME, TYPE) head;
+.Ed
+.Pp
+where
+.Fa HEADNAME
+is the name of the structure to be defined, and struct
+.Fa TYPE
+is the type of the elements to be inserted into the tree.
+.Pp
+The
+.Fn RB_ENTRY
+macro declares a structure that allows elements to be connected in the tree.
+.Pp
+In order to use the functions that manipulate the tree structure,
+their prototypes need to be declared with the
+.Fn RB_PROTOTYPE
+macro,
+where
+.Fa NAME
+is a unique identifier for this particular tree.
+The
+.Fa TYPE
+argument is the type of the structure that is being managed
+by the tree.
+The
+.Fa FIELD
+argument is the name of the element defined by
+.Fn RB_ENTRY .
+.Pp
+The function bodies are generated with the
+.Fn RB_GENERATE
+macro.
+It takes the same arguments as the
+.Fn RB_PROTOTYPE
+macro, but should be used only once.
+.Pp
+Finally,
+the
+.Fa CMP
+argument is the name of a function used to compare trees noded
+with each other.
+The function takes two arguments of type
+.Fa "struct TYPE *" .
+If the first argument is smaller than the second, the function returns a
+value smaller than zero.
+If they are equal, the function returns zero.
+Otherwise, it should return a value greater than zero.
+The compare function defines the order of the tree elements.
+.Pp
+The
+.Fn RB_INIT
+macro initializes the tree referenced by
+.Fa head .
+.Pp
+The red-black tree can also be initialized statically by using the
+.Fn RB_INITIALIZER
+macro like this:
+.Bd -literal -offset indent
+RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(&head);
+.Ed
+.Pp
+The
+.Fn RB_INSERT
+macro inserts the new element
+.Fa elm
+into the tree.
+.Pp
+The
+.Fn RB_REMOVE
+macro removes the element
+.Fa elm
+from the tree pointed by
+.Fa head .
+.Pp
+The
+.Fn RB_FIND
+macro can be used to find a particular element in the tree.
+.Bd -literal -offset indent
+struct TYPE find, *res;
+find.key = 30;
+res = RB_FIND(NAME, &head, &find);
+.Ed
+.Pp
+The
+.Fn RB_ROOT ,
+.Fn RB_MIN ,
+.Fn RB_MAX ,
+and
+.Fn RB_NEXT
+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))
+.Ed
+.Pp
+Or, for simplicity, one can use the
+.Fn RB_FOREACH
+macro:
+.Bd -literal -offset indent
+RB_FOREACH(np, NAME, &head)
+.Ed
+.Pp
+The
+.Fn RB_EMPTY
+macro should be used to check whether a red-black tree is empty.
+.Sh EXAMPLES
+The following example demonstrates how to declare a red-black tree
+holding integers.
+Values are inserted into it and the contents of the tree are printed
+in order.
+Lastly, the internal structure of the tree is printed.
+.Bd -literal -offset 3n
+#include <sys/tree.h>
+#include <err.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+struct node {
+ RB_ENTRY(node) entry;
+ int i;
+};
+
+int
+intcmp(struct node *e1, struct node *e2)
+{
+ return (e1->i - e2->i);
+}
+
+RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
+RB_GENERATE(inttree, node, entry, intcmp)
+
+int testdata[] = {
+ 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18,
+ 7, 11, 14
+};
+
+void
+print_tree(struct node *n)
+{
+ struct node *left, *right;
+
+ if (n == NULL) {
+ printf("nil");
+ return;
+ }
+ left = RB_LEFT(n, entry);
+ right = RB_RIGHT(n, entry);
+ if (left == NULL && right == NULL)
+ printf("%d", n->i);
+ else {
+ printf("%d(", n->i);
+ print_tree(left);
+ printf(",");
+ print_tree(right);
+ printf(")");
+ }
+}
+
+int
+main()
+{
+ int i;
+ struct node *n;
+
+ for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {
+ if ((n = malloc(sizeof(struct node))) == NULL)
+ err(1, NULL);
+ n->i = testdata[i];
+ RB_INSERT(inttree, &head, n);
+ }
+
+ RB_FOREACH(n, inttree, &head) {
+ printf("%d\en", n->i);
+ }
+ print_tree(RB_ROOT(&head));
+ printf("\en");
+ return (0);
+}
+.Ed
+.Sh NOTES
+Trying to free a tree in the following way is a common error:
+.Bd -literal -offset indent
+SPLAY_FOREACH(var, NAME, &head) {
+ SPLAY_REMOVE(NAME, &head, var);
+ free(var);
+}
+free(head);
+.Ed
+.Pp
+Since
+.Va var
+is free'd, the
+.Fn FOREACH
+macro refers to a pointer that may have been reallocated already.
+Proper code needs a second variable.
+.Bd -literal -offset indent
+for (var = SPLAY_MIN(NAME, &head); var != NULL; var = nxt) {
+ nxt = SPLAY_NEXT(NAME, &head, var);
+ SPLAY_REMOVE(NAME, &head, var);
+ free(var);
+}
+.Ed
+.Pp
+Both
+.Fn RB_INSERT
+and
+.Fn SPLAY_INSERT
+return
+.Va NULL
+if the element was inserted in the tree successfully, otherwise they
+return a pointer to the element with the colliding key.
+.Pp
+Accordingly,
+.Fn RB_REMOVE
+and
+.Fn SPLAY_REMOVE
+return the pointer to the removed element, otherwise they return
+.Va NULL
+to indicate an error.
+.Sh AUTHORS
+The author of the tree macros is Niels Provos.
Added: trunk/ezstream/compat/sys/tree.h
===================================================================
--- trunk/ezstream/compat/sys/tree.h (rev 0)
+++ trunk/ezstream/compat/sys/tree.h 2007-08-02 18:48:26 UTC (rev 13431)
@@ -0,0 +1,677 @@
+/* $OpenBSD: tree.h,v 1.9 2004/11/24 18:10:42 tdeval Exp $ */
+/*
+ * Copyright 2002 Niels Provos <provos at 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.
+ *
+ * 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.
+ */
+
+#ifndef _SYS_TREE_H_
+#define _SYS_TREE_H_
+
+/*
+ * This file defines data structures for different types of trees:
+ * splay trees and red-black trees.
+ *
+ * A splay tree is a self-organizing data structure. Every operation
+ * on the tree causes a splay to happen. The splay moves the requested
+ * node to the root of the tree and partly rebalances it.
+ *
+ * This has the benefit that request locality causes faster lookups as
+ * the requested nodes move to the top of the tree. On the other hand,
+ * every lookup causes memory writes.
+ *
+ * The Balance Theorem bounds the total access time for m operations
+ * and n inserts on an initially empty tree as O((m + n)lg n). The
+ * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
+ *
+ * A red-black tree is a binary search tree with the node color as an
+ * extra attribute. It fulfills a set of conditions:
+ * - every search path from the root to a leaf consists of the
+ * same number of black nodes,
+ * - each red node (except for the root) has a black parent,
+ * - each leaf node is black.
+ *
+ * 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).
+ */
+
+#define SPLAY_HEAD(name, type) \
+struct name { \
+ struct type *sph_root; /* root of the tree */ \
+}
+
+#define SPLAY_INITIALIZER(root) \
+ { NULL }
+
+#define SPLAY_INIT(root) do { \
+ (root)->sph_root = NULL; \
+} while (0)
+
+#define SPLAY_ENTRY(type) \
+struct { \
+ struct type *spe_left; /* left element */ \
+ struct type *spe_right; /* right element */ \
+}
+
+#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
+#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
+#define SPLAY_ROOT(head) (head)->sph_root
+#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
+
+/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
+#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (0)
+
+#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (0)
+
+#define SPLAY_LINKLEFT(head, tmp, field) do { \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
+} while (0)
+
+#define SPLAY_LINKRIGHT(head, tmp, field) do { \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
+} while (0)
+
+#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
+ SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
+ SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
+} while (0)
+
+/* Generates prototypes and inline functions */
+
+#define SPLAY_PROTOTYPE(name, type, field, cmp) \
+void name##_SPLAY(struct name *, struct type *); \
+void name##_SPLAY_MINMAX(struct name *, int); \
+struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
+ \
+/* Finds the node with the same key as elm */ \
+static __inline struct type * \
+name##_SPLAY_FIND(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) \
+ return(NULL); \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) \
+ return (head->sph_root); \
+ return (NULL); \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_NEXT(struct name *head, struct type *elm) \
+{ \
+ name##_SPLAY(head, elm); \
+ if (SPLAY_RIGHT(elm, field) != NULL) { \
+ elm = SPLAY_RIGHT(elm, field); \
+ while (SPLAY_LEFT(elm, field) != NULL) { \
+ elm = SPLAY_LEFT(elm, field); \
+ } \
+ } else \
+ elm = NULL; \
+ return (elm); \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_MIN_MAX(struct name *head, int val) \
+{ \
+ name##_SPLAY_MINMAX(head, val); \
+ return (SPLAY_ROOT(head)); \
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp) \
+struct type * \
+name##_SPLAY_INSERT(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) { \
+ SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
+ } else { \
+ int __comp; \
+ name##_SPLAY(head, elm); \
+ __comp = (cmp)(elm, (head)->sph_root); \
+ if(__comp < 0) { \
+ SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
+ SPLAY_RIGHT(elm, field) = (head)->sph_root; \
+ SPLAY_LEFT((head)->sph_root, field) = NULL; \
+ } else if (__comp > 0) { \
+ SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT(elm, field) = (head)->sph_root; \
+ SPLAY_RIGHT((head)->sph_root, field) = NULL; \
+ } else \
+ return ((head)->sph_root); \
+ } \
+ (head)->sph_root = (elm); \
+ return (NULL); \
+} \
+ \
+struct type * \
+name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *__tmp; \
+ if (SPLAY_EMPTY(head)) \
+ return (NULL); \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) { \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
+ } else { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
+ name##_SPLAY(head, elm); \
+ SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
+ } \
+ return (elm); \
+ } \
+ return (NULL); \
+} \
+ \
+void \
+name##_SPLAY(struct name *head, struct type *elm) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+ int __comp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while ((__comp = (cmp)(elm, (head)->sph_root))) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) > 0){ \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+} \
+ \
+/* Splay with either the minimum or the maximum element \
+ * Used to find minimum or maximum element in tree. \
+ */ \
+void name##_SPLAY_MINMAX(struct name *head, int __comp) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while (1) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp > 0) { \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+}
+
+#define SPLAY_NEGINF -1
+#define SPLAY_INF 1
+
+#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
+#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
+#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
+#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
+#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
+#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
+
+#define SPLAY_FOREACH(x, name, head) \
+ for ((x) = SPLAY_MIN(name, head); \
+ (x) != NULL; \
+ (x) = SPLAY_NEXT(name, head, x))
+
+/* Macros that define a red-black tree */
+#define RB_HEAD(name, type) \
+struct name { \
+ struct type *rbh_root; /* root of the tree */ \
+}
+
+#define RB_INITIALIZER(root) \
+ { NULL }
+
+#define RB_INIT(root) do { \
+ (root)->rbh_root = NULL; \
+} while (0)
+
+#define RB_BLACK 0
+#define RB_RED 1
+#define RB_ENTRY(type) \
+struct { \
+ struct type *rbe_left; /* left element */ \
+ struct type *rbe_right; /* right element */ \
+ struct type *rbe_parent; /* parent element */ \
+ int rbe_color; /* node color */ \
+}
+
+#define RB_LEFT(elm, field) (elm)->field.rbe_left
+#define RB_RIGHT(elm, field) (elm)->field.rbe_right
+#define RB_PARENT(elm, field) (elm)->field.rbe_parent
+#define RB_COLOR(elm, field) (elm)->field.rbe_color
+#define RB_ROOT(head) (head)->rbh_root
+#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
+
+#define RB_SET(elm, parent, field) do { \
+ RB_PARENT(elm, field) = parent; \
+ RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
+ RB_COLOR(elm, field) = RB_RED; \
+} while (0)
+
+#define RB_SET_BLACKRED(black, red, field) do { \
+ RB_COLOR(black, field) = RB_BLACK; \
+ RB_COLOR(red, field) = RB_RED; \
+} while (0)
+
+#ifndef RB_AUGMENT
+#define RB_AUGMENT(x)
+#endif
+
+#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
+ (tmp) = RB_RIGHT(elm, field); \
+ if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
+ RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_LEFT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} while (0)
+
+#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
+ (tmp) = RB_LEFT(elm, field); \
+ if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
+ RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_RIGHT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} 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); \
+ \
+
+/* Main rb operation.
+ * Moves node close to the key of elm to top
+ */
+#define RB_GENERATE(name, type, field, cmp) \
+void \
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
+{ \
+ struct type *parent, *gparent, *tmp; \
+ while ((parent = RB_PARENT(elm, field)) && \
+ RB_COLOR(parent, field) == RB_RED) { \
+ gparent = RB_PARENT(parent, field); \
+ if (parent == RB_LEFT(gparent, field)) { \
+ tmp = RB_RIGHT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_RIGHT(parent, field) == elm) { \
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_RIGHT(head, gparent, tmp, field); \
+ } else { \
+ tmp = RB_LEFT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_LEFT(parent, field) == elm) { \
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_LEFT(head, gparent, tmp, field); \
+ } \
+ } \
+ RB_COLOR(head->rbh_root, field) = RB_BLACK; \
+} \
+ \
+void \
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+{ \
+ 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) == RB_BLACK) {\
+ struct type *oleft; \
+ if ((oleft = RB_LEFT(tmp, field)))\
+ RB_COLOR(oleft, field) = RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_RIGHT(head, tmp, oleft, field);\
+ 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_BLACK;\
+ 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_BLACK) {\
+ struct type *oright; \
+ if ((oright = RB_RIGHT(tmp, field)))\
+ RB_COLOR(oright, field) = RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_LEFT(head, tmp, oright, field);\
+ 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_BLACK;\
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ elm = RB_ROOT(head); \
+ break; \
+ } \
+ } \
+ } \
+ if (elm) \
+ RB_COLOR(elm, field) = RB_BLACK; \
+} \
+ \
+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; \
+ RB_AUGMENT(parent); \
+ } 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;\
+ RB_AUGMENT(RB_PARENT(old, field)); \
+ } 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 { \
+ RB_AUGMENT(left); \
+ } 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; \
+ RB_AUGMENT(parent); \
+ } 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 */ \
+struct type * \
+name##_RB_INSERT(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp; \
+ struct type *parent = NULL; \
+ int comp = 0; \
+ tmp = RB_ROOT(head); \
+ while (tmp) { \
+ parent = tmp; \
+ comp = (cmp)(elm, parent); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ RB_SET(elm, parent, field); \
+ if (parent != NULL) { \
+ if (comp < 0) \
+ RB_LEFT(parent, field) = elm; \
+ else \
+ RB_RIGHT(parent, field) = elm; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = elm; \
+ name##_RB_INSERT_COLOR(head, elm); \
+ return (NULL); \
+} \
+ \
+/* Finds the node with the same key as elm */ \
+struct type * \
+name##_RB_FIND(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (NULL); \
+} \
+ \
+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); \
+} \
+ \
+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_NEXT(name, x, y) name##_RB_NEXT(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))
+
+#endif /* _SYS_TREE_H_ */
Modified: trunk/ezstream/configure.in
===================================================================
--- trunk/ezstream/configure.in 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/configure.in 2007-08-02 18:48:26 UTC (rev 13431)
@@ -40,7 +40,21 @@
XIPH_CPPFLAGS="-Wall -Wwrite-strings -Wpointer-arith -Wsign-compare -Wstrict-prototypes -Wmissing-prototypes -Wmissing-declarations"
fi
+ez_enable_debug=no
+AC_ARG_ENABLE(debug,
+ AS_HELP_STRING([--enable-debug],
+ [enable memory debugging (default: no)]),
+[case "$enableval" in
+ no) ;;
+ *) ez_enable_debug=yes ;;
+esac], [])
+AC_MSG_CHECKING([whether to enable debugging])
+if test x"$ez_enable_debug" = "xyes"; then
+ AC_DEFINE(XALLOC_DEBUG, 1, [Define whether to build with XALLOC debugging])
+fi
+AC_MSG_RESULT([$ez_enable_debug])
+
dnl MISC SYSTEM CHARACTERISTICS
dnl __progname check adapted from OpenNTPd-portable configure.ac
@@ -66,7 +80,31 @@
AC_CHECK_HEADERS(sys/time.h paths.h signal.h libgen.h)
+COMPAT_INCLUDES=""
+if test x"$ez_enable_debug" = "xyes"; then
+ AC_CHECK_HEADERS(sys/tree.h)
+ if test x"$ac_cv_header_sys_tree_h" = "xyes"; then
+ AC_MSG_CHECKING([for RB_FOREACH and RB_INSERT in sys/tree.h])
+ AC_EGREP_CPP([yes], [
+#include <sys/tree.h>
+#if defined(RB_FOREACH) && defined(RB_INSERT)
+ yes
+#endif
+ ], [
+ AC_MSG_RESULT([yes])
+ AC_DEFINE(HAVE_WORKING_SYS_TREE_H, 1,
+ [Define whether RB_FOREACH is defined in <sys/tree.h>])
+ ], [
+ AC_MSG_RESULT([no])
+ COMPAT_INCLUDES="-I\$(top_srcdir)/compat"
+ ])
+ else
+ COMPAT_INCLUDES="-I\$(top_srcdir)/compat"
+ fi
+fi
+AC_SUBST(COMPAT_INCLUDES)
+
dnl LIBRARY FUNCTIONS
AC_CHECK_LIB(gen, basename)
@@ -201,6 +239,8 @@
dnl OUTPUT
AC_CONFIG_FILES(Makefile \
+ compat/Makefile \
+ compat/sys/Makefile \
doc/Makefile \
examples/Makefile \
m4/Makefile \
Modified: trunk/ezstream/src/Makefile.am
===================================================================
--- trunk/ezstream/src/Makefile.am 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/src/Makefile.am 2007-08-02 18:48:26 UTC (rev 13431)
@@ -3,13 +3,15 @@
bin_PROGRAMS = ezstream
ezstream_SOURCES = compat.c configfile.c ezstream.c metadata.c playlist.c \
- util.c
+ util.c xalloc.c
ezstream_LDADD = @LIBOBJS@ @XIPH_LIBS@ @TAGLIB_LIBS@
-
+
+INCLUDES = @COMPAT_INCLUDES@
+
AM_CFLAGS = @XIPH_CFLAGS@ @TAGLIB_CFLAGS@
AM_CPPFLAGS = @XIPH_CPPFLAGS@ @TAGLIB_CPPFLAGS@
EXTRA_DIST = compat.h configfile.h getopt.h metadata.h playlist.h \
- strfctns.h util.h
+ strfctns.h util.h xalloc.h
CLEANFILES = core *.core *~ .*~
Modified: trunk/ezstream/src/configfile.c
===================================================================
--- trunk/ezstream/src/configfile.c 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/src/configfile.c 2007-08-02 18:48:26 UTC (rev 13431)
@@ -29,7 +29,7 @@
#include "compat.h"
#include "configfile.h"
#include "strfctns.h"
-#include "util.h"
+#include "xalloc.h"
extern char *__progname;
Modified: trunk/ezstream/src/ezstream.c
===================================================================
--- trunk/ezstream/src/ezstream.c 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/src/ezstream.c 2007-08-02 18:48:26 UTC (rev 13431)
@@ -64,6 +64,7 @@
#include "playlist.h"
#include "strfctns.h"
#include "util.h"
+#include "xalloc.h"
#define STREAM_DONE 0
#define STREAM_CONT 1
@@ -127,6 +128,7 @@
char * getProgname(const char *);
void usage(void);
void usageHelp(void);
+int shutdown(int);
#ifdef HAVE_SIGNALS
void sig_handler(int);
@@ -961,12 +963,16 @@
return (1);
}
-/* Borrowed from OpenNTPd-portable's compat-openbsd/bsd-misc.c */
+/*
+ * Borrowed from OpenNTPd-portable's compat-openbsd/bsd-misc.c.
+ * Does not use xalloc on purpose, as the 9 bytes of memory that don't get
+ * cleaned up in the end really don't matter.
+ */
char *
getProgname(const char *argv0)
{
#ifdef HAVE___PROGNAME
- return (xstrdup(__progname));
+ return (strdup(__progname));
#else
char *p;
@@ -978,10 +984,20 @@
else
p++;
- return (xstrdup(p));
+ return (strdup(p));
#endif /* HAVE___PROGNAME */
}
+int
+shutdown(int exitval)
+{
+ shout_shutdown();
+ playlist_shutdown();
+ xalloc_shutdown();
+
+ return (exitval);
+}
+
void
usage(void)
{
@@ -1017,6 +1033,14 @@
unsigned int i;
#endif
+#ifdef XALLOC_DEBUG
+ xalloc_initialize_debug(2, NULL);
+#else
+ xalloc_initialize();
+#endif /* XALLOC_DEBUG */
+ playlist_init();
+ shout_init();
+
__progname = getProgname(argv[0]);
pezConfig = getEZConfig();
@@ -1029,26 +1053,26 @@
if (configFile != NULL) {
printf("Error: multiple -c arguments given\n");
usage();
- return (2);
+ return (shutdown(2));
}
configFile = xstrdup(optarg);
break;
case 'h':
usage();
usageHelp();
- return (0);
+ return (shutdown(0));
case 'q':
qFlag = 1;
break;
case 'V':
printf("%s\n", PACKAGE_STRING);
- return (0);
+ return (shutdown(0));
case 'v':
vFlag++;
break;
case '?':
usage();
- return (2);
+ return (shutdown(2));
default:
break;
}
@@ -1059,7 +1083,7 @@
if (configFile == NULL) {
printf("You must supply a config file with the -c argument.\n");
usage();
- return (2);
+ return (shutdown(2));
} else {
/*
* Attempt to open configFile here for a more meaningful error
@@ -1072,7 +1096,7 @@
if (stat(configFile, &st) == -1) {
printf("%s: %s\n", configFile, strerror(errno));
usage();
- return (2);
+ return (shutdown(2));
}
if (vFlag && (st.st_mode & (S_IRGRP | S_IROTH)))
printf("%s: Warning: %s is group and/or world readable\n",
@@ -1080,7 +1104,7 @@
if (st.st_mode & (S_IWGRP | S_IWOTH)) {
printf("%s: Error: %s is group and/or world writeable\n",
__progname, configFile);
- return (2);
+ return (shutdown(2));
}
#else
FILE *tmp;
@@ -1088,43 +1112,40 @@
if ((tmp = fopen(configFile, "r")) == NULL) {
printf("%s: %s\n", configFile, strerror(errno));
usage();
- return (2);
+ return (shutdown(2));
}
fclose(tmp);
#endif /* HAVE_STAT */
}
if (!parseConfig(configFile))
- return (2);
+ return (shutdown(2));
- shout_init();
- playlist_init();
-
if (pezConfig->URL == NULL) {
printf("%s: Error: Missing <url>\n", configFile);
- return (2);
+ return (shutdown(2));
}
if (!urlParse(pezConfig->URL, &host, &port, &mount)) {
printf("Must be of the form ``http://server:port/mountpoint''\n");
- return (2);
+ return (shutdown(2));
}
if (strlen(host) == 0) {
printf("%s: Error: Invalid <url>: Missing server:\n", configFile);
printf("Must be of the form ``http://server:port/mountpoint''\n");
- return (2);
+ return (shutdown(2));
}
if (strlen(mount) == 0) {
printf("%s: Error: Invalid <url>: Missing mountpoint:\n", configFile);
printf("Must be of the form ``http://server:port/mountpoint''\n");
- return (2);
+ return (shutdown(2));
}
if (pezConfig->password == NULL) {
printf("%s: Error: Missing <sourcepassword>\n", configFile);
- return (2);
+ return (shutdown(2));
}
if (pezConfig->fileName == NULL) {
printf("%s: Error: Missing <filename>\n", configFile);
- return (2);
+ return (shutdown(2));
}
if (pezConfig->format == NULL) {
printf("%s: Warning: Missing <format>:\n", configFile);
@@ -1135,45 +1156,45 @@
if ((shout = shout_new()) == NULL) {
printf("%s: shout_new(): %s", __progname, strerror(ENOMEM));
- return (1);
+ return (shutdown(1));
}
if (shout_set_host(shout, host) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_host(): %s\n", __progname,
shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
if (shout_set_protocol(shout, SHOUT_PROTOCOL_HTTP) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_protocol(): %s\n", __progname,
shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
if (shout_set_port(shout, port) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_port: %s\n", __progname,
shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
if (shout_set_password(shout, pezConfig->password) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_password(): %s\n", __progname,
shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
if (shout_set_mount(shout, mount) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_mount(): %s\n", __progname,
shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
if (shout_set_user(shout, "source") != SHOUTERR_SUCCESS) {
printf("%s: shout_set_user(): %s\n", __progname,
shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
if (!strcmp(pezConfig->format, MP3_FORMAT)) {
if (shout_set_format(shout, SHOUT_FORMAT_MP3) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_format(MP3): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
if (!strcmp(pezConfig->format, VORBIS_FORMAT) ||
@@ -1181,7 +1202,7 @@
if (shout_set_format(shout, SHOUT_FORMAT_OGG) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_format(OGG): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
@@ -1189,63 +1210,63 @@
if (shout_set_name(shout, pezConfig->serverName) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_name(): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
if (pezConfig->serverURL) {
if (shout_set_url(shout, pezConfig->serverURL) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_url(): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
if (pezConfig->serverGenre) {
if (shout_set_genre(shout, pezConfig->serverGenre) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_genre(): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
if (pezConfig->serverDescription) {
if (shout_set_description(shout, pezConfig->serverDescription) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_description(): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
if (pezConfig->serverBitrate) {
if (shout_set_audio_info(shout, SHOUT_AI_BITRATE, pezConfig->serverBitrate) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_audio_info(AI_BITRATE): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
if (pezConfig->serverChannels) {
if (shout_set_audio_info(shout, SHOUT_AI_CHANNELS, pezConfig->serverChannels) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_audio_info(AI_CHANNELS): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
if (pezConfig->serverSamplerate) {
if (shout_set_audio_info(shout, SHOUT_AI_SAMPLERATE, pezConfig->serverSamplerate) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_audio_info(AI_SAMPLERATE): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
if (pezConfig->serverQuality) {
if (shout_set_audio_info(shout, SHOUT_AI_QUALITY, pezConfig->serverQuality) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_audio_info(AI_QUALITY): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
}
if (shout_set_public(shout, pezConfig->serverPublic) != SHOUTERR_SUCCESS) {
printf("%s: shout_set_public(): %s\n",
__progname, shout_get_error(shout));
- return (1);
+ return (shutdown(1));
}
if (pezConfig->metadataProgram != NULL)
@@ -1263,7 +1284,7 @@
if (sigaction(ezstream_signals[i], &act, NULL) == -1) {
printf("%s: sigaction(): %s\n",
__progname, strerror(errno));
- return (1);
+ return (shutdown(1));
}
}
#endif /* HAVE_SIGNALS */
@@ -1301,6 +1322,8 @@
if (pezConfig->streamOnce)
break;
} while (ret);
+
+ shout_close(shout);
} else
printf("%s: Connection to http://%s:%d%s failed: %s\n", __progname,
host, port, mount, shout_get_error(shout));
@@ -1308,15 +1331,9 @@
if (vFlag)
printf("%s: Exiting ...\n", __progname);
- shout_close(shout);
-
- playlist_free(&playlist);
- playlist_shutdown();
-
- shout_shutdown();
-
xfree(host);
xfree(mount);
+ playlist_free(&playlist);
- return 0;
+ return (shutdown(0));
}
Modified: trunk/ezstream/src/metadata.c
===================================================================
--- trunk/ezstream/src/metadata.c 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/src/metadata.c 2007-08-02 18:48:26 UTC (rev 13431)
@@ -41,7 +41,7 @@
#include "compat.h"
#include "metadata.h"
#include "strfctns.h"
-#include "util.h"
+#include "xalloc.h"
extern char *__progname;
extern int vFlag;
Modified: trunk/ezstream/src/playlist.c
===================================================================
--- trunk/ezstream/src/playlist.c 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/src/playlist.c 2007-08-02 18:48:26 UTC (rev 13431)
@@ -33,7 +33,7 @@
#include "compat.h"
#include "playlist.h"
-#include "util.h"
+#include "xalloc.h"
extern char *__progname;
Modified: trunk/ezstream/src/util.c
===================================================================
--- trunk/ezstream/src/util.c 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/src/util.c 2007-08-02 18:48:26 UTC (rev 13431)
@@ -1,130 +1,30 @@
/*
- * Copyright (c) 2007 Moritz Grimm <mdgrimm at gmx.net>
+ * ezstream - source client for Icecast with external en-/decoder support
+ * Copyright (C) 2003, 2004, 2005, 2006 Ed Zaleski <oddsock at oddsock.org>
+ * Copyright (C) 2007 Moritz Grimm <mdgrimm at gmx.net>
*
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
*
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
-#ifdef HAVE_SYS_TYPES_H
-# include <sys/types.h>
-#endif
-#include <errno.h>
-#include <limits.h>
-#include <stdio.h>
-#include <stdlib.h>
#include <string.h>
#include "util.h"
-#ifndef SIZE_T_MAX
-# define SIZE_T_MAX ((size_t)-1)
-#endif
-
-extern char *__progname;
-
-void *
-xmalloc(size_t size)
-{
- void *ret;
-
- if (size == 0) {
- printf("%s: xmalloc(): Internal error: zero size\n",
- __progname);
- abort();
- }
-
- if ((ret = malloc(size)) == NULL) {
- printf("%s: xmalloc(): Allocating %lu bytes: %s\n",
- __progname, (unsigned long)(size), strerror(errno));
- exit(1);
- }
-
- return (ret);
-}
-
-void *
-xcalloc(size_t nmemb, size_t size)
-{
- void *ret;
-
- if (nmemb == 0 || size == 0) {
- printf("%s: xcalloc(): Internal error: zero size\n",
- __progname);
- abort();
- }
-
- if (SIZE_T_MAX / nmemb < size) {
- printf("%s: xcalloc(): Integer overflow: nmemb * size > SIZE_T_MAX\n",
- __progname);
- exit(1);
- }
-
- if ((ret = calloc(nmemb, size)) == NULL) {
- printf("%s: xcalloc(): Allocating %lu bytes: %s\n",
- __progname, (unsigned long)(nmemb * size), strerror(errno));
- exit(1);
- }
-
- return (ret);
-}
-
-void *
-xrealloc(void *ptr, size_t nmemb, size_t size)
-{
- void *ret;
- size_t nsiz = nmemb * size;
-
- if (nmemb == 0 || size == 0) {
- printf("%s: xrealloc(): Internal error: zero size\n",
- __progname);
- abort();
- }
-
- if (SIZE_T_MAX / nmemb < size) {
- printf("%s: xrealloc(): Integer overflow: nmemb * size > SIZE_T_MAX\n",
- __progname);
- exit(1);
- }
-
- if (ptr == NULL)
- ret = malloc(nsiz);
- else
- ret = realloc(ptr, nsiz);
-
- if (ret == NULL) {
- printf("%s: xrealloc(): (Re)allocating %lu bytes: %s\n",
- __progname, (unsigned long)(nmemb * size), strerror(errno));
- exit(1);
- }
-
- return (ret);
-}
-
-char *
-xstrdup(const char *str)
-{
- size_t len;
- char *nstr;
-
- len = strlen(str) + 1;
- nstr = xcalloc(len, sizeof(char));
- memcpy(nstr, str, len);
- return (nstr);
-}
-
int
strrcmp(const char *s, const char *sub)
{
Modified: trunk/ezstream/src/util.h
===================================================================
--- trunk/ezstream/src/util.h 2007-08-02 18:16:54 UTC (rev 13430)
+++ trunk/ezstream/src/util.h 2007-08-02 18:48:26 UTC (rev 13431)
@@ -1,36 +1,25 @@
/*
- * Copyright (c) 2007 Moritz Grimm <mdgrimm at gmx.net>
+ * ezstream - source client for Icecast with external en-/decoder support
+ * Copyright (C) 2003, 2004, 2005, 2006 Ed Zaleski <oddsock at oddsock.org>
+ * Copyright (C) 2007 Moritz Grimm <mdgrimm at gmx.net>
*
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
*
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
#ifndef __UTIL_H__
#define __UTIL_H__
-void * xmalloc(size_t /* size */);
-void * xcalloc(size_t /* nmemb */, size_t /* size */);
-void * xrealloc(void *, size_t /* nmemb */, size_t /* size */);
-char * xstrdup(const char *);
int strrcmp(const char *, const char *);
-#define xfree(ptr) do { \
- if ((ptr) == NULL) { \
- printf("%s: xfree(): Internal error: NULL argument\n", \
- __progname); \
- abort(); \
- } \
- free(ptr); \
- (ptr) = NULL; \
-} while (0)
-
#endif /* __UTIL_H__ */
Copied: trunk/ezstream/src/xalloc.c (from rev 13428, experimental/moritz/xalloc/xalloc.c)
===================================================================
--- trunk/ezstream/src/xalloc.c (rev 0)
+++ trunk/ezstream/src/xalloc.c 2007-08-02 18:48:26 UTC (rev 13431)
@@ -0,0 +1,717 @@
+/*
+ * Copyright (C) 2007 Moritz Grimm <mgrimm at gmx.net>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#ifdef HAVE_SYS_TYPES_H
+# include <sys/types.h>
+#endif
+#include <errno.h>
+#include <limits.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "xalloc.h"
+
+#ifndef SIZE_T_MAX
+# define SIZE_T_MAX ((size_t)-1)
+#endif
+#ifndef va_copy
+# define va_copy(d, s) (d) = (s)
+#endif
+#define XALLOC_DBGLVL_MAX 2
+
+#if defined(XALLOC_DEBUG) && defined(XALLOC_SILENT)
+# undef XALLOC_SILENT
+#endif /* XALLOC_DEBUG && XALLOC_SILENT */
+
+#ifdef THREAD_SAFE
+# include <pthread.h>
+static pthread_mutex_t xalloc_mutex;
+static pthread_mutex_t strerror_mutex;
+# define XALLOC_LOCK(mtx) do { \
+ int error; \
+ if ((error = pthread_mutex_lock(&mtx)) != 0) \
+ _xalloc_error(error, "XALLOC: Internal error in %s:%u: pthread_mutex_lock()", \
+ __FILE__, __LINE__); \
+} while (0)
+# define XALLOC_UNLOCK(mtx) do { \
+ int error; \
+ if ((error = pthread_mutex_unlock(&mtx)) != 0) \
+ _xalloc_error(error, "XALLOC: Internal error in %s:%u: pthread_mutex_unlock()", \
+ __FILE__, __LINE__); \
+} while (0)
+#else
+# define XALLOC_LOCK(mtx) ((void)0)
+# define XALLOC_UNLOCK(mtx) ((void)0)
+#endif /* THREAD_SAFE */
+
+#ifdef XALLOC_DEBUG
+# include <sys/tree.h>
+
+int _memory_cmp(void *, void *);
+
+struct memory {
+ RB_ENTRY(memory) entry;
+ void *ptr;
+ size_t size;
+ const char *allocated_by;
+ unsigned int allocated_in_line;
+ const char *reallocated_by;
+ unsigned int reallocated_in_line;
+ const char *freed_by;
+ unsigned int freed_in_line;
+};
+RB_HEAD(memory_tree, memory) memory_tree_head = RB_INITIALIZER(&memory_tree_head);
+RB_PROTOTYPE(memory_tree, memory, entry, _memory_cmp)
+
+void _memory_free(struct memory **);
+#endif /* XALLOC_DEBUG */
+
+void _xalloc_warn(const char *, ...);
+void _xalloc_error(int, const char *, ...);
+void _xalloc_fatal(const char *, ...);
+void _xalloc_debug_printf(unsigned int, const char *, ...);
+#ifdef XALLOC_WITH_XASPRINTF
+int _xalloc_vasprintf(char **, const char *, va_list, size_t *);
+#endif /* XALLOC_WITH_XASPRINTF */
+
+static unsigned int debug_level = 0;
+static FILE *debug_output = NULL;
+static int xalloc_initialized = 0;
+static size_t xalloc_allocated;
+static size_t xalloc_total;
+static size_t xalloc_peak;
+static size_t xalloc_freed;
+static void * (*real_malloc)(size_t) = NULL;
+static void * (*real_calloc)(size_t, size_t) = NULL;
+static void * (*real_realloc)(void *, size_t) = NULL;
+static const char *unknown_file = "<unknown>";
+
+#ifdef XALLOC_DEBUG
+RB_GENERATE(memory_tree, memory, entry, _memory_cmp)
+
+int
+_memory_cmp(void *arg_a, void *arg_b)
+{
+ struct memory *a = (struct memory *)arg_a;
+ struct memory *b = (struct memory *)arg_b;
+
+ if (a->ptr < b->ptr)
+ return (-1);
+ else if (a->ptr > b->ptr)
+ return (1);
+ return (0);
+}
+
+void
+_memory_free(struct memory **mem_p)
+{
+ struct memory *mem = *mem_p;
+
+ if (mem->allocated_by != NULL)
+ mem->allocated_by = NULL;
+ if (mem->reallocated_by != NULL)
+ mem->reallocated_by = NULL;
+ if (mem->freed_by != NULL)
+ mem->freed_by = NULL;
+ free(mem);
+ *mem_p = NULL;
+}
+#endif /* XALLOC_DEBUG */
+
+void
+_xalloc_warn(const char *fmt, ...)
+{
+ va_list ap;
+
+ if (debug_output == NULL)
+ debug_output = XALLOC_DEFAULT_OUTPUT;
+
+ va_start(ap, fmt);
+#ifndef XALLOC_SILENT
+ vfprintf(debug_output, fmt, ap);
+ fflush(debug_output);
+#endif /* !XALLOC_SILENT */
+ va_end(ap);
+}
+
+void
+_xalloc_error(int errnum, const char *fmt, ...)
+{
+ va_list ap;
+
+ if (debug_output == NULL)
+ debug_output = XALLOC_DEFAULT_OUTPUT;
+
+ va_start(ap, fmt);
+#ifndef XALLOC_SILENT
+ vfprintf(debug_output, fmt, ap);
+ if (errnum > 0) {
+ if (xalloc_initialized)
+ XALLOC_LOCK(strerror_mutex);
+ vfprintf(debug_output, ": %s\n", strerror(errnum));
+ if (xalloc_initialized)
+ XALLOC_UNLOCK(strerror_mutex);
+ }
+ fflush(debug_output);
+#endif /* !XALLOC_SILENT */
+ va_end(ap);
+
+ exit(1);
+}
+
+void
+_xalloc_fatal(const char *fmt, ...)
+{
+ va_list ap;
+
+ if (debug_output == NULL)
+ debug_output = XALLOC_DEFAULT_OUTPUT;
+
+ va_start(ap, fmt);
+#ifndef XALLOC_SILENT
+ vfprintf(debug_output, fmt, ap);
+ fflush(debug_output);
+#endif /* !XALLOC_SILENT */
+ va_end(ap);
+
+ abort();
+}
+
+void
+_xalloc_debug_printf(unsigned int level, const char *fmt, ...)
+{
+ va_list ap;
+
+ if (level > debug_level)
+ return;
+
+ va_start(ap, fmt);
+#ifdef XALLOC_DEBUG
+ vfprintf(debug_output, fmt, ap);
+ fflush(debug_output);
+#endif /* XALLOC_DEBUG */
+ va_end(ap);
+}
+
+#ifdef XALLOC_WITH_XASPRINTF
+int
+_xalloc_vasprintf(char **str_p, const char *fmt, va_list ap, size_t *strsiz)
+{
+ int ret = -1;
+ va_list ap_local;
+
+ *str_p = NULL;
+#ifndef WIN32
+# ifndef HAVE_BROKEN_VSNPRINTF
+
+ /* MODERN UNIX */
+
+ va_copy(ap_local, ap);
+ *strsiz = vsnprintf(NULL, (size_t)0, fmt, ap_local) + 1;
+ va_end(ap_local);
+# ifdef HAVE_ASPRINTF
+ if ((ret = vasprintf(str_p, fmt, ap)) == -1)
+ *str_p = NULL;
+# else
+ if ((*str_p = real_calloc(*strsiz, sizeof(char))) == NULL)
+ return (-1);
+ ret = vsnprintf(*str_p, *strsiz, fmt, ap);
+# endif /* HAVE_ASPRINTF */
+# else
+
+ /* ANCIENT UNIX */
+
+ {
+ char *buf = NULL;
+
+ *strsiz = 4;
+ for (;;) {
+ char *tbuf;
+ int pret;
+
+ if ((tbuf = real_realloc(buf, *strsiz)) == NULL) {
+ free(buf);
+ return (-1);
+ }
+ buf = tbuf;
+ va_copy(ap_local, ap);
+ pret = vsnprintf(buf, *strsiz, fmt, ap_local);
+ va_end(ap_local);
+ if (pret > 0 && pret < (int)*strsiz)
+ break;
+ if ((int)(*strsiz *= 2) < 0) {
+ free(buf);
+ return (-1);
+ }
+ }
+ ret = vsnprintf(buf, *strsiz, fmt, ap);
+ *str_p = buf;
+ }
+# endif /* !HAVE_BROKEN_VSNPRINTF */
+#else
+
+ /* WINDOWS */
+
+ va_copy(ap_local, ap);
+ *strsiz = _vscprintf(fmt, ap_local) + 1;
+ va_end(ap_local);
+ if ((*str_p = real_calloc(*strsiz, sizeof(char))) == NULL)
+ return (-1);
+ ret = _vsnprintf(*str_p, *strsiz, fmt, ap);
+#endif /* !WIN32 */
+
+ return (ret);
+}
+#endif /* XALLOC_WITH_XASPRINTF */
+
+void
+xalloc_initialize_debug(unsigned int level, FILE *output)
+{
+#ifdef THREAD_SAFE
+ int err;
+#endif /* THREAD_SAFE */
+
+ if (xalloc_initialized)
+ _xalloc_fatal("XALLOC: xalloc_initialize(): Xalloc library already initialized\n");
+
+ if ((debug_level = level) > XALLOC_DBGLVL_MAX)
+ debug_level = XALLOC_DBGLVL_MAX;
+ if (output == NULL)
+ debug_output = XALLOC_DEFAULT_OUTPUT;
+ else
+ debug_output = output;
+
+ real_malloc = malloc;
+ real_calloc = calloc;
+ real_realloc = realloc;
+ xalloc_allocated = 0;
+ xalloc_total = 0;
+ xalloc_peak = 0;
+ xalloc_freed = 0;
+
+#ifdef THREAD_SAFE
+ if ((err = pthread_mutex_init(&strerror_mutex, NULL)) != 0)
+ _xalloc_error(err, "XALLOC: xalloc_initialize(): Initializing xalloc_mutex");
+ if ((err = pthread_mutex_init(&xalloc_mutex, NULL)) != 0)
+ _xalloc_error(err, "XALLOC: xalloc_initialize(): Initializing strerror_mutex");
+#endif /* THREAD_SAFE */
+
+ xalloc_initialized = 1;
+}
+
+void
+xalloc_set_functions(void *(*malloc_func)(size_t),
+ void *(*calloc_func)(size_t, size_t),
+ void *(*realloc_func)(void *, size_t))
+{
+ if (!xalloc_initialized)
+ _xalloc_fatal("XALLOC: xalloc_set_functions(): Xalloc library not initialized\n");
+
+ if (malloc_func == NULL ||
+ calloc_func == NULL ||
+ realloc_func == NULL)
+ _xalloc_fatal("XALLOC: xalloc_set_functions(): Bad argument(s)\n");
+
+ XALLOC_LOCK(xalloc_mutex);
+ real_malloc = malloc_func;
+ real_calloc = calloc_func;
+ real_realloc = realloc_func;
+ XALLOC_UNLOCK(xalloc_mutex);
+}
+
+void
+xalloc_shutdown(void)
+{
+ if (!xalloc_initialized)
+ _xalloc_fatal("XALLOC: xalloc_shutdown(): Xalloc library not initialized\n");
+
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ struct memory *mem, *mem_next;
+ size_t leaked_bytes = 0;
+
+ XALLOC_LOCK(xalloc_mutex);
+
+ for (mem = RB_MIN(memory_tree, &memory_tree_head);
+ mem != NULL;
+ mem = mem_next) {
+ mem_next = RB_NEXT(memory_tree, &memory_tree_head, mem);
+ RB_REMOVE(memory_tree, &memory_tree_head, mem);
+
+ if (mem->freed_by == NULL) {
+ _xalloc_debug_printf(1, "XALLOC: MEMORY LEAK (%p): allocated in %s:%u, ",
+ mem->ptr,
+ mem->allocated_by,
+ mem->allocated_in_line);
+ if (mem->reallocated_by != NULL)
+ _xalloc_debug_printf(1, "last reallocated in %s:%u, ",
+ mem->reallocated_by,
+ mem->reallocated_in_line);
+ _xalloc_debug_printf(1, "leaks %lu bytes\n",
+ (unsigned long)mem->size);
+ leaked_bytes += mem->size;
+ free(mem->ptr);
+ }
+
+ _memory_free(&mem);
+ }
+
+ if (leaked_bytes != xalloc_allocated)
+ _xalloc_fatal("XALLOC: Internal error: xalloc_shutdown(): leaked_bytes(%lu) != xalloc_allocated(%lu)\n",
+ (unsigned long)leaked_bytes,
+ (unsigned long)xalloc_allocated);
+
+ _xalloc_debug_printf(1, "XALLOC: STATS: leaked: %lu bytes, peak allocation: %lu bytes (freed/total: %lu/%lu bytes)\n",
+ (unsigned long)xalloc_allocated,
+ (unsigned long)xalloc_peak,
+ (unsigned long)xalloc_freed,
+ (unsigned long)xalloc_total);
+
+ XALLOC_UNLOCK(xalloc_mutex);
+ }
+#endif /* XALLOC_DEBUG */
+
+#ifdef THREAD_SAFE
+ if (pthread_mutex_destroy(&xalloc_mutex) != 0)
+ _xalloc_fatal("XALLOC: Internal error: xalloc_shutdown(): xalloc_mutex %p cannot be destroyed\n",
+ xalloc_mutex);
+ if (pthread_mutex_destroy(&strerror_mutex) != 0)
+ _xalloc_fatal("XALLOC: Internal error: xalloc_shutdown(): strerror_mutex %p cannot be destroyed\n",
+ strerror_mutex);
+#endif /* THREAD_SAFE */
+
+ xalloc_initialized = 0;
+}
+
+void *
+xmalloc_c(size_t size, const char *file, unsigned int line)
+{
+ void *ret;
+
+ if (!xalloc_initialized)
+ _xalloc_fatal("XALLOC: xmalloc(): Xalloc library not initialized\n");
+
+ if (size == 0)
+ _xalloc_fatal("XALLOC: xmalloc(): %s:%u: Zero size\n",
+ file ? file : unknown_file, line);
+
+ if ((ret = real_malloc(size)) == NULL)
+ _xalloc_error(errno, "XALLOC: xmalloc(): %s:%u: Allocating %lu bytes",
+ file ? file : unknown_file, line,
+ (unsigned long)(size));
+
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ struct memory *mem;
+
+ if ((mem = real_calloc(1, sizeof(struct memory))) == NULL)
+ _xalloc_error(errno, "XALLOC: Internal error");
+ mem->ptr = ret;
+ mem->size = size;
+ if (file)
+ mem->allocated_by = file;
+ else
+ mem->allocated_by = unknown_file;
+ mem->allocated_in_line = line;
+ XALLOC_LOCK(xalloc_mutex);
+ RB_INSERT(memory_tree, &memory_tree_head, mem);
+ xalloc_allocated += size;
+ xalloc_total += size;
+ if (xalloc_allocated > xalloc_peak)
+ xalloc_peak = xalloc_allocated;
+ XALLOC_UNLOCK(xalloc_mutex);
+ }
+#endif /* XALLOC_DEBUG */
+
+ return (ret);
+}
+
+void *
+xcalloc_c(size_t nmemb, size_t size, int may_fail,
+ const char *file, unsigned int line)
+{
+ void *ret;
+
+ if (!xalloc_initialized)
+ _xalloc_fatal("XALLOC: xcalloc(): Xalloc library not initialized\n");
+
+ if (nmemb == 0 || size == 0)
+ _xalloc_fatal("XALLOC: xcalloc(): %s:%u: Zero size\n",
+ file ? file : unknown_file, line);
+
+ if (SIZE_T_MAX / nmemb < size)
+ _xalloc_fatal("XALLOC: xcalloc(): %s:%u: Integer overflow (nmemb * size > SIZE_T_MAX)\n",
+ file ? file : unknown_file, line);
+
+ if ((ret = real_calloc(nmemb, size)) == NULL && may_fail == 0)
+ _xalloc_error(errno, "XALLOC: xcalloc(): %s:%u: Allocating %lu bytes",
+ file ? file : unknown_file, line,
+ (unsigned long)(nmemb * size));
+
+#ifdef XALLOC_DEBUG
+ if (ret != NULL && debug_level > 0) {
+ struct memory *mem;
+
+ if ((mem = real_calloc(1, sizeof(struct memory))) == NULL)
+ _xalloc_error(errno, "XALLOC: Internal error");
+ mem->ptr = ret;
+ mem->size = nmemb * size;
+ if (file)
+ mem->allocated_by = file;
+ else
+ mem->allocated_by = unknown_file;
+ mem->allocated_in_line = line;
+ XALLOC_LOCK(xalloc_mutex);
+ RB_INSERT(memory_tree, &memory_tree_head, mem);
+ xalloc_allocated += nmemb * size;
+ xalloc_total += nmemb * size;
+ if (xalloc_allocated > xalloc_peak)
+ xalloc_peak = xalloc_allocated;
+ XALLOC_UNLOCK(xalloc_mutex);
+ }
+#endif /* XALLOC_DEBUG */
+
+ return (ret);
+}
+
+void *
+xrealloc_c(void *ptr, size_t nmemb, size_t size,
+ const char *file, unsigned int line)
+{
+ void *ret;
+ size_t nsiz = nmemb * size;
+#ifdef XALLOC_DEBUG
+ struct memory *mem = NULL;
+#endif /* XALLOC_DEBUG */
+
+ if (!xalloc_initialized)
+ _xalloc_fatal("XALLOC: xrealloc(): Xalloc library not initialized\n");
+
+ if (nmemb == 0 || size == 0)
+ _xalloc_fatal("XALLOC: xrealloc(): %s:%u: Zero size\n",
+ file ? file : unknown_file, line);
+
+ if (SIZE_T_MAX / nmemb < size)
+ _xalloc_fatal("XALLOC: xrealloc(): %s:%u: Integer overflow (nmemb * size > SIZE_T_MAX)\n",
+ file ? file : unknown_file, line);
+
+ if (ptr == NULL) {
+ ret = real_malloc(nsiz);
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ if ((mem = real_calloc(1, sizeof(struct memory))) == NULL)
+ _xalloc_error(errno, "XALLOC: Internal error");
+ mem->ptr = ret;
+ if (file)
+ mem->allocated_by = file;
+ else
+ mem->allocated_by = unknown_file;
+ mem->allocated_in_line = line;
+ }
+#endif /* XALLOC_DEBUG */
+ } else {
+#ifdef XALLOC_DEBUG
+ struct memory find_mem;
+
+ XALLOC_LOCK(xalloc_mutex);
+ if (debug_level > 0) {
+ find_mem.ptr = ptr;
+ if ((mem = RB_FIND(memory_tree, &memory_tree_head, &find_mem)) == NULL)
+ _xalloc_fatal("XALLOC: xrealloc(): %s:%u: Junk pointer %p not accounted for\n",
+ file ? file : unknown_file,
+ line, ptr);
+ RB_REMOVE(memory_tree, &memory_tree_head, mem);
+ }
+ XALLOC_UNLOCK(xalloc_mutex);
+#endif /* XALLOC_DEBUG */
+ ret = real_realloc(ptr, nsiz);
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ mem->ptr = ret;
+ if (file)
+ mem->reallocated_by = file;
+ else
+ mem->reallocated_by = unknown_file;
+ mem->reallocated_in_line = line;
+ }
+#endif /* XALLOC_DEBUG */
+ }
+
+ if (ret == NULL)
+ _xalloc_error(errno, "XALLOC: xrealloc(): %s:%u: (Re)allocating %lu bytes",
+ file ? file : unknown_file, line,
+ (unsigned long)(nmemb * size));
+
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ ssize_t diff = nsiz - mem->size;
+
+ XALLOC_LOCK(xalloc_mutex);
+ xalloc_allocated += diff;
+ if (diff < 0)
+ xalloc_freed += -diff;
+ else
+ xalloc_total += diff;
+ if (xalloc_allocated > xalloc_peak)
+ xalloc_peak = xalloc_allocated;
+ mem->size = nsiz;
+ RB_INSERT(memory_tree, &memory_tree_head, mem);
+ XALLOC_UNLOCK(xalloc_mutex);
+ }
+#endif /* XALLOC_DEBUG */
+
+ return (ret);
+}
+
+char *
+xstrdup_c(const char *str, const char *file, unsigned int line)
+{
+ size_t len;
+ char *nstr;
+
+ if (!xalloc_initialized)
+ _xalloc_fatal("XALLOC: xstrdup(): Xalloc library not initialized\n");
+
+ len = strlen(str) + 1;
+ if ((nstr = xcalloc_c(len, sizeof(char), 0, file, line)) == NULL)
+ _xalloc_error(errno, "XALLOC: xstrdup(): %s:%u: Allocating %lu bytes: %s\n",
+ file ? file : unknown_file, line,
+ (unsigned long)(len));
+ memcpy(nstr, str, len);
+ return (nstr);
+}
+
+void
+xfree_c(void **ptr_p, const char *file, unsigned int line)
+{
+ if (!xalloc_initialized)
+ _xalloc_fatal("XALLOC: xfree(): Xalloc library not initialized\n");
+
+ if (ptr_p == NULL)
+ _xalloc_fatal("XALLOC: xfree(): Bad argument(s)\n");
+
+ if (*ptr_p == NULL) {
+ _xalloc_warn("XALLOC: xfree(): Warning: %s:%u: Freeing NULL pointer\n",
+ file ? file : unknown_file, line);
+ return;
+ }
+
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ struct memory *mem = NULL, find_mem;
+
+ XALLOC_LOCK(xalloc_mutex);
+ find_mem.ptr = *ptr_p;
+ if ((mem = RB_FIND(memory_tree, &memory_tree_head, &find_mem)) == NULL)
+ _xalloc_fatal("XALLOC: xfree(): %s:%u: Junk pointer %p not accounted for\n",
+ file ? file : unknown_file, line,
+ *ptr_p);
+
+ if (mem->freed_by != NULL) {
+ _xalloc_debug_printf(2, "XALLOC: DOUBLE FREE in %s:%u: allocated in %s:%u, ",
+ file ? file : unknown_file, line,
+ mem->allocated_by,
+ mem->allocated_in_line);
+ if (mem->reallocated_by != NULL)
+ _xalloc_debug_printf(2, "last reallocated in %s:%u, ",
+ mem->reallocated_by,
+ mem->reallocated_in_line);
+ _xalloc_debug_printf(2, "already freed in %s:%u\n",
+ mem->freed_by,
+ mem->freed_in_line);
+ abort();
+ }
+
+ xalloc_freed += mem->size;
+ xalloc_allocated -= mem->size;
+ mem->size = 0;
+ if (debug_level > 1) {
+ if (file)
+ mem->freed_by = file;
+ else
+ mem->freed_by = unknown_file;
+ mem->freed_in_line = line;
+ } else {
+ RB_REMOVE(memory_tree, &memory_tree_head, mem);
+ _memory_free(&mem);
+ }
+ XALLOC_UNLOCK(xalloc_mutex);
+ }
+#endif /* XALLOC_DEBUG */
+
+ free(*ptr_p);
+#ifdef XALLOC_DEBUG
+ if (debug_level <= 1)
+#endif /* XALLOC_DEBUG */
+ {
+ *ptr_p = NULL;
+ }
+}
+
+#ifdef XALLOC_WITH_XASPRINTF
+int
+xasprintf_c(const char *file, unsigned int line,
+ char **str_p, const char *fmt, ...)
+{
+ int ret;
+ va_list ap;
+ size_t strsiz = 0;
+
+ if (!xalloc_initialized)
+ _xalloc_fatal("XALLOC: xasprintf(): Xalloc library not initialized\n");
+
+ if (str_p == NULL || fmt == NULL)
+ _xalloc_fatal("XALLOC: xasprintf(): Bad argument(s)\n");
+
+ va_start(ap, fmt);
+ ret = _xalloc_vasprintf(str_p, fmt, ap, &strsiz);
+ va_end(ap);
+ if (ret == -1)
+ _xalloc_error(errno, "XALLOC: xasprintf(): %s:%u: Allocating %lu bytes",
+ file ? file : unknown_file, line, strsiz);
+
+# ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ struct memory *mem;
+
+ if ((mem = real_calloc(1, sizeof(struct memory))) == NULL)
+ _xalloc_error(errno, "XALLOC: Internal error");
+ mem->ptr = *str_p;
+ mem->size = strsiz;
+ if (file)
+ mem->allocated_by = file;
+ else
+ mem->allocated_by = unknown_file;
+ mem->allocated_in_line = line;
+ XALLOC_LOCK(xalloc_mutex);
+ RB_INSERT(memory_tree, &memory_tree_head, mem);
+ xalloc_allocated += strsiz;
+ xalloc_total += strsiz;
+ if (xalloc_allocated > xalloc_peak)
+ xalloc_peak = xalloc_allocated;
+ XALLOC_UNLOCK(xalloc_mutex);
+ }
+# endif /* XALLOC_DEBUG */
+
+ return (ret);
+}
+#endif /* XALLOC_WITH_XASPRINTF */
Copied: trunk/ezstream/src/xalloc.h (from rev 13428, experimental/moritz/xalloc/xalloc.h)
===================================================================
--- trunk/ezstream/src/xalloc.h (rev 0)
+++ trunk/ezstream/src/xalloc.h 2007-08-02 18:48:26 UTC (rev 13431)
@@ -0,0 +1,118 @@
+/*
+ * libxalloc - Portable memory allocation wrapper library, with extensive
+ * error checking, debugging facilities and hooks for 3rd party
+ * memory allocation functions.
+ * This library also detects and prevents double-free errors,
+ * and ensures that out-of-memory issues always cause the
+ * application to exit.
+ *
+ * Copyright (C) 2007 Moritz Grimm <mgrimm at gmx.net>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef __XALLOC_H__
+#define __XALLOC_H__
+
+/*
+ * Define XALLOC_DEBUG to compile the debugging features. Doing so will make
+ * this library more expensive in every case, but not change its (visible)
+ * behavior unless the debugging level is set > 0. The debugging levels are:
+ * 0: disable debugging
+ * 1: enable most debugging features
+ * 2: additionally enable double-free checking
+ * (Warning: This requires libxalloc to keep track of all allocations
+ * and frees, which means that memory usage may increase a lot
+ * over time!)
+ *
+ * Define XALLOC_SILENT to suppress all messages, which makes libxalloc
+ * abort() and exit() silently. This has no effect when THREAD_DEBUG is
+ * defined.
+ *
+ * Define XALLOC_WITH_XASPRINTF to expose the xasprintf() interface. Doing
+ * so will require libxalloc to be compiled with a compiler that supports C99
+ * variadic macros, and work only on systems with vasprintf() or vsnprintf(),
+ * and MS Windows. Note that doing so constitutes an incompatible ABI change!
+ *
+ * Note that none of the x*_c() functions should be used directly, unless it
+ * is ensured that /file/ is a const char * to a real string constant.
+ */
+/* #define XALLOC_DEBUG 1 */
+/* #define XALLOC_SILENT 1 */
+/* #define XALLOC_WITH_XASPRINTF 1 */
+
+/* The default output stream for messages: */
+#define XALLOC_DEFAULT_OUTPUT stderr
+
+#if (defined(_REENTRANT) || defined(_POSIX_THREADS)) && !defined(THREAD_SAFE)
+# define THREAD_SAFE 1
+#endif
+
+
+/*
+ * Library initialization and shutdown.
+ */
+
+#define xalloc_initialize() \
+ xalloc_initialize_debug(0, NULL)
+void xalloc_initialize_debug(unsigned int /* level */,
+ FILE * /* output stream */);
+
+void xalloc_set_functions(void *(*)(size_t) /* malloc function */,
+ void *(*)(size_t, size_t) /* calloc function */,
+ void *(*)(void *, size_t) /* realloc function */);
+
+/* Memory leak checks happen during shutdown! */
+void xalloc_shutdown(void);
+
+
+/*
+ * Memory management functions.
+ * Note that xrealloc() has calloc() semantics, to detect and prevent integer
+ * overflows.
+ */
+
+#define xmalloc(s) \
+ xmalloc_c(s, __FILE__, __LINE__)
+void * xmalloc_c(size_t /* size */,
+ const char * /* file */, unsigned int /* line */);
+
+#define xcalloc(n, s) \
+ xcalloc_c(n, s, 0, __FILE__, __LINE__)
+void * xcalloc_c(size_t /* nmemb */, size_t /* size */, int /* may fail */,
+ const char * /* file */, unsigned int /* line */);
+
+#define xrealloc(p, n, s) \
+ xrealloc_c(p, n, s, __FILE__, __LINE__)
+void * xrealloc_c(void *, size_t /* nmemb */, size_t /* size */,
+ const char * /* file */, unsigned int /* line */);
+
+#define xstrdup(s) \
+ xstrdup_c(s, __FILE__, __LINE__)
+char * xstrdup_c(const char *,
+ const char * /* file */, unsigned int /* line */);
+
+#define xfree(p) \
+ xfree_c((void *)&(p), __FILE__, __LINE__)
+void xfree_c(void **,
+ const char * /* file */, unsigned int /* line */);
+
+#ifdef XALLOC_WITH_XASPRINTF
+# define xasprintf(s, f, ...) \
+ xasprintf_c(__FILE__, __LINE__, s, f, __VA_ARGS__)
+int xasprintf_c(const char * /* file */, unsigned int /* line */,
+ char ** /* string pointer */, const char * /* format */,
+ ...);
+#endif /* XALLOC_WITH_XASPRINTF */
+
+#endif /* __XALLOC_H__ */
More information about the commits
mailing list