1 /***********************************************************************
2 * *
3 * This software is part of the ast package *
4 * Copyright (c) 1985-2010 AT&T Intellectual Property *
5 * and is licensed under the *
6 * Common Public License, Version 1.0 *
7 * by AT&T Intellectual Property *
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 /* List, Stack, Queue.
25 **
26 ** Written by Kiem-Phong Vo (05/25/96)
27 */
28
29 #if __STD_C
dtlist(reg Dt_t * dt,reg Void_t * obj,reg int type)30 static Void_t* dtlist(reg Dt_t* dt, reg Void_t* obj, reg int type)
31 #else
32 static Void_t* dtlist(dt, obj, type)
33 reg Dt_t* dt;
34 reg Void_t* obj;
35 reg int type;
36 #endif
37 {
38 reg int lk, sz, ky;
39 reg Dtcompar_f cmpf;
40 reg Dtdisc_t* disc;
41 reg Dtlink_t *r, *t;
42 reg Void_t *key, *k;
43
44 UNFLATTEN(dt);
45 disc = dt->disc; _DTDSC(disc,ky,sz,lk,cmpf);
46 dt->type &= ~DT_FOUND;
47
48 if(!obj)
49 { if(type&(DT_LAST|DT_FIRST) )
50 { if((r = dt->data->head) )
51 { if(type&DT_LAST)
52 r = r->left;
53 dt->data->here = r;
54 }
55 return r ? _DTOBJ(r,lk) : NIL(Void_t*);
56 }
57 else if(type&(DT_DELETE|DT_DETACH))
58 { if((dt->data->type&DT_LIST) || !(r = dt->data->head))
59 return NIL(Void_t*);
60 else goto dt_delete;
61 }
62 else if(type&DT_CLEAR)
63 { if(disc->freef || disc->link < 0)
64 { for(r = dt->data->head; r; r = t)
65 { t = r->right;
66 if(disc->freef)
67 (*disc->freef)(dt,_DTOBJ(r,lk),disc);
68 if(disc->link < 0)
69 (*dt->memoryf)(dt,(Void_t*)r,0,disc);
70 }
71 }
72 dt->data->head = dt->data->here = NIL(Dtlink_t*);
73 dt->data->size = 0;
74 return NIL(Void_t*);
75 }
76 else return NIL(Void_t*);
77 }
78
79 if(type&(DT_INSERT|DT_ATTACH))
80 { if(disc->makef && (type&DT_INSERT) &&
81 !(obj = (*disc->makef)(dt,obj,disc)) )
82 return NIL(Void_t*);
83 if(lk >= 0)
84 r = _DTLNK(obj,lk);
85 else
86 { r = (Dtlink_t*)(*dt->memoryf)
87 (dt,NIL(Void_t*),sizeof(Dthold_t),disc);
88 if(r)
89 ((Dthold_t*)r)->obj = obj;
90 else
91 { if(disc->makef && disc->freef && (type&DT_INSERT))
92 (*disc->freef)(dt,obj,disc);
93 return NIL(Void_t*);
94 }
95 }
96
97 if(dt->data->type&DT_LIST)
98 { if((t = dt->data->here) && t != dt->data->head)
99 { r->left = t->left;
100 t->left->right = r;
101 r->right = t;
102 t->left = r;
103 }
104 else goto dt_stack;
105 }
106 else if(dt->data->type&DT_STACK)
107 { dt_stack:
108 r->right = t = dt->data->head;
109 if(t)
110 { r->left = t->left;
111 t->left = r;
112 }
113 else r->left = r;
114 dt->data->head = r;
115 }
116 else /* if(dt->data->type&DT_QUEUE) */
117 { if((t = dt->data->head) )
118 { t->left->right = r;
119 r->left = t->left;
120 t->left = r;
121 }
122 else
123 { dt->data->head = r;
124 r->left = r;
125 }
126 r->right = NIL(Dtlink_t*);
127 }
128
129 if(dt->data->size >= 0)
130 dt->data->size += 1;
131
132 dt->data->here = r;
133 return _DTOBJ(r,lk);
134 }
135
136 if((type&DT_MATCH) || !(r = dt->data->here) || _DTOBJ(r,lk) != obj)
137 { key = (type&DT_MATCH) ? obj : _DTKEY(obj,ky,sz);
138 for(r = dt->data->head; r; r = r->right)
139 { k = _DTOBJ(r,lk); k = _DTKEY(k,ky,sz);
140 if(_DTCMP(dt,key,k,disc,cmpf,sz) == 0)
141 break;
142 }
143 }
144
145 if(!r)
146 return NIL(Void_t*);
147 dt->type |= DT_FOUND;
148
149 if(type&(DT_DELETE|DT_DETACH))
150 { dt_delete:
151 if(r->right)
152 r->right->left = r->left;
153 if(r == (t = dt->data->head) )
154 { dt->data->head = r->right;
155 if(dt->data->head)
156 dt->data->head->left = t->left;
157 }
158 else
159 { r->left->right = r->right;
160 if(r == t->left)
161 t->left = r->left;
162 }
163
164 dt->data->here = r == dt->data->here ? r->right : NIL(Dtlink_t*);
165 dt->data->size -= 1;
166
167 obj = _DTOBJ(r,lk);
168 if(disc->freef && (type&DT_DELETE))
169 (*disc->freef)(dt,obj,disc);
170 if(disc->link < 0)
171 (*dt->memoryf)(dt,(Void_t*)r,0,disc);
172 return obj;
173 }
174 else if(type&DT_NEXT)
175 r = r->right;
176 else if(type&DT_PREV)
177 r = r == dt->data->head ? NIL(Dtlink_t*) : r->left;
178
179 dt->data->here = r;
180 return r ? _DTOBJ(r,lk) : NIL(Void_t*);
181 }
182
183 #ifndef KPVDEL /* to be remove next round */
184 #define static
185 #endif
186 static Dtmethod_t _Dtlist = { dtlist, DT_LIST };
187 static Dtmethod_t _Dtstack = { dtlist, DT_STACK };
188 static Dtmethod_t _Dtqueue = { dtlist, DT_QUEUE };
189
190 __DEFINE__(Dtmethod_t*,Dtlist,&_Dtlist);
191 __DEFINE__(Dtmethod_t*,Dtstack,&_Dtstack);
192 __DEFINE__(Dtmethod_t*,Dtqueue,&_Dtqueue);
193
194 #ifdef NoF
195 NoF(dtlist)
196 #endif
197