[sr-dev] git:master: htable: iterator implementation for hash tables

Module: sip-router Branch: master Commit: 0c62f0d960ce4786bbf8d0bd9b7b0ce8fcf0cd7b URL: http://git.sip-router.org/cgi-bin/gitweb.cgi/sip-router/?a=commit;h=0c62f0d… Author: Elena-Ramona Modroiu &lt;ramona(a)asipto.com&gt; Committer: Elena-Ramona Modroiu &lt;ramona(a)asipto.com&gt; Date: Tue Sep 9 14:56:35 2014 +0200 htable: iterator implementation for hash tables - new functions: - sht_iterator_start(iname, hname) - sht_iterator_next(iname) - sht_iterator_end(iname) - iname is a string to identify the iterator - hname is the name of a hash table - note that the slot is left locked by sht_iterator_next(), therefore there must be no update to the hash table content in between sht_iterator_start() and sht_iterator_end() - sht_iterator_end() must be called for each sht_iterator_start() with the same iterator name - internally can be up to 4 iterators at one time, they can have different names - the current item in the iterator is accessible via: - $shtitkey(iname) - $shtitval(iname) - example sht_iterator_start("i1", "h1"); while(sht_iterator_next("i1")) { xlog("h1[$shtitkey(i1)] is: $shtitval(i1)\n"); } sht_iterator_end("i1"); --- modules/htable/ht_api.c | 178 +++++++++++++++++++++++++++++++++++++++++++++++ modules/htable/ht_api.h | 6 ++ modules/htable/ht_var.c | 49 +++++++++++++ modules/htable/ht_var.h | 5 ++ modules/htable/htable.c | 63 +++++++++++++++++ 5 files changed, 301 insertions(+), 0 deletions(-) diff --git a/modules/htable/ht_api.c b/modules/htable/ht_api.c index af227c0..1d39149 100644 --- a/modules/htable/ht_api.c +++ b/modules/htable/ht_api.c @@ -1332,3 +1332,181 @@ int ht_count_cells_re(str *sre, ht_t *ht, int mode) return cnt; } +#define HT_ITERATOR_SIZE 4 +#define HT_ITERATOR_NAME_SIZE 32 + +typedef struct ht_iterator { + str name; + char bname[HT_ITERATOR_NAME_SIZE]; + ht_t *ht; + int slot; + ht_cell_t *it; +} ht_iterator_t; + +static ht_iterator_t _ht_iterators[HT_ITERATOR_SIZE]; + +void ht_iterator_init(void) +{ + memset(_ht_iterators, 0, HT_ITERATOR_SIZE*sizeof(ht_iterator_t)); +} + +int ht_iterator_start(str *iname, str *hname) +{ + int i; + int k; + + k = -1; + for(i=0; i<HT_ITERATOR_SIZE; i++) + { + if(_ht_iterators[i].name.len>0) + { + if(_ht_iterators[i].name.len==iname->len + && strncmp(_ht_iterators[i].name.s, iname->s, iname->len)==0) + { + k = i; + break; + } + } else { + if(k==-1) k = i; + } + } + if(k==-1) + { + LM_ERR("no iterator available - max number is %d\n", HT_ITERATOR_SIZE); + return -1; + } + if(_ht_iterators[k].name.len>0) + { + if(_ht_iterators[k].ht!=NULL && _ht_iterators[k].it!=NULL) + { + if(_ht_iterators[k].slot>=0 && _ht_iterators[k].slot<_ht_iterators[k].ht->htsize) + { + lock_release(&_ht_iterators[k].ht->entries[_ht_iterators[k].slot].lock); + } + } + } else { + if(iname->len>=HT_ITERATOR_NAME_SIZE) + { + LM_ERR("iterator name is too big [%.*s] (max %d)\n", + iname->len, iname->s, HT_ITERATOR_NAME_SIZE); + return -1; + } + strncpy(_ht_iterators[k].bname, iname->s, iname->len); + _ht_iterators[k].bname[iname->len] = '\0'; + } + _ht_iterators[k].it = NULL; + _ht_iterators[k].slot = 0; + _ht_iterators[k].ht = ht_get_table(hname); + if(_ht_iterators[k].ht==NULL) + { + LM_ERR("cannot get hash table [%.*s]\n", hname->len, hname->s); + return -1; + } + return 0; +} + +int ht_iterator_next(str *iname) +{ + int i; + int k; + + for(i=0; i<HT_ITERATOR_SIZE; i++) + { + if(_ht_iterators[i].name.len>0) + { + if(_ht_iterators[i].name.len==iname->len + && strncmp(_ht_iterators[i].name.s, iname->s, iname->len)==0) + { + k = i; + break; + } + } else { + if(k==-1) k = i; + } + } + if(k==-1) + { + LM_ERR("iterator not found [%.*s]\n", iname->len, iname->s); + return -1; + } + if(_ht_iterators[k].ht==NULL) + { + LM_ERR("iterator not initialized [%.*s]\n", iname->len, iname->s); + return -1; + } + if(_ht_iterators[k].it==NULL) + { + /* first execution - start from first slot */ + _ht_iterators[k].slot=0; + } else { + _ht_iterators[k].it = _ht_iterators[k].it->next; + if(_ht_iterators[k].it!=NULL) + { + /* next item is in the same slot */ + return 0; + } + /* next is not in the same slot - release and try next one */ + _ht_iterators[k].it = NULL; + lock_release(&_ht_iterators[k].ht->entries[_ht_iterators[k].slot].lock); + _ht_iterators[k].slot++; + } + + for( ; _ht_iterators[k].slot<_ht_iterators[k].ht->htsize; _ht_iterators[k].slot++) + { + lock_get(&_ht_iterators[k].ht->entries[_ht_iterators[k].slot].lock); + if(_ht_iterators[k].ht->entries[_ht_iterators[k].slot].first!=NULL) + { + _ht_iterators[k].it = _ht_iterators[k].ht->entries[_ht_iterators[k].slot].first; + return 0; + } + lock_release(&_ht_iterators[k].ht->entries[_ht_iterators[k].slot].lock); + } + return -1; +} + +int ht_iterator_end(str *iname) +{ + int i; + + for(i=0; i<HT_ITERATOR_SIZE; i++) + { + if(_ht_iterators[i].name.len>0) + { + if(_ht_iterators[i].name.len==iname->len + && strncmp(_ht_iterators[i].name.s, iname->s, iname->len)==0) + { + if(_ht_iterators[i].ht!=NULL && _ht_iterators[i].it!=NULL) + { + if(_ht_iterators[i].slot>=0 && _ht_iterators[i].slot<_ht_iterators[i].ht->htsize) + { + lock_release(&_ht_iterators[i].ht->entries[_ht_iterators[i].slot].lock); + } + } + memset(&_ht_iterators[i], 0, sizeof(ht_iterator_t)); + return 0; + } + } + } + + return -1; +} + +ht_cell_t* ht_iterator_get_current(str *iname) +{ + int i; + if(iname==NULL || iname->len<=0) + return NULL; + + for(i=0; i<HT_ITERATOR_SIZE; i++) + { + if(_ht_iterators[i].name.len>0) + { + if(_ht_iterators[i].name.len==iname->len + && strncmp(_ht_iterators[i].name.s, iname->s, iname->len)==0) + { + return _ht_iterators[i].it; + } + } + } + return NULL; +} diff --git a/modules/htable/ht_api.h b/modules/htable/ht_api.h index 924b4b2..d7ba916 100644 --- a/modules/htable/ht_api.h +++ b/modules/htable/ht_api.h @@ -104,4 +104,10 @@ int ht_count_cells_re(str *sre, ht_t *ht, int mode); ht_t *ht_get_root(void); int ht_reset_content(ht_t *ht); +void ht_iterator_init(void); +int ht_iterator_start(str *iname, str *hname); +int ht_iterator_next(str *iname); +int ht_iterator_end(str *iname); +ht_cell_t* ht_iterator_get_current(str *iname); + #endif diff --git a/modules/htable/ht_var.c b/modules/htable/ht_var.c index 50901d3..5ac76cb 100644 --- a/modules/htable/ht_var.c +++ b/modules/htable/ht_var.c @@ -410,3 +410,52 @@ int pv_get_ht_expired_cell(struct sip_msg *msg, pv_param_t *param, return 0; } + +int pv_parse_iterator_name(pv_spec_t *sp, str *in) +{ + if(in->len<=0) + { + return -1; + } + + sp->pvp.pvn.u.isname.name.s.s = in->s; + sp->pvp.pvn.u.isname.name.s.len = in->len; + sp->pvp.pvn.u.isname.type = 0; + sp->pvp.pvn.type = PV_NAME_INTSTR; + + return 0; +} + +int pv_get_iterator_key(sip_msg_t *msg, pv_param_t *param, pv_value_t *res) +{ + ht_cell_t *it=NULL; + if (res == NULL) + { + return -1; + } + + it = ht_iterator_get_current(&param->pvn.u.isname.name.s); + if(it==NULL) { + return pv_get_null(msg, param, res); + } + return pv_get_strval(msg, param, res, &it->name); +} + +int pv_get_iterator_val(sip_msg_t *msg, pv_param_t *param, pv_value_t *res) +{ + ht_cell_t *it=NULL; + if (res == NULL) + { + return -1; + } + + it = ht_iterator_get_current(&param->pvn.u.isname.name.s); + if(it==NULL) { + return pv_get_null(msg, param, res); + } + if(it->flags&AVP_VAL_STR) + return pv_get_strval(msg, param, res, &it->value.s); + + /* integer */ + return pv_get_sintval(msg, param, res, it->value.n); +} diff --git a/modules/htable/ht_var.h b/modules/htable/ht_var.h index 14320a1..4ffe8c2 100644 --- a/modules/htable/ht_var.h +++ b/modules/htable/ht_var.h @@ -46,4 +46,9 @@ int pv_get_ht_dec(struct sip_msg *msg, pv_param_t *param, int pv_parse_ht_expired_cell(pv_spec_t *sp, str *in); int pv_get_ht_expired_cell(struct sip_msg *msg, pv_param_t *param, pv_value_t *res); + +int pv_parse_iterator_name(pv_spec_t *sp, str *in); +int pv_get_iterator_key(sip_msg_t *msg, pv_param_t *param, pv_value_t *res); +int pv_get_iterator_val(sip_msg_t *msg, pv_param_t *param, pv_value_t *res); + #endif diff --git a/modules/htable/htable.c b/modules/htable/htable.c index 563773e..90a5532 100644 --- a/modules/htable/htable.c +++ b/modules/htable/htable.c @@ -66,6 +66,9 @@ static int ht_rm_value_re(struct sip_msg* msg, char* key, char* foo); static int ht_slot_lock(struct sip_msg* msg, char* key, char* foo); static int ht_slot_unlock(struct sip_msg* msg, char* key, char* foo); static int ht_reset(struct sip_msg* msg, char* htname, char* foo); +static int w_ht_iterator_start(struct sip_msg* msg, char* iname, char* hname); +static int w_ht_iterator_next(struct sip_msg* msg, char* iname, char* foo); +static int w_ht_iterator_end(struct sip_msg* msg, char* iname, char* foo); int ht_param(modparam_t type, void* val); @@ -89,6 +92,10 @@ static pv_export_t mod_pvs[] = { pv_parse_ht_name, 0, 0, 0 }, { {"shtrecord", sizeof("shtrecord")-1}, PVT_OTHER, pv_get_ht_expired_cell, 0, pv_parse_ht_expired_cell, 0, 0, 0 }, + { {"shtitkey", sizeof("shtitkey")-1}, PVT_OTHER, pv_get_iterator_key, 0, + pv_parse_iterator_name, 0, 0, 0 }, + { {"shtitval", sizeof("shtitval")-1}, PVT_OTHER, pv_get_iterator_val, 0, + pv_parse_iterator_name, 0, 0, 0 }, { {0, 0}, 0, 0, 0, 0, 0, 0, 0 } }; @@ -113,6 +120,12 @@ static cmd_export_t cmds[]={ ANY_ROUTE}, {"sht_reset", (cmd_function)ht_reset, 1, fixup_spve_null, 0, ANY_ROUTE}, + {"sht_iterator_start", (cmd_function)w_ht_iterator_start, 2, fixup_spve_spve, 0, + ANY_ROUTE}, + {"sht_iterator_next", (cmd_function)w_ht_iterator_next, 1, fixup_spve_null, 0, + ANY_ROUTE}, + {"sht_iterator_end", (cmd_function)w_ht_iterator_end, 1, fixup_spve_null, 0, + ANY_ROUTE}, {"bind_htable", (cmd_function)bind_htable, 0, 0, 0, ANY_ROUTE}, {0,0,0,0,0,0} @@ -201,6 +214,8 @@ static int mod_init(void) return -1; } + ht_iterator_init(); + return 0; } @@ -379,6 +394,54 @@ static int ht_reset(struct sip_msg* msg, char* htname, char* foo) return 1; } +static int w_ht_iterator_start(struct sip_msg* msg, char* iname, char* hname) +{ + str siname; + str shname; + + if(fixup_get_svalue(msg, (gparam_t*)iname, &siname)<0 || siname.len<=0) + { + LM_ERR("cannot get iterator name\n"); + return -1; + } + if(fixup_get_svalue(msg, (gparam_t*)hname, &shname)<0 || shname.len<=0) + { + LM_ERR("cannot get hash table name\n"); + return -1; + } + + if(ht_iterator_start(&siname, &shname)<0) + return -1; + return 1; +} + +static int w_ht_iterator_next(struct sip_msg* msg, char* iname, char* foo) +{ + str siname; + + if(fixup_get_svalue(msg, (gparam_t*)iname, &siname)<0 || siname.len<=0) + { + LM_ERR("cannot get iterator name\n"); + return -1; + } + if(ht_iterator_next(&siname)<0) + return -1; + return 1; +} + +static int w_ht_iterator_end(struct sip_msg* msg, char* iname, char* foo) +{ + str siname; + + if(fixup_get_svalue(msg, (gparam_t*)iname, &siname)<0 || siname.len<=0) + { + LM_ERR("cannot get iterator name\n"); + return -1; + } + if(ht_iterator_end(&siname)<0) + return -1; + return 1; +} /** * lock the slot for a given key in a hash table