commit - fc75ac9d8ce9e5332732edc1403fb3856e2a6d24
commit + f8b19efda6453501f8bc4ce868f953b703dca576
blob - 06d450cdb8bfabc4d5e9452f3df3200f0c05e6d5
blob + 3e7e0f2980063ffec434cf50b193542c81dec258
--- lib/fetch.c
+++ lib/fetch.c
@@ -17,6 +17,7 @@
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/wait.h>
blob - d12c1d0d2ac9ef2b17d24062220b1f89c1f7ae78
blob + b99fe9fe68c49923f58a4b5c45969f4bbcded942
--- lib/got_lib_repository.h
+++ lib/got_lib_repository.h
@@ -31,14 +31,21 @@
 #define GOT_PACK_CACHE_SIZE	64
 
 struct got_packidx_bloom_filter {
-	char path_packidx[PATH_MAX]; /* on-disk path */
-	size_t path_packidx_len;
+	RB_ENTRY(got_packidx_bloom_filter) entry;
+	char path[PATH_MAX]; /* on-disk path */
+	size_t path_len;
 	struct bloom *bloom;
-	STAILQ_ENTRY(got_packidx_bloom_filter) entry;
 };
 
-STAILQ_HEAD(got_packidx_bloom_filter_head, got_packidx_bloom_filter);
+RB_HEAD(got_packidx_bloom_filter_tree, got_packidx_bloom_filter);
 
+static inline int
+got_packidx_bloom_filter_cmp(const struct got_packidx_bloom_filter *f1,
+    const struct got_packidx_bloom_filter *f2)
+{
+	return got_path_cmp(f1->path, f2->path, f1->path_len, f2->path_len);
+}
+
 struct got_repository {
 	char *path;
 	char *path_git_dir;
@@ -52,7 +59,7 @@ struct got_repository {
 	 * Used to avoid opening a pack index in search of an
 	 * object ID which is not contained in this pack index.
 	 */
-	struct got_packidx_bloom_filter_head packidx_bloom_filters;
+	struct got_packidx_bloom_filter_tree packidx_bloom_filters;
 
 	/* Open file handles for pack files. */
 	struct got_pack packs[GOT_PACK_CACHE_SIZE];
blob - be9fe5d22bf084651ce1c9dd2db67d37c1c77de7
blob + c66294529994282158f2e9cc6f210b715b65ca43
--- lib/object.c
+++ lib/object.c
@@ -17,6 +17,7 @@
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/wait.h>
blob - dfcc9099ca77bca83c34abf28dcf2e82742f59be
blob + 3a483955358cbec0e4265a879e78817317bfd347
--- lib/object_parse.c
+++ lib/object_parse.c
@@ -17,6 +17,7 @@
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/wait.h>
blob - edaba0504b633bbda16633528dc8c085ed9058e5
blob + 47d4d3b47baf43dd8ff3231d19b7552a197ceffb
--- lib/pack_create.c
+++ lib/pack_create.c
@@ -17,6 +17,7 @@
 
 #include <sys/types.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/stat.h>
 
@@ -32,6 +33,7 @@
 #include "got_error.h"
 #include "got_cancel.h"
 #include "got_object.h"
+#include "got_path.h"
 #include "got_reference.h"
 #include "got_repository_admin.h"
 
blob - fbd865693d2ff3f7a2c995f814ffc0ca5b9f1290
blob + bd802443593987f376a69bc5909a3e7497bb7297
--- lib/repository.c
+++ lib/repository.c
@@ -16,6 +16,7 @@
 
 #include <sys/types.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/stat.h>
@@ -66,6 +67,9 @@
 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
 #endif
 
+RB_PROTOTYPE(got_packidx_bloom_filter_tree, got_packidx_bloom_filter, entry,
+    got_packidx_bloom_filter_cmp);
+
 const char *
 got_repo_get_path(struct got_repository *repo)
 {
@@ -637,7 +641,7 @@ got_repo_open(struct got_repository **repop, const cha
 		goto done;
 	}
 
-	STAILQ_INIT(&repo->packidx_bloom_filters);
+	RB_INIT(&repo->packidx_bloom_filters);
 
 	for (i = 0; i < nitems(repo->privsep_children); i++) {
 		memset(&repo->privsep_children[i], 0,
@@ -727,6 +731,7 @@ const struct got_error *
 got_repo_close(struct got_repository *repo)
 {
 	const struct got_error *err = NULL, *child_err;
+	struct got_packidx_bloom_filter *bf;
 	size_t i;
 
 	for (i = 0; i < repo->pack_cache_size; i++) {
@@ -735,10 +740,10 @@ got_repo_close(struct got_repository *repo)
 		got_packidx_close(repo->packidx_cache[i]);
 	}
 
-	while (!STAILQ_EMPTY(&repo->packidx_bloom_filters)) {
-		struct got_packidx_bloom_filter *bf;
-		bf = STAILQ_FIRST(&repo->packidx_bloom_filters);
-		STAILQ_REMOVE_HEAD(&repo->packidx_bloom_filters, entry);
+	while ((bf = RB_MIN(got_packidx_bloom_filter_tree,
+	    &repo->packidx_bloom_filters))) {
+		RB_REMOVE(got_packidx_bloom_filter_tree,
+		    &repo->packidx_bloom_filters, bf);
 		free(bf->bloom);
 		free(bf);
 	}
@@ -967,19 +972,29 @@ got_repo_is_packidx_filename(const char *name, size_t 
 	return 1;
 }
 
+static struct got_packidx_bloom_filter *
+get_packidx_bloom_filter(struct got_repository *repo,
+    const char *path, size_t path_len)
+{
+	struct got_packidx_bloom_filter key;
+
+	if (strlcpy(key.path, path, sizeof(key.path)) >= sizeof(key.path))
+		return NULL; /* XXX */
+	key.path_len = path_len;
+
+	return RB_FIND(got_packidx_bloom_filter_tree,
+	    &repo->packidx_bloom_filters, &key);
+}
+
 static int
 check_packidx_bloom_filter(struct got_repository *repo,
     const char *path_packidx, struct got_object_id *id)
 {
 	struct got_packidx_bloom_filter *bf;
 
-	STAILQ_FOREACH(bf, &repo->packidx_bloom_filters, entry) {
-		if (got_path_cmp(bf->path_packidx, path_packidx,
-		    bf->path_packidx_len, strlen(path_packidx)) == 0) {
-			return bloom_check(bf->bloom, id->sha1,
-			    sizeof(id->sha1));
-		}
-	}
+	bf = get_packidx_bloom_filter(repo, path_packidx, strlen(path_packidx));
+	if (bf)
+		return bloom_check(bf->bloom, id->sha1, sizeof(id->sha1));
 
 	/* No bloom filter means this pack index must be searched. */
 	return 1;
@@ -1005,11 +1020,9 @@ add_packidx_bloom_filter(struct got_repository *repo,
 		return NULL;
 
 	/* Do we already have a filter for this pack index? */
-	STAILQ_FOREACH(bf, &repo->packidx_bloom_filters, entry) {
-		if (got_path_cmp(bf->path_packidx, path_packidx,
-		    bf->path_packidx_len, strlen(path_packidx)) == 0)
-			return NULL;
-	}
+	if (get_packidx_bloom_filter(repo, path_packidx,
+	    strlen(path_packidx)) != NULL)
+		return NULL;
 
 	bf = calloc(1, sizeof(*bf));
 	if (bf == NULL)
@@ -1020,14 +1033,13 @@ add_packidx_bloom_filter(struct got_repository *repo,
 		return got_error_from_errno("calloc");
 	}
 	
-	
-	len = strlcpy(bf->path_packidx, path_packidx, sizeof(bf->path_packidx));
-	if (len >= sizeof(bf->path_packidx)) {
+	len = strlcpy(bf->path, path_packidx, sizeof(bf->path));
+	if (len >= sizeof(bf->path)) {
 		free(bf->bloom);
 		free(bf);
 		return got_error(GOT_ERR_NO_SPACE);
 	}
-	bf->path_packidx_len = len;
+	bf->path_len = len;
 
 	/* Minimum size supported by our bloom filter is 1000 entries. */
 	bloom_init(bf->bloom, nobjects < 1000 ? 1000 : nobjects, 0.1);
@@ -1037,7 +1049,8 @@ add_packidx_bloom_filter(struct got_repository *repo,
 		bloom_add(bf->bloom, id->sha1, sizeof(id->sha1));
 	}
 
-	STAILQ_INSERT_TAIL(&repo->packidx_bloom_filters, bf, entry);
+	RB_INSERT(got_packidx_bloom_filter_tree,
+	    &repo->packidx_bloom_filters, bf);
 	return NULL;
 }
 
@@ -2126,3 +2139,6 @@ done:
 	}
 	return err;
 }
+
+RB_GENERATE(got_packidx_bloom_filter_tree, got_packidx_bloom_filter, entry,
+    got_packidx_bloom_filter_cmp);
blob - 865369efec481b7e7d68445a796d1a075ac52e70
blob + d7d0ab9f80f5bc272b6a81a901c3647364c3e962
--- lib/repository_admin.c
+++ lib/repository_admin.c
@@ -16,6 +16,7 @@
 
 #include <sys/types.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/stat.h>
 #include <sys/socket.h>
blob - 6a928efef76409f746a25050dabef6f6c6001c95
blob + 7250f245c5c0f1d67211774b2cb6c6c571879eec
--- lib/send.c
+++ lib/send.c
@@ -18,6 +18,7 @@
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/wait.h>