aboutsummaryrefslogtreecommitdiffstats
path: root/kernel/dirhash.c
diff options
context:
space:
mode:
authorH. Peter Anvin <hpa@zytor.com>1997-10-06 21:27:09 +0000
committerH. Peter Anvin <hpa@zytor.com>1997-10-06 21:27:09 +0000
commit93aa1d55b4ffe513fb10d897dd52a09165484e4e (patch)
treeb7c45bd4579a285261ab11c0557e99e4b3f8037d /kernel/dirhash.c
parent6919185c2ea948793620b5acc57721a65c631710 (diff)
downloadautofs3-93aa1d55b4ffe513fb10d897dd52a09165484e4e.tar.gz
autofs3-93aa1d55b4ffe513fb10d897dd52a09165484e4e.tar.xz
autofs3-93aa1d55b4ffe513fb10d897dd52a09165484e4e.zip
Added kernel code to CVS repository
Diffstat (limited to 'kernel/dirhash.c')
-rw-r--r--kernel/dirhash.c160
1 files changed, 160 insertions, 0 deletions
diff --git a/kernel/dirhash.c b/kernel/dirhash.c
new file mode 100644
index 0000000..60a3c69
--- /dev/null
+++ b/kernel/dirhash.c
@@ -0,0 +1,160 @@
+/* -*- 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;
+}
+
+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, struct qstr *name)
+{
+ struct autofs_dir_ent *dhn;
+
+ DPRINTK(("autofs_hash_lookup: hash = 0x%08x, name = ", name->hash));
+ autofs_say(name->name,name->len);
+
+ for ( dhn = dh->h[(unsigned) name->hash % AUTOFS_HASH_SIZE] ; dhn ; dhn = dhn->next ) {
+ if ( name->hash == dhn->hash &&
+ name->len == dhn->len &&
+ !memcmp(name->name, dhn->name, 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[(unsigned) 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);
+ }
+ }
+}