summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2019-03-06 21:06:48 -0800
committerTavian Barnes <tavianator@tavianator.com>2019-03-06 21:06:48 -0800
commitbae9b31ddfd377609b9de06937987d851d025e32 (patch)
treed851c82a3fe93e1b1348949a461fb1e473c602ca
parent7b482d64e934bb5828ed734260f82f79e5e87651 (diff)
downloadbfs-bae9b31ddfd377609b9de06937987d851d025e32.tar.xz
mtab: Replace the linked list of file system types with a trie
-rw-r--r--mtab.c68
1 files changed, 24 insertions, 44 deletions
diff --git a/mtab.c b/mtab.c
index 19c8331..0d5a153 100644
--- a/mtab.c
+++ b/mtab.c
@@ -15,6 +15,7 @@
****************************************************************************/
#include "mtab.h"
+#include "trie.h"
#include "util.h"
#include <errno.h>
#include <fcntl.h>
@@ -47,50 +48,29 @@
# include <sys/mnttab.h>
#endif
-/**
- * A mount point in the mount table.
- */
-struct bfs_mtab_entry {
- /** The device number for this mount point. */
- dev_t dev;
- /** The file system type of this mount point. */
- char *type;
-};
-
struct bfs_mtab {
- /** The array of mtab entries. */
- struct bfs_mtab_entry *table;
- /** The size of the array. */
- size_t size;
- /** Capacity of the array. */
- size_t capacity;
+ struct trie types;
};
/**
* Add an entry to the mount table.
*/
static int bfs_mtab_push(struct bfs_mtab *mtab, dev_t dev, const char *type) {
- size_t size = mtab->size + 1;
+ struct trie_leaf *leaf = trie_insert_mem(&mtab->types, &dev, sizeof(dev));
+ if (!leaf) {
+ return -1;
+ }
- if (size >= mtab->capacity) {
- size_t capacity = 2*size;
- struct bfs_mtab_entry *table = realloc(mtab->table, capacity*sizeof(*table));
- if (!table) {
- return -1;
- }
- mtab->table = table;
- mtab->capacity = capacity;
+ if (leaf->value) {
+ return 0;
}
- struct bfs_mtab_entry *entry = mtab->table + (size - 1);
- entry->dev = dev;
- entry->type = strdup(type);
- if (!entry->type) {
+ leaf->value = strdup(type);
+ if (leaf->value) {
+ return 0;
+ } else {
return -1;
}
-
- mtab->size = size;
- return 0;
}
struct bfs_mtab *parse_bfs_mtab() {
@@ -109,9 +89,7 @@ struct bfs_mtab *parse_bfs_mtab() {
if (!mtab) {
goto fail_file;
}
- mtab->table = NULL;
- mtab->size = 0;
- mtab->capacity = 0;
+ trie_init(&mtab->types);
struct mntent *mnt;
while ((mnt = getmntent(file))) {
@@ -218,21 +196,23 @@ fail:
}
const char *bfs_fstype(const struct bfs_mtab *mtab, const struct bfs_stat *statbuf) {
- for (struct bfs_mtab_entry *mnt = mtab->table; mnt < mtab->table + mtab->size; ++mnt) {
- if (statbuf->dev == mnt->dev) {
- return mnt->type;
- }
+ const struct trie_leaf *leaf = trie_find_mem(&mtab->types, &statbuf->dev, sizeof(statbuf->dev));
+ if (leaf) {
+ return leaf->value;
+ } else {
+ return "unknown";
}
-
- return "unknown";
}
void free_bfs_mtab(struct bfs_mtab *mtab) {
if (mtab) {
- for (struct bfs_mtab_entry *mnt = mtab->table; mnt < mtab->table + mtab->size; ++mnt) {
- free(mnt->type);
+ struct trie_leaf *leaf;
+ while ((leaf = trie_first_leaf(&mtab->types))) {
+ free((char *)leaf->value);
+ trie_remove_mem(&mtab->types, leaf->key, leaf->length);
}
- free(mtab->table);
+
+ trie_destroy(&mtab->types);
free(mtab);
}
}