Add sorted cache data type

This adds a convenient new data type for caching the contents of
file in memory when each item in that file corresponds to a name
and you need to both be able to lookup items by name and iterate
over them in some sorted order.  The new data type has locks in
place to manage usage in a threaded environment.

3 files changed, 403 insertions, 0 deletions

diff --git a/src/sortedcache.c b/src/sortedcache.c
new file mode 100644
index 000000000..6015d616d
--- /dev/null
+++ b/src/sortedcache.c
@@ -0,0 +1,297 @@
+#include "sortedcache.h"
+
+GIT__USE_STRMAP;
+
+int git_sortedcache_new(
+	git_sortedcache **out,
+	size_t item_path_offset,
+	git_sortedcache_free_item_fn free_item,
+	void *free_item_payload,
+	git_vector_cmp item_cmp,
+	const char *path)
+{
+	git_sortedcache *sc;
+	size_t pathlen;
+
+	pathlen = path ? strlen(path) : 0;
+
+	sc = git__calloc(sizeof(git_sortedcache) + pathlen + 1, 1);
+	GITERR_CHECK_ALLOC(sc);
+
+	if (git_pool_init(&sc->pool, 1, 0) < 0 ||
+		git_vector_init(&sc->items, 4, item_cmp) < 0 ||
+		(sc->map = git_strmap_alloc()) == NULL)
+		goto fail;
+
+	if (git_mutex_init(&sc->lock)) {
+		giterr_set(GITERR_OS, "Failed to initialize mutex");
+		goto fail;
+	}
+
+	sc->item_path_offset = item_path_offset;
+	sc->free_item = free_item;
+	sc->free_item_payload = free_item_payload;
+	GIT_REFCOUNT_INC(sc);
+	if (pathlen)
+		memcpy(sc->path, path, pathlen);
+
+	*out = sc;
+	return 0;
+
+fail:
+	if (sc->map)
+		git_strmap_free(sc->map);
+	git_vector_free(&sc->items);
+	git_pool_clear(&sc->pool);
+	git__free(sc);
+	return -1;
+}
+
+void git_sortedcache_incref(git_sortedcache *sc)
+{
+	GIT_REFCOUNT_INC(sc);
+}
+
+static void sortedcache_clear(git_sortedcache *sc)
+{
+	git_strmap_clear(sc->map);
+
+	if (sc->free_item) {
+		size_t i;
+		void *item;
+
+		git_vector_foreach(&sc->items, i, item) {
+			sc->free_item(sc->free_item_payload, item);
+		}
+	}
+
+	git_vector_clear(&sc->items);
+
+	git_pool_clear(&sc->pool);
+}
+
+static void sortedcache_free(git_sortedcache *sc)
+{
+	if (git_mutex_lock(&sc->lock) < 0) {
+		giterr_set(GITERR_OS, "Unable to acquire mutex lock for free");
+		return;
+	}
+
+	sortedcache_clear(sc);
+
+	git_vector_free(&sc->items);
+	git_strmap_free(sc->map);
+
+	git_mutex_unlock(&sc->lock);
+	git_mutex_free(&sc->lock);
+
+	git__free(sc);
+}
+
+void git_sortedcache_free(git_sortedcache *sc)
+{
+	if (!sc)
+		return;
+	GIT_REFCOUNT_DEC(sc, sortedcache_free);
+}
+
+static int sortedcache_copy_item(void *payload, void *tgt_item, void *src_item)
+{
+	git_sortedcache *sc = payload;
+	/* path will already have been copied by upsert */
+	memcpy(tgt_item, src_item, sc->item_path_offset);
+	return 0;
+}
+
+/* copy a sorted cache */
+int git_sortedcache_copy(
+	git_sortedcache **out,
+	git_sortedcache *src,
+	int (*copy_item)(void *payload, void *tgt_item, void *src_item),
+	void *payload)
+{
+	git_sortedcache *tgt;
+	size_t i;
+	void *src_item, *tgt_item;
+
+	if (!copy_item) {
+		copy_item = sortedcache_copy_item;
+		payload   = src;
+	}
+
+	if (git_sortedcache_new(
+			&tgt, src->item_path_offset,
+			src->free_item, src->free_item_payload,
+			src->items._cmp, src->path) < 0)
+		return -1;
+
+	if (git_sortedcache_lock(src) < 0) {
+		git_sortedcache_free(tgt);
+		return -1;
+	}
+
+	if (git_sortedcache_lock(tgt) < 0)
+		goto fail;
+
+	git_vector_foreach(&src->items, i, src_item) {
+		if (git_sortedcache_upsert(
+				&tgt_item, tgt, ((char *)src_item) + src->item_path_offset) < 0)
+			goto fail;
+		if (copy_item(payload, tgt_item, src_item) < 0)
+			goto fail;
+	}
+
+	git_sortedcache_unlock(tgt);
+	git_sortedcache_unlock(src);
+
+	*out = tgt;
+	return 0;
+
+fail:
+	git_sortedcache_unlock(src);
+	git_sortedcache_free(tgt);
+	return -1;
+}
+
+/* release all items in sorted cache */
+void git_sortedcache_clear(git_sortedcache *sc, bool lock)
+{
+	if (lock && git_mutex_lock(&sc->lock) < 0) {
+		giterr_set(GITERR_OS, "Unable to acquire mutex lock for clear");
+		return;
+	}
+
+	sortedcache_clear(sc);
+
+	if (lock)
+		git_mutex_unlock(&sc->lock);
+}
+
+/* check file stamp to see if reload is required */
+bool git_sortedcache_out_of_date(git_sortedcache *sc)
+{
+	return (git_futils_filestamp_check(&sc->stamp, sc->path) != 0);
+}
+
+/* lock sortedcache while making modifications */
+int git_sortedcache_lock(git_sortedcache *sc)
+{
+	if (git_mutex_lock(&sc->lock) < 0) {
+		giterr_set(GITERR_OS, "Unable to acquire mutex lock");
+		return -1;
+	}
+	return 0;
+}
+
+/* unlock sorted cache when done with modifications */
+int git_sortedcache_unlock(git_sortedcache *sc)
+{
+	git_vector_sort(&sc->items);
+	git_mutex_unlock(&sc->lock);
+	return 0;
+}
+
+/* if the file has changed, lock cache and load file contents into buf;
+ * returns <0 on error, >0 if file has not changed
+ */
+int git_sortedcache_lockandload(git_sortedcache *sc, git_buf *buf)
+{
+	int error, fd;
+
+	if ((error = git_sortedcache_lock(sc)) < 0)
+		return error;
+
+	if ((error = git_futils_filestamp_check(&sc->stamp, sc->path)) <= 0)
+		goto unlock;
+
+	if (!git__is_sizet(sc->stamp.size)) {
+		giterr_set(GITERR_INVALID, "Unable to load file larger than size_t");
+		error = -1;
+		goto unlock;
+	}
+
+	if ((fd = git_futils_open_ro(sc->path)) < 0) {
+		error = fd;
+		goto unlock;
+	}
+
+	if (buf)
+		error = git_futils_readbuffer_fd(buf, fd, (size_t)sc->stamp.size);
+
+	(void)p_close(fd);
+
+	if (error < 0)
+		goto unlock;
+
+	return 1; /* return 1 -> file needs reload and was successfully loaded */
+
+unlock:
+	git_sortedcache_unlock(sc);
+	return error;
+}
+
+/* find and/or insert item, returning pointer to item data */
+int git_sortedcache_upsert(
+	void **out, git_sortedcache *sc, const char *key)
+{
+	int error = 0;
+	khiter_t pos;
+	void *item;
+	size_t keylen;
+	char *item_key;
+
+	pos = git_strmap_lookup_index(sc->map, key);
+	if (git_strmap_valid_index(sc->map, pos)) {
+		item = git_strmap_value_at(sc->map, pos);
+		goto done;
+	}
+
+	keylen = strlen(key);
+	item = git_pool_mallocz(&sc->pool, sc->item_path_offset + keylen + 1);
+	GITERR_CHECK_ALLOC(item);
+
+	/* one strange thing is that even if the vector or hash table insert
+	 * fail, there is no way to free the pool item so we just abandon it
+	 */
+
+	item_key = ((char *)item) + sc->item_path_offset;
+	memcpy(item_key, key, keylen);
+
+	pos = kh_put(str, sc->map, item_key, &error);
+	if (error < 0)
+		goto done;
+
+	if (!error)
+		kh_key(sc->map, pos) = item_key;
+	kh_val(sc->map, pos) = item;
+
+	error = git_vector_insert(&sc->items, item);
+	if (error < 0)
+		git_strmap_delete_at(sc->map, pos);
+
+done:
+	if (out)
+		*out = !error ? item : NULL;
+	return error;
+}
+
+/* lookup item by key */
+void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key)
+{
+	khiter_t pos = git_strmap_lookup_index(sc->map, key);
+	if (git_strmap_valid_index(sc->map, pos))
+		return git_strmap_value_at(sc->map, pos);
+	return NULL;
+}
+
+/* find out how many items are in the cache */
+size_t git_sortedcache_entrycount(const git_sortedcache *sc)
+{
+	return git_vector_length(&sc->items);
+}
+
+/* lookup item by index */
+void *git_sortedcache_entry(const git_sortedcache *sc, size_t pos)
+{
+	return git_vector_get(&sc->items, pos);
+}
diff --git a/src/sortedcache.h b/src/sortedcache.h
new file mode 100644
index 000000000..5d0d8f5a7
--- /dev/null
+++ b/src/sortedcache.h
@@ -0,0 +1,101 @@
+/*
+ * Copyright (C) the libgit2 contributors. All rights reserved.
+ *
+ * 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_sorted_cache_h__
+#define INCLUDE_sorted_cache_h__
+
+#include "util.h"
+#include "fileops.h"
+#include "vector.h"
+#include "thread-utils.h"
+#include "pool.h"
+#include "strmap.h"
+
+/*
+ * The purpose of this data structure is to cache the parsed contents of a
+ * file where each item in the file can be identified by a key string and
+ * you want to both look them up by name and traverse them in sorted
+ * order.  Each item is assumed to itself end in a GIT_FLEX_ARRAY.
+ */
+
+typedef void (*git_sortedcache_free_item_fn)(void *payload, void *item);
+
+typedef struct {
+	git_refcount rc;
+	git_mutex    lock;
+	size_t       item_path_offset;
+	git_sortedcache_free_item_fn free_item;
+	void         *free_item_payload;
+	git_pool     pool;
+	git_vector   items;
+	git_strmap   *map;
+	git_futils_filestamp stamp;
+	char         path[GIT_FLEX_ARRAY];
+} git_sortedcache;
+
+/* create a new sortedcache
+ *
+ * even though every sortedcache stores items with a GIT_FLEX_ARRAY at
+ * the end containing their key string, you have to provide the item_cmp
+ * sorting function because the sorting function doesn't get a payload
+ * and therefore can't know the offset to the item key string. :-(
+ */
+int git_sortedcache_new(
+	git_sortedcache **out,
+	size_t item_path_offset, /* use offsetof() macro */
+	git_sortedcache_free_item_fn free_item,
+	void *free_item_payload,
+	git_vector_cmp item_cmp,
+	const char *path);
+
+/* copy a sorted cache
+ *
+ * - copy_item can be NULL to memcpy
+ * - locks src while copying
+ */
+int git_sortedcache_copy(
+	git_sortedcache **out,
+	git_sortedcache *src,
+	int (*copy_item)(void *payload, void *tgt_item, void *src_item),
+	void *payload);
+
+/* free sorted cache (first calling free_item callbacks) */
+void git_sortedcache_free(git_sortedcache *sc);
+
+/* increment reference count */
+void git_sortedcache_incref(git_sortedcache *sc);
+
+/* release all items in sorted cache - lock during clear if lock is true */
+void git_sortedcache_clear(git_sortedcache *sc, bool lock);
+
+/* check file stamp to see if reload is required */
+bool git_sortedcache_out_of_date(git_sortedcache *sc);
+
+/* lock sortedcache while making modifications */
+int git_sortedcache_lock(git_sortedcache *sc);
+
+/* unlock sorted cache when done with modifications */
+int git_sortedcache_unlock(git_sortedcache *sc);
+
+/* if the file has changed, lock cache and load file contents into buf;
+ * @return 0 if up-to-date, 1 if out-of-date, <0 on error
+ */
+int git_sortedcache_lockandload(git_sortedcache *sc, git_buf *buf);
+
+/* find and/or insert item, returning pointer to item data - lock first */
+int git_sortedcache_upsert(
+	void **out, git_sortedcache *sc, const char *key);
+
+/* lookup item by key */
+void *git_sortedcache_lookup(const git_sortedcache *sc, const char *key);
+
+/* find out how many items are in the cache */
+size_t git_sortedcache_entrycount(const git_sortedcache *sc);
+
+/* lookup item by index */
+void *git_sortedcache_entry(const git_sortedcache *sc, size_t pos);
+
+#endif
diff --git a/src/vector.h b/src/vector.h
index 1bda9c93d..ad1c34ea1 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -55,6 +55,11 @@ GIT_INLINE(void *) git_vector_get(const git_vector *v, size_t position)
 
 #define GIT_VECTOR_GET(V,I) ((I) < (V)->length ? (V)->contents[(I)] : NULL)
 
+GIT_INLINE(size_t) git_vector_length(const git_vector *v)
+{
+	return v->length;
+}
+
 GIT_INLINE(void *) git_vector_last(const git_vector *v)
 {
 	return (v->length > 0) ? git_vector_get(v, v->length - 1) : NULL;