Implement git_pool paged memory allocator

This adds a `git_pool` object that can do simple paged memory
allocation with free for the entire pool at once.  Using this,
you can replace many small allocations with large blocks that
can then cheaply be doled out in small pieces.  This is best
used when you plan to free the small blocks all at once - for
example, if they represent the parsed state from a file or data
stream that are either all kept or all discarded.

There are two real patterns of usage for `git_pools`: either
for "string" allocation, where the item size is a single byte
and you end up just packing the allocations in together, or for
"fixed size" allocation where you are allocating a large object
(e.g. a `git_oid`) and you generally just allocation single
objects that can be tightly packed.  Of course, you can use it
for other things, but those two cases are the easiest.

1 files changed, 108 insertions, 0 deletions

diff --git a/src/pool.h b/src/pool.h
new file mode 100644
index 000000000..5f65412a0
--- /dev/null
+++ b/src/pool.h
@@ -0,0 +1,108 @@
+/*
+ * Copyright (C) 2012 the libgit2 contributors
+ *
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
+ */
+#ifndef INCLUDE_pool_h__
+#define INCLUDE_pool_h__
+
+#include "common.h"
+
+typedef struct git_pool_page git_pool_page;
+
+/**
+ * Chunked allocator.
+ *
+ * A `git_pool` can be used when you want to cheaply allocate
+ * multiple items of the same type and are willing to free them
+ * all together with a single call.  The two most common cases
+ * are a set of fixed size items (such as lots of OIDs) or a
+ * bunch of strings.
+ *
+ * Internally, a `git_pool` allocates pages of memory and then
+ * deals out blocks from the trailing unused portion of each page.
+ * The pages guarantee that the number of actual allocations done
+ * will be much smaller than the number of items needed.
+ *
+ * For examples of how to set up a `git_pool` see `git_pool_init`.
+ */
+typedef struct {
+	git_pool_page *open; /* pages with space left */
+	git_pool_page *full; /* pages with no space left */
+	void *free_list;     /* optional: list of freed blocks */
+	uint32_t item_size;  /* size of single alloc unit in bytes */
+	uint32_t page_size;  /* size of page in bytes */
+	unsigned has_string_alloc : 1; /* was the strdup function used */
+	unsigned has_multi_item_alloc : 1; /* was items ever > 1 in malloc */
+	unsigned has_large_page_alloc : 1; /* are any pages > page_size */
+} git_pool;
+
+/**
+ * Initialize a pool.
+ *
+ * To allocation strings, use like this:
+ *
+ *     git_pool_init(&string_pool, 1, 0);
+ *     my_string = git_pool_strdup(&string_pool, your_string);
+ *
+ * To allocate items of fixed size, use like this:
+ *
+ *     git_pool_init(&pool, sizeof(item), 0);
+ *     git_pool_malloc(&pool, 1, &my_item_ptr);
+ *
+ * Of course, you can use this in other ways, but those are the
+ * two most common patterns.
+ */
+extern int git_pool_init(
+	git_pool *pool, uint32_t item_size, uint32_t items_per_page);
+
+/**
+ * Free all items in pool
+ */
+extern void git_pool_clear(git_pool *pool);
+
+/**
+ * Allocate space for one or more items from a pool.
+ */
+extern int git_pool_malloc(git_pool *pool, uint32_t items, void **ptr);
+
+/**
+ * Allocate space and duplicate string data into it.
+ *
+ * This is allowed only for pools with item_size == sizeof(char)
+ */
+extern char *git_pool_strndup(git_pool *pool, const char *str, size_t n);
+
+/**
+ * Allocate space and duplicate a string into it.
+ *
+ * This is allowed only for pools with item_size == sizeof(char)
+ */
+extern char *git_pool_strdup(git_pool *pool, const char *str);
+
+/**
+ * Push a block back onto the free list for the pool.
+ *
+ * This is allowed only if the item_size is >= sizeof(void*).
+ *
+ * In some cases, it is helpful to "release" an allocated block
+ * for reuse.  Pools don't support a general purpose free, but
+ * they will keep a simple free blocks linked list provided the
+ * native block size is large enough to hold a void pointer
+ */
+extern void git_pool_free(git_pool *pool, void *ptr);
+
+/*
+ * Misc utilities
+ */
+
+extern uint32_t git_pool__open_pages(git_pool *pool);
+
+extern uint32_t git_pool__full_pages(git_pool *pool);
+
+extern bool git_pool__ptr_in_pool(git_pool *pool, void *ptr);
+
+extern uint32_t git_pool__system_page_size(void);
+
+#endif