include @TOP_OBJDIR@/src/config/Makefile.pthread
include @TOP_OBJDIR@/src/config/Makefile.libtool
-LT_objs = assert.lo casestrcpy.lo rbtree.lo uuid.lo
+LT_objs = assert.lo casestrcpy.lo dict.lo rbtree.lo uuid.lo
LT_libs = $(LIB_hcrypto) $(LIB_roken)
HEADERS = $(TOP_INCDIR)/afs/opr.h \
$(TOP_INCDIR)/afs/opr_assert.h \
+ $(TOP_INCDIR)/opr/dict.h \
$(TOP_INCDIR)/opr/jhash.h \
$(TOP_INCDIR)/opr/lock.h \
$(TOP_INCDIR)/opr/lockstub.h \
$(TOP_INCDIR)/afs/opr_assert.h: ${srcdir}/opr_assert.h
$(INSTALL_DATA) $? $@
+$(TOP_INCDIR)/opr/dict.h: ${srcdir}/dict.h
+ $(INSTALL_DATA) $? $@
+
$(TOP_INCDIR)/opr/jhash.h: ${srcdir}/jhash.h
$(INSTALL_DATA) $? $@
--- /dev/null
+/*
+ * Copyright (c) 2012 Your File System Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+#include <afsconfig.h>
+#include <afs/param.h>
+
+#include <roken.h>
+
+#include "dict.h"
+
+static_inline int
+isPowerOf2(int value)
+{
+ return value && !(value & (value -1));
+}
+
+struct opr_dict *
+opr_dict_Init(unsigned int size)
+{
+ struct opr_dict *dict;
+ int i;
+
+ if (!isPowerOf2(size))
+ return NULL;
+
+ dict = calloc(1, sizeof(struct opr_dict));
+ dict->size = size;
+
+ dict->table = malloc(dict->size * sizeof(struct opr_queue));
+ for (i = 0; i < dict->size; i++) {
+ opr_queue_Init(&dict->table[i]);
+ }
+
+ return dict;
+}
+
+void
+opr_dict_Free(struct opr_dict **dict)
+{
+ free((*dict)->table);
+ free(*dict);
+ *dict = NULL;
+}
--- /dev/null
+/*
+ * Copyright (c) 2012 Your File System Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <opr/queue.h>
+
+struct opr_dict {
+ int size;
+ struct opr_queue *table;
+};
+
+static_inline void
+opr_dict_Prepend(struct opr_dict *dict, int index, struct opr_queue *entry)
+{
+ opr_queue_Prepend(&dict->table[index & (dict->size-1)], entry);
+}
+
+static_inline void
+opr_dict_Append(struct opr_dict *dict, int index, struct opr_queue *entry)
+{
+ opr_queue_Append(&dict->table[index & (dict->size-1)], entry);
+}
+
+static_inline void
+opr_dict_Promote(struct opr_dict *dict, int index, struct opr_queue *entry)
+{
+ opr_queue_Remove(entry);
+ opr_dict_Prepend(dict, index, entry);
+}
+
+#define opr_dict_ScanBucket(dict, index, cursor) \
+ opr_queue_Scan(&(dict)->table[index & ((dict)->size-1)], cursor)
+
+#define opr_dict_ScanBucketSafe(dict, index, cursor, store) \
+ opr_queue_ScanSafe(&(dict)->table[index & ((dict)->size-1)], \
+ cursor, store)
+
+extern struct opr_dict *opr_dict_Init(unsigned int size);
+extern void opr_dict_Free(struct opr_dict **dict);
opr_stoupper
opr_strcompose
opr_AssertionFailed
+opr_dict_Init
+opr_dict_Free
opr_rbtree_first
opr_rbtree_next
opr_rbtree_remove
auth/authcon
auth/realms
cmd/command
+opr/dict
opr/jhash
opr/queues
opr/rbtree
LIBS=../tap/libtap.a $(abs_top_builddir)/src/opr/liboafs_opr.la
-tests = jhash-t queues-t rbtree-t time-t uuid-t
+tests = dict-t jhash-t queues-t rbtree-t time-t uuid-t
all check test tests: $(tests)
+dict-t: dict-t.o
+ $(LT_LDRULE_static) dict-t.o $(LIBS) $(XLIBS)
+
queues-t: queues-t.o
$(LT_LDRULE_static) queues-t.o ../tap/libtap.a $(XLIBS)
--- /dev/null
+/*
+ * Copyright (c) 2012 Your File System Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR `AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <afsconfig.h>
+#include <afs/param.h>
+
+#include <tests/tap/basic.h>
+#include <opr/dict.h>
+
+struct myentry {
+ int value;
+ struct opr_queue d;
+};
+
+int
+find(struct opr_dict *dict, int value, struct myentry **entryp)
+{
+ struct myentry *ent;
+ struct opr_queue *cursor;
+ int length = 0;
+
+ for (opr_dict_ScanBucket(dict, value, cursor)) {
+ ent = opr_queue_Entry(cursor, struct myentry, d);
+ length++;
+
+ if (ent->value == value) {
+ if (entryp)
+ *entryp = ent;
+ return length;
+ }
+ }
+ return 0;
+}
+
+int
+main(void)
+{
+ struct opr_dict *dict;
+ struct myentry *entry;
+ int members[] = {1,2,3,4,5,6,7,8,9,10,17,0};
+ int i;
+
+ plan(10);
+
+ ok(opr_dict_Init(3) == NULL,
+ "Initialising a dictionary with a bad size fails");
+
+ dict = opr_dict_Init(8);
+ ok(dict != NULL,
+ "Initialising a dictionary succeeds");
+
+ for (i = 0; members[i] !=0; i++) {
+ entry = malloc(sizeof(struct myentry));
+ entry->value = members[i];
+ opr_dict_Append(dict, entry->value, &entry->d);
+ }
+ ok(1, "Hash populated successfully");
+
+ is_int(1, find(dict, 1, NULL),
+ "Entry 1 is first in hash chain");
+ is_int(2, find(dict, 9, NULL),
+ "Entry 9 is second in hash chain");
+ is_int(3, find(dict, 17, NULL),
+ "Entry 17 is third in hash chain");
+ is_int(1, find(dict, 2, NULL),
+ "Entry 2 is first in hash chain");
+ is_int(1, find(dict, 8, NULL),
+ "Entry 8 is first in hash chain");
+
+ find(dict, 17, &entry);
+ ok(entry != NULL && entry->value == 17, "Retrieved entry 17");
+ opr_dict_Promote(dict, entry->value, &entry->d);
+ is_int(1, find(dict, 17, NULL),
+ "Entry 17 is first in hash chain following promotion");
+
+ return 0;
+}
git://git.openafs.org / openafs.git / commitdiff