Signed-off-by: Richard Cochran <richardcoch...@gmail.com>
---
hash.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
hash.h | 59 +++++++++++++++++++++++++++++++++
makefile | 2 +-
3 files changed, 173 insertions(+), 1 deletion(-)
create mode 100644 hash.c
create mode 100644 hash.h
diff --git a/hash.c b/hash.c
new file mode 100644
index 0000000..e768692
--- /dev/null
+++ b/hash.c
@@ -0,0 +1,113 @@
+/**
+ * @file hash.c
+ * @brief Implements a simple hash table.
+ * @note Copyright (C) 2015 Richard Cochran <richardcoch...@gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+#include <stdlib.h>
+#include <string.h>
+
+#include "hash.h"
+
+#define HASH_TABLE_SIZE 200
+
+struct node {
+ char *key;
+ void *data;
+ struct node *next;
+};
+
+struct hash {
+ struct node *table[HASH_TABLE_SIZE];
+};
+
+static unsigned int hash_function(const char* s)
+{
+ unsigned int i;
+
+ for (i = 0; *s; s++) {
+ i = 131 * i + *s;
+ }
+ return i % HASH_TABLE_SIZE;
+}
+
+struct hash *hash_create(void)
+{
+ struct hash *ht = calloc(1, sizeof(*ht));
+ return ht;
+}
+
+void hash_destroy(struct hash *ht, void (*func)(void *))
+{
+ unsigned int i;
+ struct node *n, *next, **table = ht->table;
+
+ for (i = 0; i < HASH_TABLE_SIZE; i++) {
+ for (n = table[i] ; n; n = next) {
+ next = n->next;
+ if (func) {
+ func(n->data);
+ }
+ free(n->key);
+ free(n);
+ }
+ }
+
+ free(ht);
+}
+
+int hash_insert(struct hash *ht, const char* key, void *data)
+{
+ unsigned int h;
+ struct node *n, **table = ht->table;
+
+ h = hash_function(key);
+
+ for (n = table[h] ; n; n = n->next) {
+ if (!strcmp(n->key, key)) {
+ /* reject duplicate keys */
+ return -1;
+ }
+ }
+ n = calloc(1, sizeof(*n));
+ if (!n) {
+ return -1;
+ }
+ n->key = strdup(key);
+ if (!n->key) {
+ free(n);
+ return -1;
+ }
+ n->data = data;
+ n->next = table[h];
+ table[h] = n;
+ return 0;
+}
+
+void *hash_lookup(struct hash *ht, const char* key)
+{
+ unsigned int h;
+ struct node *n, **table = ht->table;
+
+ h = hash_function(key);
+
+ for (n = table[h] ; n; n = n->next) {
+ if (!strcmp(n->key, key)) {
+ return n->data;
+ }
+ }
+ return NULL;
+}
diff --git a/hash.h b/hash.h
new file mode 100644
index 0000000..74aae0b
--- /dev/null
+++ b/hash.h
@@ -0,0 +1,59 @@
+/**
+ * @file hash.h
+ * @brief Implements a simple hash table.
+ * @note Copyright (C) 2015 Richard Cochran <richardcoch...@gmail.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License along
+ * with this program; if not, write to the Free Software Foundation, Inc.,
+ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ */
+#ifndef HAVE_HASH_H
+#define HAVE_HASH_H
+
+struct hash;
+
+/**
+ * Create a new hash table.
+ * @return A pointer to a new hash table on success, NULL otherwise.
+ */
+struct hash *hash_create(void);
+
+/**
+ * Destroy an instance of a hash table.
+ * @param ht Pointer to a hash table obtained via @ref hash_create().
+ * @param func Callback function, possibly NULL, to apply to the
+ * data of each element in the table.
+ */
+void hash_destroy(struct hash *ht, void (*func)(void *));
+
+/**
+ * Inserts an element into a hash table.
+ * @param ht Hash table into which the element is to be stored.
+ * @param key Key that identifies the element.
+ * @param data Pointer to the user data to be stored.
+ * @return Zero on success and non-zero on error. Attempting to
+ * insert a duplicate key will fail with an error.
+ */
+int hash_insert(struct hash *ht, const char* key, void *data);
+
+/**
+ * Looks up an element from the hash table.
+ * @param ht Hash table to consult.
+ * @param key Key identifying the element of interest.
+ * @return Pointer to the element's data, or NULL if the key is not found.
+ */
+void *hash_lookup(struct hash *ht, const char* key);
+
+#endif
+
+
diff --git a/makefile b/makefile
index a8e5ce8..922769b 100644
--- a/makefile
+++ b/makefile
@@ -24,7 +24,7 @@ CFLAGS = -Wall $(VER) $(incdefs) $(DEBUG)
$(EXTRA_CFLAGS)
LDLIBS = -lm -lrt $(EXTRA_LDFLAGS)
PRG = ptp4l pmc phc2sys hwstamp_ctl phc_ctl timemaster
OBJ = bmc.o clock.o clockadj.o clockcheck.o config.o fault.o \
- filter.o fsm.o linreg.o mave.o mmedian.o msg.o ntpshm.o nullf.o phc.o \
+ filter.o fsm.o hash.o linreg.o mave.o mmedian.o msg.o ntpshm.o nullf.o phc.o \
pi.o port.o print.o ptp4l.o raw.o servo.o sk.o stats.o tlv.o \
transport.o tsproc.o udp.o udp6.o uds.o util.o version.o
--
2.1.4
------------------------------------------------------------------------------
_______________________________________________
Linuxptp-devel mailing list
Linuxptp-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linuxptp-devel
