Use hash tables instead of linked lists for a nice speedup at the cost of sorted output

4 files changed, 163 insertions, 133 deletions

diff --git a/metaentry.c b/metaentry.c
index ac2960a..683a126 100644
--- a/metaentry.c
+++ b/metaentry.c
@@ -66,6 +66,29 @@ mentry_free(struct metaentry *m)
 }
 #endif
 
+/* Allocates an empty metahash table */
+static struct metahash *
+mhash_alloc()
+{
+	struct metahash *mhash;
+	mhash = xmalloc(sizeof(struct metahash));
+	memset(mhash, 0, sizeof(struct metahash));
+	return mhash;
+}
+
+/* Generates a hash key (using djb2) */
+static unsigned int
+hash(const char *str)
+{
+	unsigned int hash = 5381;
+	int c;
+
+	while ((c = *str++))
+		hash = ((hash << 5) + hash) + c;
+
+	return hash % HASH_INDEXES;
+}
+
 /* Allocates an empty metaentry */
 static struct metaentry *
 mentry_alloc()
@@ -76,39 +99,43 @@ mentry_alloc()
 	return mentry;
 }
 
-/* Inserts a metaentry into a metaentry list */
-static void
-mentry_insert(struct metaentry *mentry, struct metaentry **mlist)
+/* Does a bisect search for the closest match in a metaentry list */
+struct metaentry *
+mentry_find(const char *path, struct metahash *mhash)
 {
-	struct metaentry *prev;
-	struct metaentry *curr;
-	int comp;
+	struct metaentry *base;
+	unsigned int key;
 
-	if (!(*mlist)) {
-		*mlist = mentry;
-		return;
+	if (!mhash) {
+		msg(MSG_ERROR, "%s called with empty hash table\n", __FUNCTION__);
+		return NULL;
 	}
 
-	if (strcmp(mentry->path, (*mlist)->path) < 0) {
-		mentry->next = *mlist;
-		*mlist = mentry;
-		return;
+	key = hash(path);
+	for (base = mhash->bucket[key]; base; base = base->next) {
+		if (!strcmp(base->path, path))
+			return base;
 	}
 
-	prev = *mlist;
-	for (curr = prev->next; curr; curr = curr->next) {
-		comp = strcmp(mentry->path, curr->path);
-		if (!comp)
-			/* Two matching paths */
-			return;
-		if (comp < 0)
-			break;
-		prev = curr;
+	return NULL;
+}
+
+/* Inserts a metaentry into a metaentry list */
+static void
+mentry_insert(struct metaentry *mentry, struct metahash *mhash)
+{
+	struct metaentry *base;
+	unsigned int key;
+
+	key = hash(mentry->path);
+	if (!mhash->bucket[key]) {
+		mhash->bucket[key] = mentry;
+		return;
 	}
 
-	if (curr)
-		mentry->next = curr;
-	prev->next = mentry;
+	for (base = mhash->bucket[key]; base->next; base = base->next)
+		/* Do nothing */;
+	base->next = mentry;
 }
 
 #ifdef DEBUG
@@ -145,17 +172,16 @@ mentry_print(const struct metaentry *mentry)
 
 /* Prints all metaentries in a metaentry list */
 static void
-mentries_print(const struct metaentry *mlist)
+mentries_print(const struct metahash *mhash)
 {
 	const struct metaentry *mentry;
-	int i;
+	int index;
 
-	for (mentry = mlist; mentry; mentry = mentry->next) {
-		i++;
-		mentry_print(mentry);
-	}
+	for (index = 0; index < HASH_INDEXES; index++)
+		for (mentry = mhash->bucket[i]; mentry; mentry = mentry->next)
+			mentry_print(mentry);
 
-	msg(MSG_DEBUG, "%i entries in total\n", i);
+	msg(MSG_DEBUG, "%i entries in total\n", mhash->count);
 }
 #endif
 
@@ -288,7 +314,7 @@ normalize_path(const char *orig)
 
 /* Internal function for the recursive path walk */
 static void
-mentries_recurse(const char *path, struct metaentry **mlist)
+mentries_recurse(const char *path, struct metahash *mhash)
 {
 	struct stat sbuf;
 	struct metaentry *mentry;
@@ -309,7 +335,7 @@ mentries_recurse(const char *path, struct metaentry **mlist)
 	if (!mentry)
 		return;
 
-	mentry_insert(mentry, mlist);
+	mentry_insert(mentry, mhash);
 
 	if (S_ISDIR(sbuf.st_mode)) {
 		dir = opendir(path);
@@ -326,7 +352,7 @@ mentries_recurse(const char *path, struct metaentry **mlist)
 				continue;
 			snprintf(tpath, PATH_MAX, "%s/%s", path, dent->d_name);
 			tpath[PATH_MAX - 1] = '\0';
-			mentries_recurse(tpath, mlist);
+			mentries_recurse(tpath, mhash);
 		}
 
 		closedir(dir);
@@ -335,20 +361,23 @@ mentries_recurse(const char *path, struct metaentry **mlist)
 
 /* Recurses opath and adds metadata entries to the metaentry list */
 void
-mentries_recurse_path(const char *opath, struct metaentry **mlist)
+mentries_recurse_path(const char *opath, struct metahash **mhash)
 {
 	char *path = normalize_path(opath);
-	mentries_recurse(path, mlist);
+
+	if (!(*mhash))
+		*mhash = mhash_alloc();
+	mentries_recurse(path, *mhash);
 	free(path);
 }
 
-/* Stores a metaentry list to a file */
+/* Stores metaentries to a file */
 void 
-mentries_tofile(const struct metaentry *mlist, const char *path)
+mentries_tofile(const struct metahash *mhash, const char *path)
 {
 	FILE *to;
 	const struct metaentry *mentry;
-	int i;
+	int key, i;
 
 	to = fopen(path, "w");
 	if (!to) {
@@ -360,19 +389,21 @@ mentries_tofile(const struct metaentry *mlist, const char *path)
 	write_binary_string(SIGNATURE, SIGNATURELEN, to);
 	write_binary_string(VERSION, VERSIONLEN, to);
 
-	for (mentry = mlist; mentry; mentry = mentry->next) {
-		write_string(mentry->path, to);
-		write_string(mentry->owner, to);
-		write_string(mentry->group, to);
-		write_int((uint64_t)mentry->mtime, 8, to);
-		write_int((uint64_t)mentry->mtimensec, 8, to);
-		write_int((uint64_t)mentry->mode, 2, to);
-		write_int(mentry->xattrs, 4, to);
-		for (i = 0; i < mentry->xattrs; i++) {
-			write_string(mentry->xattr_names[i], to);
-			write_int(mentry->xattr_lvalues[i], 4, to);
-			write_binary_string(mentry->xattr_values[i],
-					    mentry->xattr_lvalues[i], to);
+	for (key = 0; key < HASH_INDEXES; key++) {		
+		for (mentry = mhash->bucket[key]; mentry; mentry = mentry->next) {
+			write_string(mentry->path, to);
+			write_string(mentry->owner, to);
+			write_string(mentry->group, to);
+			write_int((uint64_t)mentry->mtime, 8, to);
+			write_int((uint64_t)mentry->mtimensec, 8, to);
+			write_int((uint64_t)mentry->mode, 2, to);
+			write_int(mentry->xattrs, 4, to);
+			for (i = 0; i < mentry->xattrs; i++) {
+				write_string(mentry->xattr_names[i], to);
+				write_int(mentry->xattr_lvalues[i], 4, to);
+				write_binary_string(mentry->xattr_values[i],
+						    mentry->xattr_lvalues[i], to);
+			}
 		}
 	}
 
@@ -381,7 +412,7 @@ mentries_tofile(const struct metaentry *mlist, const char *path)
 
 /* Creates a metaentry list from a file */
 void
-mentries_fromfile(struct metaentry **mlist, const char *path)
+mentries_fromfile(struct metahash **mhash, const char *path)
 {
 	struct metaentry *mentry;
 	char *mmapstart;
@@ -391,6 +422,9 @@ mentries_fromfile(struct metaentry **mlist, const char *path)
 	struct stat sbuf;
 	int i;
 
+	if (!(*mhash))
+		*mhash = mhash_alloc();
+
 	fd = open(path, O_RDONLY);
 	if (fd < 0) {
 		msg(MSG_CRITICAL, "Failed to open %s: %s\n",
@@ -448,7 +482,7 @@ mentries_fromfile(struct metaentry **mlist, const char *path)
 		mentry->xattrs = (unsigned int)read_int(&ptr, 4, max);
 
 		if (!mentry->xattrs) {
-			mentry_insert(mentry, mlist);
+			mentry_insert(mentry, *mhash);
 			continue;
 		}
 
@@ -468,7 +502,7 @@ mentries_fromfile(struct metaentry **mlist, const char *path)
 						   mentry->xattr_lvalues[i],
 						   max);
 		}
-		mentry_insert(mentry, mlist);
+		mentry_insert(mentry, *mhash);
 	}
 
 out:
@@ -476,20 +510,6 @@ out:
 	close(fd);
 }
 
-/* Finds a metaentry matching path */
-static struct metaentry *
-mentry_find(const char *path, struct metaentry *mlist)
-{
-	struct metaentry *m;
-
-	/* FIXME - We can do a bisect search here instead */
-	for (m = mlist; m; m = m->next) {
-		if (!strcmp(path, m->path))
-			return m;
-	}
-	return NULL;
-}
-
 /* Searches haystack for an xattr matching xattr number n in needle */
 int
 mentry_find_xattr(struct metaentry *haystack, struct metaentry *needle, int n)
@@ -570,33 +590,36 @@ mentry_compare(struct metaentry *left, struct metaentry *right, int do_mtime)
 
 /* Compares lists of real and stored metadata and calls pfunc for each */
 void
-mentries_compare(struct metaentry *mlistreal,
-		 struct metaentry *mliststored,
+mentries_compare(struct metahash *mhashreal,
+		 struct metahash *mhashstored,
 		 void (*pfunc)
 		 (struct metaentry *real, struct metaentry *stored, int do_mtime),
 		 int do_mtime)
 {
 	struct metaentry *real, *stored;
-	int cmp;
+	int key;
 
-	if (!mlistreal || !mliststored) {
+	if (!mhashreal || !mhashstored) {
 		msg(MSG_ERROR, "%s called with empty list\n", __FUNCTION__);
 		return;
 	}
 
-	for (real = mlistreal; real; real = real->next) {
-		stored = mentry_find(real->path, mliststored);
-		if (!stored)
-			cmp = DIFF_ADDED;
-		else
-			cmp = mentry_compare(real, stored, do_mtime);
-		pfunc(real, stored, cmp);
-	}
+	for (key = 0; key < HASH_INDEXES; key++) {
+		for (real = mhashreal->bucket[key]; real; real = real->next) {
+			stored = mentry_find(real->path, mhashstored);
+
+			if (!stored)
+				pfunc(real, NULL, DIFF_ADDED);
+			else
+				pfunc(real, stored, mentry_compare(real, stored, do_mtime));
+		}
 
-	for (stored = mliststored; stored; stored = stored->next) {
-		real = mentry_find(stored->path, mlistreal);
-		if (!real)
-			pfunc(real, stored, DIFF_DELE);
+		for (stored = mhashstored->bucket[key]; stored; stored = stored->next) {
+			real = mentry_find(stored->path, mhashreal);
+
+			if (!real)
+				pfunc(NULL, stored, DIFF_DELE);
+		}
 	}
 }
 
diff --git a/metaentry.h b/metaentry.h
index 7ec9465..c2c9e01 100644
--- a/metaentry.h
+++ b/metaentry.h
@@ -18,14 +18,37 @@
  *
  */
 
+/* Data structure to hold all metadata for a file */
+struct metaentry {
+	struct metaentry *next;
+	char *path;
+	char *owner;
+	char *group;
+        mode_t mode;
+	time_t mtime;
+        long mtimensec;
+	unsigned int xattrs;
+	char **xattr_names;
+	ssize_t *xattr_lvalues;
+	char **xattr_values;
+};
+
+#define HASH_INDEXES 1024
+
+/* Data structure to hold a number of metadata entries */
+struct metahash {
+        struct metaentry *bucket[HASH_INDEXES];
+        unsigned int count;
+};
+
 /* Recurses opath and adds metadata entries to the metaentry list */
-void mentries_recurse_path(const char *opath, struct metaentry **mlist);
+void mentries_recurse_path(const char *opath, struct metahash **mhash);
 
 /* Stores a metaentry list to a file */
-void mentries_tofile(const struct metaentry *mlist, const char *path);
+void mentries_tofile(const struct metahash *mhash, const char *path);
 
 /* Creates a metaentry list from a file */
-void mentries_fromfile(struct metaentry **mlist, const char *path);
+void mentries_fromfile(struct metahash **mhash, const char *path);
 
 /* Searches haystack for an xattr matching xattr number n in needle */
 int mentry_find_xattr(struct metaentry *haystack,
@@ -43,8 +66,8 @@ int mentry_find_xattr(struct metaentry *haystack,
 #define DIFF_DELE  0x80
 
 /* Compares lists of real and stored metadata and calls pfunc for each */
-void mentries_compare(struct metaentry *mlistreal,
-                      struct metaentry *mliststored,
+void mentries_compare(struct metahash *mhashreal,
+                      struct metahash *mhashstored,
                       void (*pfunc)(struct metaentry *real,
                                     struct metaentry *stored,
                                     int cmp),
diff --git a/metastore.c b/metastore.c
index c0b70c2..affcf19 100644
--- a/metastore.c
+++ b/metastore.c
@@ -43,13 +43,8 @@ static int do_mtime = 0;
 static void
 compare_print(struct metaentry *real, struct metaentry *stored, int cmp)
 {
-	if (!real) {
-		msg(MSG_QUIET, "%s:\tremoved\n", stored->path);
-		return;
-	}
-
-	if (!stored) {
-		msg(MSG_QUIET, "%s:\tadded\n", real->path);
+	if (!real && !stored) {
+		msg(MSG_ERROR, "%s called with incorrect arguments\n", __FUNCTION__);
 		return;
 	}
 
@@ -58,7 +53,12 @@ compare_print(struct metaentry *real, struct metaentry *stored, int cmp)
 		return;
 	}
 
-	msg(MSG_QUIET, "%s:\t", real->path);
+	msg(MSG_QUIET, "%s:\t", real ? real->path : stored->path);
+
+	if (cmp & DIFF_ADDED)
+		msg(MSG_QUIET, "added ", real->path);
+	if (cmp & DIFF_DELE)
+		msg(MSG_QUIET, "removed ", stored->path);
 	if (cmp & DIFF_OWNER)
 		msg(MSG_QUIET, "owner ");
 	if (cmp & DIFF_GROUP)
@@ -237,8 +237,8 @@ int
 main(int argc, char **argv, char **envp)
 {
 	int i, c;
-	struct metaentry *lreal = NULL;
-	struct metaentry *lstored = NULL;
+	struct metahash *real = NULL;
+	struct metahash *stored = NULL;
 	int action = 0;
 
 	/* Parse options */
@@ -302,8 +302,8 @@ main(int argc, char **argv, char **envp)
 	/* Perform action */
 	switch (action) {
 	case ACTION_DIFF:
-		mentries_fromfile(&lstored, METAFILE);
-		if (!lstored) {
+		mentries_fromfile(&stored, METAFILE);
+		if (!stored) {
 			msg(MSG_CRITICAL, "Failed to load metadata from %s\n",
 			    METAFILE);
 			exit(EXIT_FAILURE);
@@ -311,40 +311,40 @@ main(int argc, char **argv, char **envp)
 
 		if (optind < argc) {
 			while (optind < argc)
-				mentries_recurse_path(argv[optind++], &lreal);
+				mentries_recurse_path(argv[optind++], &real);
 		} else {
-			mentries_recurse_path(".", &lreal);
+			mentries_recurse_path(".", &real);
 		}
 
-		if (!lreal) {
+		if (!real) {
 			msg(MSG_CRITICAL,
 			    "Failed to load metadata from file system\n");
 			exit(EXIT_FAILURE);
 		}
 
-		mentries_compare(lreal, lstored, compare_print, do_mtime);
+		mentries_compare(real, stored, compare_print, do_mtime);
 		break;
 
 	case ACTION_SAVE:
 		if (optind < argc) {
 			while (optind < argc)
-				mentries_recurse_path(argv[optind++], &lreal);
+				mentries_recurse_path(argv[optind++], &real);
 		} else {
-			mentries_recurse_path(".", &lreal);
+			mentries_recurse_path(".", &real);
 		}
 
-		if (!lreal) {
+		if (!real) {
 			msg(MSG_CRITICAL,
 			    "Failed to load metadata from file system\n");
 			exit(EXIT_FAILURE);
 		}
 
-		mentries_tofile(lreal, METAFILE);
+		mentries_tofile(real, METAFILE);
 		break;
 
 	case ACTION_APPLY:
-		mentries_fromfile(&lstored, METAFILE);
-		if (!lstored) {
+		mentries_fromfile(&stored, METAFILE);
+		if (!stored) {
 			msg(MSG_CRITICAL, "Failed to load metadata from %s\n",
 			    METAFILE);
 			exit(EXIT_FAILURE);
@@ -352,18 +352,18 @@ main(int argc, char **argv, char **envp)
 
 		if (optind < argc) {
 			while (optind < argc)
-				mentries_recurse_path(argv[optind++], &lreal);
+				mentries_recurse_path(argv[optind++], &real);
 		} else {
-			mentries_recurse_path(".", &lreal);
+			mentries_recurse_path(".", &real);
 		}
 
-		if (!lreal) {
+		if (!real) {
 			msg(MSG_CRITICAL,
 			    "Failed to load metadata from file system\n");
 			exit(EXIT_FAILURE);
 		}
 
-		mentries_compare(lreal, lstored, compare_fix, do_mtime);
+		mentries_compare(real, stored, compare_fix, do_mtime);
 		break;
 
 	case ACTION_HELP:
diff --git a/metastore.h b/metastore.h
index fc8ceb1..7bc7868 100644
--- a/metastore.h
+++ b/metastore.h
@@ -32,19 +32,3 @@
 #define ACTION_SAVE  0x02
 #define ACTION_APPLY 0x04
 #define ACTION_HELP  0x08
-
-/* Data structure to hold all metadata for a file */
-struct metaentry {
-	struct metaentry *next;
-	char *path;
-	char *owner;
-	char *group;
-        mode_t mode;
-	time_t mtime;
-        long mtimensec;
-	unsigned int xattrs;
-	char **xattr_names;
-	ssize_t *xattr_lvalues;
-	char **xattr_values;
-};
-