[sr-dev] git:master: htable: iterator implementation for hash tables
Elena-Ramona Modroiu
ramona at rosdev.ro
Tue Sep 9 15:26:01 CEST 2014
Module: sip-router
Branch: master
Commit: 0c62f0d960ce4786bbf8d0bd9b7b0ce8fcf0cd7b
URL: http://git.sip-router.org/cgi-bin/gitweb.cgi/sip-router/?a=commit;h=0c62f0d960ce4786bbf8d0bd9b7b0ce8fcf0cd7b
Author: Elena-Ramona Modroiu <ramona at asipto.com>
Committer: Elena-Ramona Modroiu <ramona at asipto.com>
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(¶m->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(¶m->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
More information about the sr-dev
mailing list