1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2011 AT&T Intellectual Property * 5 * and is licensed under the * 6 * Eclipse Public License, Version 1.0 * 7 * by AT&T Intellectual Property * 8 * * 9 * A copy of the License is available at * 10 * http://www.eclipse.org/org/documents/epl-v10.html * 11 * (with md5 checksum b35adb5213ca9657e911e9befb180842) * 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 /* these operations must be done without viewpathing */ 30 #define DT_NOVIEWPATH (DT_INSERT|DT_APPEND|DT_DELETE|\ 31 DT_ATTACH|DT_DETACH|DT_RELINK|DT_CLEAR| \ 32 DT_FLATTEN|DT_EXTRACT|DT_RESTORE|DT_STAT) 33 34 #if __STD_C 35 static Void_t* dtvsearch(Dt_t* dt, reg Void_t* obj, reg int type) 36 #else 37 static Void_t* dtvsearch(dt,obj,type) 38 Dt_t* dt; 39 reg Void_t* obj; 40 reg int type; 41 #endif 42 { 43 int cmp; 44 Dt_t *d, *p; 45 Void_t *o, *n, *oky, *nky; 46 47 if(type&DT_NOVIEWPATH) 48 return (*(dt->meth->searchf))(dt,obj,type); 49 50 o = NIL(Void_t*); 51 52 /* these ops look for the first appearance of an object of the right type */ 53 if((type & (DT_MATCH|DT_SEARCH)) || 54 ((type & (DT_FIRST|DT_LAST|DT_ATLEAST|DT_ATMOST)) && !(dt->meth->type&DT_ORDERED) ) ) 55 { for(d = dt; d; d = d->view) 56 if((o = (*(d->meth->searchf))(d,obj,type)) ) 57 break; 58 dt->walk = d; 59 return o; 60 } 61 62 if(dt->meth->type & DT_ORDERED) /* ordered sets/bags */ 63 { if(!(type & (DT_FIRST|DT_LAST|DT_NEXT|DT_PREV|DT_ATLEAST|DT_ATMOST)) ) 64 return NIL(Void_t*); 65 66 /* find the min/max element that satisfies the op requirement */ 67 n = nky = NIL(Void_t*); p = NIL(Dt_t*); 68 for(d = dt; d; d = d->view) 69 { if(!(o = (*d->meth->searchf)(d, obj, type)) ) 70 continue; 71 oky = _DTKEY(d->disc,o); 72 73 if(n) /* get the right one among all dictionaries */ 74 { cmp = _DTCMP(d,oky,nky,d->disc); 75 if(((type & (DT_NEXT|DT_FIRST|DT_ATLEAST)) && cmp < 0) || 76 ((type & (DT_PREV|DT_LAST|DT_ATMOST)) && cmp > 0) ) 77 goto b_est; 78 } 79 else 80 { b_est: /* current best element to fit op requirement */ 81 p = d; 82 n = o; 83 nky = oky; 84 } 85 } 86 87 dt->walk = p; 88 return n; 89 } 90 91 /* unordered collections */ 92 if(!(type&(DT_NEXT|DT_PREV)) ) 93 return NIL(Void_t*); 94 95 if(!dt->walk ) 96 { for(d = dt; d; d = d->view) 97 if((o = (*(d->meth->searchf))(d, obj, DT_SEARCH)) ) 98 break; 99 dt->walk = d; 100 if(!(obj = o) ) 101 return NIL(Void_t*); 102 } 103 104 for(d = dt->walk, obj = (*d->meth->searchf)(d, obj, type);; ) 105 { while(obj) /* keep moving until finding an uncovered object */ 106 { for(p = dt; ; p = p->view) 107 { if(p == d) /* adjacent object is uncovered */ 108 return obj; 109 if((*(p->meth->searchf))(p, obj, DT_SEARCH) ) 110 break; 111 } 112 obj = (*d->meth->searchf)(d, obj, type); 113 } 114 115 if(!(d = dt->walk = d->view) ) /* move on to next dictionary */ 116 return NIL(Void_t*); 117 else if(type&DT_NEXT) 118 obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_FIRST); 119 else obj = (*(d->meth->searchf))(d,NIL(Void_t*),DT_LAST); 120 } 121 } 122 123 #if __STD_C 124 Dt_t* dtview(reg Dt_t* dt, reg Dt_t* view) 125 #else 126 Dt_t* dtview(dt,view) 127 reg Dt_t* dt; 128 reg Dt_t* view; 129 #endif 130 { 131 reg Dt_t* d; 132 133 if(view && view->meth != dt->meth) /* must use the same method */ 134 return NIL(Dt_t*); 135 136 /* make sure there won't be a cycle */ 137 for(d = view; d; d = d->view) 138 if(d == dt) 139 return NIL(Dt_t*); 140 141 /* no more viewing lower dictionary */ 142 if((d = dt->view) ) 143 d->nview -= 1; 144 dt->view = dt->walk = NIL(Dt_t*); 145 146 if(!view) 147 { dt->searchf = dt->meth->searchf; 148 return d; 149 } 150 151 /* ok */ 152 dt->view = view; 153 dt->searchf = dtvsearch; 154 view->nview += 1; 155 156 return view; 157 } 158