summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFlavio Cruz <flaviocruz@gmail.com>2016-02-13 17:12:34 -0500
committerJustus Winter <4winter@informatik.uni-hamburg.de>2016-02-13 23:59:26 +0100
commit6edf2d7cdecac6031e4ecfcc2b14ba5bed7c02a1 (patch)
tree56fc5fdc00a0cf64ca1dcd8a816296bbc91c6994
parent028dfd979c1098f213d3bf9f0fc039ec55da2483 (diff)
Use libihash to store directory entries in ftpfs.
* ftpfs/ftpfs.h: Add dir_locp for each directory entry and replace the table with a libihash table. * ftpfs/dir.c: Modify the code to use libihash. Remove several functions such as rehash and insert.
-rw-r--r--ftpfs/dir.c146
-rw-r--r--ftpfs/ftpfs.h17
2 files changed, 44 insertions, 119 deletions
diff --git a/ftpfs/dir.c b/ftpfs/dir.c
index be20b3db..733a2dcf 100644
--- a/ftpfs/dir.c
+++ b/ftpfs/dir.c
@@ -30,72 +30,31 @@
void
free_entry (struct ftpfs_dir_entry *e)
{
- assert (! e->self_p); /* We should only free deleted nodes. */
+ assert (e->deleted);
free (e->name);
if (e->symlink_target)
free (e->symlink_target);
free (e);
}
-/* Put the directory entry E into the hash table HTABLE, of length HTABLE_LEN. */
-static void
-insert (struct ftpfs_dir_entry *e,
- struct ftpfs_dir_entry **htable, size_t htable_len)
+/* Calculate NAME_PTR's hash value. */
+static hurd_ihash_key_t
+ihash_hash (const void *name_ptr)
{
- struct ftpfs_dir_entry **t = &htable[e->hv % htable_len];
- if (*t)
- (*t)->self_p = &e->next;
- e->next = *t;
- e->self_p = t;
- *t = e;
+ const char *name = (const char *) name_ptr;
+ return (hurd_ihash_key_t) hurd_ihash_hash32 (name, strlen (name), 0);
}
-
-/* Replace DIR's hashtable with a new one of length NEW_LEN, retaining all
- existing entries. */
-static error_t
-rehash (struct ftpfs_dir *dir, size_t new_len)
+
+/* Compare two names which are used as keys. */
+static int
+ihash_compare (const void *key1, const void *key2)
{
- int i;
- size_t old_len = dir->htable_len;
- struct ftpfs_dir_entry **old_htable = dir->htable;
- struct ftpfs_dir_entry **new_htable =
- malloc (new_len * sizeof (struct ftpfs_dir_entry *));
-
- if (! new_htable)
- return ENOMEM;
-
- memset (new_htable, 0, new_len * sizeof(struct ftpfs_dir_entry *));
-
- for (i = 0; i < old_len; i++)
- while (old_htable[i])
- {
- struct ftpfs_dir_entry *e = old_htable[i];
+ const char *name1 = (const char *) key1;
+ const char *name2 = (const char *) key2;
- /* Remove E from the old table (don't bother to fixup
- e->next->self_p). */
- old_htable[i] = e->next;
-
- insert (e, new_htable, new_len);
- }
-
- free (old_htable);
-
- dir->htable = new_htable;
- dir->htable_len = new_len;
-
- return 0;
+ return strcmp (name1, name2) == 0;
}
-/* Calculate NAME's hash value. */
-static size_t
-hash (const char *name)
-{
- size_t hv = 0;
- while (*name)
- hv = ((hv << 5) + *name++) & 0xFFFFFF;
- return hv;
-}
-
/* Lookup NAME in DIR and return its entry. If there is no such entry, and
ADD is true, then a new entry is allocated and returned, otherwise 0 is
returned (if ADD is true then 0 can be returned if a memory allocation
@@ -103,23 +62,14 @@ hash (const char *name)
struct ftpfs_dir_entry *
lookup (struct ftpfs_dir *dir, const char *name, int add)
{
- size_t hv = hash (name);
- struct ftpfs_dir_entry *h = dir->htable[hv % dir->htable_len], *e = h;
-
- while (e && strcmp (name, e->name) != 0)
- e = e->next;
+ struct ftpfs_dir_entry *e =
+ hurd_ihash_find (&dir->htable, (hurd_ihash_key_t) name);
if (!e && add)
{
- if (dir->num_entries > dir->htable_len)
- /* Grow the hash table. */
- if (rehash (dir, (dir->htable_len + 1) * 2 - 1) != 0)
- return 0;
-
e = malloc (sizeof *e);
if (e)
{
- e->hv = hv;
e->name = strdup (name);
e->node = 0;
e->dir = dir;
@@ -128,13 +78,11 @@ lookup (struct ftpfs_dir *dir, const char *name, int add)
e->symlink_target = 0;
e->noent = 0;
e->valid = 0;
+ e->deleted = 0;
e->name_timestamp = e->stat_timestamp = 0;
e->ordered_next = 0;
e->ordered_self_p = 0;
- e->next = 0;
- e->self_p = 0;
- insert (e, dir->htable, dir->htable_len);
- dir->num_entries++;
+ hurd_ihash_add (&dir->htable, (hurd_ihash_key_t) e->name, e);
}
}
@@ -148,28 +96,21 @@ ordered_unlink (struct ftpfs_dir_entry *e)
if (e->ordered_self_p)
*e->ordered_self_p = e->ordered_next;
if (e->ordered_next)
- e->ordered_next->self_p = e->ordered_self_p;
+ e->ordered_next->ordered_self_p = e->ordered_self_p;
}
-
+
/* Delete E from its directory, freeing any resources it holds. */
static void
delete (struct ftpfs_dir_entry *e, struct ftpfs_dir *dir)
{
- dir->num_entries--;
-
- /* Take out of the hash chain. */
- if (e->self_p)
- *e->self_p = e->next;
- if (e->next)
- e->next->self_p = e->self_p;
-
/* This indicates a deleted entry. */
- e->self_p = 0;
- e->next = 0;
+ e->deleted = 1;
/* Take out of the directory ordered list. */
ordered_unlink (e);
+ hurd_ihash_locp_remove (&dir->htable, e->dir_locp);
+
/* If there's a node attached, we'll delete the entry whenever it goes
away, otherwise, just delete it now. */
if (! e->node)
@@ -180,25 +121,23 @@ delete (struct ftpfs_dir_entry *e, struct ftpfs_dir *dir)
static void
mark (struct ftpfs_dir *dir)
{
- size_t len = dir->htable_len, i;
- struct ftpfs_dir_entry **htable = dir->htable, *e;
-
- for (i = 0; i < len; i++)
- for (e = htable[i]; e; e = e->next)
+ HURD_IHASH_ITERATE (&dir->htable, value)
+ {
+ struct ftpfs_dir_entry *e = (struct ftpfs_dir_entry *) value;
e->valid = 0;
+ }
}
-
+
/* Delete any entries in DIR which don't have their valid bit set. */
static void
sweep (struct ftpfs_dir *dir)
{
- size_t len = dir->htable_len, i;
- struct ftpfs_dir_entry **htable = dir->htable, *e;
-
- for (i = 0; i < len; i++)
- for (e = htable[i]; e; e = e->next)
+ HURD_IHASH_ITERATE (&dir->htable, value)
+ {
+ struct ftpfs_dir_entry *e = (struct ftpfs_dir_entry *) value;
if (!e->valid && !e->noent)
- delete (e, dir);
+ delete (e, dir);
+ }
}
/* Update the directory entry for NAME to reflect ST and SYMLINK_TARGET.
@@ -466,7 +405,7 @@ ftpfs_refresh_node (struct node *node)
pthread_mutex_lock (&dir->node->lock);
- if (! entry->self_p)
+ if (entry->deleted)
/* This is a deleted entry, just awaiting disposal; do so. */
{
nn->dir_entry = 0;
@@ -572,7 +511,7 @@ ftpfs_detach_node (struct node *node)
pthread_mutex_lock (&dir->node->lock);
- if (entry->self_p)
+ if (! entry->deleted)
/* Just detach NODE from the still active entry. */
entry->node = 0;
else
@@ -837,15 +776,10 @@ ftpfs_dir_create (struct ftpfs *fs, struct node *node, const char *rmt_path,
struct ftpfs_dir **dir)
{
struct ftpfs_dir *new = malloc (sizeof (struct ftpfs_dir));
- struct ftpfs_dir_entry **htable
- = calloc (INIT_HTABLE_LEN, sizeof (struct ftpfs_dir_entry *));
- if (!new || !htable)
+ if (! new)
{
- if (new)
- free (new);
- if (htable)
- free (htable);
+ free (new);
return ENOMEM;
}
@@ -854,10 +788,9 @@ ftpfs_dir_create (struct ftpfs *fs, struct node *node, const char *rmt_path,
node->references++;
pthread_spin_unlock (&netfs_node_refcnt_lock);
- new->num_entries = 0;
+ hurd_ihash_init (&new->htable, offsetof (struct ftpfs_dir_entry, dir_locp));
+ hurd_ihash_set_gki (&new->htable, ihash_hash, ihash_compare);
new->num_live_entries = 0;
- new->htable_len = INIT_HTABLE_LEN;
- new->htable = htable;
new->ordered = 0;
new->rmt_path = rmt_path;
new->fs = fs;
@@ -880,8 +813,7 @@ ftpfs_dir_free (struct ftpfs_dir *dir)
mark (dir);
sweep (dir);
- if (dir->htable)
- free (dir->htable);
+ hurd_ihash_destroy (&dir->htable);
netfs_nrele (dir->node);
diff --git a/ftpfs/ftpfs.h b/ftpfs/ftpfs.h
index 206726f1..a067bfe4 100644
--- a/ftpfs/ftpfs.h
+++ b/ftpfs/ftpfs.h
@@ -35,7 +35,6 @@ struct ftpfs_conn;
struct ftpfs_dir_entry
{
char *name; /* Name of this entry */
- size_t hv; /* Hash value of NAME (before mod'ing) */
/* The active node referred to by this name (may be 0).
NETFS_NODE_REFCNT_LOCK should be held while frobbing this. */
@@ -48,11 +47,6 @@ struct ftpfs_dir_entry
/* The directory to which this entry belongs. */
struct ftpfs_dir *dir;
- /* Link to next entry in hash bucket, and address of previous entry's (or
- hash table's) pointer to this entry. If the SELF_P field is 0, then
- this is a deleted entry, awaiting final disposal. */
- struct ftpfs_dir_entry *next, **self_p;
-
/* Next entry in `directory order', or 0 if none known. */
struct ftpfs_dir_entry *ordered_next, **ordered_self_p;
@@ -61,24 +55,23 @@ struct ftpfs_dir_entry
hurd_ihash_locp_t inode_locp; /* Used for removing this entry */
+ hurd_ihash_locp_t dir_locp; /* Position in the directory table. */
+
int noent : 1; /* A negative lookup result. */
int valid : 1; /* Marker for GC'ing. */
+ int deleted : 1; /* Indicates a deleted entry. */
};
/* A directory. */
struct ftpfs_dir
{
- /* Number of entries in HTABLE. */
- size_t num_entries;
+ /* Hash table mapping names to children nodes. */
+ struct hurd_ihash htable;
/* The number of entries that have nodes attached. We keep an additional
reference to our node if there are any, to prevent it from going away. */
size_t num_live_entries;
- /* Hash table of entries. */
- struct ftpfs_dir_entry **htable;
- size_t htable_len; /* # of elements in HTABLE (not bytes). */
-
/* List of dir entries in `directory order', in a linked list using the
ORDERED_NEXT and ORDERED_SELF_P fields in each entry. Not all entries
in HTABLE need be in this list. */