From 7e877be8fb34ab99421a2eaf3d8fb1b96ed95206 Mon Sep 17 00:00:00 2001
From: cheliequan <liequanche@126.com>
Date: 星期四, 08 十二月 2022 21:06:52 +0800
Subject: [PATCH] 增加共享内存hash链表操作
---
/dev/null | 26
src/memfd.c | 12
include/shmht_debug.h | 13
sample/shmht_mytests.c | 495 ++++++++++++++++++
src/CMakeLists.txt | 2
include/shmht_private.h | 90 +++
src/shmht.c | 704 ++++++++++++++++++++++++++
include/shmht_sem.h | 79 ++
sample/CMakeLists.txt | 7
include/shmht.h | 140 +++++
src/Makefile | 23
11 files changed, 1,556 insertions(+), 35 deletions(-)
diff --git a/include/shmht.h b/include/shmht.h
new file mode 100644
index 0000000..9e337c0
--- /dev/null
+++ b/include/shmht.h
@@ -0,0 +1,140 @@
+#ifndef __HASHTABLE_CWC22_H__
+#define __HASHTABLE_CWC22_H__
+
+#include <unistd.h>
+
+struct shmht;
+
+/*! \mainpage lib_shmht
+ *
+ * \section Introduction
+ *
+ * The lib_shmht is a full-functionall hashtable implementation in shared memory.<BR>
+ * This library is designed for high-performace caches, but it can be used for
+ * many pourpouses. <BR>
+ * Design principles of the lib_shmht: <BR>
+ * <b>no-reallocation</b> of the shared memory. So, the HT can't grow in size from it's creation, but you
+ * can define the % of older entries that can be erased when a element has not enought
+ * space.<BR>
+ * <b>concurrency</b>: The accesses are controlled by a semaphore R/W lock implemntation, so not concurrency
+ * problem is possible.<BR>
+ * <b>performance</b>: The performance is the main target of this implementation.<BR>
+ *
+ * It has the next <b>limitations</b>: <BR>
+ * * Key size limited by compiling time.<BR>
+ * * The erased elements are the oldests, not the less used. This is to don't write (and lock the entire ht)
+ * in all the reads.<BR>
+ *
+ * Please, check the design file if you want more specifical data.
+ *
+ */
+
+
+/*!
+ * @name shmht_hashtable
+ * @param name Name of the HashTable.
+ * @param number Number of records.
+ * @param size Size of each record.
+ * @param hashfunction function for hashing keys.
+ * @param key_eq_fn function for determining key equality
+ * @return newly created hashtable or NULL on failure
+ *
+ * This function, takes the existing shared memory, or creates if it does not
+ * exists.
+ * The name is the primary key of the shared memory hash table. If it exists,
+ * the create_hashtable will asociate with the apropiate shared memory.
+ *
+ */
+
+struct shmht *create_shmht(char *name,
+ unsigned int number,
+ size_t size,
+ unsigned int (*hashfunction) (void *),
+ int (*key_eq_fn) (void *, void *));
+
+/*!
+ * @name shmht_insert
+ * @param h the hashtable to insert into
+ * @param k the key - hashtable claims ownership and will free on removal
+ * @param v the value - does not claim ownership
+ * @return > zero for successful insertion, else for error.
+ *
+ * This function does not check for repeated insertions with a duplicate key.
+ * The value returned when using a duplicate key is undefined.
+ * If in doubt, remove before insert.
+ * The size of this hashtable is fixed, so if the hashtable is full, the insert
+ * will fail.
+ */
+
+int
+shmht_insert (struct shmht *h, void *k, size_t key_size, void *v,
+ size_t value_size);
+
+
+/*!
+ * @name shmht_search
+ * @param h the hashtable to search
+ * @param k the key to search for - does not claim ownership
+ * @param key_size Size of the key.
+ * @param returned_size [out], the size of the returned value.
+ * @return the value associated with the key, or NULL if none found
+ *
+ * You should be careful, beacause, this function returns a pointer to the
+ * shared memory area. DO NOT FREE THIS POINTER!
+ */
+
+void *shmht_search (struct shmht *h, void *k, size_t key_size,
+ size_t * returned_size);
+
+
+/*!
+ * @name shmht_remove
+ * @param h the hashtable to remove the item from
+ * @param k the key to search for - does not claim ownership
+ * @param returned_size [out] returns the size of the returned void *.
+ * @return the number of items removed.
+ */
+
+int shmht_remove (struct shmht *h, void *k, size_t key_size);
+
+
+
+/*!
+ * @name shmht_count
+ * @param h the hashtable
+ * @return the number of items stored in the hashtable, -1 if something
+ * nasty happens.
+ */
+int shmht_count (struct shmht *h);
+
+
+/*!
+ * @name shmht_flush
+ * @param h the hashtable
+ * @return 0 if not problem, <0 if error.
+ */
+
+int shmht_flush (struct shmht *h);
+
+/*!
+ * @name shmht_remove_older_entries
+ * @param h the hashtable
+ * @param p the % of older values to erase
+ * @return The number of deleted entries.
+ */
+
+int shmht_remove_older_entries (struct shmht *h, int p);
+
+/*!
+ * @name shmht_destroy
+ * @param h the hashtable
+ *
+ * Be careful with this operation, beacause all the processes that are currently
+ * using the shared memory hash table will fail (it deletes the shared memory and
+ * the semaphores used as mutex).
+ * If you have any doubt, use the hashtable_flush, instead of this function.
+ */
+
+int shmht_destroy (struct shmht *h);
+
+#endif /* __HASHTABLE_CWC22_H__ */
diff --git a/include/shmht_debug.h b/include/shmht_debug.h
new file mode 100644
index 0000000..4b75ba2
--- /dev/null
+++ b/include/shmht_debug.h
@@ -0,0 +1,13 @@
+#ifndef __HASHTABLE_DEBUG__HH__
+#define __HASHTABLE_DEBUG__HH__
+
+//#define __SHMT_DEBUG_MODE__
+
+#ifdef __SHMT_DEBUG_MODE__
+#include <stdio.h>
+#define shmht_debug(a) printf a
+#else
+#define shmht_debug(a)
+#endif
+
+#endif //__HASHTABLE_DEBUG__HH__
diff --git a/include/shmht_private.h b/include/shmht_private.h
new file mode 100644
index 0000000..fb4980f
--- /dev/null
+++ b/include/shmht_private.h
@@ -0,0 +1,90 @@
+#ifndef __HASHTABLE_PRIVATE_CWC22_H__
+#define __HASHTABLE_PRIVATE_CWC22_H__
+
+#include "shmht.h"
+#include <fcntl.h> /* For O_* constants */
+#include <sys/stat.h> /* For mode constants */
+#include <semaphore.h>
+
+//Max size of a key = > By default 512 bytes.
+#define MAX_KEY_SIZE 512
+/*****************************************************************************/
+
+struct entry
+{
+ //Marks if the entry is used or not.
+ int used;
+ //Store the key in a char array, later, transform to a void *, and the
+ //compare function will be who treat it as it is.
+ // BE CAREFULL with keys with longer sizes, the behaviour is not defined!!.
+ char k[MAX_KEY_SIZE];
+ //key_size
+ size_t key_size;
+ //Hash of the key.
+ unsigned int h;
+ //Offset of the next. (Must be in collisions)
+ unsigned int next;
+ //offset of the bucket where the entry is stored on.
+ int bucket;
+ //The size of the stored in the bucket. (This is to allow storing variable size
+ //items, maximun, the size of the bucket). We only copy to the destiny, the
+ //stored size, not all the bucket. [optimization]
+ int bucket_stored_size;
+ //Position where the entry is stored on. In the entries and in the colisions.
+ int position;
+ //Seconds from epoch. This is the creation time.
+ //We use this value for deleting the older values, we use seconds, beacause
+ //is an aproximate cleaning (designed for cache pourposes).
+ long sec;
+};
+
+//Struct only with the flag of used / not.
+struct bucket
+{
+ int used;
+};
+
+
+
+struct internal_hashtable
+{
+ unsigned int tablelength;
+ unsigned int registry_max_size;
+ char * sem_name;
+ sem_t * sem;
+ unsigned int fd;
+ unsigned int entrycount;
+ unsigned int primeindex;
+};
+
+
+struct shmht
+{
+ //Those values are updated at creation time, so, they MUST be pointers.
+ //Are process related values, so to each process return his pointers.
+ void *internal_ht;
+ void *entrypoint;
+ void *collisionentries;
+ void *bucketmarket;
+
+ // Functions related to the data type stored.
+ unsigned int (*hashfn) (void *k);
+ int (*eqfn) (void *k1, void *k2);
+
+};
+
+/*****************************************************************************/
+static unsigned int hash (struct shmht *h, void *k);
+
+/*****************************************************************************/
+/* indexFor */
+static inline unsigned int
+indexFor (unsigned int tablelength, unsigned int hashvalue)
+{
+ return (hashvalue % tablelength);
+};
+
+
+/*****************************************************************************/
+
+#endif /* __HASHTABLE_PRIVATE_CWC22_H__ */
diff --git a/include/shmht_sem.h b/include/shmht_sem.h
new file mode 100644
index 0000000..f7ff6fe
--- /dev/null
+++ b/include/shmht_sem.h
@@ -0,0 +1,79 @@
+/*
+ * This is a R/W lock implementation using the SYS semaphores.
+ * Based on http://www.experts-exchange.com/Programming/Languages/C/Q_23939132.html
+ */
+
+
+#ifndef __HASHTABLE_SEM__
+#define __HASHTABLE_SEM__
+
+#include <sys/types.h>
+#include <sys/ipc.h>
+#include <sys/sem.h>
+#include <stdio.h>
+
+#define SEM_READER 0
+#define SEM_WRITER 1
+
+struct sembuf read_start[] =
+ { {SEM_READER, 1, SEM_UNDO}, {SEM_WRITER, 0, SEM_UNDO} };
+struct sembuf read_end[] = { {SEM_READER, -1, SEM_UNDO} };
+
+struct sembuf write_start1[] = { {SEM_WRITER, 1, SEM_UNDO} };
+struct sembuf write_start2[] =
+ { {SEM_READER, 0, SEM_UNDO}, {SEM_READER, 1, SEM_UNDO} };
+struct sembuf write_fail_end[] = { {SEM_WRITER, -1, SEM_UNDO} };
+struct sembuf write_end[] =
+ { {SEM_READER, -1, SEM_UNDO}, {SEM_WRITER, -1, SEM_UNDO} };
+
+#define SEMOP(semid,tbl,exc) { if(0>semop (semid, tbl, sizeof(tbl)/sizeof(struct sembuf) )){perror("semop: ");return exc;}}
+
+//Necessary stuff for locking.
+int
+write_end_proc (int semid)
+{
+ SEMOP (semid, write_fail_end, 0);
+ return -1;
+}
+
+#define READ_LOCK(semid) SEMOP(semid,read_start,-1)
+#define READ_UNLOCK(semid) SEMOP(semid,read_end,-1)
+
+#define WRITE_LOCK_READERS(semid) (SEMOP(semid,write_start1,-1))
+#define WRITE_LOCK_TO_WRITE(semid) (SEMOP(semid,write_start2,write_end_proc(semid)))
+
+//This macro returns a 0 different value if something goes wrong with the locking.
+#define WRITE_LOCK(semid) (WRITE_LOCK_READERS(semid) && WRITE_LOCK_TO_WRITE(semid))
+
+#define WRITE_UNLOCK(semid) SEMOP(semid,write_end, -1)
+
+int
+read_lock (int semid)
+{
+ READ_LOCK (semid);
+ return 0;
+}
+
+int
+read_unlock (int semid)
+{
+ READ_UNLOCK (semid);
+ return 0;
+}
+
+int
+write_lock (int semid)
+{
+ WRITE_LOCK_READERS (semid);
+ WRITE_LOCK_TO_WRITE (semid);
+ return 0;
+}
+
+int
+write_unlock (int semid)
+{
+ WRITE_UNLOCK (semid);
+ return 0;
+}
+
+#endif // __HASHTABLE_SEM__
diff --git a/sample/CMakeLists.txt b/sample/CMakeLists.txt
index 5270d20..031540c 100644
--- a/sample/CMakeLists.txt
+++ b/sample/CMakeLists.txt
@@ -7,6 +7,7 @@
add_executable(sample_create sample_create.c)
add_executable(sample_open sample_open.c)
add_executable(test_list_in_shm test_list_in_shm.c)
+add_executable(shmht_mytests shmht_mytests.c)
target_link_libraries(sample_create
PRIVATE
@@ -23,3 +24,9 @@
pthread
)
+target_link_libraries(shmht_mytests
+ PRIVATE
+ memfd
+ pthread
+ )
+
diff --git a/sample/shmht_mytests.c b/sample/shmht_mytests.c
new file mode 100644
index 0000000..5b316b1
--- /dev/null
+++ b/sample/shmht_mytests.c
@@ -0,0 +1,495 @@
+//#include <cgreen/cgreen.h>
+#include "shmht.h"
+#include <string.h>
+#include<stdlib.h>
+#include <stdio.h>
+#include <math.h>
+#include <assert.h>
+
+/*dbj2 hash function:*/
+unsigned int
+dbj2_hash (void *str_)
+{
+ unsigned long hash = 5381;
+ char *str = (char *) str_;
+ int c;
+
+ while (0 != (c = *str++))
+ hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
+
+ return (unsigned int) hash;
+}
+
+/* comparison function: */
+int
+str_compar (void *c1, void *c2)
+{
+ char *c1_str = (char *) c1;
+ return !bcmp (c1, c2, strlen (c1_str));
+}
+
+
+/*
+ * \test-name check_create_from_NotExistentFile
+ * \test-function test_check_create_from_NotExistentFile
+ */
+void
+test_check_create_from_NotExistentFile ()
+{
+ size_t key_size = 100;
+ struct shmht *h1 =
+ create_shmht ("Not_Exists_file", 16, key_size, dbj2_hash, str_compar);
+ assert(h1 == NULL);
+} // test_check_create_from_NotExistentFile
+
+
+/*
+ * \test-name check_create_HTs
+ * \test-function test_check_create_HTs
+ */
+void
+test_check_create_HTs ()
+{
+ struct shmht *h1 = NULL;
+ struct shmht *h2 = NULL;
+ size_t key_size = 100;
+
+ h1 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ //assert_not_equal (h1, NULL);
+ assert (h1 != NULL);
+
+ h2 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ //assert_not_equal (h2, NULL);
+ assert (h2 != NULL);
+
+ //Destroy the global shmht
+ shmht_destroy (h1);
+ shmht_destroy (h2);
+
+ //Free the two references
+ free (h1);
+ free (h2);
+} // test_check_create_HTs
+
+
+/*
+ * \test-name check_create_when_inserted
+ * \test-function test_check_create_when_inserted
+ */
+void
+test_check_create_when_inserted ()
+{
+ struct shmht *h1 = NULL;
+ struct shmht *h2 = NULL;
+ char *key = "Key_for_test_check_find";
+ char *stored_value = "This is the stored Value!";
+ size_t key_size = 100;
+
+ h1 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h1 != NULL);
+
+ int shmht_insert_ret = shmht_insert (h1, key, strlen (key)
+ , stored_value,
+ strlen (stored_value) + 1);
+ assert(shmht_insert_ret > 0);
+
+ h2 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert (h2 != NULL);
+
+ //Check that after creation the existing entries are still there.
+ assert(shmht_count (h2) == 0);
+ assert(shmht_count (h1) == 1);
+
+ //Destroy the global shmht
+ shmht_destroy (h1);
+ shmht_destroy (h2);
+
+ //Free the two references
+ free (h1);
+ free (h2);
+
+} // test_check_create_when_inserted
+
+/*
+ * \test-name check_find
+ * \test-function test_check_find
+ */
+void
+test_check_find ()
+{
+ struct shmht *h1 = NULL;
+ struct shmht *h2 = NULL;
+ struct shmht *h3 = NULL;
+ struct shmht *h4 = NULL;
+ char *key = "Key_for_test_check_find";
+ char *stored_value = "This is the stored Value!";
+ size_t key_size = 100;
+
+ h1 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h1 != NULL);
+
+ h2 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h2 != NULL);
+
+ h3 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h3 != NULL);
+
+ h4 = create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h4 != NULL);
+
+ int shmht_insert_ret = shmht_insert (h1, key, strlen (key) , stored_value, strlen (stored_value) + 1);
+ assert(shmht_insert_ret > 0);
+
+ size_t ret_size;
+ void *ret = shmht_search (h1, key, strlen (key), &ret_size);
+
+ assert(ret != NULL);
+ assert(strlen (stored_value) + 1 == ret_size);
+ assert(!strncmp (ret, stored_value, strlen (stored_value) + 1));
+
+ shmht_insert_ret = shmht_insert (h2, key, strlen (key), stored_value, strlen (stored_value) + 1);
+ assert(shmht_insert_ret > 0);
+ ret = shmht_search(h2, key, strlen (key), &ret_size);
+
+ assert(ret != NULL);
+ assert(strlen (stored_value) + 1 == ret_size);
+ assert(!strncmp (ret, stored_value, strlen (stored_value)));
+
+ shmht_insert_ret = shmht_insert (h3, key, strlen (key), stored_value, strlen (stored_value) + 1);
+ assert(shmht_insert_ret > 0);
+ ret = shmht_search(h3, key, strlen (key), &ret_size);
+
+ assert(ret != NULL);
+ assert(strlen (stored_value) + 1 == ret_size);
+ assert(!strncmp (ret, stored_value, strlen (stored_value)));
+
+ shmht_insert_ret = shmht_insert (h4, key, strlen (key), stored_value, strlen (stored_value) + 1);
+ assert(shmht_insert_ret > 0);
+ ret = shmht_search(h4, key, strlen (key), &ret_size);
+
+ assert(ret != NULL);
+ assert(strlen (stored_value) + 1 == ret_size);
+ assert(!strncmp (ret, stored_value, strlen (stored_value)));
+
+
+ //Destroy the global shmht
+ shmht_destroy (h1);
+ shmht_destroy (h2);
+ shmht_destroy (h3);
+ shmht_destroy (h4);
+
+ //Free the two references
+ free (h1);
+ free (h2);
+ free (h3);
+ free (h4);
+
+} // test_check_find
+
+/*
+ * \test-name check_count
+ * \test-function test_check_count
+ */
+void
+test_check_count ()
+{
+ char *key = "Key_for_test_check_count";
+ char *stored_value = "This is the stored Value!";
+ size_t key_size = 100;
+
+ //Create a shmht.
+ struct shmht *h =
+ create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h != NULL);
+
+
+ //Insert a value into.
+ int shmht_insert_ret = shmht_insert (h, key, strlen (key)
+ , stored_value,
+ strlen (stored_value) + 1);
+ assert(shmht_insert_ret > 0);
+
+ //Count
+ assert(shmht_count (h) == 1);
+
+ //Destroy the global shmht
+ shmht_destroy (h);
+
+ assert(shmht_count (h) < 0);
+
+ free (h);
+} // test_check_count
+
+
+/*
+ * \test-name check_long_insertions
+ * \test-function test_check_long_insertions
+ */
+void
+test_check_long_insertions ()
+{
+ char *key = "Key_for_test_check_count";
+ char *stored_value = "This is the stored Value!";
+ size_t key_size = 100;
+ int i;
+
+ //Create a shmht.
+ struct shmht *h =
+ create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h != NULL);
+
+
+ //Insert a value until all is over.
+ for (i = 0; i < 100; i++) {
+ int shmht_insert_ret = shmht_insert (h, key, strlen (key)
+ , stored_value,
+ strlen (stored_value) + 1);
+ if (shmht_insert_ret < 0) {
+ //Insert until there is no more space.
+ break;
+ }
+ }
+
+ int shmht_insert_ret = shmht_insert (h, key, strlen (key)
+ , stored_value,
+ strlen (stored_value) + 1);
+ assert(shmht_insert_ret < 0);
+
+ //Destroy the global shmht
+ shmht_destroy (h);
+
+ assert(shmht_count (h) < 0);
+ free (h);
+
+} // test_check_long_insertions
+
+/*
+ * \test-name check_flush
+ * \test-function test_check_flush
+ */
+void
+test_check_flush ()
+{
+ char *key = "Key_for_test_check_count";
+ char *stored_value = "This is the stored Value!";
+ size_t key_size = 100;
+ int i;
+
+ //Create a shmht.
+ struct shmht *h =
+ create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h != NULL);
+
+ //Create a shmht.
+ struct shmht *h2 =
+ create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h != NULL);
+
+
+ //Insert a value until all is over.
+ for (i = 0; i < 100; i++) {
+ int shmht_insert_ret = shmht_insert (h, key, strlen (key)
+ , stored_value,
+ strlen (stored_value) + 1);
+ if (shmht_insert_ret < 0) {
+ //Insert until there is no more space.
+ break;
+ }
+ }
+
+ //Check that we flush all the entries.
+ assert(shmht_flush (h2) == 0);
+ assert(shmht_count (h) != 0);
+ assert(shmht_count (h2) == 0);
+
+ //Destroy the global shmht
+ shmht_destroy (h);
+ shmht_destroy (h2);
+
+ assert(shmht_count (h) < 0);
+ assert(shmht_count (h2) < 0);
+
+ free (h);
+ free (h2);
+
+} // test_check_flush
+
+/*
+ * \test-name check_remove_older_entries
+ * \test-function test_check_remove_older_entries
+ */
+void
+test_check_remove_older_entries ()
+{
+ char *key = "Key_for_test_check_count";
+ char *stored_value = "This is the stored Value!";
+ size_t key_size = 100;
+ int i;
+
+ //Create a shmht.
+ struct shmht *h =
+ create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert(h != NULL);
+
+
+ //Insert a value 10000 times erasing the older entries.
+ for (i = 0; i < 10000; i++) {
+ int shmht_insert_ret = shmht_insert (h, key, strlen (key)
+ , stored_value,
+ strlen (stored_value) + 1);
+ if (shmht_insert_ret < 0) {
+ //remove the 30% of the older entries.
+ if (shmht_remove_older_entries (h, 30) == 0) {
+ assert(1);
+ break;
+ }
+ }
+ }
+
+ //Destroy the global shmht
+ shmht_destroy (h);
+
+ assert (shmht_count (h) < 0);
+ free (h);
+
+} // test_check_remove_older_entries
+
+
+/*
+ * \test-name check_number_of_removed_with_remove_older
+ * \test-function test_check_number_of_removed_with_remove_older
+ */
+void
+test_check_number_of_removed_with_remove_older ()
+{
+ char *key = "Key_for_test_remove_older";
+ char *stored_value = "This is the stored Value!";
+ size_t key_size = 100;
+ int i;
+
+ //Create a shmht.
+ struct shmht *h =
+ create_shmht ("run_tests", 16, key_size, dbj2_hash, str_compar);
+ assert (h != NULL);
+
+ //Insert a value until all is over.
+ for (i = 0; i < 100; i++) {
+ int shmht_insert_ret = shmht_insert (h, key, strlen (key)
+ , stored_value,
+ strlen (stored_value) + 1);
+ if (shmht_insert_ret < 0) {
+ //Insert until there is no more space.
+ break;
+ }
+ }
+
+ //Store the deletion of the 30% of the entries.
+ int number_of_destroyed_30 = shmht_remove_older_entries (h, 30);
+
+ //Fill the ht again:
+
+ //Insert a value until all is over.
+ for (i = 0; i < 100; i++) {
+ int shmht_insert_ret = shmht_insert (h, key, strlen (key)
+ , stored_value,
+ strlen (stored_value) + 1);
+ if (shmht_insert_ret < 0) {
+ //Insert until there is no more space.
+ break;
+ }
+ }
+ //Get the number of destroyed entries with 50%
+ int number_of_destroyed_50 = shmht_remove_older_entries (h, 50);
+ //Check that with the 50% we destroy more than with the 30%
+ assert(number_of_destroyed_50 > number_of_destroyed_30);
+
+ //Destroy the global shmht
+ shmht_destroy (h);
+
+ assert(shmht_count (h) < 0);
+
+ free (h);
+
+} // test_check_flush
+
+/*
+ * \test-name check_create_huge_number_ht
+ * \test-function test_check_create_huge_number_ht
+ */
+void
+test_check_create_huge_number_ht ()
+{
+ size_t key_size = 100;
+ char *key = "Key_for_huge_ht";
+ char *stored_value = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
+ int i;
+ #define MAX 1000
+
+ struct shmht **h = (struct shmht**)malloc(sizeof(struct shmht *) * MAX);
+
+ //Create a shmht.
+ for (i = 0; i < MAX; i++) {
+ h[i] =
+ create_shmht("run_tests", 16, key_size, dbj2_hash, str_compar);
+ if (h[i] == NULL) {
+ assert(1);
+ break;
+ }
+ }
+
+ assert(shmht_insert (h[0], key, strlen (key) , stored_value, strlen (stored_value) + 1) > 0);
+ //assert(shmht_insert (h[10], key, strlen (key) , stored_value, strlen (stored_value) + 1) > 0);
+
+ //assert(shmht_count (h[10]) == 1);
+ assert(shmht_count (h[0]) == 1);
+
+
+ int ret_size;
+ void *ret = shmht_search(h[0], key, strlen (key), &ret_size);
+
+ assert(ret != NULL);
+ assert(strlen (stored_value) + 1 == ret_size);
+ assert(!strncmp (ret, stored_value, strlen (stored_value)));
+/*
+ assert(strncmp
+ ((char *)
+ shmht_search (h[10], key, strlen (key), (size_t *)&ret_size),
+ stored_value, strlen(stored_value)) == 0);*/
+
+
+ //Destroy the global shmht
+ for (i = 0; i < MAX; i++) {
+ shmht_destroy (h[i]);
+ }
+
+// assert(shmht_count (h[MAX/2]) == 0);
+
+
+ for (i = 0; i < MAX; i++) {
+ free (h[i]);
+ }
+ free(h);
+
+} // test_check_create_huge_number_ht
+
+
+int main (int argc, char * argv [])
+{
+//TestSuite *suite = create_test_suite();
+
+// test_check_create_from_NotExistentFile();
+ test_check_create_HTs();
+
+ test_check_create_when_inserted();
+ test_check_find();
+ test_check_count();
+ test_check_long_insertions();
+ test_check_flush();
+ test_check_remove_older_entries();
+ test_check_number_of_removed_with_remove_older();
+ test_check_create_huge_number_ht();
+
+//return run_test_suite(suite, create_text_reporter());
+ return 0;
+}
+
diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 907383e..8d596ed 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -5,7 +5,7 @@
include_directories(../include)
# add library
-add_library(memfd SHARED memfd.c list_in_shm.c)
+add_library(memfd SHARED memfd.c list_in_shm.c shmht.c)
target_link_libraries(memfd PRIVATE pthread)
diff --git a/src/Makefile b/src/Makefile
index ec69481..5dd8487 100644
--- a/src/Makefile
+++ b/src/Makefile
@@ -1,6 +1,21 @@
-all:
- gcc -g -c -Wall -Werror -fpic list_in_shm.c memfd.c -lpthread
+CC=gcc
+AR=ar
+CFLAGS=-g -D __SHMT_DEBUG_MODE__=1 -Wall -I${INCLUDE}
+INCLUDE=-I. -I ../include
+all:shmht shmht_mytests
+ gcc -g -c -Wall -Werror -I${INCLUDE} -fpic list_in_shm.c memfd.c -lpthread
gcc -shared -o liblistInShm.so list_in_shm.o memfd.o
- gcc test_list_in_shm.c liblistInShm.so -lpthread
+# gcc test_list_in_shm.c liblistInShm.so -lpthread
+shmht: shmht.o memfd.o
+ $(CC) -o libshmht.so $(CFLAGS) -shared $^
+ $(AR) rcs libshmht.a $^
+shmht.o: shmht.c shmht.h
+ $(CC) $(CFLAGS) $(INCLUDE) -fPIC -c shmht.c
+shmht_mytests: shmht_mytests.o shmht.o memfd.o
+ $(CC) $(CFLAGS) $(INCLUDE) -L . -pthread -o $@ $^
+shmht_mytests.o: shmht.h
+ $(CC) $(CFLAGS) $(INCLUDE) -fPIC -c shmht_mytests.c
+memfd.o:
+ $(CC) $(CFLAGS) $(INCLUDE) -fPIC -c memfd.c
clean:
- rm -rf *.so *.o a.out
+ rm -rf *.so *.o a.out shmht_mytests *.a
diff --git a/src/core b/src/core
deleted file mode 100644
index de2eede..0000000
--- a/src/core
+++ /dev/null
Binary files differ
diff --git a/src/list_in_shm.h b/src/list_in_shm.h
deleted file mode 100644
index 1e01924..0000000
--- a/src/list_in_shm.h
+++ /dev/null
@@ -1,65 +0,0 @@
-#ifndef __LIST_IN_SHM_H__
-#define __LIST_IN_SHM_M__
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-#include <sys/types.h>
-#include "stdint.h"
-#include "errno.h"
-#include <unistd.h>
-#include <fcntl.h>
-#include <sys/stat.h>
-#include <semaphore.h>
-#include "stdio.h"
-#include <string.h>
-
-
-typedef struct sm_list_s
-{
- uint32_t n_off;
- uint32_t p_off;
- uint32_t c ;
-// uint32_t mc;
-} sm_list_t;
-
-
-typedef struct node_sm_s
-{
- uint32_t p_off ;
- uint32_t n_off ;
- uint32_t data;
-}node_sm_t ;
-
-typedef struct list_in_shm_handle_s {
- int fd;
- uint64_t size;
- sem_t * sem;
- uint8_t * ptr ;
- sm_list_t *pFreeListStruct;
- sm_list_t *pList;
- uint8_t *pStart;
-
-}list_in_shm_handle_t;
-
-
-#define GET_OFFSET(baseptr,ptr) ((uint8_t *)ptr-(uint8_t *)baseptr)
-#define GET_PTR(baseptr,offset) ((uint8_t *)baseptr+offset)
-#define FROM_FREE_LIST 0x01
-#define FROM_LIST 0x02
-#define FROM_FRONT 0x10
-#define FROM_BACK 0x20
-
-int list_in_shm_init(list_in_shm_handle_t * h, char * name, uint32_t size,uint32_t num,char *nameSem,uint8_t init );
-int list_in_shm_insert_node(sm_list_t * plst, uint8_t * basePtr , node_sm_t * node ,uint8_t front);
-node_sm_t *list_in_shm_get_node(sm_list_t * plst,uint8_t * basePtr,uint8_t front);
-node_sm_t * get_node_from_shm(list_in_shm_handle_t * h,uint8_t flags );
-int put_node_in_list(list_in_shm_handle_t * h,node_sm_t *node,uint8_t flags);
-void list_in_shm_finish(list_in_shm_handle_t * h);
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif
diff --git a/src/memfd.c b/src/memfd.c
index 04ced4d..2509685 100644
--- a/src/memfd.c
+++ b/src/memfd.c
@@ -70,12 +70,16 @@
struct stat st;
/* Create an anonymous file in tmpfs; */
+ if(0 >= len)
+ {
+ return -1;
+ }
fd = sys_memfd_create(name, MFD_CLOEXEC);
if (fd == -1)
{
- errExit("memfd_create");
+ errExit("memfd_create");
}
/* Size the file as specified on the command line */
@@ -83,7 +87,7 @@
mydebug("length: %zu\n", len);
if (ftruncate(fd, len) == -1)
{
- errExit("truncate");
+ errExit("ftruncate");
}
if (fstat (fd, &st))
@@ -174,12 +178,12 @@
}
len = st.st_size;
- ret = munmap(*ppaddr, len);
+ ret = munmap((void *)*ppaddr, len);
if (ret == -1)
{
errExit("munmap()");
}
-
+ *ppaddr = NULL;
mydebug("length: %zu, atime: %lu.%lu\n", len, st.st_atim.tv_sec, st.st_atim.tv_nsec);
return len;
}
diff --git a/src/memfd.h b/src/memfd.h
deleted file mode 100644
index d6db1f9..0000000
--- a/src/memfd.h
+++ /dev/null
@@ -1,26 +0,0 @@
-
-#ifndef MEMFD_H
-#define MEMFD_H
-#include "unistd.h"
-
-#ifdef __cplusplus
-extern "C" {
-#endif
-
-int basic_shm_create(char *name, ssize_t len);
-int basic_shm_open(int fd, pid_t pid, int flags);
-int basic_shm_mmap(int fd, unsigned char** ppaddr);
-int basic_shm_unmmap(int fd, unsigned char** ppaddr);
-int basic_shm_close(int fd);
-int basic_shm_shrink(int fd, ssize_t len);
-int basic_shm_grow(int fd, ssize_t len);
-
-enum{
- local_open_flag = 0,
- remote_open_flag
-};
-
-#ifdef __cplusplus
-}
-#endif
-#endif
diff --git a/src/shmht.c b/src/shmht.c
new file mode 100644
index 0000000..dc23056
--- /dev/null
+++ b/src/shmht.c
@@ -0,0 +1,704 @@
+#include "shmht.h"
+//#include "shmht_sem.h"
+#include "shmht_private.h"
+#include "shmht_debug.h"
+#include <limits.h>
+#include <math.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/sem.h>
+#include <sys/types.h>
+#include <sys/ipc.h>
+#include <sys/shm.h>
+#include <sys/time.h>
+#include <assert.h>
+#include <errno.h>
+#include <fcntl.h> /* For O_* constants */
+#include <sys/stat.h> /* For mode constants */
+#include <semaphore.h>
+#include "memfd.h"
+
+/*
+Credit for primes table: Aaron Krowne
+ http://br.endernet.org/~akrowne/
+ http://planetmath.org/encyclopedia/GoodHashTablePrimes.html
+*/
+static const unsigned int primes[] = {
+ 53, 97, 193, 389,
+ 769, 1543, 3079, 6151,
+ 12289, 24593, 49157, 98317,
+ 196613, 393241, 786433, 1572869,
+ 3145739, 6291469, 12582917, 25165843,
+ 50331653, 100663319, 201326611, 402653189,
+ 805306457, 1610612741
+};
+
+const unsigned int prime_table_length = sizeof (primes) / sizeof (primes[0]);
+const float max_load_factor = 0.65;
+
+/*Necessary union for the semaphore*/
+union semun
+{
+ int val; /* value for SETVAL */
+ struct semid_ds *buf; /* buffer for IPC_STAT, IPC_SET */
+ unsigned short *array; /* array for GETALL, SETALL */
+ struct seminfo *__buf; /* buffer for IPC_INFO */
+};
+
+
+/****************************************************/
+struct shmht *
+create_shmht (char *name,
+ unsigned int number,
+ size_t register_size,
+ unsigned int (*hashf) (void *), int (*eqf) (void *, void *))
+{
+
+ unsigned char *primary_pointer;
+ struct shmht *h;
+ int created = 0;
+ unsigned int pindex, size = primes[0];
+ //Stuff for the semaphore.
+ //union semun arg;
+ //arg.val = 0;
+
+ /* Check requested hashtable isn't too large */
+ if (number > (1u << 30))
+ return NULL;
+ /* Enforce size as prime */
+
+ for (pindex = 0; pindex < prime_table_length; pindex++) {
+ if (primes[pindex] > number) {
+ size = primes[pindex];
+ break;
+ }
+ }
+
+
+ /*Calcule the necessary size for the hash table */
+ //hashtable structure + 2* entry size + buckets.
+ int all_ht_size =
+ sizeof (struct internal_hashtable) +
+ 2 * sizeof (struct entry) * size + (sizeof (struct bucket) +
+ register_size) * size;
+
+ shmht_debug(("create_shmht size=%d, register_size:%u, all_ht_size=%d\n", size, register_size, all_ht_size));
+ int fd = basic_shm_create(name, all_ht_size);
+ if ( 0 >= fd )
+ {
+ printf("\nbasic_shm_create failed errono %u\n",errno);
+ return NULL;
+ }
+ else
+ {
+ created = 1;
+ }
+
+ shmht_debug (("create_shmht: The shmem fd is: %d\n The size is %d \n",
+ fd, all_ht_size));
+
+ char fd_str[16] = {0};
+ int sem_len = strlen(name) + sizeof(fd_str);
+ char * sem_name = (char *)malloc(sem_len+1);
+ memset(sem_name, 0 , sem_len);
+ snprintf(sem_name, sem_len, "%s%d", name, fd);
+ /* Change umask temporarily to make sure the correct permission */
+ mode_t mask = umask(0);
+ sem_t * sem = sem_open(sem_name, O_CREAT | O_RDWR, 0666, 1);
+ umask(mask);
+ if (NULL == sem )
+ {
+ basic_shm_close(fd);
+ printf("\nsem_open failed for name %s %u\n", name, errno);
+ return NULL ;
+ }
+
+ int len = basic_shm_mmap(fd, &primary_pointer);
+ if(0 >= len || (void *) -1 == primary_pointer)
+ {
+ printf("\nbasic_shm_open failed %u\n",errno);
+ basic_shm_close(fd);
+ sem_close(sem);
+ return NULL;
+ }
+
+ h = (struct shmht *) malloc (sizeof (struct shmht));
+
+ if (created) {
+ shmht_debug(("create_shmht: As created, clean all the shm!\n"));
+ bzero (primary_pointer, all_ht_size);
+ }
+
+ //Check if the shmat has worked.
+ if (h == NULL)
+ return h;
+
+ //The created structure:
+ //------------------------------------------------------------
+ //| internal_hashtable | entries | colision entries | buckets |
+ //------------------------------------------------------------
+ //Entries point, use the void* to do the pointer arithmetic:
+ h->internal_ht = (void *)primary_pointer;
+ h->entrypoint = h->internal_ht + sizeof (struct internal_hashtable);
+ //Collision entries:
+ h->collisionentries = h->entrypoint + sizeof (struct entry) * size;
+ //Bucket entries:
+ h->bucketmarket = h->entrypoint + 2 * sizeof (struct entry) * size;
+
+
+ //Store the necessary values:
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+
+ if (created) {
+ iht->sem_name = sem_name;
+ iht->sem = sem;
+ iht->fd = fd;
+ }
+
+ //The register_size
+ if (!created)
+ assert
+ ("Logical Error: initiated with different length the hash table"
+ || iht->registry_max_size != register_size);
+
+ iht->registry_max_size = register_size;
+ //The number of registers
+ if (!created)
+ assert
+ ("Logical Error: initiated with different length the hash table"
+ || iht->tablelength != size);
+ iht->tablelength = size;
+ //Index in the prime array.
+ iht->primeindex = pindex;
+ //Number of entries.
+ if (created)
+ iht->entrycount = 0;
+ //Its possible to update in runtime the hash functions of the HT.
+ //hash function.
+ h->hashfn = hashf;
+ //equal funcion.
+ h->eqfn = eqf;
+ return h;
+} //create_shmht
+
+/*****************************************************************************/
+static unsigned int
+hash (struct shmht *h, void *k)
+{
+ /* Aim to protect against poor hash functions by adding logic here
+ * - logic taken from java 1.4 hashtable source */
+ unsigned int i = h->hashfn (k);
+ i += ~(i << 9);
+ i ^= ((i >> 14) | (i << 18)); /* >>> */
+ i += (i << 4);
+ i ^= ((i >> 10) | (i << 22)); /* >>> */
+ return i;
+}
+
+
+/*****************************************************************************/
+int
+shmht_count (struct shmht *h)
+{
+ int value = -1;
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+ if(NULL == iht)
+ {
+ return -1;
+ }
+ sem_wait(iht->sem);
+ value = iht->entrycount;
+ sem_post(iht->sem);
+ return value;
+} // hashtable_count
+
+
+/****************************************************************************/
+
+//This function looks for free colision entries in the hash table.
+static int
+locate_free_colision_entry (struct shmht *h)
+{
+ int i;
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+ for (i = 0; i < iht->tablelength; i++) {
+ struct entry *aux = h->collisionentries + (i * sizeof (struct entry));
+ if (!aux->used)
+ return i;
+ }
+ return -1;
+} // locate_free_colision_entry
+
+
+/*****************************************************************************/
+
+//This function looks for free buckets in the shm.
+static int
+locate_free_bucket (struct shmht *h)
+{
+ int i;
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+ for (i = 0; i < iht->tablelength; i++) {
+ struct bucket *aux =
+ h->bucketmarket +
+ (i * (sizeof (struct bucket) + iht->registry_max_size));
+ if (!aux->used)
+ return i;
+ }
+ return -1;
+} // locate_free_bucket
+
+/*****************************************************************************/
+int
+shmht_insert (struct shmht *h, void *k, size_t key_size,
+ void *v, size_t value_size)
+{
+
+ //first acquire the lock.
+ //If it fails return -ECANCELED.
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+
+ sem_wait(iht->sem);
+
+ int index = -1;
+ unsigned int key_hash;
+ struct timeval tv;
+
+ if (value_size > iht->registry_max_size) {
+ sem_post(iht->sem);
+ return -EINVAL;
+ }
+
+ if (key_size > MAX_KEY_SIZE) {
+ sem_post(iht->sem);
+ return -EINVAL;
+ }
+
+ //Test if we have reached the max size of the HT. This is FIXED.
+ if (iht->tablelength <= iht->entrycount) {
+ sem_post(iht->sem);
+ return -1;
+ }
+
+ //By default if there is size, should be free buckets, but check is almost free.
+ index = locate_free_bucket (h);
+ if (index < 0) {
+ sem_post(iht->sem);
+ return -1;
+ }
+
+ //Get the seconds from epoch:
+ gettimeofday (&tv, NULL);
+
+ //Set to used.
+ struct bucket *bucket_ptr =
+ h->bucketmarket +
+ (index * (sizeof (struct bucket) + iht->registry_max_size));
+ bucket_ptr->used = 1;
+ //Copy the value in the bucket.
+ memcpy (h->bucketmarket +
+ (index * (sizeof (struct bucket) + iht->registry_max_size)) +
+ sizeof (struct bucket)
+ , v, value_size);
+ shmht_debug (("shmht_insert: Located free bucket in %d\n", index));
+ key_hash = hash (h, k);
+ int entryIndex = indexFor (iht->tablelength, key_hash);
+ shmht_debug (("shmht_insert: Generated Entry Index: %d \n",
+ entryIndex));
+ struct entry *index_Entry =
+ h->entrypoint + (entryIndex * sizeof (struct entry));
+
+ if (!index_Entry->used) {
+ //!Colision
+ index_Entry->used = 1;
+
+ memcpy (index_Entry->k, k, key_size);
+ index_Entry->key_size = key_size;
+ index_Entry->h = key_hash;
+ index_Entry->next = -1;
+ index_Entry->bucket = index;
+ index_Entry->position = entryIndex;
+ index_Entry->bucket_stored_size = value_size;
+ index_Entry->sec = tv.tv_sec;
+
+ }
+ else {
+ //Colision
+ shmht_debug (("shmht_insert: Collision in the entry %d \n",
+ entryIndex));
+ int colision_index = locate_free_colision_entry (h);
+
+ //Paranoid check.
+ assert (colision_index == -1
+ || "Logical Error: Not free colision entries");
+ shmht_debug (("shmht_insert: Located free colision entry : %d\n",
+ colision_index));
+ struct entry *colision_Entry =
+ h->collisionentries + (colision_index * sizeof (struct entry));
+ //Paranoid check.
+ assert (colision_Entry->used
+ ||
+ "Logical Error: locate_free_colision_entry returns a used entry!");
+ colision_Entry->used = 1;
+ memcpy (colision_Entry->k, k, key_size);
+ colision_Entry->key_size = key_size;
+ colision_Entry->h = key_hash;
+ colision_Entry->next = -1;
+ colision_Entry->position = colision_index;
+ colision_Entry->bucket = index;
+ colision_Entry->bucket_stored_size = value_size;
+ colision_Entry->sec = tv.tv_sec;
+ //Look for the previous one.
+ if (index_Entry->next == -1) {
+ //There are not more colisions.
+ index_Entry->next = colision_index;
+ colision_Entry->next = -1;
+ }
+ else {
+ //Look for the previous!
+ struct entry *aux = index_Entry;
+ while (aux->next != -1)
+ aux =
+ h->collisionentries + (aux->next * sizeof (struct entry));
+ //Set all the stuff of entries:
+ aux->next = colision_index;
+ colision_Entry->next = -1;
+ }
+ }
+ // Add 1 to the entrycount.
+ iht->entrycount++;
+ //unlock the write sem.
+ sem_post(iht->sem);
+
+ return 1;
+} // shmht_insert
+
+/*****************************************************************************/
+//Compare two keys :D
+//Return 0 if equal, 1 if not.
+
+static int
+compareBinaryKeys (size_t sk1, void *k1, size_t sk2, void *k2)
+{
+ //First compare key sizes:
+ if (sk1 != sk2)
+ return 1;
+
+ return bcmp (k1, k2, sk1);
+} // compareBinaryKeys
+
+/*****************************************************************************/
+void * /* returns the fist value associated with key */
+shmht_search (struct shmht *h, void *k, size_t key_size,
+ size_t * returned_size)
+{
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+ sem_wait(iht->sem);
+ void *retValue = NULL;
+ struct entry *index_Entry;
+ unsigned int hashvalue, index;
+
+ //Calcule the hash
+ hashvalue = hash (h, k);
+ //Look for the index in the hashtable.
+ index = indexFor (iht->tablelength, hashvalue);
+ shmht_debug (("shmht_search: Index for this key: %d", index));
+ //Calcule the offset:
+ index_Entry = h->entrypoint + (index * sizeof (struct entry));
+ while (index_Entry != NULL && index_Entry->used) {
+ /* Check hash value to short circuit heavier comparison */
+ if (hashvalue == index_Entry->h
+ &&
+ !compareBinaryKeys (index_Entry->key_size,
+ (void *) index_Entry->k, key_size, k)) {
+ shmht_debug (("shmht_search: finded shmht_search!\n"));
+ //Look for the bucket.
+ //Calcule it as: buckets offset + number * sizeof(complete bucket)
+ //+ sizeof(bucket structure)
+ retValue = h->bucketmarket +
+ (index_Entry->bucket *
+ (sizeof (struct bucket) + iht->registry_max_size))
+ + sizeof (struct bucket);
+ (*returned_size) = index_Entry->bucket_stored_size;
+
+ //Paranoid check ;)
+ struct bucket *target_bucket = h->bucketmarket +
+ (index_Entry->bucket *
+ (sizeof (struct bucket) + iht->registry_max_size));
+ assert (target_bucket->used == 1
+ || "Logical Error: found an entry with Empty bucket");
+
+ break;
+ }
+
+ //If there is not in the entries... look in colisions :D
+ index_Entry = (index_Entry->next != -1) ?
+ h->collisionentries + (index_Entry->next * sizeof (struct entry))
+ : NULL;
+ }
+ sem_post(iht->sem);
+
+ return retValue;
+} // shmht_search
+
+/*****************************************************************************/
+
+
+/*
+ Since hashtable_remove can be called from a locked context, I've extracted the logic
+ into an internal function, and left only the lock/unlock logic in the hastable_remove
+ function.
+ To call from a locked context, call __shmht_remove__ instead hashtable_remove
+ */
+static int
+__shmht_remove__ (struct shmht *h, void *k, size_t key_size)
+{
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+ struct entry *index_Entry = NULL;
+ struct entry *previous_Entry = NULL; // previous Entry
+ int retValue = 0;
+ unsigned int hashvalue, index;
+
+ hashvalue = hash (h, k);
+ index = indexFor (iht->tablelength, hash (h, k));
+
+ shmht_debug (("__shmht_remove__: Index for this key: %d\n", index));
+ //Calcule the offset:
+ index_Entry = h->entrypoint + (index * sizeof (struct entry));
+ while (index_Entry != NULL && index_Entry->used) {
+ /* Check hash value to short circuit heavier comparison */
+ if (hashvalue == index_Entry->h
+ &&
+ !compareBinaryKeys (index_Entry->key_size,
+ (void *) index_Entry->k, key_size, k)) {
+ shmht_debug (("__shmht_remove__: finded hashtable_remove!\n"));
+ break;
+ }
+
+ //If there is not in the entries... look in colisions :D
+ previous_Entry = index_Entry;
+ index_Entry = (index_Entry->next != -1) ?
+ h->collisionentries + (index_Entry->next * sizeof (struct entry))
+ : NULL;
+ }
+
+ //If the key has been found:
+ if (index_Entry != NULL && index_Entry->used) {
+ //First, mark the bucket as not used.
+ struct bucket *target_bucket = h->bucketmarket +
+ (index_Entry->bucket *
+ (sizeof (struct bucket) + iht->registry_max_size));
+ target_bucket->used = 0;
+ //+1 to the retValue (by default 0)
+ retValue += 1;
+ //Decrease the hash table entry count.
+ iht->entrycount -= 1;
+ if (!previous_Entry) {
+ //The found instance is NOT stored in Colision.
+ //So, we must copy to Entries the first of Colision.
+ if (index_Entry->next != -1) {
+ //Found the copy
+ struct entry *next_Entry =
+ h->collisionentries +
+ (index_Entry->next * sizeof (struct entry));
+ //Direct copy of the context of the next entry into entries.
+ int aux_position = index_Entry->position;
+ (*index_Entry) = (*next_Entry);
+ //Delete the "used" from the entry
+ next_Entry->used = 0;
+ //Set the correct position
+ index_Entry->position = aux_position;
+ }
+ else //There is not colision.
+ index_Entry->used = 0;
+ }
+ else {
+ //The found instance is stored in Colision:
+ previous_Entry->next = index_Entry->next;
+ //Mark the entry as not used.
+ index_Entry->used = 0;
+ }
+ }
+ // Now we're in a consistent state.
+
+ return retValue;
+} // __shmht_remove__
+
+
+/****************************************************************************/
+int
+shmht_remove (struct shmht *h, void *k, size_t key_size)
+{
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+ sem_wait(iht->sem);
+ int retValue = __shmht_remove__ (h, k, key_size);
+ sem_post(iht->sem);
+ return retValue;
+} // hashtable_remove
+
+/*****************************************************************************/
+
+int
+shmht_flush (struct shmht *h)
+{
+
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+ sem_wait(iht->sem);
+ int i;
+ //First, clear all the buckets:
+ for (i = 0; i < iht->tablelength; i++) {
+ struct bucket *target_bucket = h->bucketmarket +
+ (i * (sizeof (struct bucket) + iht->registry_max_size));
+ target_bucket->used = 0;
+ }
+
+ struct entry *target_entry;
+ //Second, clear all the entries:
+ for (i = 0; i < iht->tablelength; i++) {
+ target_entry = h->entrypoint + (i * sizeof (struct entry));
+ target_entry->used = 0;
+ }
+
+ //Last, clear all the colisions.
+ for (i = 0; i < iht->tablelength; i++) {
+ target_entry = h->collisionentries + (i * sizeof (struct entry));
+ target_entry->used = 0;
+ }
+ iht->entrycount = 0;
+ sem_post(iht->sem);
+ return 0;
+
+} // shmht_flush
+
+/****************************************************************************/
+
+int
+shmht_remove_older_entries (struct shmht *h, int p)
+{
+ //Define a local aux structure ;D
+ struct finder_aux_struct
+ {
+ long sec;
+ int is_in_col;
+ int index;
+ };
+ //Define a local function.
+ void insert_older_if_necessary (struct entry *e,
+ struct finder_aux_struct *into,
+ unsigned int size_of_into, int is_in_col)
+ {
+
+ int i;
+ //Var that points to the place to replace.
+ struct finder_aux_struct *aux = NULL;
+ for (i = 0; i < size_of_into; i++){
+ //x printf ("Comparison => entry: %ld, struct: %ld \n", e->sec, into[i].sec);
+ if (e->sec < into[i].sec) {
+ //If it's -1, it's not initiated, stop.
+ aux = &into[i];
+ break;
+ }
+ }
+
+ if (aux != NULL) {
+ //In aux, we have the element to replace.
+ shmht_debug (("insert_older_if_necessary: Inserted Entry : secs %ld, is_in_col: %d, position: %d \n"
+ , e->sec, is_in_col, e->position));
+ aux->sec = e->sec;
+ aux->is_in_col = is_in_col;
+ aux->index = e->position;
+ }
+ } // insert_older_if_necessary
+
+
+
+ //Check before lock:
+ if (p > 100)
+ return -EINVAL;
+
+ struct internal_hashtable *iht = (struct internal_hashtable *)h->internal_ht;
+
+ sem_wait(iht->sem);
+
+ //Start the stuff
+ int retValue = 0;
+ //Calcule the number of entries to delete:
+ int deleteEntries = iht->tablelength * p / 100;
+
+ shmht_debug (("shmht_remove_older_entries: Number of entries to Delete: %d\n", deleteEntries));
+
+ struct finder_aux_struct older_storage[deleteEntries];
+
+ int i;
+ //Init the struct:
+ for (i = 0; i < deleteEntries; i++) {
+ older_storage[i].sec = LONG_MAX;
+ older_storage[i].is_in_col = -1;
+ older_storage[i].index = -1;
+ }
+
+ //Go around the structs:
+ //Mantain ordered the structure.
+ struct entry *target_entry;
+ //Second, clear all the entries:
+ for (i = 0; i < iht->tablelength; i++) {
+ target_entry = h->entrypoint + (i * sizeof (struct entry));
+ if (target_entry->used)
+ insert_older_if_necessary (target_entry, older_storage,
+ deleteEntries, 0);
+ }
+
+ //Last, clear all the colisions.
+ for (i = 0; i < iht->tablelength; i++) {
+ target_entry = h->collisionentries + (i * sizeof (struct entry));
+ if (target_entry->used)
+ insert_older_if_necessary (target_entry, older_storage,
+ deleteEntries, 1);
+ }
+
+
+ //Now, delete the entries stored in older_storage:
+ for (i = 0; i < deleteEntries; i++) {
+ if (older_storage[i].index != LONG_MAX) {
+ if (!older_storage[i].is_in_col)
+ target_entry =
+ h->entrypoint +
+ (older_storage[i].index * sizeof (struct entry));
+ else
+ target_entry =
+ h->collisionentries +
+ (older_storage[i].index * sizeof (struct entry));
+ __shmht_remove__ (h, target_entry->k, target_entry->key_size);
+ retValue++;
+ }
+ else
+ break;
+ } //for
+
+ sem_post(iht->sem);
+ return retValue;
+} // shmht_remove_older_entries
+
+
+/****************************************************************************/
+
+/* destroy, it destroys all the shared memory and the semaphores :P*/
+int
+shmht_destroy (struct shmht *h)
+{
+ struct internal_hashtable *iht = (struct internal_hashtable *)(h->internal_ht);
+ //Wait untill there are not more processess.
+ //Delete the shared memory.
+ sem_wait(iht->sem);
+ sem_post(iht->sem);
+
+ int fd = iht->fd;
+ sem_close(iht->sem);
+ sem_unlink(iht->sem_name);
+ free(iht->sem_name);
+ basic_shm_unmmap(fd, (unsigned char **)&iht);
+ basic_shm_close(fd);
+ h->internal_ht = NULL;
+ return 0;
+} // shmht_destroy
--
Gitblit v1.8.0