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;