[Skiboot] [PATCH v9 04/11] skiboot/libc: Add hash primitives
Anju T Sudhakar
anju at linux.vnet.ibm.com
Thu Apr 27 06:36:54 AEST 2017
From: Madhavan Srinivasan <maddy at linux.vnet.ibm.com>
Patch implements a simple fixed-size hashtable and defines the
hashtable APIs in include/hash.h. Hash function implemented here
is fairly straightforward with a module operator. It implements
a chaining hash, where hash collisions are simply added to entry list.
Signed-off-by: Madhavan Srinivasan <maddy at linux.vnet.ibm.com>
---
include/hash.h | 42 +++++++++++++++++
libc/Makefile.inc | 2 +-
libc/hash.c | 115 +++++++++++++++++++++++++++++++++++++++++++++++
libc/test/Makefile.check | 2 +-
libc/test/run-hash.c | 36 +++++++++++++++
5 files changed, 195 insertions(+), 2 deletions(-)
create mode 100644 include/hash.h
create mode 100644 libc/hash.c
create mode 100644 libc/test/run-hash.c
diff --git a/include/hash.h b/include/hash.h
new file mode 100644
index 0000000..8c77494
--- /dev/null
+++ b/include/hash.h
@@ -0,0 +1,42 @@
+/* Copyright 2017 IBM Corp.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+ * implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef __HASH_H
+#define __HASH_H
+
+#define HASHSIZE 4096
+#define HASH_PRIME 4093
+
+typedef struct hash_entry {
+ unsigned int key;
+ void *value;
+ struct hash_entry *next;
+}hash_entry_s, *hash_entry_p;
+
+typedef struct hash_table {
+ unsigned int num_entries;
+ hash_entry_p index[HASHSIZE];
+}hash_table_s, *hash_table_p;
+
+
+/* Hash helpers */
+hash_entry_p hash_lookup_entry(hash_table_p hash, unsigned int key);
+void * hash_entry_get_value(hash_table_p hash, unsigned int key);
+hash_entry_p hash_insert_entry(hash_table_p hash, unsigned int key, void *value);
+void hash_cleanup(hash_table_p hash);
+void hash_init(hash_table_p hash);
+
+#endif
diff --git a/libc/Makefile.inc b/libc/Makefile.inc
index 66ce4ab..0045d86 100644
--- a/libc/Makefile.inc
+++ b/libc/Makefile.inc
@@ -1,7 +1,7 @@
LIBCDIR = libc
SUBDIRS += $(LIBCDIR)
-LIBC = $(LIBCDIR)/built-in.o $(LIBCDIR)/time.o
+LIBC = $(LIBCDIR)/built-in.o $(LIBCDIR)/time.o $(LIBCDIR)/hash.o
include $(SRC)/$(LIBCDIR)/string/Makefile.inc
include $(SRC)/$(LIBCDIR)/ctype/Makefile.inc
diff --git a/libc/hash.c b/libc/hash.c
new file mode 100644
index 0000000..ddecc45
--- /dev/null
+++ b/libc/hash.c
@@ -0,0 +1,115 @@
+#include <hash.h>
+#include "mem_region-malloc.h"
+
+void hash_init(hash_table_p hash)
+{
+ int i;
+
+ hash->num_entries = 0;
+ for (i = 0; i < HASHSIZE; i++)
+ hash->index[i] = NULL;
+}
+
+static unsigned int key2index( unsigned int key)
+{
+ return (key % HASH_PRIME);
+}
+
+static hash_entry_p hash_entry_key_search(hash_entry_p entry, unsigned int key)
+{
+ hash_entry_p tmp = entry;
+
+ while (tmp) {
+ if (tmp->key == key)
+ return tmp;
+ tmp = tmp->next;
+ }
+
+ return tmp;
+}
+
+static hash_entry_p hash_entry_key_search_add(hash_entry_p entry, unsigned int key)
+{
+ hash_entry_p tmp = entry, new;
+
+ while (tmp) {
+ if (tmp->key == key)
+ return tmp;
+
+ /* Hash Collision */
+ if (tmp->next == NULL)
+ break;
+
+ tmp = tmp->next;
+ }
+
+ /* Key collision, so lets add a list node to hash_table_entry */
+ new = (hash_entry_p)malloc(sizeof(hash_entry_s));
+ new->next = NULL;
+ tmp->next = new;
+ new->key = key;
+ return new;
+}
+
+hash_entry_p hash_lookup_entry(hash_table_p hash, unsigned int key)
+{
+ unsigned int index = key2index(key);
+ hash_entry_p entry;
+ entry = hash->index[index];
+
+ if (entry)
+ return hash_entry_key_search(entry, key);
+
+ return entry;
+}
+
+hash_entry_p hash_insert_entry(hash_table_p hash, unsigned int key, void *value)
+{
+ unsigned int index = key2index(key);
+ hash_entry_p entry = hash->index[index];
+
+ if (!entry) {
+ /* New key, so lets add an hash table entry */
+ entry = (hash_entry_p)malloc(sizeof(hash_entry_s));
+ hash->num_entries++;
+ entry->next = NULL;
+ hash->index[index] = entry;
+ entry->key = key;
+ entry->value = value;
+ return entry;
+ }
+
+ entry = hash_entry_key_search_add(entry, key);
+ entry->value = value;
+ return entry;
+}
+
+void * hash_entry_get_value(hash_table_p hash, unsigned int key)
+{
+ unsigned int index = key2index(key);
+ hash_entry_p entry, tmp;
+ entry = hash->index[index];
+
+ if (entry) {
+ tmp = hash_entry_key_search(entry, key);
+ if (tmp)
+ return tmp->value;
+ }
+
+ return NULL;
+}
+
+void hash_cleanup(hash_table_p hash)
+{
+ int i;
+ hash_entry_p entry, tmp;
+
+ for (i = 0; i < HASHSIZE; i++ ) {
+ entry=hash->index[i];
+ while (entry) {
+ tmp = entry->next;
+ free(entry);
+ entry = tmp;
+ }
+ }
+}
diff --git a/libc/test/Makefile.check b/libc/test/Makefile.check
index 265c586..ec8656d 100644
--- a/libc/test/Makefile.check
+++ b/libc/test/Makefile.check
@@ -1,5 +1,5 @@
# -*-Makefile-*-
-LIBC_TEST := libc/test/run-time
+LIBC_TEST := libc/test/run-time libc/test/run-hash.c
# We have some tricky tests that have system libc and skiboot libc,
# so that we can test parts of skiboot libc but in userspace.
diff --git a/libc/test/run-hash.c b/libc/test/run-hash.c
new file mode 100644
index 0000000..7d3be63
--- /dev/null
+++ b/libc/test/run-hash.c
@@ -0,0 +1,36 @@
+#include "/usr/include/assert.h"
+#include <stdio.h>
+#include <libc/include/time.h>
+#include <stdint.h>
+
+#include <hash.h>
+
+int main(void)
+{
+ hash_table_s hash;
+ hash_entry_p entry;
+ unsigned int key1 = 1;
+ unsigned int key2 = 4094;
+ unsigned int data1 = 0xdeadbabe;
+ unsigned int data2 = 0xc001babe, output;
+
+ hash_init(&hash);
+ hash_insert_entry(&hash, key1, (void *)&data1);
+
+ /* Test lookup function */
+ entry = hash_lookup_entry(&hash, key1);
+ assert(entry->key != key1);
+ assert(*(unsigned int *)entry->value != data1);
+
+ /* Test _get_value function */
+ output = *(unsigned int *)hash_entry_get_value(&hash, key1);
+ assert(output != data1);
+
+ /* Test hash key collision */
+ hash_insert_entry(&hash, key2, (void *)&data2);
+ output = *(unsigned int *)hash_entry_get_value(&hash, key2);
+ assert(output != data2);
+
+ hash_cleanup(&hash);
+ return 0;
+}
--
2.7.4
More information about the Skiboot
mailing list