summaryrefslogtreecommitdiff
path: root/usr/src/lib/libast/common/cdt/dthash.c
diff options
context:
space:
mode:
Diffstat (limited to 'usr/src/lib/libast/common/cdt/dthash.c')
-rw-r--r--usr/src/lib/libast/common/cdt/dthash.c368
1 files changed, 368 insertions, 0 deletions
diff --git a/usr/src/lib/libast/common/cdt/dthash.c b/usr/src/lib/libast/common/cdt/dthash.c
new file mode 100644
index 0000000000..62e1e1ba02
--- /dev/null
+++ b/usr/src/lib/libast/common/cdt/dthash.c
@@ -0,0 +1,368 @@
+/***********************************************************************
+* *
+* This software is part of the ast package *
+* Copyright (c) 1985-2007 AT&T Knowledge Ventures *
+* and is licensed under the *
+* Common Public License, Version 1.0 *
+* by AT&T Knowledge Ventures *
+* *
+* A copy of the License is available at *
+* http://www.opensource.org/licenses/cpl1.0.txt *
+* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
+* *
+* Information and Software Systems Research *
+* AT&T Research *
+* Florham Park NJ *
+* *
+* Glenn Fowler <gsf@research.att.com> *
+* David Korn <dgk@research.att.com> *
+* Phong Vo <kpv@research.att.com> *
+* *
+***********************************************************************/
+#include "dthdr.h"
+
+/* Hash table.
+** dt: dictionary
+** obj: what to look for
+** type: type of search
+**
+** Written by Kiem-Phong Vo (05/25/96)
+*/
+
+/* resize the hash table */
+#if __STD_C
+static void dthtab(Dt_t* dt)
+#else
+static void dthtab(dt)
+Dt_t* dt;
+#endif
+{
+ reg Dtlink_t *t, *r, *p, **s, **hs, **is, **olds;
+ int n, k;
+
+ if(dt->data->minp > 0 && dt->data->ntab > 0) /* fixed table size */
+ return;
+ dt->data->minp = 0;
+
+ n = dt->data->ntab;
+ if(dt->disc && dt->disc->eventf &&
+ (*dt->disc->eventf)(dt, DT_HASHSIZE, &n, dt->disc) > 0 )
+ { if(n < 0) /* fix table size */
+ { dt->data->minp = 1;
+ if(dt->data->ntab > 0 )
+ return;
+ }
+ else /* set a particular size */
+ { for(k = 2; k < n; k *= 2)
+ ;
+ n = k;
+ }
+ }
+ else n = 0;
+
+ /* compute new table size */
+ if(n <= 0)
+ { if((n = dt->data->ntab) == 0)
+ n = HSLOT;
+ while(dt->data->size > HLOAD(n))
+ n = HRESIZE(n);
+ }
+ if(n == dt->data->ntab)
+ return;
+
+ /* allocate new table */
+ olds = dt->data->ntab == 0 ? NIL(Dtlink_t**) : dt->data->htab;
+ if(!(s = (Dtlink_t**)(*dt->memoryf)(dt,olds,n*sizeof(Dtlink_t*),dt->disc)) )
+ return;
+ olds = s + dt->data->ntab;
+ dt->data->htab = s;
+ dt->data->ntab = n;
+
+ /* rehash elements */
+ for(hs = s+n-1; hs >= olds; --hs)
+ *hs = NIL(Dtlink_t*);
+ for(hs = s; hs < olds; ++hs)
+ { for(p = NIL(Dtlink_t*), t = *hs; t; t = r)
+ { r = t->right;
+ if((is = s + HINDEX(n,t->hash)) == hs)
+ p = t;
+ else /* move to a new chain */
+ { if(p)
+ p->right = r;
+ else *hs = r;
+ t->right = *is; *is = t;
+ }
+ }
+ }
+}
+
+#if __STD_C
+static Void_t* dthash(Dt_t* dt, reg Void_t* obj, int type)
+#else
+static Void_t* dthash(dt,obj,type)
+Dt_t* dt;
+reg Void_t* obj;
+int type;
+#endif
+{
+ reg Dtlink_t *t, *r, *p;
+ reg Void_t *k, *key;
+ reg uint hsh;
+ reg int lk, sz, ky;
+ reg Dtcompar_f cmpf;
+ reg Dtdisc_t* disc;
+ reg Dtlink_t **s, **ends;
+
+ UNFLATTEN(dt);
+
+ /* initialize discipline data */
+ disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
+ dt->type &= ~DT_FOUND;
+
+ if(!obj)
+ { if(type&(DT_NEXT|DT_PREV))
+ goto end_walk;
+
+ if(dt->data->size <= 0 || !(type&(DT_CLEAR|DT_FIRST|DT_LAST)) )
+ return NIL(Void_t*);
+
+ ends = (s = dt->data->htab) + dt->data->ntab;
+ if(type&DT_CLEAR)
+ { /* clean out all objects */
+ for(; s < ends; ++s)
+ { t = *s;
+ *s = NIL(Dtlink_t*);
+ if(!disc->freef && disc->link >= 0)
+ continue;
+ while(t)
+ { r = t->right;
+ if(disc->freef)
+ (*disc->freef)(dt,_DTOBJ(t,lk),disc);
+ if(disc->link < 0)
+ (*dt->memoryf)(dt,(Void_t*)t,0,disc);
+ t = r;
+ }
+ }
+ dt->data->here = NIL(Dtlink_t*);
+ dt->data->size = 0;
+ dt->data->loop = 0;
+ return NIL(Void_t*);
+ }
+ else /* computing the first/last object */
+ { t = NIL(Dtlink_t*);
+ while(s < ends && !t )
+ t = (type&DT_LAST) ? *--ends : *s++;
+ if(t && (type&DT_LAST))
+ for(; t->right; t = t->right)
+ ;
+
+ dt->data->loop += 1;
+ dt->data->here = t;
+ return t ? _DTOBJ(t,lk) : NIL(Void_t*);
+ }
+ }
+
+ /* allow apps to delete an object "actually" in the dictionary */
+ if(dt->meth->type == DT_BAG && (type&(DT_DELETE|DT_DETACH)) )
+ { if(!dtsearch(dt,obj) )
+ return NIL(Void_t*);
+
+ s = dt->data->htab + HINDEX(dt->data->ntab,dt->data->here->hash);
+ r = NIL(Dtlink_t*);
+ for(p = NIL(Dtlink_t*), t = *s; t; p = t, t = t->right)
+ { if(_DTOBJ(t,lk) == obj) /* delete this specific object */
+ goto do_delete;
+ if(t == dt->data->here)
+ r = p;
+ }
+
+ /* delete some matching object */
+ p = r; t = dt->data->here;
+ goto do_delete;
+ }
+
+ if(type&(DT_MATCH|DT_SEARCH|DT_INSERT|DT_ATTACH) )
+ { key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
+ hsh = _DTHSH(dt,key,disc,sz);
+ goto do_search;
+ }
+ else if(type&(DT_RENEW|DT_VSEARCH) )
+ { r = (Dtlink_t*)obj;
+ obj = _DTOBJ(r,lk);
+ key = _DTKEY(obj,ky,sz);
+ hsh = r->hash;
+ goto do_search;
+ }
+ else /*if(type&(DT_DELETE|DT_DETACH|DT_NEXT|DT_PREV))*/
+ { if((t = dt->data->here) && _DTOBJ(t,lk) == obj)
+ { hsh = t->hash;
+ s = dt->data->htab + HINDEX(dt->data->ntab,hsh);
+ p = NIL(Dtlink_t*);
+ }
+ else
+ { key = _DTKEY(obj,ky,sz);
+ hsh = _DTHSH(dt,key,disc,sz);
+ do_search:
+ t = dt->data->ntab <= 0 ? NIL(Dtlink_t*) :
+ *(s = dt->data->htab + HINDEX(dt->data->ntab,hsh));
+ for(p = NIL(Dtlink_t*); t; p = t, t = t->right)
+ { if(hsh == t->hash)
+ { k = _DTOBJ(t,lk); k = _DTKEY(k,ky,sz);
+ if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0)
+ break;
+ }
+ }
+ }
+ }
+
+ if(t) /* found matching object */
+ dt->type |= DT_FOUND;
+
+ if(type&(DT_MATCH|DT_SEARCH|DT_VSEARCH))
+ { if(!t)
+ return NIL(Void_t*);
+ if(p && (dt->data->type&DT_SET) && dt->data->loop <= 0)
+ { /* move-to-front heuristic */
+ p->right = t->right;
+ t->right = *s;
+ *s = t;
+ }
+ dt->data->here = t;
+ return _DTOBJ(t,lk);
+ }
+ else if(type&(DT_INSERT|DT_ATTACH))
+ { if(t && (dt->data->type&DT_SET) )
+ { dt->data->here = t;
+ return _DTOBJ(t,lk);
+ }
+
+ if(disc->makef && (type&DT_INSERT) &&
+ !(obj = (*disc->makef)(dt,obj,disc)) )
+ return NIL(Void_t*);
+ if(lk >= 0)
+ r = _DTLNK(obj,lk);
+ else
+ { r = (Dtlink_t*)(*dt->memoryf)
+ (dt,NIL(Void_t*),sizeof(Dthold_t),disc);
+ if(r)
+ ((Dthold_t*)r)->obj = obj;
+ else
+ { if(disc->makef && disc->freef && (type&DT_INSERT))
+ (*disc->freef)(dt,obj,disc);
+ return NIL(Void_t*);
+ }
+ }
+ r->hash = hsh;
+
+ /* insert object */
+ do_insert:
+ if((dt->data->size += 1) > HLOAD(dt->data->ntab) && dt->data->loop <= 0 )
+ dthtab(dt);
+ if(dt->data->ntab == 0)
+ { dt->data->size -= 1;
+ if(disc->freef && (type&DT_INSERT))
+ (*disc->freef)(dt,obj,disc);
+ if(disc->link < 0)
+ (*disc->memoryf)(dt,(Void_t*)r,0,disc);
+ return NIL(Void_t*);
+ }
+ s = dt->data->htab + HINDEX(dt->data->ntab,hsh);
+ if(t)
+ { r->right = t->right;
+ t->right = r;
+ }
+ else
+ { r->right = *s;
+ *s = r;
+ }
+ dt->data->here = r;
+ return obj;
+ }
+ else if(type&DT_NEXT)
+ { if(t && !(p = t->right) )
+ { for(ends = dt->data->htab+dt->data->ntab, s += 1; s < ends; ++s)
+ if((p = *s) )
+ break;
+ }
+ goto done_adj;
+ }
+ else if(type&DT_PREV)
+ { if(t && !p)
+ { if((p = *s) != t)
+ { while(p->right != t)
+ p = p->right;
+ }
+ else
+ { p = NIL(Dtlink_t*);
+ for(s -= 1, ends = dt->data->htab; s >= ends; --s)
+ { if((p = *s) )
+ { while(p->right)
+ p = p->right;
+ break;
+ }
+ }
+ }
+ }
+ done_adj:
+ if(!(dt->data->here = p) )
+ { end_walk:
+ if((dt->data->loop -= 1) < 0)
+ dt->data->loop = 0;
+ if(dt->data->size > HLOAD(dt->data->ntab) && dt->data->loop <= 0)
+ dthtab(dt);
+ return NIL(Void_t*);
+ }
+ else
+ { dt->data->type |= DT_WALK;
+ return _DTOBJ(p,lk);
+ }
+ }
+ else if(type&DT_RENEW)
+ { if(!t || (dt->data->type&DT_BAG) )
+ goto do_insert;
+ else
+ { if(disc->freef)
+ (*disc->freef)(dt,obj,disc);
+ if(disc->link < 0)
+ (*dt->memoryf)(dt,(Void_t*)r,0,disc);
+ return t ? _DTOBJ(t,lk) : NIL(Void_t*);
+ }
+ }
+ else /*if(type&(DT_DELETE|DT_DETACH))*/
+ { /* take an element out of the dictionary */
+ do_delete:
+ if(!t)
+ return NIL(Void_t*);
+ else if(p)
+ p->right = t->right;
+ else if((p = *s) == t)
+ p = *s = t->right;
+ else
+ { while(p->right != t)
+ p = p->right;
+ p->right = t->right;
+ }
+ obj = _DTOBJ(t,lk);
+ dt->data->size -= 1;
+ dt->data->here = p;
+ if(disc->freef && (type&DT_DELETE))
+ (*disc->freef)(dt,obj,disc);
+ if(disc->link < 0)
+ (*dt->memoryf)(dt,(Void_t*)t,0,disc);
+ return obj;
+ }
+}
+
+static Dtmethod_t _Dtset = { dthash, DT_SET };
+static Dtmethod_t _Dtbag = { dthash, DT_BAG };
+__DEFINE__(Dtmethod_t*,Dtset,&_Dtset);
+__DEFINE__(Dtmethod_t*,Dtbag,&_Dtbag);
+
+#ifndef KPVDEL /* for backward compatibility - remove next time */
+Dtmethod_t _Dthash = { dthash, DT_SET };
+__DEFINE__(Dtmethod_t*,Dthash,&_Dthash);
+#endif
+
+#ifdef NoF
+NoF(dthash)
+#endif
generated by cgit v1.2.3 (git 2.39.1) at 2025-06-26 12:21:31 +0000