[PATCH] Use libihash to store directory entries in ftpfs.

[Flavio Cruz]

* 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 = &htable[e->hv % htable_len];
-  if (*t)
-    (*t)->self_p = &e->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++) & 0xFFFFFF;
   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 (&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 +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 (&dir->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 (&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 +123,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 +407,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 +513,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 +778,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 +790,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 +815,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 206726f..a067bfe 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.  */
-- 
2.6.4