RPA Toolkit
work on the hash
authormstoilov <mstoilov@b0bb84a5-424d-4f98-af44-3ef3f117eb03>
Sat, 21 Aug 2010 07:21:23 +0000 (00:21 -0700)
committermstoilov <mstoilov@b0bb84a5-424d-4f98-af44-3ef3f117eb03>
Sat, 21 Aug 2010 07:21:23 +0000 (00:21 -0700)
git-svn-id: svn+ssh://svn.crossrain.com/svn/rpase/trunk/rtk@160 b0bb84a5-424d-4f98-af44-3ef3f117eb03

arch/linux/x86_64/rtypes.h
rlib/build/linux/rlib.mk
rlib/rhash.c
rlib/rhash.h
rlib/rlist.c
rlib/rlist.h
tests/build/linux/robject-tests.mk
tests/rhash-test.c [new file with mode: 0644]

index ba6c82e..afbeb50 100644 (file)
@@ -70,5 +70,14 @@ typedef unsigned int ratomic_t;
 #endif
 #endif
 
+#ifndef TRUE
+#define TRUE ((rboolean)1)
+#endif
+
+#ifndef FALSE
+#define FALSE ((rboolean)0)
+#endif
+
+
 #endif
 
index f9b48db..d33c88c 100644 (file)
@@ -7,9 +7,9 @@ RLIB_OBJECTS =  \
        $(OUTDIR)/ratomic.o \
        $(OUTDIR)/rspinlock.o \
        $(OUTDIR)/rarray.o \
-       $(OUTDIR)/rlist.o \
        $(OUTDIR)/rhash.o \
        $(OUTDIR)/rstring.o \
+       $(OUTDIR)/rlist.o \
 
 
 ifeq ($(OS), linux)
index c29c63f..00921b9 100644 (file)
@@ -1,7 +1,61 @@
 #include "rmem.h"
+#include "rstring.h"
 #include "rhash.h"
 
 
+typedef struct rhash_node_s {
+       rlink_t lnk;
+       rconstpointer key;
+       rpointer value;
+} rhash_node_t;
+
+
+static rhash_node_t *r_hash_node_create()
+{
+       rhash_node_t *node;
+
+       return (rhash_node_t *)r_malloc(sizeof(*node));
+}
+
+
+static void r_hash_node_destroy(rhash_node_t *node)
+{
+       r_free(node);
+}
+
+
+static rhash_node_t *r_hash_node_lookup(rhash_t* hash, rconstpointer key)
+{
+       ruint nbucket = hash->hfunc(key) & r_hash_mask(hash);
+       rhash_node_t *node;
+       rlink_t *pos;
+
+       r_list_foreach(pos, &hash->buckets[nbucket]) {
+               node = r_list_entry(pos, rhash_node_t, lnk);
+               if (hash->eqfunc(node->key, key)) {
+                       return node;
+               }
+       }
+       return NULL;
+}
+
+
+ruint r_hash_strhash(rconstpointer key)
+{
+       const rchar *str = (const rchar*) key;
+       ruint hash = 0;
+       int c;
+
+       while ((c = *str++))
+               hash = c + (hash << 6) + (hash << 16) - hash;
+       return hash;
+}
+
+
+rboolean r_hash_strequal(rconstpointer key1, rconstpointer key2)
+{
+       return r_strcmp((const rchar*)key1, (const rchar*)key2) ? FALSE : TRUE;
+}
 
 rhash_t *r_hash_create(ruint nbits, r_hash_equalfunc eqfunc, r_hash_hashfun hfunc)
 {
@@ -21,21 +75,83 @@ rhash_t *r_hash_create(ruint nbits, r_hash_equalfunc eqfunc, r_hash_hashfun hfun
 
 rhash_t *r_hash_init(rhash_t *hash, ruint nbits, r_hash_equalfunc eqfunc, r_hash_hashfun hfunc)
 {
+       ruint i;
+       rsize_t size;
+
        hash->nbits = nbits;
        hash->eqfunc = eqfunc;
        hash->hfunc = hfunc;
        hash->buckets = (rlist_t*)r_malloc(sizeof(rlist_t) * r_hash_size(hash));
-       return NULL;
+       if (!hash->buckets)
+               return NULL;
+       size = r_hash_size(hash);
+       for (i = 0; i < size; i++) {
+               r_list_init(&hash->buckets[i]);
+       }
+       return hash;
 }
 
 
 void r_hash_destroy(rhash_t *hash)
 {
+       r_hash_cleanup(hash);
        r_free(hash);
 }
 
 
 void r_hash_cleanup(rhash_t *hash)
 {
+       r_hash_removeall(hash);
        r_free(hash->buckets);
 }
+
+
+void r_hash_insert(rhash_t* hash, rconstpointer key, rpointer value)
+{
+       ruint nbucket = hash->hfunc(key) & r_hash_mask(hash);
+       rhash_node_t *node = r_hash_node_create();
+       if (node) {
+               r_list_init(&node->lnk);
+               node->key = key;
+               node->value = value;
+       }
+       r_list_addt(&hash->buckets[nbucket], &node->lnk);
+
+}
+
+
+void r_hash_remove(rhash_t* hash, rconstpointer key)
+{
+       rhash_node_t *node;
+
+       while ((node = r_hash_node_lookup(hash, key)) != NULL) {
+               r_list_del(&node->lnk);
+               r_hash_node_destroy(node);
+       }
+}
+
+
+void r_hash_removeall(rhash_t* hash)
+{
+       ruint nbucket;
+       rhead_t *head;
+       rhash_node_t *node;
+
+       for (nbucket = 0; nbucket < r_hash_size(hash); nbucket++) {
+               head = &hash->buckets[nbucket];
+               while (!r_list_empty(head)) {
+                       node = r_list_entry(r_list_first(head), rhash_node_t, lnk);
+                       r_list_del(&node->lnk);
+                       r_hash_node_destroy(node);
+               }
+       }
+}
+
+
+rpointer r_hash_lookup(rhash_t* hash, rconstpointer key)
+{
+       rhash_node_t *node = r_hash_node_lookup(hash, key);
+       if (node)
+               return node->value;
+       return NULL;
+}
index 36900f0..c435d1e 100644 (file)
@@ -10,9 +10,10 @@ extern "C" {
 
 
 typedef struct rhash_s rhash_t;
-typedef rboolean (*r_hash_equalfunc)(rconstpointer p1, rconstpointer p2);
+typedef rboolean (*r_hash_equalfunc)(rconstpointer key1, rconstpointer key2);
 typedef ruint (*r_hash_hashfun)(rconstpointer key);
 
+
 struct rhash_s {
        rlist_t *buckets;
        ruint nbits;
@@ -22,11 +23,18 @@ struct rhash_s {
 
 
 #define r_hash_size(__h__) (1 << (__h__)->nbits)
-#define r_hash_mask(__h__) (R_HASH_SIZE(__h__) - 1)
+#define r_hash_mask(__h__) (r_hash_size(__h__) - 1)
 rhash_t *r_hash_create(ruint nbits, r_hash_equalfunc eqfunc, r_hash_hashfun hfunc);
 rhash_t *r_hash_init(rhash_t *hash, ruint nbits, r_hash_equalfunc eqfunc, r_hash_hashfun hfunc);
 void r_hash_destroy(rhash_t *hash);
 void r_hash_cleanup(rhash_t *hash);
+void r_hash_insert(rhash_t* hash, rconstpointer key, rpointer value);
+void r_hash_remove(rhash_t* hash, rconstpointer key);
+void r_hash_removeall(rhash_t* hash);
+rpointer r_hash_lookup(rhash_t* hash, rconstpointer key);
+
+ruint r_hash_strhash(rconstpointer key);
+rboolean r_hash_strequal(rconstpointer key1, rconstpointer key2);
 
 #ifdef __cplusplus
 }
index b7215ef..846b94e 100644 (file)
@@ -1,14 +1,14 @@
 #include "rlist.h"
 
 
-void rpa_list_init(rlist_t *ptr)
+void r_list_init(rlist_t *ptr)
 {
        ptr->next = ptr;
        ptr->prev = ptr;
 }
 
 
-void rpa_list_add(rlist_t *pNew, rlist_t *pPrev, rlist_t *pNext)
+void r_list_add(rlist_t *pNew, rlist_t *pPrev, rlist_t *pNext)
 {
        pNext->prev = pNew;
        pNew->next = pNext;
@@ -17,56 +17,56 @@ void rpa_list_add(rlist_t *pNew, rlist_t *pPrev, rlist_t *pNext)
 }
 
 
-void rpa_list_addh(rlist_t *pHead, rlist_t *pNew)
+void r_list_addh(rlist_t *pHead, rlist_t *pNew)
 {
-       rpa_list_add(pNew, pHead, (pHead)->next);
+       r_list_add(pNew, pHead, (pHead)->next);
 }
 
 
-void rpa_list_addt(rlist_t *pHead, rlist_t *pNew)
+void r_list_addt(rlist_t *pHead, rlist_t *pNew)
 {
-       rpa_list_add(pNew, (pHead)->prev, pHead);
+       r_list_add(pNew, (pHead)->prev, pHead);
 }
 
 
-void rpa_list_unlink(rlist_t *pPrev, rlist_t *pNext)
+void r_list_unlink(rlist_t *pPrev, rlist_t *pNext)
 {
        pNext->prev = pPrev;
        pPrev->next = pNext;
 }
 
 
-void rpa_list_del(rlist_t *pEntry)
+void r_list_del(rlist_t *pEntry)
 {
-       rpa_list_unlink((pEntry)->prev, (pEntry)->next);
+       r_list_unlink((pEntry)->prev, (pEntry)->next);
 }
 
 
-rlist_t *rpa_list_first(rlist_t *pHead)
+rlist_t *r_list_first(rlist_t *pHead)
 {
        return (((pHead)->next != (pHead)) ? (pHead)->next: ((void*)0));
 }
 
 
-rlist_t *rpa_list_last(rlist_t *pHead)
+rlist_t *r_list_last(rlist_t *pHead)
 {
        return (((pHead)->prev != (pHead)) ? (pHead)->prev: ((void*)0));
 }
 
 
-rlist_t *rpa_list_prev(rlist_t *pHead, rlist_t *pElem)
+rlist_t *r_list_prev(rlist_t *pHead, rlist_t *pElem)
 {
        return (pElem && pElem->prev != pHead) ? (pElem)->prev: ((void*)0);
 }
 
 
-rlist_t *rpa_list_next(rlist_t *pHead, rlist_t *pElem)
+rlist_t *r_list_next(rlist_t *pHead, rlist_t *pElem)
 {
        return (pElem && pElem->next != pHead) ? pElem->next: ((void*)0);
 }
 
 
-void rpa_list_splice(rlist_t *pList, rlist_t *pHead)
+void r_list_splice(rlist_t *pList, rlist_t *pHead)
 {
        rlist_t *pFirst;
 
@@ -82,7 +82,7 @@ void rpa_list_splice(rlist_t *pList, rlist_t *pHead)
 }
 
 
-int rpa_list_count(rlist_t *pHead)
+int r_list_count(rlist_t *pHead)
 {
        rlist_t *pCur;
        int n = 0;
index 6b0139d..94cdeca 100644 (file)
@@ -11,9 +11,9 @@ extern "C" {
 typedef struct rlist_s rlist_t, rlink_t, rhead_t;
 
 #define R_LIST_HEAD(__name__) {&(__name__), &(__name__) }
-#define r_list(__name__) t __name__ = { &(__name__), &(__name__) }
+#define r_list(__name__) rlist_t __name__ = { &(__name__), &(__name__) }
 #define r_list_empty(__head__) ((__head__)->next == ((void*)0) || (__head__)->next == __head__)
-#define r_list_entry(_ptr, _type, __member__) ((_type *)((char *)(_ptr)-(ruint)(&((_type *)0)->__member__)))
+#define r_list_entry(__ptr__, __type__, __member__) ((__type__ *)((char *)(__ptr__)-(rword)(&((__type__ *)0)->__member__)))
 #define r_list_foreach(__pos__, __head__) for (__pos__ = (__head__)->next; __pos__ != (__head__); __pos__ = (__pos__)->next)
 #define r_list_foreachreverse(__pos__, __head__) for (__pos__ = (__head__)->prev; __pos__ != (__head__); __pos__ = (__pos__)->prev)
 #define r_list_fo_eachsafe(__pos__, __n__, __head__) \
index 7b41773..f502f99 100644 (file)
@@ -12,6 +12,7 @@ LIBS += -lrvm -lrlib -lpthread --static
 TESTS  = \
        $(OUTDIR)/rlock-test \
        $(OUTDIR)/rarray-test \
+       $(OUTDIR)/rhash-test \
        $(OUTDIR)/rvm-test \
        $(OUTDIR)/memalloc-test \
        $(OUTDIR)/asm-add \
diff --git a/tests/rhash-test.c b/tests/rhash-test.c
new file mode 100644 (file)
index 0000000..f17d4f4
--- /dev/null
@@ -0,0 +1,27 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include "rhash.h"
+#include "rmem.h"
+
+
+int main(int argc, char *argv[])
+{
+       rhash_t *h;
+       ruint idig[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+       rchar *sdig[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
+
+       h = r_hash_create(5, r_hash_strequal, r_hash_strhash);
+       r_hash_insert(h, sdig[0], &idig[0]);
+       r_hash_insert(h, sdig[7], &idig[7]);
+       r_hash_insert(h, sdig[7], &idig[8]);
+       r_hash_insert(h, sdig[5], &idig[5]);
+       fprintf(stdout, "key: %s, value: %d\n", "seven", *((ruint*)r_hash_lookup(h, "seven")));
+       fprintf(stdout, "key: %s, value: %d\n", sdig[5], *((ruint*)r_hash_lookup(h, sdig[5])));
+       fprintf(stdout, "key: %s, value: %d\n", sdig[0], *((ruint*)r_hash_lookup(h, sdig[0])));
+
+       r_hash_destroy(h);
+
+       fprintf(stdout, "Max alloc mem: %ld\n", r_debug_get_maxmem());
+       fprintf(stdout, "Leaked mem: %ld\n", r_debug_get_allocmem());
+       return 0;
+}