commit - 40d16f06b477a3e4552e99de8ec91bce62125c6b
commit + 0be8fa4c11ab3b1e2c7f93a8d8649c885cd72d28
blob - 14f895c1ec910a384eec39f6e8d68c60ffa65538
blob + 2b173017176381035ce051fd5a542a032ce7ece7
--- lib/fetch.c
+++ lib/fetch.c
@@ -16,6 +16,8 @@
 
 #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 - f9d1969b15f4cb43862b7013f35e7485fea9e8b5
blob + a2a77eec3583a812ce8b2b1da88c1970e30fb163
--- lib/object.c
+++ lib/object.c
@@ -16,6 +16,8 @@
 
 #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 - 1dc86652038f22a8bbfaad63930eb197d314c21b
blob + cb9e1e66b8b4e4c2db906ac6472f37b6af5c7487
--- lib/object_parse.c
+++ lib/object_parse.c
@@ -16,6 +16,8 @@
 
 #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 - c0d6e28feff22e3c6f2c9901d5faf98218b9eab2
blob + 55f61382d4f074d706dc6d052fd5df1313c5b78d
--- lib/pack_create.c
+++ lib/pack_create.c
@@ -16,6 +16,8 @@
  */
 
 #include <sys/types.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/stat.h>
 
@@ -29,6 +31,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 - 38d61ae41b5d5e94177f872aefb961dbaaf3a579
blob + ece760d04d7554cbe9da184cb110afd48bddff28
--- lib/repository.c
+++ lib/repository.c
@@ -15,6 +15,8 @@
  */
 
 #include <sys/types.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/stat.h>
@@ -61,6 +63,9 @@
 #ifndef nitems
 #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)
@@ -633,7 +638,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,
@@ -723,6 +728,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++) {
@@ -731,10 +737,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);
 	}
@@ -963,19 +969,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;
@@ -1001,11 +1017,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)
@@ -1016,14 +1030,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);
@@ -1033,7 +1046,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;
 }
 
@@ -2125,3 +2139,6 @@ done:
 	}
 	return err;
 }
+
+RB_GENERATE(got_packidx_bloom_filter_tree, got_packidx_bloom_filter, entry,
+    got_packidx_bloom_filter_cmp);
blob - f73c38388a2637a76122e000a939cc43c4314c89
blob + 12174bd21c15a9ea4fa8bd42b3382c936afccd77
--- lib/repository_admin.c
+++ lib/repository_admin.c
@@ -15,6 +15,8 @@
  */
 
 #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 - 9082a982b2d18cfec0e4a2b47e43d39474a99fa2
blob + d983e298afbf41bdaf8560eb6a46db4c9148df0c
--- lib/send.c
+++ lib/send.c
@@ -17,6 +17,8 @@
 
 #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>