[xiph-commits] r13389 - in experimental/moritz: . compat compat/sys
xalloc
moritz at svn.xiph.org
moritz at svn.xiph.org
Sat Jul 28 17:07:20 PDT 2007
Author: moritz
Date: 2007-07-28 17:07:20 -0700 (Sat, 28 Jul 2007)
New Revision: 13389
Added:
experimental/moritz/compat/
experimental/moritz/compat/sys/
experimental/moritz/compat/sys/tree.h
experimental/moritz/xalloc/
experimental/moritz/xalloc/Makefile
experimental/moritz/xalloc/config.h
experimental/moritz/xalloc/main.c
experimental/moritz/xalloc/xalloc.c
experimental/moritz/xalloc/xalloc.h
Log:
Add libxalloc, based upon ezstream's src/util.*. This is a *alloc() wrapper
library with debugging facilities.
Added: experimental/moritz/compat/sys/tree.h
===================================================================
--- experimental/moritz/compat/sys/tree.h (rev 0)
+++ experimental/moritz/compat/sys/tree.h 2007-07-29 00:07:20 UTC (rev 13389)
@@ -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_ */
Added: experimental/moritz/xalloc/Makefile
===================================================================
--- experimental/moritz/xalloc/Makefile (rev 0)
+++ experimental/moritz/xalloc/Makefile 2007-07-29 00:07:20 UTC (rev 13389)
@@ -0,0 +1,26 @@
+PROG = xalloc-test
+
+SRC = main.c xalloc.c
+OBJ = main.o xalloc.o
+
+CC ?= gcc
+CFLAGS ?= -O2 -pipe
+CFLAGS += -DHAVE_CONFIG_H=1 -fstrict-aliasing -Wall -W -ansi -pedantic -Wwrite-strings -Wpointer-arith
+DEBUG ?= -g -ggdb
+INCLUDEFLAGS = -I../compat
+LDFLAGS =
+
+
+all: depend $(PROG)
+
+depend: $(SRC)
+ $(CC) -M $(CFLAGS) $(INCLUDEFLAGS) $(SRC) > .depend
+
+.c.o: $(SRC)
+ $(CC) $(CFLAGS) $(DEBUG) $(INCLUDEFLAGS) -c $<
+
+$(PROG): $(OBJ)
+ $(CC) $(DEBUG) $(OBJ) $(LDFLAGS) -o $(PROG)
+
+clean:
+ - at rm *.o *~ *.core core .depend $(PROG)
Added: experimental/moritz/xalloc/config.h
===================================================================
--- experimental/moritz/xalloc/config.h (rev 0)
+++ experimental/moritz/xalloc/config.h 2007-07-29 00:07:20 UTC (rev 13389)
@@ -0,0 +1,20 @@
+#if !defined(WIN32)
+
+# define HAVE_SYS_TIME_H 1
+# define HAVE_SYS_TREE_H 1
+# define HAVE_SYS_TYPES_H 1
+# define HAVE_SYS_WAIT_H 1
+# define HAVE_GETTIMEOFDAY 1
+# define HAVE_SETPROCTITLE 1
+# define HAVE_SIGNAL_H 1
+# define HAVE_STDINT_H 1
+# define HAVE_UNISTD_H 1
+
+#else
+
+# define HAVE_SYS_TIMEB_H 1
+# define HAVE_FTIME 1
+# define HAVE_SIGNAL_H 1
+# define HAVE_WINDOWS_H 1
+
+#endif /* !WIN32 */
Added: experimental/moritz/xalloc/main.c
===================================================================
--- experimental/moritz/xalloc/main.c (rev 0)
+++ experimental/moritz/xalloc/main.c 2007-07-29 00:07:20 UTC (rev 13389)
@@ -0,0 +1,34 @@
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#ifdef HAVE_SYS_TYPES_H
+# include <sys/types.h>
+#endif
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "xalloc.h"
+
+int
+main(void)
+{
+ char *foo, *bar, *baz;
+
+#ifdef XALLOC_DEBUG
+ xalloc_initialize_debug(2, NULL);
+#else
+ xalloc_initialize();
+#endif
+
+ foo = xstrdup("FooFooFooFooFoo!");
+ bar = xcalloc(12, sizeof(char));
+ baz = xmalloc(80);
+ baz = xrealloc(baz, 100, sizeof(char));
+ xfree(foo);
+ xfree(baz);
+
+ xalloc_shutdown();
+
+ return (0);
+}
Added: experimental/moritz/xalloc/xalloc.c
===================================================================
--- experimental/moritz/xalloc/xalloc.c (rev 0)
+++ experimental/moritz/xalloc/xalloc.c 2007-07-29 00:07:20 UTC (rev 13389)
@@ -0,0 +1,663 @@
+/*
+ * 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 XALLOC_DEBUG
+# ifdef HAVE_SYS_TREE_H
+# include <sys/tree.h>
+# else
+# include "compat/sys/tree.h"
+# endif
+
+int _memory_cmp(void *, void *);
+
+struct memory {
+ RB_ENTRY(memory) entry;
+ void *ptr;
+ size_t size;
+ char *allocated_by;
+ unsigned int allocated_in_line;
+ char *reallocated_by;
+ unsigned int reallocated_in_line;
+ char *freed_by;
+ unsigned int freed_in_line;
+};
+RB_HEAD(memory_tree, memory) memory_tree_head = RB_INITIALIZER(&memory_tree_head);
+RB_GENERATE(memory_tree, memory, entry, _memory_cmp)
+
+void _memory_free(struct memory **);
+#else
+void xalloc_initialize_debug(unsigned int, FILE *);
+void _xalloc_warn(const char *, ...);
+#endif /* XALLOC_DEBUG */
+
+void _xalloc_error(const char *, ...);
+void _xalloc_fatal(const char *, ...);
+void _xalloc_debug_printf(unsigned int, const char *, ...);
+char * _xalloc_strdup(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_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;
+
+#ifdef XALLOC_DEBUG
+int
+_memory_cmp(void *arg_a, void *arg_b)
+{
+ struct memory *a = (struct memory *)arg_a;
+ struct memory *b = (struct memory *)arg_b;
+
+ return ((int)a->ptr - (int)b->ptr);
+}
+
+void
+_memory_free(struct memory **mem_p)
+{
+ struct memory *mem = *mem_p;
+
+ if (mem->allocated_by != NULL) {
+ free(mem->allocated_by);
+ mem->allocated_by = NULL;
+ }
+ if (mem->reallocated_by != NULL) {
+ free(mem->reallocated_by);
+ mem->reallocated_by = NULL;
+ }
+ if (mem->freed_by != NULL) {
+ free(mem->freed_by);
+ mem->freed_by = NULL;
+ }
+ free(mem);
+ mem = 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(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);
+
+ 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);
+}
+
+char *
+_xalloc_strdup(const char *str)
+{
+ size_t len;
+ char *nstr;
+
+ len = strlen(str) + 1;
+ if ((nstr = real_calloc(len, sizeof(char))) == NULL)
+ return (NULL);
+ memcpy(nstr, str, len);
+ return (nstr);
+}
+
+#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(void)
+{
+ if (xalloc_initialized)
+ _xalloc_fatal("XALLOC: xalloc_initialize(): Xalloc library already initialized\n");
+
+ real_malloc = malloc;
+ real_calloc = calloc;
+ real_realloc = realloc;
+ xalloc_allocated = 0;
+ xalloc_peak = 0;
+ xalloc_freed = 0;
+
+ xalloc_initialized = 1;
+}
+
+void
+xalloc_initialize_debug(unsigned int level, FILE *output)
+{
+ 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;
+
+ xalloc_initialize();
+}
+
+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");
+
+ real_malloc = malloc_func;
+ real_calloc = calloc_func;
+ real_realloc = realloc_func;
+}
+
+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;
+
+ 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: %lu bytes)\n",
+ (unsigned long)xalloc_allocated,
+ (unsigned long)xalloc_peak,
+ (unsigned long)xalloc_freed);
+ }
+#endif /* XALLOC_DEBUG */
+
+ 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, line);
+
+ if ((ret = real_malloc(size)) == NULL)
+ _xalloc_error("XALLOC: xmalloc(): %s:%u: Allocating %lu bytes: %s\n",
+ file, line, (unsigned long)(size),
+ strerror(errno));
+
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ struct memory *mem;
+
+ if ((mem = real_calloc(1, sizeof(struct memory))) == NULL)
+ _xalloc_error("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->ptr = ret;
+ mem->size = size;
+ if ((mem->allocated_by = _xalloc_strdup(file)) == NULL)
+ _xalloc_error("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->allocated_in_line = line;
+ RB_INSERT(memory_tree, &memory_tree_head, mem);
+ xalloc_allocated += size;
+ if (xalloc_allocated > xalloc_peak)
+ xalloc_peak = xalloc_allocated;
+ }
+#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, line);
+
+ if (SIZE_T_MAX / nmemb < size)
+ _xalloc_fatal("XALLOC: xcalloc(): %s:%u: Integer overflow (nmemb * size > SIZE_T_MAX)\n",
+ file, line);
+
+ if ((ret = real_calloc(nmemb, size)) == NULL && may_fail == 0)
+ _xalloc_error("XALLOC: xcalloc(): %s:%u: Allocating %lu bytes: %s\n",
+ file, line, (unsigned long)(nmemb * size),
+ strerror(errno));
+
+#ifdef XALLOC_DEBUG
+ if (ret != NULL && debug_level > 0) {
+ struct memory *mem;
+
+ if ((mem = real_calloc(1, sizeof(struct memory))) == NULL)
+ _xalloc_error("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->ptr = ret;
+ mem->size = nmemb * size;
+ if ((mem->allocated_by = _xalloc_strdup(file)) == NULL)
+ _xalloc_error("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->allocated_in_line = line;
+ RB_INSERT(memory_tree, &memory_tree_head, mem);
+ xalloc_allocated += nmemb * size;
+ if (xalloc_allocated > xalloc_peak)
+ xalloc_peak = xalloc_allocated;
+ }
+#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, line);
+
+ if (SIZE_T_MAX / nmemb < size)
+ _xalloc_fatal("XALLOC: xrealloc(): %s:%u: Integer overflow (nmemb * size > SIZE_T_MAX)\n",
+ 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("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->ptr = ret;
+ if ((mem->allocated_by = _xalloc_strdup(file)) == NULL)
+ _xalloc_error("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->allocated_in_line = line;
+ }
+#endif /* XALLOC_DEBUG */
+ } else {
+#ifdef XALLOC_DEBUG
+ struct memory find_mem;
+
+ 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, line, ptr);
+ RB_REMOVE(memory_tree, &memory_tree_head, mem);
+ }
+#endif /* XALLOC_DEBUG */
+ ret = real_realloc(ptr, nsiz);
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ mem->ptr = ret;
+ if (mem->reallocated_by != NULL) {
+ free(mem->reallocated_by);
+ mem->reallocated_by = NULL;
+ }
+ if ((mem->reallocated_by = _xalloc_strdup(file)) == NULL)
+ _xalloc_error("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->reallocated_in_line = line;
+ }
+#endif /* XALLOC_DEBUG */
+ }
+
+ if (ret == NULL)
+ _xalloc_error("XALLOC: xrealloc(): %s:%u: (Re)allocating %lu bytes: %s\n",
+ file, line, (unsigned long)(nmemb * size),
+ strerror(errno));
+
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ xalloc_allocated -= mem->size;
+ xalloc_allocated += nsiz;
+ if (xalloc_allocated > xalloc_peak)
+ xalloc_peak = xalloc_allocated;
+ mem->size = nsiz;
+ RB_INSERT(memory_tree, &memory_tree_head, mem);
+ }
+#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("XALLOC: xstrdup(): %s:%u: Allocating %lu bytes: %s\n",
+ file, line, (unsigned long)(len),
+ strerror(errno));
+ memcpy(nstr, str, len);
+ return (nstr);
+}
+
+#ifdef XALLOC_DEBUG
+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, line);
+ return;
+ }
+
+ if (debug_level > 0) {
+ struct memory *mem = NULL, find_mem;
+
+ 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, line, *ptr_p);
+
+ if (mem->freed_by != NULL) {
+ _xalloc_debug_printf(2, "XALLOC: DOUBLE FREE in %s:%u: allocated in %s:%u, ",
+ 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 ((mem->freed_by = _xalloc_strdup(file)) == NULL)
+ _xalloc_error("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->freed_in_line = line;
+ } else {
+ RB_REMOVE(memory_tree, &memory_tree_head, mem);
+ _memory_free(&mem);
+ }
+ }
+
+ free(*ptr_p);
+ if (debug_level <= 1)
+ *ptr_p = NULL;
+}
+#endif /* XALLOC_DEBUG */
+
+#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: xfree(): Xalloc library not initialized\n");
+
+ if (str_p == NULL || fmt == NULL)
+ _xalloc_fatal("XALLOC: xfree(): Bad argument(s)\n");
+
+ va_start(ap, fmt);
+ ret = _xalloc_vasprintf(str_p, fmt, ap, &strsiz);
+ va_end(ap);
+ if (ret == -1)
+ _xalloc_error("XALLOC: xasprintf(): %s:%u: Allocating %lu bytes: %s\n",
+ file, line, strsiz, strerror(errno));
+
+#ifdef XALLOC_DEBUG
+ if (debug_level > 0) {
+ struct memory *mem;
+
+ if ((mem = real_calloc(1, sizeof(struct memory))) == NULL)
+ _xalloc_error("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->ptr = *str_p;
+ mem->size = strsiz;
+ if ((mem->allocated_by = _xalloc_strdup(file)) == NULL)
+ _xalloc_error("XALLOC: Internal error: %s\n",
+ strerror(errno));
+ mem->allocated_in_line = line;
+ RB_INSERT(memory_tree, &memory_tree_head, mem);
+ xalloc_allocated += strsiz;
+ if (xalloc_allocated > xalloc_peak)
+ xalloc_peak = xalloc_allocated;
+ }
+#endif /* XALLOC_DEBUG */
+
+ return (ret);
+}
+#endif /* XALLOC_WITH_XASPRINTF */
Added: experimental/moritz/xalloc/xalloc.h
===================================================================
--- experimental/moritz/xalloc/xalloc.h (rev 0)
+++ experimental/moritz/xalloc/xalloc.h 2007-07-29 00:07:20 UTC (rev 13389)
@@ -0,0 +1,125 @@
+/*
+ * 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 and expose the
+ * xalloc_initialize_debug() interface. 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 C99 compiler, and work
+ * only on systems with (v)asprintf() or a modern (v)snprintf(). MS Windows
+ * is supported.
+ */
+/* #define XALLOC_DEBUG 1 */
+/* #define XALLOC_SILENT 1 */
+/* #define XALLOC_WITH_XASPRINTF 1 */
+
+/* The default output stream for messages: */
+#define XALLOC_DEFAULT_OUTPUT stderr
+
+
+/*
+ * Library initialization and shutdown.
+ */
+
+void xalloc_initialize(void);
+
+#ifdef XALLOC_DEBUG
+void xalloc_initialize_debug(unsigned int /* level */,
+ FILE * /* output stream */);
+#endif /* XALLOC_DEBUG */
+
+void xalloc_set_functions(void *(*)(size_t) /* malloc function */,
+ void *(*)(size_t, size_t) /* calloc function */,
+ void *(*)(void *, size_t) /* realloc function */);
+
+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 */);
+
+#ifdef XALLOC_DEBUG
+# define xfree(p) \
+ xfree_c((void *)&(p), __FILE__, __LINE__)
+void xfree_c(void **,
+ const char * /* file */, unsigned int /* line */);
+#else /* XALLOC_DEBUG */
+void _xalloc_warn(const char *, ...);
+
+# define xfree(p) \
+do { \
+ if ((p) == NULL) { \
+ _xalloc_warn("XALLOC: xfree(): Warning: Freeing NULL pointer\n"); \
+ break; \
+ } \
+ free(p); \
+ (p) = NULL; \
+} while (0)
+#endif /* XALLOC_DEBUG */
+
+#ifdef XALLOC_WITH_XASPRINTF
+# define xasprintf(s, f, va...) \
+ xasprintf_c(__FILE__, __LINE__, s, f , ##va)
+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