summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--metaentry.c195
-rw-r--r--metaentry.h33
-rw-r--r--metastore.c52
-rw-r--r--metastore.h16
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;
-};
-
generated by cgit v1.2.1 (git 2.18.0) at 2025-01-23 20:51:44 +0000