summaryrefslogtreecommitdiff
path: root/3rdparty/plibsys/src/phashtable.c
diff options
context:
space:
mode:
authorsanine <sanine.not@pm.me>2022-08-27 23:52:56 -0500
committersanine <sanine.not@pm.me>2022-08-27 23:52:56 -0500
commita4dd0ad63c00f4dee3b86dfd3075d1d61b2b3180 (patch)
tree13bd5bfa15e6fea2a12f176bae79adf9c6fd0933 /3rdparty/plibsys/src/phashtable.c
parentbde3e4f1bb7b8f8abca0884a7d994ee1c17a66b1 (diff)
add plibsys
Diffstat (limited to '3rdparty/plibsys/src/phashtable.c')
-rw-r--r--3rdparty/plibsys/src/phashtable.c243
1 files changed, 243 insertions, 0 deletions
diff --git a/3rdparty/plibsys/src/phashtable.c b/3rdparty/plibsys/src/phashtable.c
new file mode 100644
index 0000000..a9fc052
--- /dev/null
+++ b/3rdparty/plibsys/src/phashtable.c
@@ -0,0 +1,243 @@
+/*
+ * The MIT License
+ *
+ * Copyright (C) 2010-2019 Alexander Saprykin <saprykin.spb@gmail.com>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * 'Software'), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED 'AS IS', WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+ * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+ * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+ * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/* Hash table organized like this: table[hash key]->[list with values]
+ * Note: this implementation is not intended to use on huge loads */
+
+#include "pmem.h"
+#include "phashtable.h"
+
+#include <stdlib.h>
+
+typedef struct PHashTableNode_ PHashTableNode;
+
+struct PHashTableNode_ {
+ PHashTableNode *next;
+ ppointer key;
+ ppointer value;
+};
+
+struct PHashTable_ {
+ PHashTableNode **table;
+ psize size;
+};
+
+/* Size of unique hash keys in hash table */
+#define P_HASH_TABLE_SIZE 101
+
+static puint pp_hash_table_calc_hash (pconstpointer pointer, psize modulo);
+static PHashTableNode * pp_hash_table_find_node (const PHashTable *table, pconstpointer key, puint hash);
+
+static puint
+pp_hash_table_calc_hash (pconstpointer pointer, psize modulo)
+{
+ /* As simple as we can :) */
+ return (puint) (((psize) (P_POINTER_TO_INT (pointer) + 37)) % modulo);
+}
+
+static PHashTableNode *
+pp_hash_table_find_node (const PHashTable *table, pconstpointer key, puint hash)
+{
+ PHashTableNode *ret;
+
+ for (ret = table->table[hash]; ret != NULL; ret = ret->next)
+ if (ret->key == key)
+ return ret;
+
+ return NULL;
+}
+
+P_LIB_API PHashTable *
+p_hash_table_new (void)
+{
+ PHashTable *ret;
+
+ if (P_UNLIKELY ((ret = p_malloc0 (sizeof (PHashTable))) == NULL)) {
+ P_ERROR ("PHashTable::p_hash_table_new: failed(1) to allocate memory");
+ return NULL;
+ }
+
+ if (P_UNLIKELY ((ret->table = p_malloc0 (P_HASH_TABLE_SIZE * sizeof (PHashTableNode *))) == NULL)) {
+ P_ERROR ("PHashTable::p_hash_table_new: failed(2) to allocate memory");
+ p_free (ret);
+ return NULL;
+ }
+
+ ret->size = P_HASH_TABLE_SIZE;
+
+ return ret;
+}
+
+P_LIB_API void
+p_hash_table_insert (PHashTable *table, ppointer key, ppointer value)
+{
+ PHashTableNode *node;
+ puint hash;
+
+ if (P_UNLIKELY (table == NULL))
+ return;
+
+ hash = pp_hash_table_calc_hash (key, table->size);
+
+ if ((node = pp_hash_table_find_node (table, key, hash)) == NULL) {
+ if (P_UNLIKELY ((node = p_malloc0 (sizeof (PHashTableNode))) == NULL)) {
+ P_ERROR ("PHashTable::p_hash_table_insert: failed to allocate memory");
+ return;
+ }
+
+ /* Insert a new node in front of others */
+ node->key = key;
+ node->value = value;
+ node->next = table->table[hash];
+
+ table->table[hash] = node;
+ } else
+ node->value = value;
+}
+
+P_LIB_API ppointer
+p_hash_table_lookup (const PHashTable *table, pconstpointer key)
+{
+ PHashTableNode *node;
+ puint hash;
+
+ if (P_UNLIKELY (table == NULL))
+ return NULL;
+
+ hash = pp_hash_table_calc_hash (key, table->size);
+
+ return ((node = pp_hash_table_find_node (table, key, hash)) == NULL) ? (ppointer) (-1) : node->value;
+}
+
+P_LIB_API PList *
+p_hash_table_keys (const PHashTable *table)
+{
+ PList *ret = NULL;
+ PHashTableNode *node;
+ puint i;
+
+ if (P_UNLIKELY (table == NULL))
+ return NULL;
+
+ for (i = 0; i < table->size; ++i)
+ for (node = table->table[i]; node != NULL; node = node->next)
+ ret = p_list_append (ret, node->key);
+
+ return ret;
+}
+
+P_LIB_API PList *
+p_hash_table_values (const PHashTable *table)
+{
+ PList *ret = NULL;
+ PHashTableNode *node;
+ puint i;
+
+ if (P_UNLIKELY (table == NULL))
+ return NULL;
+
+ for (i = 0; i < table->size; ++i)
+ for (node = table->table[i]; node != NULL; node = node->next)
+ ret = p_list_append (ret, node->value);
+
+ return ret;
+}
+
+P_LIB_API void
+p_hash_table_free (PHashTable *table)
+{
+ PHashTableNode *node, *next_node;
+ puint i;
+
+ if (P_UNLIKELY (table == NULL))
+ return;
+
+ for (i = 0; i < table->size; ++i)
+ for (node = table->table[i]; node != NULL; ) {
+ next_node = node->next;
+ p_free (node);
+ node = next_node;
+ }
+
+ p_free (table->table);
+ p_free (table);
+}
+
+P_LIB_API void
+p_hash_table_remove (PHashTable *table, pconstpointer key)
+{
+ PHashTableNode *node, *prev_node;
+ puint hash;
+
+ if (P_UNLIKELY (table == NULL))
+ return;
+
+ hash = pp_hash_table_calc_hash (key, table->size);
+
+ if (pp_hash_table_find_node (table, key, hash) != NULL) {
+ node = table->table[hash];
+ prev_node = NULL;
+
+ while (node != NULL) {
+ if (node->key == key) {
+ if (prev_node == NULL)
+ table->table[hash] = node->next;
+ else
+ prev_node->next = node->next;
+
+ p_free (node);
+ break;
+ } else {
+ prev_node = node;
+ node = node->next;
+ }
+ }
+ }
+}
+
+P_LIB_API PList *
+p_hash_table_lookup_by_value (const PHashTable *table, pconstpointer val, PCompareFunc func)
+{
+ PList *ret = NULL;
+ PHashTableNode *node;
+ puint i;
+ pboolean res;
+
+ if (P_UNLIKELY (table == NULL))
+ return NULL;
+
+ for (i = 0; i < table->size; ++i)
+ for (node = table->table[i]; node != NULL; node = node->next) {
+ if (func == NULL)
+ res = (node->value == val);
+ else
+ res = (func (node->value, val) == 0);
+
+ if (res)
+ ret = p_list_append (ret, node->key);
+ }
+
+ return ret;
+}