Subversion Repositories or1k

/* -*- linux-c -*- --------------------------------------------------------- *

 *

 * linux/fs/autofs/dirhash.c

 *

 *  Copyright 1997 Transmeta Corporation -- All Rights Reserved

 *

 * This file is part of the Linux kernel and is made available under

 * the terms of the GNU General Public License, version 2, or at your

 * option, any later version, incorporated herein by reference.

 *

 * ------------------------------------------------------------------------- */

#include "autofs_i.h"

/* Functions for maintenance of expiry queue */

static void autofs_init_usage(struct autofs_dirhash *dh,

                              struct autofs_dir_ent *ent)

{

        ent->exp_next = &dh->expiry_head;

        ent->exp_prev = dh->expiry_head.exp_prev;

        dh->expiry_head.exp_prev->exp_next = ent;

        dh->expiry_head.exp_prev = ent;

        ent->last_usage = jiffies;

}

static void autofs_delete_usage(struct autofs_dir_ent *ent)

{

        ent->exp_prev->exp_next = ent->exp_next;

        ent->exp_next->exp_prev = ent->exp_prev;

}

void autofs_update_usage(struct autofs_dirhash *dh,

                         struct autofs_dir_ent *ent)

{

        autofs_delete_usage(ent);   /* Unlink from current position */

        autofs_init_usage(dh,ent);  /* Relink at queue tail */

}

struct autofs_dir_ent *autofs_expire(struct autofs_dirhash *dh,

                                     unsigned long timeout)

{

        struct autofs_dir_ent *ent;

        ent = dh->expiry_head.exp_next;

        if ( ent == &(dh->expiry_head) ) return NULL;

        return (jiffies - ent->last_usage >= timeout) ? ent : NULL;

}

/* Adapted from the Dragon Book, page 436 */

/* This particular hashing algorithm requires autofs_hash_t == u32 */

autofs_hash_t autofs_hash(const char *name, int len)

{

        autofs_hash_t h = 0;

        while ( len-- ) {

                h = (h << 4) + (unsigned char) (*name++);

                h ^= ((h & 0xf0000000) >> 24);

        }

        return h;

}

void autofs_initialize_hash(struct autofs_dirhash *dh) {

        memset(&dh->h, 0, AUTOFS_HASH_SIZE*sizeof(struct autofs_dir_ent *));

        dh->expiry_head.exp_next = dh->expiry_head.exp_prev =

                &dh->expiry_head;

}

struct autofs_dir_ent *autofs_hash_lookup(const struct autofs_dirhash *dh, autofs_hash_t hash, const char *name, int len)

{

        struct autofs_dir_ent *dhn;

        DPRINTK(("autofs_hash_lookup: hash = 0x%08x, name = ", hash));

        autofs_say(name,len);

        for ( dhn = dh->h[hash % AUTOFS_HASH_SIZE] ; dhn ; dhn = dhn->next ) {

                if ( hash == dhn->hash &&

                     len == dhn->len &&

                     !memcmp(name, dhn->name, len) )

                        break;

        }

        return dhn;

}

void autofs_hash_insert(struct autofs_dirhash *dh, struct autofs_dir_ent *ent)

{

        struct autofs_dir_ent **dhnp;

        DPRINTK(("autofs_hash_insert: hash = 0x%08x, name = ", ent->hash));

        autofs_say(ent->name,ent->len);

        autofs_init_usage(dh,ent);

        dhnp = &dh->h[ent->hash % AUTOFS_HASH_SIZE];

        ent->next = *dhnp;

        ent->back = dhnp;

        *dhnp = ent;

}

void autofs_hash_delete(struct autofs_dir_ent *ent)

{

        *(ent->back) = ent->next;

        autofs_delete_usage(ent);

        kfree(ent->name);

        kfree(ent);

}

/*

 * Used by readdir().  We must validate "ptr", so we can't simply make it

 * a pointer.  Values below 0xffff are reserved; calling with any value

 * <= 0x10000 will return the first entry found.

 */

struct autofs_dir_ent *autofs_hash_enum(const struct autofs_dirhash *dh, off_t *ptr)

{

        int bucket, ecount, i;

        struct autofs_dir_ent *ent;

        bucket = (*ptr >> 16) - 1;

        ecount = *ptr & 0xffff;

        if ( bucket < 0 ) {

                bucket = ecount = 0;

        }

        DPRINTK(("autofs_hash_enum: bucket %d, entry %d\n", bucket, ecount));

        ent = NULL;

        while  ( bucket < AUTOFS_HASH_SIZE ) {

                ent = dh->h[bucket];

                for ( i = ecount ; ent && i ; i-- )

                        ent = ent->next;

                if (ent) {

                        ecount++; /* Point to *next* entry */

                        break;

                }

                bucket++; ecount = 0;

        }

#ifdef DEBUG

        if ( !ent )

                printk("autofs_hash_enum: nothing found\n");

        else {

                printk("autofs_hash_enum: found hash %08x, name", ent->hash);

                autofs_say(ent->name,ent->len);

        }

#endif

        *ptr = ((bucket+1) << 16) + ecount;

        return ent;

}

/* Delete everything.  This is used on filesystem destruction, so we

   make no attempt to keep the pointers valid */

void autofs_hash_nuke(struct autofs_dirhash *dh)

{

        int i;

        struct autofs_dir_ent *ent, *nent;

        for ( i = 0 ; i < AUTOFS_HASH_SIZE ; i++ ) {

                for ( ent = dh->h[i] ; ent ; ent = nent ) {

                        nent = ent->next;

                        kfree(ent->name);

                        kfree(ent);

                }

        }

}