RPA Toolkit
Work on rmap_t - 2
authorMartin Stoilov <martin@rpasearch.com>
Mon, 6 Jun 2011 04:27:39 +0000 (21:27 -0700)
committerMartin Stoilov <martin@rpasearch.com>
Mon, 6 Jun 2011 04:27:39 +0000 (21:27 -0700)
rlib/rmap.c
rlib/rmap.h
rlib/robject.h
rlib/rstring.c
tests/testmisc/build/linux/misc-tests.mk

index 85d59cd..08d788f 100644 (file)
@@ -3,12 +3,69 @@
 #include "rmem.h"
 
 
 #include "rmem.h"
 
 
-typedef struct rmap_node_s {
-       rstr_t key;
-       rpointer value;
+typedef struct r_mapnode_s {
+       rstr_t *key;
+       rsize_t index;
        rlink_t active;
        rlink_t hash;
        rlink_t active;
        rlink_t hash;
-} rmap_node_t;
+} r_mapnode_t;
+
+
+static rboolean r_map_rstrequal(rstr_t *key1, rstr_t *key2)
+{
+       return (key1->size == key2->size && r_strncmp((const rchar*)key1->str, (const rchar*)key2->str, key1->size) == 0) ? TRUE : FALSE;
+}
+
+
+static rulong r_map_rstrhash(const rstr_t *key)
+{
+       const rchar *str = (const rchar*) key->str;
+       rulong i;
+       rulong size = key->size;
+       rulong hash = 0;
+
+       for (i = 0; i < size; i++, str++) {
+               hash = *str + (hash << 6) + (hash << 16) - hash;
+       }
+       return hash;
+}
+
+r_mapnode_t *r_mapnode_create(const rchar *key, rsize_t size)
+{
+       r_mapnode_t *node = (r_mapnode_t *)r_zmalloc(sizeof(*node));
+       node->key = r_rstrdup(key, size);
+       r_list_init(&node->active);
+       r_list_init(&node->hash);
+       return node;
+}
+
+
+r_mapnode_t *r_map_allocnode(rmap_t *map, const rchar *key, rsize_t size)
+{
+       r_mapnode_t *node = NULL;
+
+       if (r_list_empty(&map->inactive)) {
+               rlong index = r_carray_add(map->data, NULL);
+               node = r_mapnode_create(key, size);
+               node->index = index;
+       } else {
+               node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
+               r_list_del(&node->active);
+               node->key = r_rstrdup(key, size);
+               r_list_init(&node->active);
+               r_list_init(&node->hash);
+       }
+       return node;
+}
+
+
+void r_mapnode_destroy(r_mapnode_t *node)
+{
+       if (node)
+               r_free(node->key);
+       r_free(node);
+}
+
 
 
 robject_t *r_map_copy(const robject_t *obj)
 
 
 robject_t *r_map_copy(const robject_t *obj)
@@ -19,27 +76,58 @@ robject_t *r_map_copy(const robject_t *obj)
 
 void r_map_cleanup(robject_t *obj)
 {
 
 void r_map_cleanup(robject_t *obj)
 {
+       r_mapnode_t *node;
        rmap_t *map = (rmap_t*)obj;
        rmap_t *map = (rmap_t*)obj;
-       r_carray_destroy(map->members);
-       r_hash_destroy(map->hash);
+
+       while (!r_list_empty(&map->active)) {
+               node = r_list_entry(r_list_first(&map->active), r_mapnode_t, active);
+               r_list_del(&node->active);
+               r_mapnode_destroy(node);
+       }
+       while (!r_list_empty(&map->inactive)) {
+               node = r_list_entry(r_list_first(&map->inactive), r_mapnode_t, active);
+               r_list_del(&node->active);
+               r_mapnode_destroy(node);
+       }
+
+       r_carray_destroy(map->data);
+       r_array_destroy(map->nodes);
+       r_free(map->hash);
        r_object_cleanup(&map->obj);
 }
 
 
        r_object_cleanup(&map->obj);
 }
 
 
-robject_t *r_map_init(robject_t *obj, ruint32 type, r_object_cleanupfun cleanup, r_object_copyfun copy, ruint elt_size)
+robject_t *r_map_init(robject_t *obj, ruint32 type, r_object_cleanupfun cleanup, r_object_copyfun copy, ruint elt_size, ruint nbits)
 {
 {
+       rsize_t hashsize, i;
        rmap_t *map = (rmap_t*)obj;
        rmap_t *map = (rmap_t*)obj;
+       if (nbits == 0 || nbits > 16) {
+               R_ASSERT(0);
+               return NULL;
+       }
        r_object_init(obj, type, cleanup, copy);
        r_object_init(obj, type, cleanup, copy);
-       map->hash = r_hash_create(5, r_hash_rstrequal, r_hash_rstrhash);
-       map->members = r_carray_create(elt_size);
+       map->data = r_carray_create(elt_size);
+       map->nodes = r_array_create(sizeof(r_mapnode_t*));
+       map->nbits = nbits;
        r_list_init(&map->active);
        r_list_init(&map->inactive);
        r_list_init(&map->active);
        r_list_init(&map->inactive);
+       hashsize = r_map_hashsize(map);
+       map->hash = (rlist_t*)r_malloc(sizeof(rlist_t) * hashsize);
+       R_ASSERT(map->hash);
+       for (i = 0; i < hashsize; i++) {
+               r_list_init(&map->hash[i]);
+       }
+
        return obj;
 }
 
        return obj;
 }
 
-rmap_t *r_map_create(ruint elt_size)
+rmap_t *r_map_create(ruint elt_size, ruint nbits)
 {
 {
-       return NULL;
+       rmap_t *map;
+       map = (rmap_t*)r_object_create(sizeof(*map));
+       r_map_init((robject_t*)map, R_OBJECT_MAP, r_map_cleanup, r_map_copy, elt_size, nbits);
+       return map;
+
 }
 
 
 }
 
 
@@ -48,3 +136,65 @@ void r_map_destroy(rmap_t *map)
        r_object_destroy((robject_t*)map);
 }
 
        r_object_destroy((robject_t*)map);
 }
 
+
+rlong r_map_add(rmap_t *map, const rchar *name, rsize_t namesize, rconstpointer pval)
+{
+       r_mapnode_t *node;
+       rlong index = r_carray_add(map->data, pval);
+       rulong nbucket;
+
+       node = r_map_allocnode(map, name, namesize);
+       r_array_replace(map->nodes, index, &node);
+       nbucket = (r_map_rstrhash(node->key) & r_map_hashmask(map));
+       r_list_addt(&map->hash[nbucket], &node->hash);
+       r_list_addt(&map->active, &node->active);
+       return index;
+}
+
+
+rlong r_map_add_s(rmap_t *map, const rchar *name, rconstpointer pval)
+{
+       return r_map_add(map, name, r_strlen(name), pval);
+}
+
+
+r_mapnode_t *r_map_node(rmap_t *map, rsize_t index)
+{
+       r_mapnode_t *node;
+       if (index >= r_array_length(map->nodes))
+               return NULL;
+       node = r_array_index(map->nodes, index, r_mapnode_t*);
+       return node;
+}
+
+
+const rchar *r_map_key(rmap_t *map, rsize_t index)
+{
+       r_mapnode_t *node = r_map_node(map, index);
+       if (!node)
+               return NULL;
+       return node->key->str;
+}
+
+
+rpointer r_map_value(rmap_t *map, rsize_t index)
+{
+       r_mapnode_t *node = r_map_node(map, index);
+       if (!node)
+               return NULL;
+       return r_carray_slot(map->data, node->index);
+}
+
+
+rint r_map_delete(rmap_t *map, rsize_t index)
+{
+       r_mapnode_t *node = r_map_node(map, index);
+       if (!node)
+               return -1;
+       r_free(node->key);
+       r_list_del(&node->hash);
+       r_list_del(&node->active);
+       r_list_addt(&map->inactive, &node->active);
+       r_array_replace(map->nodes, index, NULL);
+       return 0;
+}
index ec11da4..1acbdd6 100644 (file)
@@ -12,17 +12,29 @@ extern "C" {
 #endif
 
 
 #endif
 
 
+#define r_map_hashsize(__m__) (1 << (__m__)->nbits)
+#define r_map_hashmask(__m__) (r_map_hashsize(__m__) - 1)
+
 typedef struct rmap_s {
        robject_t obj;
 typedef struct rmap_s {
        robject_t obj;
-       rhash_t *hash;
-       rcarray_t *members;
+       ruint nbits;
+       rcarray_t *data;
+       rarray_t *nodes;
+       rlist_t *hash;
        rlist_t active;
        rlist_t inactive;
 } rmap_t;
 
 
        rlist_t active;
        rlist_t inactive;
 } rmap_t;
 
 
-rmap_t *r_map_create(ruint elt_size);
+rmap_t *r_map_create(ruint elt_size, ruint nbits);
 void r_map_destroy(rmap_t *array);
 void r_map_destroy(rmap_t *array);
+rlong r_map_add(rmap_t *map, const rchar *name, rsize_t namesize, rconstpointer pval);
+rlong r_map_add_s(rmap_t *map, const rchar *name, rconstpointer pval);
+rlong r_map_replace(rmap_t *map, const rchar *name, rsize_t namesize, rconstpointer pval);
+rlong r_map_replace_s(rmap_t *map, const rchar *name, rconstpointer pval);
+const rchar *r_map_key(rmap_t *map, rsize_t index);
+rpointer r_map_value(rmap_t *map, rsize_t index);
+rint r_map_delete(rmap_t *map, rsize_t index);
 
 
 #ifdef __cplusplus
 
 
 #ifdef __cplusplus
index 4a89af1..236333e 100644 (file)
@@ -14,10 +14,11 @@ extern "C" {
 #define R_OBJECT_ARRAY 2
 #define R_OBJECT_HARRAY 3
 #define R_OBJECT_CARRAY 4
 #define R_OBJECT_ARRAY 2
 #define R_OBJECT_HARRAY 3
 #define R_OBJECT_CARRAY 4
-#define R_OBJECT_HASH 5
-#define R_OBJECT_REF 6
-#define R_OBJECT_JSOBJECT 7
-#define R_OBJECT_GC 8
+#define R_OBJECT_MAP 5
+#define R_OBJECT_HASH 6
+#define R_OBJECT_REF 7
+#define R_OBJECT_JSOBJECT 8
+#define R_OBJECT_GC 9
 #define R_OBJECT_USER 256
 
 
 #define R_OBJECT_USER 256
 
 
index 104dd20..d66fc8d 100644 (file)
@@ -98,7 +98,8 @@ rstr_t *r_rstrdup(const rchar *s, ruint size)
                r_memset(d, 0, allocsize);
                d->size = size;
                d->str = (rchar*)&d[1];
                r_memset(d, 0, allocsize);
                d->size = size;
                d->str = (rchar*)&d[1];
-               r_memcpy((rchar*)d->str, s, size);
+               if (s)
+                       r_memcpy((rchar*)d->str, s, size);
        }
        return d;
 }
        }
        return d;
 }
index e5717d9..7c6ae8f 100644 (file)
@@ -22,6 +22,7 @@ TESTS   += $(OUTDIR)/rlock-test
 TESTS   += $(OUTDIR)/rarray-test
 TESTS   += $(OUTDIR)/rcarray-test
 TESTS   += $(OUTDIR)/rharray-test
 TESTS   += $(OUTDIR)/rarray-test
 TESTS   += $(OUTDIR)/rcarray-test
 TESTS   += $(OUTDIR)/rharray-test
+TESTS   += $(OUTDIR)/rmap-test
 TESTS   += $(OUTDIR)/scope-test
 TESTS   += $(OUTDIR)/rhash-test
 TESTS   += $(OUTDIR)/rvm-test
 TESTS   += $(OUTDIR)/scope-test
 TESTS   += $(OUTDIR)/rhash-test
 TESTS   += $(OUTDIR)/rvm-test