diff options
Diffstat (limited to 'src/pool.c')
-rw-r--r-- | src/pool.c | 294 |
1 files changed, 294 insertions, 0 deletions
diff --git a/src/pool.c b/src/pool.c new file mode 100644 index 000000000..641292d06 --- /dev/null +++ b/src/pool.c @@ -0,0 +1,294 @@ +#include "pool.h" +#ifndef GIT_WIN32 +#include <unistd.h> +#endif + +struct git_pool_page { + git_pool_page *next; + uint32_t size; + uint32_t avail; + char data[GIT_FLEX_ARRAY]; +}; + +#define GIT_POOL_MIN_USABLE 4 +#define GIT_POOL_MIN_PAGESZ 2 * sizeof(void*) + +static void *pool_alloc_page(git_pool *pool, uint32_t size); +static void pool_insert_page(git_pool *pool, git_pool_page *page); + +int git_pool_init( + git_pool *pool, uint32_t item_size, uint32_t items_per_page) +{ + assert(pool); + + if (!item_size) + item_size = 1; + /* round up item_size for decent object alignment */ + if (item_size > 4) + item_size = (item_size + 7) & ~7; + else if (item_size == 3) + item_size = 4; + + if (!items_per_page) + items_per_page = git_pool__suggest_items_per_page(item_size); + if (item_size * items_per_page < GIT_POOL_MIN_PAGESZ) + items_per_page = (GIT_POOL_MIN_PAGESZ + item_size - 1) / item_size; + + memset(pool, 0, sizeof(git_pool)); + pool->item_size = item_size; + pool->page_size = item_size * items_per_page; + + return 0; +} + +void git_pool_clear(git_pool *pool) +{ + git_pool_page *scan, *next; + + for (scan = pool->open; scan != NULL; scan = next) { + next = scan->next; + git__free(scan); + } + pool->open = NULL; + + for (scan = pool->full; scan != NULL; scan = next) { + next = scan->next; + git__free(scan); + } + pool->full = NULL; + + pool->free_list = NULL; + + pool->items = 0; + + pool->has_string_alloc = 0; + pool->has_multi_item_alloc = 0; + pool->has_large_page_alloc = 0; +} + +void git_pool_swap(git_pool *a, git_pool *b) +{ + git_pool temp; + + if (a == b) + return; + + memcpy(&temp, a, sizeof(temp)); + memcpy(a, b, sizeof(temp)); + memcpy(b, &temp, sizeof(temp)); +} + +static void pool_insert_page(git_pool *pool, git_pool_page *page) +{ + git_pool_page *scan; + + /* If there are no open pages or this page has the most open space, + * insert it at the beginning of the list. This is the common case. + */ + if (pool->open == NULL || pool->open->avail < page->avail) { + page->next = pool->open; + pool->open = page; + return; + } + + /* Otherwise insert into sorted position. */ + for (scan = pool->open; + scan->next && scan->next->avail > page->avail; + scan = scan->next); + page->next = scan->next; + scan->next = page; +} + +static void *pool_alloc_page(git_pool *pool, uint32_t size) +{ + git_pool_page *page; + uint32_t alloc_size; + + if (size <= pool->page_size) + alloc_size = pool->page_size; + else { + alloc_size = size; + pool->has_large_page_alloc = 1; + } + + page = git__calloc(1, alloc_size + sizeof(git_pool_page)); + if (!page) + return NULL; + + page->size = alloc_size; + page->avail = alloc_size - size; + + if (page->avail > 0) + pool_insert_page(pool, page); + else { + page->next = pool->full; + pool->full = page; + } + + pool->items++; + + return page->data; +} + +GIT_INLINE(void) pool_remove_page( + git_pool *pool, git_pool_page *page, git_pool_page *prev) +{ + if (prev == NULL) + pool->open = page->next; + else + prev->next = page->next; +} + +void *git_pool_malloc(git_pool *pool, uint32_t items) +{ + git_pool_page *scan = pool->open, *prev; + uint32_t size = items * pool->item_size; + void *ptr = NULL; + + pool->has_string_alloc = 0; + if (items > 1) + pool->has_multi_item_alloc = 1; + else if (pool->free_list != NULL) { + ptr = pool->free_list; + pool->free_list = *((void **)pool->free_list); + return ptr; + } + + /* just add a block if there is no open one to accomodate this */ + if (size >= pool->page_size || !scan || scan->avail < size) + return pool_alloc_page(pool, size); + + pool->items++; + + /* find smallest block in free list with space */ + for (scan = pool->open, prev = NULL; + scan->next && scan->next->avail >= size; + prev = scan, scan = scan->next); + + /* allocate space from the block */ + ptr = &scan->data[scan->size - scan->avail]; + scan->avail -= size; + + /* move to full list if there is almost no space left */ + if (scan->avail < pool->item_size || scan->avail < GIT_POOL_MIN_USABLE) { + pool_remove_page(pool, scan, prev); + scan->next = pool->full; + pool->full = scan; + } + /* reorder list if block is now smaller than the one after it */ + else if (scan->next != NULL && scan->next->avail > scan->avail) { + pool_remove_page(pool, scan, prev); + pool_insert_page(pool, scan); + } + + return ptr; +} + +char *git_pool_strndup(git_pool *pool, const char *str, size_t n) +{ + void *ptr = NULL; + + assert(pool && str && pool->item_size == sizeof(char)); + + if ((ptr = git_pool_malloc(pool, (uint32_t)(n + 1))) != NULL) { + memcpy(ptr, str, n); + *(((char *)ptr) + n) = '\0'; + } + pool->has_string_alloc = 1; + + return ptr; +} + +char *git_pool_strdup(git_pool *pool, const char *str) +{ + assert(pool && str && pool->item_size == sizeof(char)); + + return git_pool_strndup(pool, str, strlen(str)); +} + +char *git_pool_strcat(git_pool *pool, const char *a, const char *b) +{ + void *ptr; + size_t len_a, len_b; + + assert(pool && a && b && pool->item_size == sizeof(char)); + + len_a = a ? strlen(a) : 0; + len_b = b ? strlen(b) : 0; + + if ((ptr = git_pool_malloc(pool, (uint32_t)(len_a + len_b + 1))) != NULL) { + if (len_a) + memcpy(ptr, a, len_a); + if (len_b) + memcpy(((char *)ptr) + len_a, b, len_b); + *(((char *)ptr) + len_a + len_b) = '\0'; + } + pool->has_string_alloc = 1; + + return ptr; +} + +void git_pool_free(git_pool *pool, void *ptr) +{ + assert(pool && ptr && pool->item_size >= sizeof(void*)); + + *((void **)ptr) = pool->free_list; + pool->free_list = ptr; +} + +uint32_t git_pool__open_pages(git_pool *pool) +{ + uint32_t ct = 0; + git_pool_page *scan; + for (scan = pool->open; scan != NULL; scan = scan->next) ct++; + return ct; +} + +uint32_t git_pool__full_pages(git_pool *pool) +{ + uint32_t ct = 0; + git_pool_page *scan; + for (scan = pool->full; scan != NULL; scan = scan->next) ct++; + return ct; +} + +bool git_pool__ptr_in_pool(git_pool *pool, void *ptr) +{ + git_pool_page *scan; + for (scan = pool->open; scan != NULL; scan = scan->next) + if ((void *)scan->data <= ptr && + (void *)(((char *)scan->data) + scan->size) > ptr) + return true; + for (scan = pool->full; scan != NULL; scan = scan->next) + if ((void *)scan->data <= ptr && + (void *)(((char *)scan->data) + scan->size) > ptr) + return true; + return false; +} + +uint32_t git_pool__system_page_size(void) +{ + static uint32_t size = 0; + + if (!size) { +#ifdef GIT_WIN32 + SYSTEM_INFO info; + GetSystemInfo(&info); + size = (uint32_t)info.dwPageSize; +#else + size = (uint32_t)sysconf(_SC_PAGE_SIZE); +#endif + + size -= 2 * sizeof(void *); /* allow space for malloc overhead */ + } + + return size; +} + +uint32_t git_pool__suggest_items_per_page(uint32_t item_size) +{ + uint32_t page_bytes = + git_pool__system_page_size() - sizeof(git_pool_page); + return page_bytes / item_size; +} + |