1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Knowledge Ventures * 8 * * 9 * A copy of the License is available at * 10 * http://www.opensource.org/licenses/cpl1.0.txt * 11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) * 12 * * 13 * Information and Software Systems Research * 14 * AT&T Research * 15 * Florham Park NJ * 16 * * 17 * Glenn Fowler <gsf@research.att.com> * 18 * David Korn <dgk@research.att.com> * 19 * Phong Vo <kpv@research.att.com> * 20 * * 21 ***********************************************************************/ 22 #include "dthdr.h" 23 24 /* Set a view path from dict to view. 25 ** 26 ** Written by Kiem-Phong Vo (5/25/96) 27 */ 28 29 30 #if __STD_C 31 static Void_t* dtvsearch(Dt_t* dt, reg Void_t* obj, reg int type) 32 #else 33 static Void_t* dtvsearch(dt,obj,type) 34 Dt_t* dt; 35 reg Void_t* obj; 36 reg int type; 37 #endif 38 { 39 Dt_t *d, *p; 40 Void_t *o, *n, *ok, *nk; 41 int cmp, lk, sz, ky; 42 Dtcompar_f cmpf; 43 44 /* these operations only happen at the top level */ 45 if(type&(DT_INSERT|DT_DELETE|DT_CLEAR|DT_RENEW)) 46 return (*(dt->meth->searchf))(dt,obj,type); 47 48 if((type&(DT_MATCH|DT_SEARCH)) || /* order sets first/last done below */ 49 ((type&(DT_FIRST|DT_LAST)) && !(dt->meth->type&(DT_OBAG|DT_OSET)) ) ) 50 { for(d = dt; d; d = d->view) 51 if((o = (*(d->meth->searchf))(d,obj,type)) ) 52 break; 53 dt->walk = d; 54 return o; 55 } 56 57 if(dt->meth->type & (DT_OBAG|DT_OSET) ) 58 { if(!(type & (DT_FIRST|DT_LAST|DT_NEXT|DT_PREV)) ) 59 return NIL(Void_t*); 60 61 n = nk = NIL(Void_t*); p = NIL(Dt_t*); 62 for(d = dt; d; d = d->view) 63 { if(!(o = (*d->meth->searchf)(d, obj, type)) ) 64 continue; 65 _DTDSC(d->disc,ky,sz,lk,cmpf); 66 ok = _DTKEY(o,ky,sz); 67 68 if(n) /* get the right one among all dictionaries */ 69 { cmp = _DTCMP(d,ok,nk,d->disc,cmpf,sz); 70 if(((type & (DT_NEXT|DT_FIRST)) && cmp < 0) || 71 ((type & (DT_PREV|DT_LAST)) && cmp > 0) ) 72 goto a_dj; 73 } 74 else /* looks good for now */ 75 { a_dj: p = d; 76 n = o; 77 nk = ok; 78 } 79 } 80 81 dt->walk = p; 82 return n; 83 } 84 85 /* non-ordered methods */ 86 if(!(type & (DT_NEXT|DT_PREV)) ) 87 return NIL(Void_t*); 88 89 if(!dt->walk || obj != _DTOBJ(dt->walk->data->here, dt->walk->disc->link) ) 90 { for(d = dt; d; d = d->view) 91 if((o = (*(d->meth->searchf))(d, obj, DT_SEARCH)) ) 92 break; 93 dt->walk = d; 94 if(!(obj = o) ) 95 return NIL(Void_t*); 96 } 97 98 for(d = dt->walk, obj = (*d->meth->searchf)(d, obj, type);; ) 99 { while(obj) /* keep moving until finding an uncovered object */ 100 { for(p = dt; ; p = p->view) 101 { if(p == d) /* adjacent object is uncovered */ 102 return obj; 103 if((*(p->meth->searchf))(p, obj, DT_SEARCH) ) 104 break; 105 } 106 obj = (*d->meth->searchf)(d, obj, type); 107 } 108 109 if(!(d = dt->walk = d->view) ) /* move on to next dictionary */ 110 return NIL(Void_t*); 111 else if(type&DT_NEXT) 112 obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_FIRST); 113 else obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_LAST); 114 } 115 } 116 117 #if __STD_C 118 Dt_t* dtview(reg Dt_t* dt, reg Dt_t* view) 119 #else 120 Dt_t* dtview(dt,view) 121 reg Dt_t* dt; 122 reg Dt_t* view; 123 #endif 124 { 125 reg Dt_t* d; 126 127 UNFLATTEN(dt); 128 if(view) 129 { UNFLATTEN(view); 130 if(view->meth != dt->meth) /* must use the same method */ 131 return NIL(Dt_t*); 132 } 133 134 /* make sure there won't be a cycle */ 135 for(d = view; d; d = d->view) 136 if(d == dt) 137 return NIL(Dt_t*); 138 139 /* no more viewing lower dictionary */ 140 if((d = dt->view) ) 141 d->nview -= 1; 142 dt->view = dt->walk = NIL(Dt_t*); 143 144 if(!view) 145 { dt->searchf = dt->meth->searchf; 146 return d; 147 } 148 149 /* ok */ 150 dt->view = view; 151 dt->searchf = dtvsearch; 152 view->nview += 1; 153 154 return view; 155 } 156