summaryrefslogtreecommitdiff
path: root/metaentry.c
diff options
context:
space:
mode:
Diffstat (limited to 'metaentry.c')
-rw-r--r--metaentry.c195
1 files changed, 109 insertions, 86 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);
+ }
}
}
generated by cgit v1.2.1 (git 2.18.0) at 2025-01-23 14:40:13 +0000