libvpx: Pull from upstream

source/libvpx/third_party/nestegg/halloc/src/halloc.c

Index: source/libvpx/third_party/nestegg/halloc/src/halloc.c
===================================================================
--- source/libvpx/third_party/nestegg/halloc/src/halloc.c	(revision 278778)
+++ source/libvpx/third_party/nestegg/halloc/src/halloc.c	(working copy)
@@ -1,254 +0,0 @@
-/*
- *	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 "third_party/nestegg/halloc/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)
-
-/*
- *
- */
-realloc_t halloc_allocator = NULL;
-
-#define allocator halloc_allocator
-
-/*
- *	static methods
- */
-static void _set_allocator(void);
-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;
-
-	/* set up default allocator */
-	if (! allocator)
-	{
-		_set_allocator();
-		assert(allocator);
-	}
-
-	/* calloc */
-	if (! ptr)
-	{
-		if (! len)
-			return NULL;
-
-		p = allocator(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 = allocator(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);
-	allocator(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 _set_allocator(void)
-{
-	void * p;
-	assert(! allocator);
-	
-	/*
-	 *	the purpose of the test below is to check the behaviour
-	 *	of realloc(ptr, 0), which is defined in the standard
-	 *	as an implementation-specific. if it returns zero,
-	 *	then it's equivalent to free(). it can however return
-	 *	non-zero, in which case it cannot be used for freeing
-	 *	memory blocks and we'll need to supply our own version
-	 *
-	 *	Thanks to Stan Tobias for pointing this tricky part out.
-	 */
-	allocator = realloc;
-	if (! (p = malloc(1)))
-		/* hmm */
-		return;
-		
-	if ((p = realloc(p, 0)))
-	{
-		/* realloc cannot be used as free() */
-		allocator = _realloc;
-		free(p);
-	}
-}
-
-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);
-		allocator(q, 0);
-	}
-}
-