Back to index

avfs  1.0.1
Classes | Defines | Functions | Variables
namespace.c File Reference
#include "namespace.h"
#include "avfs.h"
#include <stdlib.h>

Go to the source code of this file.

Classes

struct  list_head
struct  entry
struct  namespace

Defines

#define HASH_TABLE_MIN_SIZE   11
#define HASH_TABLE_MAX_SIZE   13845163
#define list_entry(ptr, type, member)   ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

Functions

static AV_LOCK_DECL (namespace_lock)
static void namespace_init_lock ()
static void init_list_head (struct list_head *head)
static void list_del (struct list_head *entry)
static void list_add (struct list_head *entry, struct list_head *head)
static unsigned int spaced_primes_closest (unsigned int num)
static unsigned int namespace_hash (struct entry *parent, const char *name, unsigned int namelen)
static struct list_headalloc_hash_table (unsigned int size)
static void resize_hashtable (struct namespace *ns)
static void namespace_delete (struct namespace *ns)
struct namespaceav_namespace_new ()
static void free_entry_locked (struct entry *ent)
static void free_entry (struct entry *ent)
static struct list_headsubdir_head (struct namespace *ns, struct entry *ent)
static struct entrylookup_name (struct namespace *ns, struct entry *parent, const char *name, unsigned int namelen)
struct entryav_namespace_lookup (struct namespace *ns, struct entry *prev, const char *name)
struct entryav_namespace_lookup_all (struct namespace *ns, struct entry *prev, const char *name)
struct entryav_namespace_resolve (struct namespace *ns, const char *path)
static char * getpath (struct entry *ent)
char * av_namespace_getpath (struct entry *ent)
void av_namespace_setflags (struct entry *ent, int setflags, int resetflags)
void av_namespace_set (struct entry *ent, void *data)
void * av_namespace_get (struct entry *ent)
char * av_namespace_name (struct entry *ent)
static struct entrycurrent_entry (struct list_head *head, struct list_head *curr)
struct entryav_namespace_next (struct entry *ent)
struct entryav_namespace_subdir (struct namespace *ns, struct entry *ent)
struct entryav_namespace_parent (struct entry *ent)
struct entryav_namespace_nth (struct namespace *ns, struct entry *parent, unsigned int n)

Variables

static pthread_once_t namespace_lock_initialized = PTHREAD_ONCE_INIT

Class Documentation

struct list_head

Definition at line 34 of file namespace.c.

Collaboration diagram for list_head:
Class Members
struct list_head * next
struct list_head * prev
struct entry

Definition at line 39 of file namespace.c.

Collaboration diagram for entry:
Class Members
void * data
int flags
char * name
struct namespace * ns
struct entry * parent
struct namespace

Definition at line 50 of file namespace.c.

Collaboration diagram for namespace:
Class Members
unsigned int hashsize
struct list_head * hashtab
unsigned int numentries

Define Documentation

#define HASH_TABLE_MAX_SIZE   13845163

Definition at line 21 of file namespace.c.

#define HASH_TABLE_MIN_SIZE   11

Definition at line 20 of file namespace.c.

#define list_entry (   ptr,
  type,
  member 
)    ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

Definition at line 31 of file namespace.c.


Function Documentation

static struct list_head* alloc_hash_table ( unsigned int  size) [static, read]

Definition at line 111 of file namespace.c.

{
    struct list_head *hashtab;
    unsigned int i;

    hashtab = (struct list_head *) av_malloc(sizeof(*hashtab) * size);
    for(i = 0; i < size; i++)
       init_list_head(&hashtab[i]);

    return hashtab;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static AV_LOCK_DECL ( namespace_lock  ) [static]
void* av_namespace_get ( struct entry ent)

Definition at line 342 of file namespace.c.

{
    void *data;
    
    AV_LOCK(namespace_lock);
    data = ent->data;
    AV_UNLOCK(namespace_lock);

    return data;
}

Here is the caller graph for this function:

char* av_namespace_getpath ( struct entry ent)

Definition at line 317 of file namespace.c.

{
    char *path;

    AV_LOCK(namespace_lock);
    path = getpath(ent);
    AV_UNLOCK(namespace_lock);

    return path;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct entry* av_namespace_lookup ( struct namespace ns,
struct entry prev,
const char *  name 
) [read]

Definition at line 252 of file namespace.c.

{
    struct entry *ent;

    AV_LOCK(namespace_lock);
    if(name == NULL) {
        ent = prev->parent;
        av_ref_obj(ent);
    }
    else
        ent = lookup_name(ns, prev, name, strlen(name));
    AV_UNLOCK(namespace_lock);

    return ent;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct entry* av_namespace_lookup_all ( struct namespace ns,
struct entry prev,
const char *  name 
) [read]

Definition at line 269 of file namespace.c.

{
    if(name != NULL) {
        if(strcmp(name, ".") == 0) {
            av_ref_obj(prev);
            return prev;
        }
        if(strcmp(name, "..") == 0)
            name = NULL;
    }
    
    return av_namespace_lookup(ns, prev, name);
}

Here is the call graph for this function:

Here is the caller graph for this function:

char* av_namespace_name ( struct entry ent)

Definition at line 353 of file namespace.c.

{
    return av_strdup(ent->name);
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct namespace* av_namespace_new ( ) [read]

Definition at line 167 of file namespace.c.

Here is the call graph for this function:

Here is the caller graph for this function:

struct entry* av_namespace_next ( struct entry ent) [read]

Definition at line 367 of file namespace.c.

{
    struct entry *rent;

    AV_LOCK(namespace_lock);
    rent = current_entry(subdir_head(ent->ns, ent->parent), ent->child.next);
    av_ref_obj(rent);
    AV_UNLOCK(namespace_lock);

    return rent;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct entry* av_namespace_nth ( struct namespace ns,
struct entry parent,
unsigned int  n 
) [read]

Definition at line 405 of file namespace.c.

{
    struct list_head *ptr;
    struct list_head *head;
    struct entry *ent = NULL;

    AV_LOCK(namespace_lock);
    head = subdir_head(ns, parent);
    for(ptr = head->next; ptr != head; ptr = ptr->next) {
       if(n == 0) {
           ent = list_entry(ptr, struct entry, child);
           av_ref_obj(ent);
           break;
       }
       n--;
    }
    AV_UNLOCK(namespace_lock);

    return ent;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct entry* av_namespace_parent ( struct entry ent) [read]

Definition at line 393 of file namespace.c.

{
    struct entry *parent;

    AV_LOCK(namespace_lock);
    parent = ent->parent;
    av_ref_obj(parent);
    AV_UNLOCK(namespace_lock);

    return parent;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct entry* av_namespace_resolve ( struct namespace ns,
const char *  path 
) [read]

Definition at line 284 of file namespace.c.

{
    struct entry *ent;
    const char *s;
    
    AV_LOCK(namespace_lock);
    ent = NULL;
    while(*path) {
        struct entry *next;

        for(s = path; *s && *s != '/'; s++);
        next = lookup_name(ns, ent, path, s - path);
        av_unref_obj(ent);
        ent = next;
        for(path = s; *path == '/'; path++);
    }
    AV_UNLOCK(namespace_lock);

    return ent;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void av_namespace_set ( struct entry ent,
void *  data 
)

Definition at line 335 of file namespace.c.

{
    AV_LOCK(namespace_lock);
    ent->data = data;
    AV_UNLOCK(namespace_lock);
}

Here is the caller graph for this function:

void av_namespace_setflags ( struct entry ent,
int  setflags,
int  resetflags 
)

Definition at line 328 of file namespace.c.

{
    AV_LOCK(namespace_lock);
    ent->flags = (ent->flags | setflags) & ~resetflags;
    AV_UNLOCK(namespace_lock);
}

Here is the caller graph for this function:

struct entry* av_namespace_subdir ( struct namespace ns,
struct entry ent 
) [read]

Definition at line 379 of file namespace.c.

{
    struct entry *rent;
    struct list_head *head;

    AV_LOCK(namespace_lock);
    head = subdir_head(ns, ent);
    rent = current_entry(head, head->next);
    av_ref_obj(rent);
    AV_UNLOCK(namespace_lock);

    return rent;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static struct entry* current_entry ( struct list_head head,
struct list_head curr 
) [static, read]

Definition at line 358 of file namespace.c.

{
    if(curr == head)
       return NULL;
    else
       return list_entry(curr, struct entry, child);
}

Here is the caller graph for this function:

static void free_entry ( struct entry ent) [static]

Definition at line 193 of file namespace.c.

{
    av_free(ent->name);
    av_unref_obj(ent->parent);
    av_unref_obj(ent->ns);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void free_entry_locked ( struct entry ent) [static]

Definition at line 184 of file namespace.c.

{
    list_del(&ent->child);
    list_del(&ent->hash);
    ent->ns->numentries --;
    resize_hashtable(ent->ns);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static char* getpath ( struct entry ent) [static]

Definition at line 305 of file namespace.c.

{
    char *path;
    
    if(ent->parent == NULL)
        return av_strdup(ent->name);
    
    path = getpath(ent->parent);

    return av_stradd(path, "/", ent->name, NULL);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void init_list_head ( struct list_head head) [static]

Definition at line 57 of file namespace.c.

{
    head->next = head;
    head->prev = head;
}

Here is the caller graph for this function:

static void list_add ( struct list_head entry,
struct list_head head 
) [static]

Definition at line 71 of file namespace.c.

{
    struct list_head *next = head;
    struct list_head *prev = head->prev;

    entry->next = next;
    entry->prev = prev;
    prev->next = entry;
    next->prev = entry;
}

Here is the caller graph for this function:

static void list_del ( struct list_head entry) [static]

Definition at line 63 of file namespace.c.

{
    struct list_head *next = entry->next;
    struct list_head *prev = entry->prev;
    prev->next = next;
    next->prev = prev;
}

Here is the caller graph for this function:

static struct entry* lookup_name ( struct namespace ns,
struct entry parent,
const char *  name,
unsigned int  namelen 
) [static, read]

Definition at line 208 of file namespace.c.

{
    struct entry *ent;
    struct list_head *ptr;
    unsigned int hash = namespace_hash(parent, name, namelen);
    struct list_head *hashlist = &ns->hashtab[hash % ns->hashsize];

    for(ptr = hashlist->next; ptr != hashlist; ptr = ptr->next) {
       ent = list_entry(ptr, struct entry, hash);
       if(ent->parent == parent && strlen(ent->name) == namelen &&
          strncmp(name, ent->name, namelen) == 0) {
           av_ref_obj(ent);
           return ent;
       }
    }
        
    AV_NEW_OBJ(ent, free_entry);
        
    ent->name = av_strndup(name, namelen);
    ent->flags = 0;

    /* set namespace lock since the entry will be in the hash without
       a reference. This prevents deleting the object in one thread
       while finding the pointer in another thread. */
    av_obj_set_ref_lock(ent, &namespace_lock);

    /* activate destructor called while holding the lock */
    av_obj_set_destr_locked(ent,(void (*)(void *))  free_entry_locked);

    init_list_head(&ent->subdir);
    list_add(&ent->child, subdir_head(ns, parent));
    list_add(&ent->hash, hashlist);
    ent->ns = ns;
    av_ref_obj(ent->ns);
    ent->parent = parent;
    av_ref_obj(ent->parent);

    ns->numentries ++;
    resize_hashtable(ns);

    return ent;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void namespace_delete ( struct namespace ns) [static]

Definition at line 162 of file namespace.c.

{
    av_free(ns->hashtab);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static unsigned int namespace_hash ( struct entry parent,
const char *  name,
unsigned int  namelen 
) [static]

Definition at line 100 of file namespace.c.

{
    unsigned int hash = (unsigned long) parent >> 2;
    for(; namelen; namelen--, name++) {
       hash = (hash << 4) | (hash >> 28);
       hash ^= (unsigned int) *name;
    }
    return hash;
}

Here is the caller graph for this function:

static void namespace_init_lock ( ) [static]

Definition at line 26 of file namespace.c.

{
    AV_INIT_RECURSIVELOCK(namespace_lock);
}

Here is the caller graph for this function:

static void resize_hashtable ( struct namespace ns) [static]

Definition at line 123 of file namespace.c.

{
    float nodes_per_list;
    unsigned int new_size;
    struct list_head *new_tab;
    unsigned int i;
    int maxlen = 0;
    
    nodes_per_list = (float) ns->numentries / (float) ns->hashsize;
       
    if ((nodes_per_list > 0.1 || ns->hashsize <= HASH_TABLE_MIN_SIZE) &&
       (nodes_per_list < 3.0 || ns->hashsize >= HASH_TABLE_MAX_SIZE))
       return;
    
    new_size = spaced_primes_closest(ns->numentries);
    new_tab = alloc_hash_table(new_size);

    for(i = 0; i < ns->hashsize; i++) {
       struct list_head *head = &ns->hashtab[i];
       struct list_head *ptr;
       int len = 0;

       for(ptr = head->next; ptr != head;) {
           struct entry *ent = list_entry(ptr, struct entry, hash);
           unsigned int hash = namespace_hash(ent->parent, ent->name,
                                          strlen(ent->name));
           ptr = ptr->next;
           list_add(&ent->hash, &new_tab[hash % new_size]);
           len ++;
       }
       if(len > maxlen)
           maxlen = len;
    }
  
    av_free(ns->hashtab);
    ns->hashtab = new_tab;
    ns->hashsize = new_size;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static unsigned int spaced_primes_closest ( unsigned int  num) [static]

Definition at line 82 of file namespace.c.

{
    static const unsigned int primes[] = { 
       11, 19, 37, 73, 109, 163, 251, 367, 557, 823, 1237, 1861, 2777, 4177,
       6247, 9371, 14057, 21089, 31627, 47431, 71143, 106721, 160073, 240101,
       360163, 540217, 810343, 1215497, 1823231, 2734867, 4102283, 6153409,
       9230113, 13845163
    };
    static const unsigned int nprimes = sizeof(primes) / sizeof(primes[0]);
    unsigned int i;

    for (i = 0; i < nprimes; i++)
       if (primes[i] > num)
           return primes[i];

    return primes[nprimes - 1];
}

Here is the caller graph for this function:

static struct list_head* subdir_head ( struct namespace ns,
struct entry ent 
) [static, read]

Definition at line 200 of file namespace.c.

{
    if(ent != NULL)
       return &ent->subdir;
    else
       return &ns->root;
}

Here is the caller graph for this function:


Variable Documentation

pthread_once_t namespace_lock_initialized = PTHREAD_ONCE_INIT [static]

Definition at line 24 of file namespace.c.