pool: Simplify implementation

1 files changed, 33 insertions, 189 deletions

diff --git a/src/pool.c b/src/pool.c
index c93d78182..78277eb40 100644
--- a/src/pool.c
+++ b/src/pool.c
@@ -8,67 +8,49 @@ struct git_pool_page {
 	git_pool_page *next;
 	uint32_t size;
 	uint32_t avail;
-	GIT_ALIGN(char data[GIT_FLEX_ARRAY], 8);
+	char data[GIT_FLEX_ARRAY];
 };
 
-struct pool_freelist {
-	struct pool_freelist *next;
-};
+static void *pool_alloc_page(git_pool *pool, uint32_t size);
 
-#define GIT_POOL_MIN_USABLE	4
-#define GIT_POOL_MIN_PAGESZ	2 * sizeof(void*)
+uint32_t git_pool__system_page_size(void)
+{
+	static uint32_t size = 0;
 
-static void *pool_alloc_page(git_pool *pool, uint32_t size);
-static void pool_insert_page(git_pool *pool, git_pool_page *page);
+	if (!size) {
+		size_t page_size;
+		if (git__page_size(&page_size) < 0)
+			page_size = 4096;
+		size = page_size - 2 * sizeof(void *); /* allow space for malloc overhead */
+	}
 
-int git_pool_init(
-	git_pool *pool, uint32_t item_size, uint32_t items_per_page)
+	return size;
+}
+
+void git_pool_init(git_pool *pool, uint32_t item_size)
 {
+	const uint32_t align_size = sizeof(void *) - 1;
 	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;
+	if (item_size > 1)
+		item_size = (item_size + align_size) & ~align_size;
 
 	memset(pool, 0, sizeof(git_pool));
 	pool->item_size = item_size;
-	pool->page_size = item_size * items_per_page;
-
-	return 0;
+	pool->page_size = git_pool__system_page_size();
 }
 
 void git_pool_clear(git_pool *pool)
 {
 	git_pool_page *scan, *next;
 
-	for (scan = pool->open; scan != NULL; scan = next) {
+	for (scan = pool->pages; 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->pages = 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)
@@ -83,110 +65,40 @@ void git_pool_swap(git_pool *a, git_pool *b)
 	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 new_page_size;
+	const uint32_t new_page_size = (size <= pool->page_size) ? pool->page_size : size;
 	size_t alloc_size;
 
-	if (size <= pool->page_size)
-		new_page_size = pool->page_size;
-	else {
-		new_page_size = size;
-		pool->has_large_page_alloc = 1;
-	}
-
 	if (GIT_ADD_SIZET_OVERFLOW(&alloc_size, new_page_size, sizeof(git_pool_page)) ||
 		!(page = git__calloc(1, alloc_size)))
 		return NULL;
 
-	page->size  = new_page_size;
+	page->size = new_page_size;
 	page->avail = new_page_size - size;
+	page->next = pool->pages;
 
-	if (page->avail > 0)
-		pool_insert_page(pool, page);
-	else {
-		page->next = pool->full;
-		pool->full = page;
-	}
-
+	pool->pages = 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) + 7) & ~7;
-	void *ptr = NULL;
+	const uint32_t size = items * pool->item_size;
 
-	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 = ((struct pool_freelist *)pool->free_list)->next;
-		return ptr;
-	}
+	git_pool_page *page = pool->pages;
+	void *ptr = NULL;
 
-	/* just add a block if there is no open one to accommodate this */
-	if (size >= pool->page_size || !scan || scan->avail < size)
+	if (!page || page->avail < size)
 		return pool_alloc_page(pool, size);
 
+	ptr = &page->data[page->size - page->avail];
+	page->avail -= 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;
 }
 
@@ -204,15 +116,12 @@ char *git_pool_strndup(git_pool *pool, const char *str, size_t n)
 		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));
 }
 
@@ -238,88 +147,23 @@ char *git_pool_strcat(git_pool *pool, const char *a, const char *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)
-{
-	struct pool_freelist *item = ptr;
-
-	assert(pool && pool->item_size >= sizeof(void*));
-
-	if (item) {
-		item->next = pool->free_list;
-		pool->free_list = item;
-	}
-}
-
-void git_pool_free_array(git_pool *pool, size_t count, void **ptrs)
-{
-	struct pool_freelist **items = (struct pool_freelist **)ptrs;
-	size_t i;
-
-	assert(pool && ptrs && pool->item_size >= sizeof(void*));
-
-	if (!count)
-		return;
-
-	for (i = count - 1; i > 0; --i)
-		items[i]->next = items[i - 1];
-
-	items[i]->next  = pool->free_list;
-	pool->free_list = items[count - 1];
-}
-
 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++;
+	for (scan = pool->pages; 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)
+	for (scan = pool->pages; 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) {
-		size_t page_size;
-		if (git__page_size(&page_size) < 0)
-			page_size = 4096;
-		size = page_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;
-}
-