diff options
author | Vicent Marti <tanoku@gmail.com> | 2011-10-28 15:38:32 -0700 |
---|---|---|
committer | Vicent Marti <tanoku@gmail.com> | 2011-10-28 15:38:32 -0700 |
commit | d78312cddb971477d8008b7b33b0b9e27c8da022 (patch) | |
tree | 5f4f7826fcbbaaa3cc8c832dd4754de76afb5684 | |
parent | 5470aa2507ab77365903ac94e3c3d4898c252fb0 (diff) | |
download | libgit2-halloc.tar.gz |
global: Deploy hallochalloc
-rw-r--r-- | CMakeLists.txt | 4 | ||||
-rw-r--r-- | deps/halloc/align.h | 36 | ||||
-rw-r--r-- | deps/halloc/halloc.c | 211 | ||||
-rw-r--r-- | deps/halloc/halloc.h | 43 | ||||
-rw-r--r-- | deps/halloc/hlist.h | 136 | ||||
-rw-r--r-- | deps/halloc/macros.h | 32 | ||||
-rw-r--r-- | src/util.h | 14 |
7 files changed, 468 insertions, 8 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 7655e0ba5..942ceff5b 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -22,9 +22,9 @@ STRING(REGEX REPLACE "^.*LIBGIT2_VERSION \"[0-9]+\\.[0-9]+\\.([0-9]+).*$" "\\1" 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 000000000..4c6e1831f --- /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 000000000..6431b1bd1 --- /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 000000000..10af4e8d8 --- /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 000000000..2791f78c7 --- /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 000000000..0123d4670 --- /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 fbf9012a3..6b17f4473 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__malloc(size_t len) 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(void *) git__calloc(size_t nelem, size_t elsize) 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 @@ GIT_INLINE(char *) git__strndup(const char *str, size_t n) 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(char *) git__strndup(const char *str, size_t n) 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); |