global: Deploy halloc
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 7655e0b..942ceff 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -22,9 +22,9 @@
SET(LIBGIT2_VERSION_STRING "${LIBGIT2_VERSION_MAJOR}.${LIBGIT2_VERSION_MINOR}.${LIBGIT2_VERSION_REV}")
# Find required dependencies
-INCLUDE_DIRECTORIES(src include deps/http-parser)
+INCLUDE_DIRECTORIES(src include deps/http-parser deps/halloc)
-FILE(GLOB SRC_HTTP deps/http-parser/*.c)
+FILE(GLOB SRC_HTTP deps/http-parser/*.c deps/halloc/*.c)
IF (NOT WIN32)
FIND_PACKAGE(ZLIB)
diff --git a/deps/halloc/align.h b/deps/halloc/align.h
new file mode 100644
index 0000000..4c6e183
--- /dev/null
+++ b/deps/halloc/align.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright (c) 2004-2010 Alex Pankratov. All rights reserved.
+ *
+ * Hierarchical memory allocator, 1.2.1
+ * http://swapped.cc/halloc
+ */
+
+/*
+ * The program is distributed under terms of BSD license.
+ * You can obtain the copy of the license by visiting:
+ *
+ * http://www.opensource.org/licenses/bsd-license.php
+ */
+
+#ifndef _LIBP_ALIGN_H_
+#define _LIBP_ALIGN_H_
+
+/*
+ * a type with the most strict alignment requirements
+ */
+union max_align
+{
+ char c;
+ short s;
+ long l;
+ int i;
+ float f;
+ double d;
+ void * v;
+ void (*q)(void);
+};
+
+typedef union max_align max_align_t;
+
+#endif
+
diff --git a/deps/halloc/halloc.c b/deps/halloc/halloc.c
new file mode 100644
index 0000000..6431b1b
--- /dev/null
+++ b/deps/halloc/halloc.c
@@ -0,0 +1,211 @@
+/*
+ * Copyright (c) 2004i-2010 Alex Pankratov. All rights reserved.
+ *
+ * Hierarchical memory allocator, 1.2.1
+ * http://swapped.cc/halloc
+ */
+
+/*
+ * The program is distributed under terms of BSD license.
+ * You can obtain the copy of the license by visiting:
+ *
+ * http://www.opensource.org/licenses/bsd-license.php
+ */
+
+#include <stdlib.h> /* realloc */
+#include <string.h> /* memset & co */
+
+#include "halloc.h"
+#include "align.h"
+#include "hlist.h"
+
+/*
+ * block control header
+ */
+typedef struct hblock
+{
+#ifndef NDEBUG
+#define HH_MAGIC 0x20040518L
+ long magic;
+#endif
+ hlist_item_t siblings; /* 2 pointers */
+ hlist_head_t children; /* 1 pointer */
+ max_align_t data[1]; /* not allocated, see below */
+
+} hblock_t;
+
+#define sizeof_hblock offsetof(hblock_t, data)
+
+/*
+ * static methods
+ */
+static void * _realloc(void * ptr, size_t n);
+
+static int _relate(hblock_t * b, hblock_t * p);
+static void _free_children(hblock_t * p);
+
+/*
+ * Core API
+ */
+void * halloc(void * ptr, size_t len)
+{
+ hblock_t * p;
+
+ /* calloc */
+ if (! ptr)
+ {
+ if (! len)
+ return NULL;
+
+ p = _realloc(0, len + sizeof_hblock);
+ if (! p)
+ return NULL;
+#ifndef NDEBUG
+ p->magic = HH_MAGIC;
+#endif
+ hlist_init(&p->children);
+ hlist_init_item(&p->siblings);
+
+ return p->data;
+ }
+
+ p = structof(ptr, hblock_t, data);
+ assert(p->magic == HH_MAGIC);
+
+ /* realloc */
+ if (len)
+ {
+ p = _realloc(p, len + sizeof_hblock);
+ if (! p)
+ return NULL;
+
+ hlist_relink(&p->siblings);
+ hlist_relink_head(&p->children);
+
+ return p->data;
+ }
+
+ /* free */
+ _free_children(p);
+ hlist_del(&p->siblings);
+ _realloc(p, 0);
+
+ return NULL;
+}
+
+void hattach(void * block, void * parent)
+{
+ hblock_t * b, * p;
+
+ if (! block)
+ {
+ assert(! parent);
+ return;
+ }
+
+ /* detach */
+ b = structof(block, hblock_t, data);
+ assert(b->magic == HH_MAGIC);
+
+ hlist_del(&b->siblings);
+
+ if (! parent)
+ return;
+
+ /* attach */
+ p = structof(parent, hblock_t, data);
+ assert(p->magic == HH_MAGIC);
+
+ /* sanity checks */
+ assert(b != p); /* trivial */
+ assert(! _relate(p, b)); /* heavy ! */
+
+ hlist_add(&p->children, &b->siblings);
+}
+
+/*
+ * malloc/free api
+ */
+void * h_malloc(size_t len)
+{
+ return halloc(0, len);
+}
+
+void * h_calloc(size_t n, size_t len)
+{
+ void * ptr = halloc(0, len*=n);
+ return ptr ? memset(ptr, 0, len) : NULL;
+}
+
+void * h_realloc(void * ptr, size_t len)
+{
+ return halloc(ptr, len);
+}
+
+void h_free(void * ptr)
+{
+ halloc(ptr, 0);
+}
+
+char * h_strdup(const char * str)
+{
+ size_t len = strlen(str);
+ char * ptr = halloc(0, len + 1);
+ return ptr ? (ptr[len] = 0, memcpy(ptr, str, len)) : NULL;
+}
+
+/*
+ * static stuff
+ */
+static void * _realloc(void * ptr, size_t n)
+{
+ /*
+ * free'ing realloc()
+ */
+ if (n)
+ return realloc(ptr, n);
+ free(ptr);
+ return NULL;
+}
+
+static int _relate(hblock_t * b, hblock_t * p)
+{
+ hlist_item_t * i;
+
+ if (!b || !p)
+ return 0;
+
+ /*
+ * since there is no 'parent' pointer, which would've allowed
+ * O(log(n)) upward traversal, the check must use O(n) downward
+ * iteration of the entire hierarchy; and this can be VERY SLOW
+ */
+ hlist_for_each(i, &p->children)
+ {
+ hblock_t * q = structof(i, hblock_t, siblings);
+ if (q == b || _relate(b, q))
+ return 1;
+ }
+ return 0;
+}
+
+static void _free_children(hblock_t * p)
+{
+ hlist_item_t * i, * tmp;
+
+#ifndef NDEBUG
+ /*
+ * this catches loops in hierarchy with almost zero
+ * overhead (compared to _relate() running time)
+ */
+ assert(p && p->magic == HH_MAGIC);
+ p->magic = 0;
+#endif
+ hlist_for_each_safe(i, tmp, &p->children)
+ {
+ hblock_t * q = structof(i, hblock_t, siblings);
+ _free_children(q);
+ _realloc(q, 0);
+ }
+}
+
diff --git a/deps/halloc/halloc.h b/deps/halloc/halloc.h
new file mode 100644
index 0000000..10af4e8
--- /dev/null
+++ b/deps/halloc/halloc.h
@@ -0,0 +1,43 @@
+/*
+ * Copyright (c) 2004-2010 Alex Pankratov. All rights reserved.
+ *
+ * Hierarchical memory allocator, 1.2.1
+ * http://swapped.cc/halloc
+ */
+
+/*
+ * The program is distributed under terms of BSD license.
+ * You can obtain the copy of the license by visiting:
+ *
+ * http://www.opensource.org/licenses/bsd-license.php
+ */
+
+#ifndef _LIBP_HALLOC_H_
+#define _LIBP_HALLOC_H_
+
+#include <stddef.h> /* size_t */
+
+/*
+ * Core API
+ */
+void * halloc (void * block, size_t len);
+void hattach(void * block, void * parent);
+
+/*
+ * standard malloc/free api
+ */
+void * h_malloc (size_t len);
+void * h_calloc (size_t n, size_t len);
+void * h_realloc(void * p, size_t len);
+void h_free (void * p);
+char * h_strdup (const char * str);
+
+/*
+ * the underlying allocator
+ */
+typedef void * (* realloc_t)(void * ptr, size_t len);
+
+extern realloc_t halloc_allocator;
+
+#endif
+
diff --git a/deps/halloc/hlist.h b/deps/halloc/hlist.h
new file mode 100644
index 0000000..2791f78
--- /dev/null
+++ b/deps/halloc/hlist.h
@@ -0,0 +1,136 @@
+/*
+ * Copyright (c) 2004-2010 Alex Pankratov. All rights reserved.
+ *
+ * Hierarchical memory allocator, 1.2.1
+ * http://swapped.cc/halloc
+ */
+
+/*
+ * The program is distributed under terms of BSD license.
+ * You can obtain the copy of the license by visiting:
+ *
+ * http://www.opensource.org/licenses/bsd-license.php
+ */
+
+#ifndef _LIBP_HLIST_H_
+#define _LIBP_HLIST_H_
+
+#include <assert.h>
+#include "macros.h" /* static_inline */
+
+/*
+ * weak double-linked list w/ tail sentinel
+ */
+typedef struct hlist_head hlist_head_t;
+typedef struct hlist_item hlist_item_t;
+
+/*
+ *
+ */
+struct hlist_head
+{
+ hlist_item_t * next;
+};
+
+struct hlist_item
+{
+ hlist_item_t * next;
+ hlist_item_t ** prev;
+};
+
+/*
+ * shared tail sentinel
+ */
+struct hlist_item hlist_null;
+
+/*
+ *
+ */
+#define __hlist_init(h) { &hlist_null }
+#define __hlist_init_item(i) { &hlist_null, &(i).next }
+
+static_inline void hlist_init(hlist_head_t * h);
+static_inline void hlist_init_item(hlist_item_t * i);
+
+/* static_inline void hlist_purge(hlist_head_t * h); */
+
+/* static_inline bool_t hlist_empty(const hlist_head_t * h); */
+
+/* static_inline hlist_item_t * hlist_head(const hlist_head_t * h); */
+
+/* static_inline hlist_item_t * hlist_next(const hlist_item_t * i); */
+/* static_inline hlist_item_t * hlist_prev(const hlist_item_t * i,
+ const hlist_head_t * h); */
+
+static_inline void hlist_add(hlist_head_t * h, hlist_item_t * i);
+
+/* static_inline void hlist_add_prev(hlist_item_t * l, hlist_item_t * i); */
+/* static_inline void hlist_add_next(hlist_item_t * l, hlist_item_t * i); */
+
+static_inline void hlist_del(hlist_item_t * i);
+
+static_inline void hlist_relink(hlist_item_t * i);
+static_inline void hlist_relink_head(hlist_head_t * h);
+
+#define hlist_for_each(i, h) \
+ for (i = (h)->next; i != &hlist_null; i = i->next)
+
+#define hlist_for_each_safe(i, tmp, h) \
+ for (i = (h)->next, tmp = i->next; \
+ i!= &hlist_null; \
+ i = tmp, tmp = i->next)
+
+/*
+ * static
+ */
+static_inline void hlist_init(hlist_head_t * h)
+{
+ assert(h);
+ h->next = &hlist_null;
+}
+
+static_inline void hlist_init_item(hlist_item_t * i)
+{
+ assert(i);
+ i->prev = &i->next;
+ i->next = &hlist_null;
+}
+
+static_inline void hlist_add(hlist_head_t * h, hlist_item_t * i)
+{
+ hlist_item_t * next;
+ assert(h && i);
+
+ next = i->next = h->next;
+ next->prev = &i->next;
+ h->next = i;
+ i->prev = &h->next;
+}
+
+static_inline void hlist_del(hlist_item_t * i)
+{
+ hlist_item_t * next;
+ assert(i);
+
+ next = i->next;
+ next->prev = i->prev;
+ *i->prev = next;
+
+ hlist_init_item(i);
+}
+
+static_inline void hlist_relink(hlist_item_t * i)
+{
+ assert(i);
+ *i->prev = i;
+ i->next->prev = &i->next;
+}
+
+static_inline void hlist_relink_head(hlist_head_t * h)
+{
+ assert(h);
+ h->next->prev = &h->next;
+}
+
+#endif
+
diff --git a/deps/halloc/macros.h b/deps/halloc/macros.h
new file mode 100644
index 0000000..0123d46
--- /dev/null
+++ b/deps/halloc/macros.h
@@ -0,0 +1,32 @@
+/*
+ * Copyright (c) 2004-2010 Alex Pankratov. All rights reserved.
+ *
+ * Hierarchical memory allocator, 1.2.1
+ * http://swapped.cc/halloc
+ */
+
+/*
+ * The program is distributed under terms of BSD license.
+ * You can obtain the copy of the license by visiting:
+ *
+ * http://www.opensource.org/licenses/bsd-license.php
+ */
+
+#ifndef _LIBP_MACROS_H_
+#define _LIBP_MACROS_H_
+
+#include <stddef.h> /* offsetof */
+
+/*
+ restore pointer to the structure by a pointer to its field
+ */
+#define structof(p,t,f) ((t*)(- offsetof(t,f) + (void*)(p)))
+
+/*
+ * redefine for the target compiler
+ */
+#define static_inline static __inline__
+
+
+#endif
+
diff --git a/src/util.h b/src/util.h
index fbf9012..6b17f44 100644
--- a/src/util.h
+++ b/src/util.h
@@ -14,6 +14,8 @@
# define min(a,b) ((a) < (b) ? (a) : (b))
#endif
+#include "halloc.h"
+
/*
* Custom memory allocation wrappers
* that set error code and error message
@@ -21,7 +23,7 @@
*/
GIT_INLINE(void *) git__malloc(size_t len)
{
- void *ptr = malloc(len);
+ void *ptr = halloc(NULL, len);
if (!ptr)
git__throw(GIT_ENOMEM, "Out of memory. Failed to allocate %d bytes.", (int)len);
return ptr;
@@ -29,7 +31,7 @@
GIT_INLINE(void *) git__calloc(size_t nelem, size_t elsize)
{
- void *ptr = calloc(nelem, elsize);
+ void *ptr = h_calloc(nelem, elsize);
if (!ptr)
git__throw(GIT_ENOMEM, "Out of memory. Failed to allocate %d bytes.", (int)elsize);
return ptr;
@@ -37,7 +39,7 @@
GIT_INLINE(char *) git__strdup(const char *str)
{
- char *ptr = strdup(str);
+ char *ptr = h_strdup(str);
if (!ptr)
git__throw(GIT_ENOMEM, "Out of memory. Failed to duplicate string");
return ptr;
@@ -52,7 +54,7 @@
if (n < length)
length = n;
- ptr = (char*)malloc(length + 1);
+ ptr = (char*)halloc(NULL, length + 1);
if (!ptr) {
git__throw(GIT_ENOMEM, "Out of memory. Failed to duplicate string");
return NULL;
@@ -66,13 +68,13 @@
GIT_INLINE(void *) git__realloc(void *ptr, size_t size)
{
- void *new_ptr = realloc(ptr, size);
+ void *new_ptr = halloc(ptr, size);
if (!new_ptr)
git__throw(GIT_ENOMEM, "Out of memory. Failed to allocate %d bytes.", (int)size);
return new_ptr;
}
-#define git__free(ptr) free(ptr)
+#define git__free(ptr) halloc(ptr, 0)
extern int git__prefixcmp(const char *str, const char *prefix);
extern int git__suffixcmp(const char *str, const char *suffix);
