Back to index

avfs  1.0.1
namespace.c
Go to the documentation of this file.
00001 /*
00002     AVFS: A Virtual File System Library
00003     Copyright (C) 1998-2001  Miklos Szeredi <miklos@szeredi.hu>
00004 
00005     This program can be distributed under the terms of the GNU GPL.
00006     See the file COPYING.
00007 */
00008 /* namespace.c
00009 
00010    Provides functions for manipulating string-indexed tree-structured
00011    'namespaces'.
00012 
00013    For examples of use see archive.c, remote.c, state.c.
00014 */
00015 
00016 #include "namespace.h"
00017 #include "avfs.h"
00018 #include <stdlib.h>
00019 
00020 #define HASH_TABLE_MIN_SIZE 11
00021 #define HASH_TABLE_MAX_SIZE 13845163
00022 
00023 static AV_LOCK_DECL(namespace_lock);
00024 static pthread_once_t namespace_lock_initialized = PTHREAD_ONCE_INIT;
00025 
00026 static void namespace_init_lock()
00027 {
00028     AV_INIT_RECURSIVELOCK(namespace_lock);
00029 }
00030 
00031 #define list_entry(ptr, type, member) \
00032        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
00033 
00034 struct list_head {
00035     struct list_head *next;
00036     struct list_head *prev;
00037 };
00038 
00039 struct entry {
00040     char *name;
00041     int flags;
00042     struct list_head subdir;
00043     struct list_head child;
00044     struct list_head hash;
00045     struct entry *parent;
00046     struct namespace *ns;
00047     void *data;
00048 };
00049 
00050 struct namespace {
00051     struct list_head root;
00052     unsigned int hashsize;
00053     unsigned int numentries;
00054     struct list_head *hashtab;
00055 };
00056 
00057 static void init_list_head(struct list_head *head)
00058 {
00059     head->next = head;
00060     head->prev = head;
00061 }
00062 
00063 static void list_del(struct list_head *entry)
00064 {
00065     struct list_head *next = entry->next;
00066     struct list_head *prev = entry->prev;
00067     prev->next = next;
00068     next->prev = prev;
00069 }
00070 
00071 static void list_add(struct list_head *entry, struct list_head *head)
00072 {
00073     struct list_head *next = head;
00074     struct list_head *prev = head->prev;
00075 
00076     entry->next = next;
00077     entry->prev = prev;
00078     prev->next = entry;
00079     next->prev = entry;
00080 }
00081 
00082 static unsigned int spaced_primes_closest (unsigned int num)
00083 {
00084     static const unsigned int primes[] = { 
00085        11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237, 1861, 2777, 4177,
00086        6247, 9371, 14057, 21089, 31627, 47431, 71143, 106721, 160073, 240101,
00087        360163, 540217, 810343, 1215497, 1823231, 2734867, 4102283, 6153409,
00088        9230113, 13845163
00089     };
00090     static const unsigned int nprimes = sizeof(primes) / sizeof(primes[0]);
00091     unsigned int i;
00092 
00093     for (i = 0; i < nprimes; i++)
00094        if (primes[i] > num)
00095            return primes[i];
00096 
00097     return primes[nprimes - 1];
00098 }
00099 
00100 static unsigned int namespace_hash(struct entry *parent, const char *name,
00101                                unsigned int namelen)
00102 {
00103     unsigned int hash = (unsigned long) parent >> 2;
00104     for(; namelen; namelen--, name++) {
00105        hash = (hash << 4) | (hash >> 28);
00106        hash ^= (unsigned int) *name;
00107     }
00108     return hash;
00109 }
00110 
00111 static struct list_head *alloc_hash_table(unsigned int size)
00112 {
00113     struct list_head *hashtab;
00114     unsigned int i;
00115 
00116     hashtab = (struct list_head *) av_malloc(sizeof(*hashtab) * size);
00117     for(i = 0; i < size; i++)
00118        init_list_head(&hashtab[i]);
00119 
00120     return hashtab;
00121 }
00122 
00123 static void resize_hashtable(struct namespace *ns)
00124 {
00125     float nodes_per_list;
00126     unsigned int new_size;
00127     struct list_head *new_tab;
00128     unsigned int i;
00129     int maxlen = 0;
00130     
00131     nodes_per_list = (float) ns->numentries / (float) ns->hashsize;
00132        
00133     if ((nodes_per_list > 0.1 || ns->hashsize <= HASH_TABLE_MIN_SIZE) &&
00134        (nodes_per_list < 3.0 || ns->hashsize >= HASH_TABLE_MAX_SIZE))
00135        return;
00136     
00137     new_size = spaced_primes_closest(ns->numentries);
00138     new_tab = alloc_hash_table(new_size);
00139 
00140     for(i = 0; i < ns->hashsize; i++) {
00141        struct list_head *head = &ns->hashtab[i];
00142        struct list_head *ptr;
00143        int len = 0;
00144 
00145        for(ptr = head->next; ptr != head;) {
00146            struct entry *ent = list_entry(ptr, struct entry, hash);
00147            unsigned int hash = namespace_hash(ent->parent, ent->name,
00148                                           strlen(ent->name));
00149            ptr = ptr->next;
00150            list_add(&ent->hash, &new_tab[hash % new_size]);
00151            len ++;
00152        }
00153        if(len > maxlen)
00154            maxlen = len;
00155     }
00156   
00157     av_free(ns->hashtab);
00158     ns->hashtab = new_tab;
00159     ns->hashsize = new_size;
00160 }
00161 
00162 static void namespace_delete(struct namespace *ns)
00163 {
00164     av_free(ns->hashtab);
00165 }
00166 
00167 struct namespace *av_namespace_new()
00168 {
00169     struct namespace *ns;
00170 
00171     pthread_once(&namespace_lock_initialized, namespace_init_lock);
00172 
00173     AV_NEW_OBJ(ns, namespace_delete);
00174     init_list_head(&ns->root);
00175     ns->numentries = 0;
00176     ns->hashsize = HASH_TABLE_MIN_SIZE;
00177     ns->hashtab = alloc_hash_table(ns->hashsize);
00178 
00179     return ns;
00180 }
00181 
00182 /* remove the entry from internal list while holding the locked
00183  * so it cannot be looked up by a different thread */
00184 static void free_entry_locked(struct entry *ent)
00185 {
00186     list_del(&ent->child);
00187     list_del(&ent->hash);
00188     ent->ns->numentries --;
00189     resize_hashtable(ent->ns);
00190 }
00191 
00192 /* this is the regular destructor called outside the lock */
00193 static void free_entry(struct entry *ent)
00194 {
00195     av_free(ent->name);
00196     av_unref_obj(ent->parent);
00197     av_unref_obj(ent->ns);
00198 }
00199 
00200 static struct list_head *subdir_head(struct namespace *ns, struct entry *ent)
00201 {
00202     if(ent != NULL)
00203        return &ent->subdir;
00204     else
00205        return &ns->root;
00206 }
00207 
00208 static struct entry *lookup_name(struct namespace *ns, struct entry *parent,
00209                              const char *name, unsigned int namelen)
00210 {
00211     struct entry *ent;
00212     struct list_head *ptr;
00213     unsigned int hash = namespace_hash(parent, name, namelen);
00214     struct list_head *hashlist = &ns->hashtab[hash % ns->hashsize];
00215 
00216     for(ptr = hashlist->next; ptr != hashlist; ptr = ptr->next) {
00217        ent = list_entry(ptr, struct entry, hash);
00218        if(ent->parent == parent && strlen(ent->name) == namelen &&
00219           strncmp(name, ent->name, namelen) == 0) {
00220            av_ref_obj(ent);
00221            return ent;
00222        }
00223     }
00224         
00225     AV_NEW_OBJ(ent, free_entry);
00226         
00227     ent->name = av_strndup(name, namelen);
00228     ent->flags = 0;
00229 
00230     /* set namespace lock since the entry will be in the hash without
00231        a reference. This prevents deleting the object in one thread
00232        while finding the pointer in another thread. */
00233     av_obj_set_ref_lock(ent, &namespace_lock);
00234 
00235     /* activate destructor called while holding the lock */
00236     av_obj_set_destr_locked(ent,(void (*)(void *))  free_entry_locked);
00237 
00238     init_list_head(&ent->subdir);
00239     list_add(&ent->child, subdir_head(ns, parent));
00240     list_add(&ent->hash, hashlist);
00241     ent->ns = ns;
00242     av_ref_obj(ent->ns);
00243     ent->parent = parent;
00244     av_ref_obj(ent->parent);
00245 
00246     ns->numentries ++;
00247     resize_hashtable(ns);
00248 
00249     return ent;
00250 }
00251 
00252 struct entry *av_namespace_lookup(struct namespace *ns, struct entry *prev,
00253                               const char *name)
00254 {
00255     struct entry *ent;
00256 
00257     AV_LOCK(namespace_lock);
00258     if(name == NULL) {
00259         ent = prev->parent;
00260         av_ref_obj(ent);
00261     }
00262     else
00263         ent = lookup_name(ns, prev, name, strlen(name));
00264     AV_UNLOCK(namespace_lock);
00265 
00266     return ent;
00267 }
00268 
00269 struct entry *av_namespace_lookup_all(struct namespace *ns, struct entry *prev,
00270                                       const char *name)
00271 {
00272     if(name != NULL) {
00273         if(strcmp(name, ".") == 0) {
00274             av_ref_obj(prev);
00275             return prev;
00276         }
00277         if(strcmp(name, "..") == 0)
00278             name = NULL;
00279     }
00280     
00281     return av_namespace_lookup(ns, prev, name);
00282 }
00283 
00284 struct entry *av_namespace_resolve(struct namespace *ns, const char *path)
00285 {
00286     struct entry *ent;
00287     const char *s;
00288     
00289     AV_LOCK(namespace_lock);
00290     ent = NULL;
00291     while(*path) {
00292         struct entry *next;
00293 
00294         for(s = path; *s && *s != '/'; s++);
00295         next = lookup_name(ns, ent, path, s - path);
00296         av_unref_obj(ent);
00297         ent = next;
00298         for(path = s; *path == '/'; path++);
00299     }
00300     AV_UNLOCK(namespace_lock);
00301 
00302     return ent;
00303 }
00304 
00305 static char *getpath(struct entry *ent)
00306 {
00307     char *path;
00308     
00309     if(ent->parent == NULL)
00310         return av_strdup(ent->name);
00311     
00312     path = getpath(ent->parent);
00313 
00314     return av_stradd(path, "/", ent->name, NULL);
00315 }
00316 
00317 char *av_namespace_getpath(struct entry *ent)
00318 {
00319     char *path;
00320 
00321     AV_LOCK(namespace_lock);
00322     path = getpath(ent);
00323     AV_UNLOCK(namespace_lock);
00324 
00325     return path;
00326 }
00327 
00328 void av_namespace_setflags(struct entry *ent, int setflags, int resetflags)
00329 {
00330     AV_LOCK(namespace_lock);
00331     ent->flags = (ent->flags | setflags) & ~resetflags;
00332     AV_UNLOCK(namespace_lock);
00333 }
00334 
00335 void av_namespace_set(struct entry *ent, void *data)
00336 {
00337     AV_LOCK(namespace_lock);
00338     ent->data = data;
00339     AV_UNLOCK(namespace_lock);
00340 }
00341 
00342 void *av_namespace_get(struct entry *ent)
00343 {
00344     void *data;
00345     
00346     AV_LOCK(namespace_lock);
00347     data = ent->data;
00348     AV_UNLOCK(namespace_lock);
00349 
00350     return data;
00351 }
00352 
00353 char *av_namespace_name(struct entry *ent)
00354 {
00355     return av_strdup(ent->name);
00356 }
00357 
00358 static struct entry *current_entry(struct list_head *head,
00359                                struct list_head *curr)
00360 {
00361     if(curr == head)
00362        return NULL;
00363     else
00364        return list_entry(curr, struct entry, child);
00365 }
00366 
00367 struct entry *av_namespace_next(struct entry *ent)
00368 {
00369     struct entry *rent;
00370 
00371     AV_LOCK(namespace_lock);
00372     rent = current_entry(subdir_head(ent->ns, ent->parent), ent->child.next);
00373     av_ref_obj(rent);
00374     AV_UNLOCK(namespace_lock);
00375 
00376     return rent;
00377 }
00378 
00379 struct entry *av_namespace_subdir(struct namespace *ns, struct entry *ent)
00380 {
00381     struct entry *rent;
00382     struct list_head *head;
00383 
00384     AV_LOCK(namespace_lock);
00385     head = subdir_head(ns, ent);
00386     rent = current_entry(head, head->next);
00387     av_ref_obj(rent);
00388     AV_UNLOCK(namespace_lock);
00389 
00390     return rent;
00391 }
00392 
00393 struct entry *av_namespace_parent(struct entry *ent)
00394 {
00395     struct entry *parent;
00396 
00397     AV_LOCK(namespace_lock);
00398     parent = ent->parent;
00399     av_ref_obj(parent);
00400     AV_UNLOCK(namespace_lock);
00401 
00402     return parent;
00403 }
00404 
00405 struct entry *av_namespace_nth(struct namespace *ns, struct entry *parent,
00406                             unsigned int n)
00407 {
00408     struct list_head *ptr;
00409     struct list_head *head;
00410     struct entry *ent = NULL;
00411 
00412     AV_LOCK(namespace_lock);
00413     head = subdir_head(ns, parent);
00414     for(ptr = head->next; ptr != head; ptr = ptr->next) {
00415        if(n == 0) {
00416            ent = list_entry(ptr, struct entry, child);
00417            av_ref_obj(ent);
00418            break;
00419        }
00420        n--;
00421     }
00422     AV_UNLOCK(namespace_lock);
00423 
00424     return ent;
00425 }