[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