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