1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2012 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 /* List, Deque, Stack, Queue. 25 ** 26 ** Written by Kiem-Phong Vo (05/25/96) 27 */ 28 29 typedef struct _dtlist_s 30 { Dtdata_t data; 31 Dtlink_t* link; /* list of objects */ 32 Dtlink_t* here; /* finger to searched objects */ 33 } Dtlist_t; 34 35 #ifdef DEBUG 36 int dtlistprint(Dt_t* dt, Dtlink_t* here, char* (*objprintf)(Void_t*) ) 37 { 38 int k; 39 char *obj, *endb, buf[1024]; 40 Dtdisc_t *disc = dt->disc; 41 Dtlist_t *list = (Dtlist_t*)dt->data; 42 43 if(!here && !(here = list->link) ) 44 return -1; 45 46 for(; here; here = here->_rght) 47 { endb = buf; /* indentation */ 48 *endb++ = '('; 49 obj = (*objprintf)(_DTOBJ(disc, here)); 50 k = strlen(obj); memcpy(endb, obj, k); endb += k; 51 *endb++ = ')'; 52 *endb++ = '\n'; 53 write(2, buf, endb-buf); 54 } 55 56 return 0; 57 } 58 #endif 59 60 /* terminal objects: DT_FIRST|DT_LAST */ 61 #if __STD_C 62 Void_t* lfirstlast(Dt_t* dt, int type) 63 #else 64 Void_t* lfirstlast(dt, type) 65 Dt_t* dt; 66 int type; 67 #endif 68 { 69 Dtlink_t *lnk; 70 Dtdisc_t *disc = dt->disc; 71 Dtlist_t *list = (Dtlist_t*)dt->data; 72 73 if((lnk = list->link) ) 74 { if(type&DT_LAST) 75 lnk = lnk->_left; 76 list->here = lnk; /* finger points to this */ 77 } 78 79 return lnk ? _DTOBJ(disc,lnk) : NIL(Void_t*); 80 } 81 82 /* DT_CLEAR */ 83 #if __STD_C 84 Void_t* lclear(Dt_t* dt) 85 #else 86 Void_t* lclear(dt) 87 Dt_t* dt; 88 #endif 89 { 90 Dtlink_t *lnk, *next; 91 Dtdisc_t *disc = dt->disc; 92 Dtlist_t *list = (Dtlist_t*)dt->data; 93 94 lnk = list->link; 95 list->link = list->here = NIL(Dtlink_t*); 96 list->data.size = 0; 97 98 if(disc->freef || disc->link < 0) 99 { for(; lnk; lnk = next) 100 { next = lnk->_rght; 101 _dtfree(dt, lnk, DT_DELETE); 102 } 103 } 104 105 return NIL(Void_t*); 106 } 107 108 /* DT_FLATTEN|DT_EXTRACT|DT_RESTORE */ 109 #if __STD_C 110 Void_t* llist(Dt_t* dt, Dtlink_t* lnk, int type) 111 #else 112 Void_t* llist(dt, lnk, type) 113 Dt_t* dt; 114 Dtlink_t* lnk; 115 int type; 116 #endif 117 { 118 Dtlist_t *list = (Dtlist_t*)dt->data; 119 120 if(type&(DT_FLATTEN|DT_EXTRACT) ) 121 { if(lnk) /* error on calling */ 122 return NIL(Void_t*); 123 124 lnk = list->link; 125 if(type&DT_EXTRACT) 126 { list->link = NIL(Dtlink_t*); 127 dt->data->size = 0; 128 } 129 } 130 else /* if(type&DT_RESTORE) */ 131 { if(list->link != NIL(Dtlink_t*)) 132 return NIL(Void_t*); 133 134 list->link = lnk; 135 136 dt->data->size = 0; 137 for(; lnk; lnk = lnk->_rght) 138 dt->data->size += 1; 139 } 140 141 return (Void_t*)lnk; 142 } 143 144 #if __STD_C 145 static Void_t* liststat(Dt_t* dt, Dtstat_t* st) 146 #else 147 static Void_t* liststat(dt, st) 148 Dt_t* dt; 149 Dtstat_t* st; 150 #endif 151 { 152 if(st) 153 { memset(st, 0, sizeof(Dtstat_t)); 154 st->meth = dt->meth->type; 155 st->size = dt->data->size; 156 st->space = sizeof(Dtlist_t) + (dt->disc->link >= 0 ? 0 : dt->data->size*sizeof(Dthold_t)); 157 } 158 159 return (Void_t*)dt->data->size; 160 } 161 162 #if __STD_C 163 static Void_t* dtlist(Dt_t* dt, Void_t* obj, int type) 164 #else 165 static Void_t* dtlist(dt, obj, type) 166 Dt_t* dt; 167 Void_t* obj; 168 int type; 169 #endif 170 { 171 Dtlink_t *r, *t, *h; 172 Void_t *key, *o, *k; 173 Dtdisc_t *disc = dt->disc; 174 Dtlist_t *list = (Dtlist_t*)dt->data; 175 176 type = DTTYPE(dt,type); /* map type for upward compatibility */ 177 if(!(type&DT_OPERATIONS) ) 178 return NIL(Void_t*); 179 180 DTSETLOCK(dt); 181 182 if(type&(DT_FIRST|DT_LAST) ) 183 DTRETURN(obj, lfirstlast(dt, type)); 184 else if(type&(DT_EXTRACT|DT_RESTORE|DT_FLATTEN) ) 185 DTRETURN(obj, llist(dt, (Dtlink_t*)obj, type)); 186 else if(type&DT_CLEAR) 187 DTRETURN(obj, lclear(dt)); 188 else if(type&DT_STAT ) 189 DTRETURN(obj, liststat(dt, (Dtstat_t*)obj)); 190 191 h = list->here; /* save finger to last search object */ 192 list->here = NIL(Dtlink_t*); 193 194 if(!obj) 195 { if((type&(DT_DELETE|DT_DETACH|DT_REMOVE)) && (dt->meth->type&(DT_STACK|DT_QUEUE)) ) 196 if((r = list->link) ) /* special case for destack or dequeue */ 197 goto dt_delete; 198 DTRETURN(obj, NIL(Void_t*)); /* error, needing non-void object */ 199 } 200 201 if(type&DT_RELINK) /* relink object after some processing */ 202 { r = (Dtlink_t*)obj; 203 goto do_insert; 204 } 205 else if(type&(DT_INSERT|DT_APPEND|DT_ATTACH)) 206 { if(!(r = _dtmake(dt, obj, type)) ) 207 DTRETURN(obj, NIL(Void_t*)); 208 dt->data->size += 1; 209 210 do_insert: 211 if(dt->meth->type&DT_DEQUE) 212 { if(type&DT_APPEND) 213 goto dt_queue; /* append at end */ 214 else goto dt_stack; /* insert at top */ 215 } 216 else if(dt->meth->type&DT_LIST) 217 { if(type&DT_APPEND) 218 { if(!h || !h->_rght) 219 goto dt_queue; 220 r->_rght = h->_rght; 221 r->_rght->_left = r; 222 r->_left = h; 223 r->_left->_rght = r; 224 } 225 else 226 { if(!h || h == list->link ) 227 goto dt_stack; 228 r->_left = h->_left; 229 r->_left->_rght = r; 230 r->_rght = h; 231 r->_rght->_left = r; 232 } 233 } 234 else if(dt->meth->type&DT_STACK) 235 { dt_stack: 236 r->_rght = t = list->link; 237 if(t) 238 { r->_left = t->_left; 239 t->_left = r; 240 } 241 else r->_left = r; 242 list->link = r; 243 } 244 else /* if(dt->meth->type&DT_QUEUE) */ 245 { dt_queue: 246 if((t = list->link) ) 247 { t->_left->_rght = r; 248 r->_left = t->_left; 249 t->_left = r; 250 } 251 else 252 { list->link = r; 253 r->_left = r; 254 } 255 r->_rght = NIL(Dtlink_t*); 256 } 257 258 list->here = r; 259 DTRETURN(obj, _DTOBJ(disc,r)); 260 } 261 262 /* define key to match */ 263 if(type&DT_MATCH) 264 { key = obj; 265 obj = NIL(Void_t*); 266 } 267 else key = _DTKEY(disc, obj); 268 269 /* try to find a matching object */ 270 if(h && _DTOBJ(disc,h) == obj && (type & (DT_SEARCH|DT_NEXT|DT_PREV)) ) 271 r = h; /* match at the finger, no search needed */ 272 else /* linear search through the list */ 273 { h = NIL(Dtlink_t*); /* track first/last obj with same key */ 274 for(r = list->link; r; r = r->_rght) 275 { o = _DTOBJ(disc,r); k = _DTKEY(disc,o); 276 if(_DTCMP(dt, key, k, disc) != 0) 277 continue; 278 else if(type & (DT_REMOVE|DT_NEXT|DT_PREV) ) 279 { if(o == obj) /* got exact object, done */ 280 break; 281 else if(type&DT_NEXT) /* track last object */ 282 h = r; 283 else if(type&DT_PREV) /* track first object */ 284 h = h ? h : r; 285 else continue; 286 } 287 else if(type & DT_ATLEAST ) 288 h = r; /* track last object */ 289 else break; 290 } 291 r = h ? h : r; 292 } 293 if(!r) 294 DTRETURN(obj, NIL(Void_t*)); 295 296 if(type&(DT_DELETE|DT_DETACH|DT_REMOVE)) 297 { dt_delete: 298 if(r->_rght) 299 r->_rght->_left = r->_left; 300 if(r == (t = list->link) ) 301 { list->link = r->_rght; 302 if((h = list->link) ) 303 h->_left = t->_left; 304 } 305 else 306 { r->_left->_rght = r->_rght; 307 if(r == t->_left) 308 t->_left = r->_left; 309 } 310 311 list->here = r == list->here ? r->_rght : NIL(Dtlink_t*); 312 313 obj = _DTOBJ(disc,r); 314 _dtfree(dt, r, type); 315 dt->data->size -= 1; 316 317 DTRETURN(obj, obj); 318 } 319 320 if(type&DT_NEXT) 321 r = r->_rght; 322 else if(type&DT_PREV) 323 r = r == list->link ? NIL(Dtlink_t*) : r->_left; 324 /* else: if(type&(DT_SEARCH|DT_MATCH|DT_ATLEAST|DT_ATMOST)) */ 325 326 list->here = r; 327 if(r) 328 DTRETURN(obj, _DTOBJ(disc,r)); 329 else DTRETURN(obj, NIL(Void_t*)); 330 331 dt_return: 332 DTANNOUNCE(dt,obj,type); 333 DTCLRLOCK(dt); 334 return obj; 335 } 336 337 #if __STD_C 338 static int listevent(Dt_t* dt, int event, Void_t* arg) 339 #else 340 static int listevent(dt, event, arg) 341 Dt_t* dt; 342 int event; 343 Void_t* arg; 344 #endif 345 { 346 Dtlist_t *list = (Dtlist_t*)dt->data; 347 348 if(event == DT_OPEN) 349 { if(list) /* already initialized */ 350 return 0; 351 if(!(list = (Dtlist_t*)(*dt->memoryf)(dt, 0, sizeof(Dtlist_t), dt->disc)) ) 352 { DTERROR(dt, "Error in allocating a list data structure"); 353 return -1; 354 } 355 memset(list, 0, sizeof(Dtlist_t)); 356 dt->data = (Dtdata_t*)list; 357 return 1; 358 } 359 else if(event == DT_CLOSE) 360 { if(!list) /* already closed */ 361 return 0; 362 if(list->link) /* remove all items */ 363 (void)lclear(dt); 364 (void)(*dt->memoryf)(dt, (Void_t*)list, 0, dt->disc); 365 dt->data = NIL(Dtdata_t*); 366 return 0; 367 } 368 else return 0; 369 } 370 371 static Dtmethod_t _Dtlist = { dtlist, DT_LIST, listevent, "Dtlist" }; 372 static Dtmethod_t _Dtdeque = { dtlist, DT_DEQUE, listevent, "Dtdeque" }; 373 static Dtmethod_t _Dtstack = { dtlist, DT_STACK, listevent, "Dtstack" }; 374 static Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE, listevent, "Dtqueue" }; 375 376 __DEFINE__(Dtmethod_t*,Dtlist,&_Dtlist); 377 __DEFINE__(Dtmethod_t*,Dtdeque,&_Dtdeque); 378 __DEFINE__(Dtmethod_t*,Dtstack,&_Dtstack); 379 __DEFINE__(Dtmethod_t*,Dtqueue,&_Dtqueue); 380 381 #ifdef NoF 382 NoF(dtlist) 383 #endif 384