[PATCH] 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.
---
ftpfs/dir.c | 146 --
ftpfs/ftpfs.h | 17 ++-
2 files changed, 44 insertions(+), 119 deletions(-)
diff --git a/ftpfs/dir.c b/ftpfs/dir.c
index be20b3d..733a2dc 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 = [e->hv % htable_len];
- if (*t)
-(*t)->self_p = >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++) & 0xFF;
- 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 (>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 (>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 (>htable, e->dir_locp);
+
/* If there's a node attached, we'll delete the entry whenever it goes
away,
Re: [PATCH] Use libihash to store directory entries in ftpfs.
Quoting Flavio Cruz (2016-02-13 23:12:34) > * 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. Merged, thanks! Justus
Re: [PATCH] Use libihash to store directory entries in ftpfs.
Quoting Flavio Cruz (2016-02-07 21:53:53) > * 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. Your changelog entries are very long, please do reflow them to a reasonable length. I don't know what the reasonable length is, but I always reflow them using meta-q in emacs. > --- > - > > + > [...] > - > > + > [...] > - > > + > [...] > - > > + > [...] > - > > + > [...] > - > > + > [...] > - > > + > [...] > - > > + Your patch removes quite a lot of the form feed characters, is that on purpose or an accident? Fwiw, the coding conventions encourage their use to break the source into logical segments. Justus
Re: [PATCH] Use libihash to store directory entries in ftpfs.
Quoting Flavio Cruz (2016-02-07 15:03:10)
> * 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.
Cool!
> -/* Calculate NAME's hash value. */
> -static size_t
> -hash (const char *name)
> +/* Calculate NAME_PTR's hash value. */
> +static hurd_ihash_key_t
> +ihash_hash (const void *name_ptr)
> {
> + const char *name = (const char *) name_ptr;
>size_t hv = 0;
>while (*name)
> hv = ((hv << 5) + *name++) & 0xFF;
>return hv;
> }
While you are at it, please replace this with hurd_ihash_hash32.
Justus
[PATCH] 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.
---
ftpfs/dir.c | 158 +-
ftpfs/ftpfs.h | 17 ++-
2 files changed, 50 insertions(+), 125 deletions(-)
diff --git a/ftpfs/dir.c b/ftpfs/dir.c
index be20b3d..96424c2 100644
--- a/ftpfs/dir.c
+++ b/ftpfs/dir.c
@@ -30,70 +30,29 @@
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 = [e->hv % htable_len];
- if (*t)
-(*t)->self_p = >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];
-
- /* 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);
+ const char *name1 = (const char *) key1;
+ const char *name2 = (const char *) key2;
- dir->htable = new_htable;
- dir->htable_len = new_len;
-
- return 0;
-}
-
-/* Calculate NAME's hash value. */
-static size_t
-hash (const char *name)
-{
- size_t hv = 0;
- while (*name)
-hv = ((hv << 5) + *name++) & 0xFF;
- return hv;
+ return strcmp (name1, name2) == 0;
}
/* Lookup NAME in DIR and return its entry. If there is no such entry, and
@@ -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 (>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,19 +78,17 @@ 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 (>htable, (hurd_ihash_key_t) e->name, e);
}
}
return e;
}
-
+
/* Remove E from its position in the ordered_next chain. */
static void
ordered_unlink (struct ftpfs_dir_entry *e)
@@ -148,59 +96,50 @@ 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 (>htable, e->dir_locp);
+
/* If there's a node attached, we'll delete the entry whenever it goes
away, otherwise,
[PATCH] 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.
---
ftpfs/dir.c | 142 --
ftpfs/ftpfs.h | 17 +++
2 files changed, 43 insertions(+), 116 deletions(-)
diff --git a/ftpfs/dir.c b/ftpfs/dir.c
index be20b3d..bd3b30c 100644
--- a/ftpfs/dir.c
+++ b/ftpfs/dir.c
@@ -30,72 +30,33 @@
void
free_entry (struct ftpfs_dir_entry *e)
{
- assert (! e->self_p);/* We should only free deleted nodes.
*/
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)
-{
- struct ftpfs_dir_entry **t = [e->hv % htable_len];
- if (*t)
-(*t)->self_p = >next;
- e->next = *t;
- e->self_p = t;
- *t = e;
-}
-
-/* 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)
-{
- 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];
-
- /* 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;
-}
-
-/* Calculate NAME's hash value. */
-static size_t
-hash (const char *name)
+/* Calculate NAME_PTR's hash value. */
+static hurd_ihash_key_t
+ihash_hash (const void *name_ptr)
{
+ const char *name = (const char *) name_ptr;
size_t hv = 0;
while (*name)
hv = ((hv << 5) + *name++) & 0xFF;
return hv;
}
+/* Compare two names which are used as keys. */
+static int
+ihash_compare (const void *key1, const void *key2)
+{
+ const char *name1 = (const char *) key1;
+ const char *name2 = (const char *) key2;
+
+ return strcmp (name1, name2) == 0;
+}
+
/* 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 +64,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 (>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 +80,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 (>htable, (hurd_ihash_key_t) e->name, e);
}
}
@@ -148,28 +98,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 (>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 +123,23 @@ delete (struct
