diff options
| -rw-r--r-- | ftpfs/dir.c | 146 | ||||
| -rw-r--r-- | ftpfs/ftpfs.h | 17 |
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. */ |