bug-hurd
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


From: Flavio Cruz
Subject: [PATCH] Use libihash to store directory entries in ftpfs.
Date: Sun, 7 Feb 2016 15:53:53 -0500
User-agent: Mutt/1.5.24 (2015-08-30)

* 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 = &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];
-
-       /* 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++) & 0xFFFFFF;
-  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 (&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,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 (&dir->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 (&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)
     free_entry (e);
 }
-
+
 /* Clear the valid bit in all DIR's htable.  */
 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.
    True is returned if successful, or false if there was a memory allocation
    error.  TIMESTAMP is used to record the time of this update.  */
@@ -238,7 +177,7 @@ update_entry (struct ftpfs_dir_entry *e, const struct stat 
*st,
   e->stat.st_fsid = fs->fsid;
   e->stat.st_fstype = FSTYPE_FTP;
 }
-
+
 /* Add the timestamp TIMESTAMP to the set used to detect bulk stats, and
    return true if there have been enough individual stats recently to call
    for just refetching the whole directory.  */
@@ -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;
@@ -556,7 +495,7 @@ ftpfs_refresh_node (struct node *node)
       return err;
     }
 }
-
+
 /* Remove NODE from its entry (if the entry is still valid, it will remain
    without a node).  NODE should be locked.  */
 error_t
@@ -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
@@ -590,7 +529,7 @@ ftpfs_detach_node (struct node *node)
 
   return 0;
 }
-
+
 /* State shared between ftpfs_dir_lookup and update_new_entry.  */
 struct new_entry_state
 {
@@ -777,7 +716,7 @@ ftpfs_dir_lookup (struct ftpfs_dir *dir, const char *name,
 
   return err;
 }
-
+
 /* Lookup the null name in DIR, and return a node for it in NODE.  Unlike
    ftpfs_dir_lookup, this won't attempt to validate the existence of the
    entry (to avoid opening a new connection if possible) -- that will happen
@@ -825,7 +764,7 @@ ftpfs_dir_null_lookup (struct ftpfs_dir *dir, struct node 
**node)
 
   return err;
 }
-
+
 /* Size of initial htable for a new directory.  */
 #define INIT_HTABLE_LEN 5
 
@@ -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 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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]