From aa5f6a35b44b24301331deabe04b33067d7f7ff8 Mon Sep 17 00:00:00 2001 From: Martin Stoilov Date: Sun, 5 Jun 2011 21:27:39 -0700 Subject: [PATCH] Work on rmap_t - 2 --- rlib/rmap.c | 172 ++++++++++++++++++++++++++++-- rlib/rmap.h | 18 +++- rlib/robject.h | 9 +- rlib/rstring.c | 3 +- tests/testmisc/build/linux/misc-tests.mk | 1 + 5 files changed, 184 insertions(+), 19 deletions(-) diff --git a/rlib/rmap.c b/rlib/rmap.c index 85d59cd..08d788f 100644 --- a/rlib/rmap.c +++ b/rlib/rmap.c @@ -3,12 +3,69 @@ #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; -} 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) @@ -19,27 +76,58 @@ robject_t *r_map_copy(const robject_t *obj) void r_map_cleanup(robject_t *obj) { + r_mapnode_t *node; 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); } -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; + if (nbits == 0 || nbits > 16) { + R_ASSERT(0); + return NULL; + } 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); + 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; } -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); } + +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; +} diff --git a/rlib/rmap.h b/rlib/rmap.h index ec11da4..1acbdd6 100644 --- a/rlib/rmap.h +++ b/rlib/rmap.h @@ -12,17 +12,29 @@ extern "C" { #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; - 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; -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); +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 diff --git a/rlib/robject.h b/rlib/robject.h index 4a89af1..236333e 100644 --- a/rlib/robject.h +++ b/rlib/robject.h @@ -14,10 +14,11 @@ extern "C" { #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 diff --git a/rlib/rstring.c b/rlib/rstring.c index 104dd20..d66fc8d 100644 --- a/rlib/rstring.c +++ b/rlib/rstring.c @@ -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_memcpy((rchar*)d->str, s, size); + if (s) + r_memcpy((rchar*)d->str, s, size); } return d; } diff --git a/tests/testmisc/build/linux/misc-tests.mk b/tests/testmisc/build/linux/misc-tests.mk index e5717d9..7c6ae8f 100644 --- a/tests/testmisc/build/linux/misc-tests.mk +++ b/tests/testmisc/build/linux/misc-tests.mk @@ -22,6 +22,7 @@ TESTS += $(OUTDIR)/rlock-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 -- 1.7.9.5