xref: /external/mesa3d/src/talloc/hieralloc.c

/*
 * Similar core function to LGPL licensed talloc from Samba
 */
#define CHECK_ALLOCATION 0

#include "hieralloc.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#if CHECK_ALLOCATION
#include <set>
#endif

typedef struct hieralloc_header
{
	unsigned beginMagic;
	struct hieralloc_header * parent;
	struct hieralloc_header * nextSibling, * prevSibling;
	struct hieralloc_header * child;
	const char * name;
	unsigned size, childCount, refCount;
	int (* destructor)(void *);
	unsigned endMagic;
} hieralloc_header_t;

#define BEGIN_MAGIC() (13377331)
#define END_MAGIC(header) ((unsigned)((const hieralloc_header_t *)header + 1) % 0x10000 | 0x13370000)

static hieralloc_header_t hieralloc_global_header = {BEGIN_MAGIC(), 0, 0, 0, 0, "hieralloc_hieralloc_global_header", 0, 0 ,1, 0, 0x13370000};

#if CHECK_ALLOCATION
static std::set<void *> allocations;
#endif

#ifdef __cplusplus
extern "C" {
#endif

// Returns 1 if it's a valid header
static inline int check_header(const hieralloc_header_t * header)
{
   if (BEGIN_MAGIC() != header->beginMagic)
      printf("*** hieralloc check_header fail: %p ***\n", header + 1);
	assert(BEGIN_MAGIC() == header->beginMagic);
	if (&hieralloc_global_header == header)
	{
      assert(0x13370000 == header->endMagic);
      return 1;
   }
	assert(END_MAGIC(header) == header->endMagic);
   assert(!header->nextSibling || header->nextSibling->prevSibling == header);
   assert(!header->nextSibling || header->nextSibling->parent == header->parent);
   assert(!header->prevSibling || header->prevSibling->nextSibling == header);
   assert(!header->prevSibling || header->prevSibling->parent == header->parent);
	return 1;
}

static inline hieralloc_header_t * get_header(const void *ptr)
{
	hieralloc_header_t * header = (hieralloc_header_t *)(ptr) - 1;
	check_header(header);
	return header;
}

static void check_children(hieralloc_header_t * header)
{
   check_header(header);
   unsigned childCount = 0;
   hieralloc_header_t * child = header->child;
   while (child)
   {
      childCount++;
      check_children(child);
      child = child->nextSibling;
   }
   assert(childCount == header->childCount);
}


// attach to parent and siblings
static void add_to_parent(hieralloc_header_t * parent, hieralloc_header_t * header)
{
	assert(NULL == header->parent);
	assert(NULL == header->prevSibling);
	assert(NULL == header->nextSibling);

	if (parent->child)
   {
//      hieralloc_header_t * child = parent->child;
//      while (child)
//      {
//         assert(child != header);
//         child = child->nextSibling;
//      }
		parent->child->prevSibling = header;
   }
	header->nextSibling = parent->child;
	header->prevSibling = NULL;
	header->parent = parent;
	parent->child = header;
	parent->childCount++;

   assert(!header->nextSibling || header->nextSibling->prevSibling == header);
   assert(!header->nextSibling || header->nextSibling->parent == header->parent);
   assert(!header->prevSibling || header->prevSibling->nextSibling == header);
   assert(!header->prevSibling || header->prevSibling->parent == header->parent);
}

// detach from parent and siblings
static void remove_from_parent(hieralloc_header_t * header)
{
   hieralloc_header_t * parent = header->parent;
	hieralloc_header_t * sibling = header->prevSibling;
   assert(!header->nextSibling || header->nextSibling->prevSibling == header);
   assert(!header->nextSibling || header->nextSibling->parent == header->parent);
   assert(!header->prevSibling || header->prevSibling->nextSibling == header);
   assert(!header->prevSibling || header->prevSibling->parent == header->parent);
	if (sibling)
	{
      if (sibling->nextSibling != header)
      {
         printf("&sibling->nextSibling=%p &header=%p \n", &sibling->nextSibling, &header);
			printf("sibling->nextSibling=%p header=%p \n", sibling->nextSibling, header);
      }
		sibling->nextSibling = header->nextSibling;
		if (header->nextSibling)
			header->nextSibling->prevSibling = sibling;
		header->prevSibling = NULL;
		header->nextSibling = NULL;
	}
	else
	{
      assert(parent->child == header);
		parent->child = header->nextSibling;
		if (header->nextSibling)
			header->nextSibling->prevSibling = NULL;
		header->nextSibling = NULL;
	}
	header->parent = NULL;
	parent->childCount--;
}

// allocate memory and attach to parent context and siblings
void * hieralloc_allocate(const void * context, unsigned size, const char * name)
{
	hieralloc_header_t * ptr = (hieralloc_header_t *)malloc(size + sizeof(hieralloc_header_t));
	assert(ptr);
	memset(ptr, 0xcd, sizeof(*ptr));
	ptr->beginMagic = BEGIN_MAGIC();
   ptr->parent = ptr->child = ptr->prevSibling = ptr->nextSibling = NULL;
	ptr->name = name;
	ptr->size = size;
	ptr->childCount = 0;
	ptr->refCount = 1;
   ptr->destructor = NULL;
	ptr->endMagic = END_MAGIC(ptr);

	hieralloc_header_t * parent = NULL;
	if (!context)
		parent = &hieralloc_global_header;
	else
		parent = get_header(context);
	add_to_parent(parent, ptr);
#if CHECK_ALLOCATION
   assert(allocations.find(ptr + 1) == allocations.end());
   allocations.insert(ptr + 1);
#endif
	return ptr + 1;
}

// (re)allocate memory and attach to parent context and siblings
void * hieralloc_reallocate(const void * context, void * ptr, unsigned size, const char * name)
{
	if (NULL == ptr)
		return hieralloc_allocate(context, size, name);
#if CHECK_ALLOCATION
   assert(allocations.find(ptr) != allocations.end());
#endif
	if (NULL == context)
		context = &hieralloc_global_header + 1;

	hieralloc_header_t * header = get_header(ptr);
	hieralloc_header_t * parent = header->parent;

	if (get_header(context) != get_header(ptr)->parent)
	{
		remove_from_parent(header);
		parent = get_header(context);
		add_to_parent(parent, header);
	}

	header = (hieralloc_header_t *)realloc(header, size + sizeof(hieralloc_header_t));
	assert(header);
	header->size = size;
	header->name = name;
	if (ptr == (header + 1))
		return ptr; // realloc didn't move allocation

   header->beginMagic = BEGIN_MAGIC();
	header->endMagic = END_MAGIC(header);
   if (header->nextSibling)
      header->nextSibling->prevSibling = header;
	if (header->prevSibling)
		header->prevSibling->nextSibling = header;
	else
		parent->child = header;

	hieralloc_header_t * child = header->child;
	while (child)
	{
		child->parent = header;
		child = child->nextSibling;
	}
#if CHECK_ALLOCATION
   allocations.erase(ptr);
   assert(allocations.find(header + 1) == allocations.end());
   allocations.insert(header + 1);
#endif
	return header + 1;
}

// calls destructor if set, and frees children.
// if destructor returns -1, then do nothing and return -1.
int hieralloc_free(void * ptr)
{
   if (!ptr)
		return 0;

   hieralloc_header_t * header = get_header(ptr);

	header->refCount--;
	if (header->refCount > 0)
		return -1;

	if (header->destructor)
		if (header->destructor(ptr))
			return -1;

   int ret = 0;

	//* TODO: implement reference and steal first
	hieralloc_header_t * child = header->child;
	while (child)
	{
		hieralloc_header_t * current = child;
		assert(!current->prevSibling);
      child = child->nextSibling;
		if (hieralloc_free(current + 1))
		{
			ret = -1;
			remove_from_parent(current);
			add_to_parent(header->parent, current);
         assert(0); // shouldn't happen since reference is always 1
		}

	}

	if (ret)
		return -1;

   assert(0 == header->childCount);
   assert(!header->child);
	remove_from_parent(header);
   memset(header, 0xfe, header->size + sizeof(*header));
#if CHECK_ALLOCATION
   assert(allocations.find(ptr) != allocations.end());
   allocations.erase(ptr);
   // don't free yet to force allocations to new addresses for checking double freeing
#else
   free(header);
#endif
	return 0;
}

// not implemented from talloc_reference
void * hieralloc_reference(const void * ref_ctx, const void * ptr)
{
   return (void *)ptr;
}

// not implemented from talloc_unlink
int hieralloc_unlink(const void * ctx, void *ptr)
{
	if (!ptr)
		return -1;
	//assert(get_header(ptr)->refCount > 0);
	//get_header(ptr)->refCount--;
	return 0;
}

// moves allocation to new parent context; maintain children but update siblings
// returns ptr on success
void * hieralloc_steal(const void * new_ctx, const void * ptr)
{
	hieralloc_header_t * header = get_header(ptr);
	remove_from_parent(header);
	add_to_parent(get_header(new_ctx), header);
	return (void *)ptr;
}

// creates 0 allocation to be used as parent context
void * hieralloc_init(const char * name)
{
	return hieralloc_allocate(NULL, 0, name);
}

// returns global context
void * hieralloc_autofree_context()
{
	return &hieralloc_global_header + 1;
}

// sets destructor to be called before freeing; dctor return -1 aborts free
void hieralloc_set_destructor(const void * ptr, int (* destructor)(void *))
{
	get_header(ptr)->destructor = destructor;
}

// gets parent context of allocated memory
void * hieralloc_parent(const void * ptr)
{
	const hieralloc_header_t * header = get_header(ptr);
	return header->parent + 1;
}

// allocate and zero memory
void * _hieralloc_zero(const void * ctx, unsigned size, const char * name)
{
	void *p = hieralloc_allocate(ctx, size, name);
	if (p)
		memset(p, 0, size);
	return p;
}

// allocate and copy
char * hieralloc_strndup(const void * ctx, const char * str, unsigned len)
{
	if (!str)
		return NULL;

    const char *p = (const char *)memchr(str, '\0', len);
    len = (p ? p - str : len);
    char * ret = (char *)hieralloc_allocate(ctx, len + 1, str);
	if (!ret)
		return NULL;
	memcpy(ret, str, len);
	ret[len] = 0;
   get_header(ret)->name = ret;
	return ret;
}

// allocate and copy
char * hieralloc_strdup(const void * ctx, const char * str)
{
	if (!str)
		return NULL;
	return hieralloc_strndup(ctx, str, strlen(str));
}

static char * _hieralloc_strlendup_append(char * str, unsigned len,
        const char * append, unsigned appendLen)
{
	//char * ret = hieralloc_allocate(str, sizeof(char) * (len + appendLen + 1), str);
	//memcpy(ret, str, len);
	hieralloc_header_t * header = get_header(str);
	char * ret = (char *)hieralloc_reallocate(header->parent + 1, str, sizeof(char) * (len + appendLen + 1), str);
	if (!ret)
		return NULL;
	memcpy(ret + len, append, appendLen);
	ret[len + appendLen] = 0;
	get_header(ret)->name = ret;
	return ret;
}

// reallocate and append
char * hieralloc_strdup_append(char * str, const char * append)
{
	if (!str)
		return hieralloc_strdup(NULL, append);
	if (!append)
		return str;
	return _hieralloc_strlendup_append(str, strlen(str), append, strlen(append));
}

// reallocate and append
char * hieralloc_strndup_append(char * str, const char * append, unsigned len)
{
	if (!str)
		return hieralloc_strdup(NULL, append);
	if (!append)
		return str;
    const char *p = (const char *)memchr(append, '\0', len);
    len = (p ? p - append : len);
	return _hieralloc_strlendup_append(str, strlen(str), append, len);
}

// allocate and vsprintf
char * hieralloc_vasprintf(const void * ctx, const char * fmt, va_list va)
{
	va_list va2;
	va_copy(va2, va);
	char c = 0;
	int len = vsnprintf(&c, 1, fmt, va2); // count how many chars would be printed
	va_end(va2);

	assert(len >= 0); // some vsnprintf may return -1
	if (len < 0)
		return NULL;

	char * ret = (char *)hieralloc_allocate(ctx, len + 1, fmt);
	if (!ret)
		return NULL;

	va_copy(va2, va);
	vsnprintf(ret, len + 1, fmt, va2);
	va_end(va2);

	get_header(ret)->name = ret;
	return ret;
}

// allocate and sprintf
char * hieralloc_asprintf(const void * ctx, const char * fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	char * ret = hieralloc_vasprintf(ctx, fmt, va);
	va_end(va);
	return ret;
}

// reallocate and append vsprintf
char * hieralloc_vasprintf_append(char * str, const char * fmt, va_list va)
{
	if (!str)
		return hieralloc_vasprintf(NULL, fmt, va);

   int len = strlen(str);
   va_list va2;
	va_copy(va2, va);
	char c = 0;
	int appendLen = vsnprintf(&c, 1, fmt, va2); // count how many chars would be printed
	va_end(va2);

	assert(appendLen >= 0); // some vsnprintf may return -1
	if (appendLen < 0)
		return str;
	str = (char *)hieralloc_reallocate(NULL, str, sizeof(char) * (len + appendLen + 1), str);
	if (!str)
		return NULL;

	va_copy(va2, va);
	vsnprintf(str + len, appendLen + 1, fmt, va2);
	va_end(va2);

	get_header(str)->name = str;
	return str;
}

// reallocate and append sprintf
char * hieralloc_asprintf_append(char * str, const char * fmt, ...)
{
	va_list va;
	va_start(va, fmt);
	str = hieralloc_vasprintf_append(str, fmt, va);
	va_end(va);
	return str;
}

static void _hieralloc_report(const hieralloc_header_t * header, FILE * file, unsigned tab)
{
	unsigned i = 0;
	for (i = 0; i < tab; i++)
		fputc(' ', file);
	check_header(header);
	fprintf(file, "%p: child=%d ref=%d size=%d dctor=%p name='%.256s' \n", header + 1,
	        header->childCount, header->refCount, header->size, header->destructor, header->name);
	const hieralloc_header_t * child = header->child;
	while (child)
	{
		_hieralloc_report(child, file, tab + 2);
		child = child->nextSibling;
	}

}

// report self and child allocations
void hieralloc_report(const void * ptr, FILE * file)
{
	if (NULL == ptr)
		ptr = &hieralloc_global_header + 1;
	fputs("hieralloc_report: \n", file);
	_hieralloc_report(get_header(ptr), file, 0);
}

static void _hieralloc_report_brief(const hieralloc_header_t * header, FILE * file, unsigned * data)
{
	check_header(header);
	data[0]++;
	data[1] += header->size;
	data[2] += header->childCount;
	data[3] += header->refCount;
	const hieralloc_header_t * child = header->child;
	while (child)
	{
		_hieralloc_report_brief(child, file, data);
		child = child->nextSibling;
	}
}

void hieralloc_report_brief(const void * ptr, FILE * file)
{
	if (NULL == ptr)
		ptr = &hieralloc_global_header + 1;
	unsigned data [4] = {0};
	_hieralloc_report_brief(get_header(ptr), file, data);
	fprintf(file, "hieralloc_report %p total: count=%d size=%d child=%d ref=%d \n",
		ptr, data[0], data[1], data[2], data[3]);
}

void hieralloc_report_lineage(const void * ptr, FILE * file, int tab)
{
   const hieralloc_header_t * header = get_header(ptr);
   if (header->parent)
      hieralloc_report_lineage(header->parent + 1, file, tab + 2);
   for (tab; tab >=0; tab--)
      fputc(' ', file);
   fprintf(file, "hieralloc_report_lineage %p: size=%d child=%d ref=%d name='%s' parent=%p \n",
      ptr, header->size, header->childCount, header->refCount, header->name, header->parent ? header->parent + 1 : NULL);
}

int hieralloc_find(const void * top, const void * ptr, FILE * file, int tab)
{
   int found = 0;
   if (NULL == top)
      top = &hieralloc_global_header + 1;
   if (0 == tab && file)
      fputs("hieralloc_find start \n", file);
   if (top == ptr)
   {
      if (file)
         fprintf(file, "hieralloc_found %p \n", ptr);
      found++;
   }
   const hieralloc_header_t * start = get_header(top);
   const hieralloc_header_t * child = start->child;
	while (child)
	{
		found += hieralloc_find(child + 1, ptr, file, tab + 2);
		child = child->nextSibling;
	}
   if (0 == tab && file)
      fprintf(file, "hieralloc_find end found=%d \n", found);
   return found;
}

#ifdef __cplusplus
} // extern "C"
#endif