diff options
Diffstat (limited to 'src/util/ralloc.c')
| -rw-r--r-- | src/util/ralloc.c | 492 |
1 files changed, 492 insertions, 0 deletions
diff --git a/src/util/ralloc.c b/src/util/ralloc.c new file mode 100644 index 00000000000..36bc61fd075 --- /dev/null +++ b/src/util/ralloc.c @@ -0,0 +1,492 @@ +/* + * Copyright © 2010 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <assert.h> +#include <stdlib.h> +#include <stdarg.h> +#include <stdio.h> +#include <string.h> +#include <stdint.h> + +/* Android defines SIZE_MAX in limits.h, instead of the standard stdint.h */ +#ifdef ANDROID +#include <limits.h> +#endif + +/* Some versions of MinGW are missing _vscprintf's declaration, although they + * still provide the symbol in the import library. */ +#ifdef __MINGW32__ +_CRTIMP int _vscprintf(const char *format, va_list argptr); +#endif + +#include "ralloc.h" + +#ifndef va_copy +#ifdef __va_copy +#define va_copy(dest, src) __va_copy((dest), (src)) +#else +#define va_copy(dest, src) (dest) = (src) +#endif +#endif + +#define CANARY 0x5A1106 + +struct ralloc_header +{ +#ifdef DEBUG + /* A canary value used to determine whether a pointer is ralloc'd. */ + unsigned canary; +#endif + + struct ralloc_header *parent; + + /* The first child (head of a linked list) */ + struct ralloc_header *child; + + /* Linked list of siblings */ + struct ralloc_header *prev; + struct ralloc_header *next; + + void (*destructor)(void *); +}; + +typedef struct ralloc_header ralloc_header; + +static void unlink_block(ralloc_header *info); +static void unsafe_free(ralloc_header *info); + +static ralloc_header * +get_header(const void *ptr) +{ + ralloc_header *info = (ralloc_header *) (((char *) ptr) - + sizeof(ralloc_header)); +#ifdef DEBUG + assert(info->canary == CANARY); +#endif + return info; +} + +#define PTR_FROM_HEADER(info) (((char *) info) + sizeof(ralloc_header)) + +static void +add_child(ralloc_header *parent, ralloc_header *info) +{ + if (parent != NULL) { + info->parent = parent; + info->next = parent->child; + parent->child = info; + + if (info->next != NULL) + info->next->prev = info; + } +} + +void * +ralloc_context(const void *ctx) +{ + return ralloc_size(ctx, 0); +} + +void * +ralloc_size(const void *ctx, size_t size) +{ + void *block = calloc(1, size + sizeof(ralloc_header)); + ralloc_header *info; + ralloc_header *parent; + + if (unlikely(block == NULL)) + return NULL; + info = (ralloc_header *) block; + parent = ctx != NULL ? get_header(ctx) : NULL; + + add_child(parent, info); + +#ifdef DEBUG + info->canary = CANARY; +#endif + + return PTR_FROM_HEADER(info); +} + +void * +rzalloc_size(const void *ctx, size_t size) +{ + void *ptr = ralloc_size(ctx, size); + if (likely(ptr != NULL)) + memset(ptr, 0, size); + return ptr; +} + +/* helper function - assumes ptr != NULL */ +static void * +resize(void *ptr, size_t size) +{ + ralloc_header *child, *old, *info; + + old = get_header(ptr); + info = realloc(old, size + sizeof(ralloc_header)); + + if (info == NULL) + return NULL; + + /* Update parent and sibling's links to the reallocated node. */ + if (info != old && info->parent != NULL) { + if (info->parent->child == old) + info->parent->child = info; + + if (info->prev != NULL) + info->prev->next = info; + + if (info->next != NULL) + info->next->prev = info; + } + + /* Update child->parent links for all children */ + for (child = info->child; child != NULL; child = child->next) + child->parent = info; + + return PTR_FROM_HEADER(info); +} + +void * +reralloc_size(const void *ctx, void *ptr, size_t size) +{ + if (unlikely(ptr == NULL)) + return ralloc_size(ctx, size); + + assert(ralloc_parent(ptr) == ctx); + return resize(ptr, size); +} + +void * +ralloc_array_size(const void *ctx, size_t size, unsigned count) +{ + if (count > SIZE_MAX/size) + return NULL; + + return ralloc_size(ctx, size * count); +} + +void * +rzalloc_array_size(const void *ctx, size_t size, unsigned count) +{ + if (count > SIZE_MAX/size) + return NULL; + + return rzalloc_size(ctx, size * count); +} + +void * +reralloc_array_size(const void *ctx, void *ptr, size_t size, unsigned count) +{ + if (count > SIZE_MAX/size) + return NULL; + + return reralloc_size(ctx, ptr, size * count); +} + +void +ralloc_free(void *ptr) +{ + ralloc_header *info; + + if (ptr == NULL) + return; + + info = get_header(ptr); + unlink_block(info); + unsafe_free(info); +} + +static void +unlink_block(ralloc_header *info) +{ + /* Unlink from parent & siblings */ + if (info->parent != NULL) { + if (info->parent->child == info) + info->parent->child = info->next; + + if (info->prev != NULL) + info->prev->next = info->next; + + if (info->next != NULL) + info->next->prev = info->prev; + } + info->parent = NULL; + info->prev = NULL; + info->next = NULL; +} + +static void +unsafe_free(ralloc_header *info) +{ + /* Recursively free any children...don't waste time unlinking them. */ + ralloc_header *temp; + while (info->child != NULL) { + temp = info->child; + info->child = temp->next; + unsafe_free(temp); + } + + /* Free the block itself. Call the destructor first, if any. */ + if (info->destructor != NULL) + info->destructor(PTR_FROM_HEADER(info)); + + free(info); +} + +void +ralloc_steal(const void *new_ctx, void *ptr) +{ + ralloc_header *info, *parent; + + if (unlikely(ptr == NULL)) + return; + + info = get_header(ptr); + parent = get_header(new_ctx); + + unlink_block(info); + + add_child(parent, info); +} + +void * +ralloc_parent(const void *ptr) +{ + ralloc_header *info; + + if (unlikely(ptr == NULL)) + return NULL; + + info = get_header(ptr); + return info->parent ? PTR_FROM_HEADER(info->parent) : NULL; +} + +static void *autofree_context = NULL; + +static void +autofree(void) +{ + ralloc_free(autofree_context); +} + +void * +ralloc_autofree_context(void) +{ + if (unlikely(autofree_context == NULL)) { + autofree_context = ralloc_context(NULL); + atexit(autofree); + } + return autofree_context; +} + +void +ralloc_set_destructor(const void *ptr, void(*destructor)(void *)) +{ + ralloc_header *info = get_header(ptr); + info->destructor = destructor; +} + +char * +ralloc_strdup(const void *ctx, const char *str) +{ + size_t n; + char *ptr; + + if (unlikely(str == NULL)) + return NULL; + + n = strlen(str); + ptr = ralloc_array(ctx, char, n + 1); + memcpy(ptr, str, n); + ptr[n] = '\0'; + return ptr; +} + +char * +ralloc_strndup(const void *ctx, const char *str, size_t max) +{ + size_t n; + char *ptr; + + if (unlikely(str == NULL)) + return NULL; + + n = strlen(str); + if (n > max) + n = max; + + ptr = ralloc_array(ctx, char, n + 1); + memcpy(ptr, str, n); + ptr[n] = '\0'; + return ptr; +} + +/* helper routine for strcat/strncat - n is the exact amount to copy */ +static bool +cat(char **dest, const char *str, size_t n) +{ + char *both; + size_t existing_length; + assert(dest != NULL && *dest != NULL); + + existing_length = strlen(*dest); + both = resize(*dest, existing_length + n + 1); + if (unlikely(both == NULL)) + return false; + + memcpy(both + existing_length, str, n); + both[existing_length + n] = '\0'; + + *dest = both; + return true; +} + + +bool +ralloc_strcat(char **dest, const char *str) +{ + return cat(dest, str, strlen(str)); +} + +bool +ralloc_strncat(char **dest, const char *str, size_t n) +{ + /* Clamp n to the string length */ + size_t str_length = strlen(str); + if (str_length < n) + n = str_length; + + return cat(dest, str, n); +} + +char * +ralloc_asprintf(const void *ctx, const char *fmt, ...) +{ + char *ptr; + va_list args; + va_start(args, fmt); + ptr = ralloc_vasprintf(ctx, fmt, args); + va_end(args); + return ptr; +} + +/* Return the length of the string that would be generated by a printf-style + * format and argument list, not including the \0 byte. + */ +static size_t +printf_length(const char *fmt, va_list untouched_args) +{ + int size; + char junk; + + /* Make a copy of the va_list so the original caller can still use it */ + va_list args; + va_copy(args, untouched_args); + +#ifdef _WIN32 + /* We need to use _vcsprintf to calculate the size as vsnprintf returns -1 + * if the number of characters to write is greater than count. + */ + size = _vscprintf(fmt, args); + (void)junk; +#else + size = vsnprintf(&junk, 1, fmt, args); +#endif + assert(size >= 0); + + va_end(args); + + return size; +} + +char * +ralloc_vasprintf(const void *ctx, const char *fmt, va_list args) +{ + size_t size = printf_length(fmt, args) + 1; + + char *ptr = ralloc_size(ctx, size); + if (ptr != NULL) + vsnprintf(ptr, size, fmt, args); + + return ptr; +} + +bool +ralloc_asprintf_append(char **str, const char *fmt, ...) +{ + bool success; + va_list args; + va_start(args, fmt); + success = ralloc_vasprintf_append(str, fmt, args); + va_end(args); + return success; +} + +bool +ralloc_vasprintf_append(char **str, const char *fmt, va_list args) +{ + size_t existing_length; + assert(str != NULL); + existing_length = *str ? strlen(*str) : 0; + return ralloc_vasprintf_rewrite_tail(str, &existing_length, fmt, args); +} + +bool +ralloc_asprintf_rewrite_tail(char **str, size_t *start, const char *fmt, ...) +{ + bool success; + va_list args; + va_start(args, fmt); + success = ralloc_vasprintf_rewrite_tail(str, start, fmt, args); + va_end(args); + return success; +} + +bool +ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt, + va_list args) +{ + size_t new_length; + char *ptr; + + assert(str != NULL); + + if (unlikely(*str == NULL)) { + // Assuming a NULL context is probably bad, but it's expected behavior. + *str = ralloc_vasprintf(NULL, fmt, args); + return true; + } + + new_length = printf_length(fmt, args); + + ptr = resize(*str, *start + new_length + 1); + if (unlikely(ptr == NULL)) + return false; + + vsnprintf(ptr + *start, new_length + 1, fmt, args); + *str = ptr; + *start += new_length; + return true; +} |