![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to list.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cfront / libstring|
Return to list.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / libstring |
1.1 root 1: #include "list.h"
2:
3: LstHead::~LstHead() {}
4:
5: void // don't specify head or tail
6: LstHead::insert(lnk *nl)
7: {
8: if (t) {
9: nl->nxt = h();
10: nl->prv = t;
11: h()->prv = nl;
12: t->nxt = nl;
13: } else t = nl->nxt = nl->prv = nl;
14: sz++;
15: }
16:
17: lnk *
18: LstHead::get()
19: {
20: if (!t)
21: return NULL;
22: lnk *oh = h();
23: if ( t == h() )
24: t = NULL;
25: else {
26: lnk *nh = oh->nxt;
27: nh->prv = t;
28: t->nxt = nh;
29: }
30: if (cache == oh) cache = NULL;
31: else cacheNo--;
32: sz--;
33: return oh;
34: }
35:
36: lnk *
37: LstHead::unput()
38: {
39: if (!t)
40: return NULL;
41: lnk *ot = t;
42: lnk *hh = h();
43: if ( h() == ot )
44: t = NULL;
45: else {
46: lnk *nt = t->prv;
47: hh->prv = t = nt;
48: t->nxt = hh;
49: }
50: if (cache == ot) cache = NULL;
51: sz--;
52: return ot;
53: }
54:
55: lnk*
56: LstHead::getAt(int ii)
57: {
58: register count;
59: int forward;
60: register lnk* from;
61: if (ii >= sz) abort(); // out of bounds
62: if (ii >= sz - ii) {
63: count = sz - ii - 1;
64: forward = FALSE;
65: from = t;
66: } else {
67: count = ii;
68: forward = TRUE;
69: from = h();
70: }
71: if (cache) {
72: register altCount = ii - cacheNo;
73: register a1 = altCount > 0 ? altCount : -altCount;
74: if (a1 < count) {
75: count = a1;
76: forward = a1 == altCount;
77: from = cache;
78: }
79: }
80: if (forward)
81: while (count--)
82: from = from->nxt;
83: else
84: while (count--)
85: from = from->prv;
86: cache = from;
87: cacheNo = ii;
88: return from;
89: }
90:
91: void
92: List::sepWork()
93: {
94: abort(); // Only derived functions should be called.
95: }
96: void
97: List::newIt(lstiter *a, int i)
98: {
99: a->nextIt = fI;
100: a->aList = this;
101: fI = a;
102: a->index = i;
103: a->pred = i == 0 || i == length() ? tail() : it->getAt(i - 1);
104: }
105: void
106: List::removeIt(lstiter *a)
107: {
108: if (fI == a)
109: fI = a->nextIt;
110: else {
111: for (register lstiter* anIt = fI; anIt->nextIt != a;
112: anIt = anIt->nextIt) ;
113: anIt->nextIt = a->nextIt;
114: }
115: a->nextIt = 0;
116: a->aList = 0;
117: a->pred = 0;
118: a->index = 0;
119: }
120: List::~List()
121: {
122: if (--it->refCount == 0)
123: delete it;
124: register lstiter* s;
125: for (register lstiter* anIt = fI; anIt; anIt = s) {
126: s = anIt->nextIt;
127: anIt->nextIt = 0;
128: anIt->aList = 0;
129: anIt->pred = 0;
130: anIt->index = 0;
131: }
132: }
133: List&
134: List::operator=(List& ll)
135: {
136: LstHead *head = ll.it;
137: head->refCount++;
138: if (--it->refCount == 0)
139: delete it;
140: it = head;
141: for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt) {
142: anIt->index = 0;
143: anIt->pred = tail();
144: }
145: return *this;
146: }
147: List&
148: List::unget(lnk* aLink)
149: {
150: separate();
151: it->unget(aLink);
152: for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt) {
153: if (anIt->index == 0)
154: anIt->pred = aLink;
155: anIt->index++;
156: }
157: return *this;
158: }
159: List&
160: List::put(lnk* aLink)
161: {
162: separate();
163: it->put(aLink);
164: for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt)
165: if (anIt->index == 0)
166: anIt->pred = aLink;
167: return *this;
168: }
169:
170: lnk*
171: List::get()
172: {
173: separate();
174: lnk* ans = it->get();
175: for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt) {
176: if (anIt->index <= 1) // 0 in case the List is empty
177: anIt->pred = tail(); // tail() returns NULL
178: if (anIt->index > 0)
179: anIt->index--;
180: }
181: return ans;
182: }
183:
184: lnk*
185: List::unput()
186: {
187: separate();
188: lnk* ans = it->unput();
189: for (register lstiter *anIt = fI; anIt; anIt = anIt->nextIt) {
190: if (anIt->pred == ans) // head or tail
191: anIt->pred = tail();
192: if (anIt->index > length())
193: anIt->index--;
194: }
195: return ans;
196: }
197:
198: lstiter&
199: lstiter::operator=(lstiter& a)
200: {
201: if (!a.aList)
202: abort(); /* invalid list iterator */
203: if (aList) aList->removeIt(this);
204: a.aList->newIt(this);
205: pred = a.pred;
206: index = a.index;
207: return *this;
208: }
209: lstiter::lstiter(lstiter& a)
210: {
211: if (!a.aList)
212: abort(); /* invalid list iterator */
213: a.aList->newIt(this);
214: pred = a.pred;
215: index = a.index;
216: }
217: lstiter::lstiter(List& a, int i)
218: {
219: a.newIt(this, i);
220: }
221: lstiter::~lstiter()
222: {
223: if (aList) aList->removeIt(this);
224: }
225: void
226: lstiter::reset(int i)
227: {
228: index = i;
229: pred = i == 0 || i == aList->length() ? aList->tail() :
230: aList->it->getAt(i - 1);
231: }
232: void
233: lstiter::insert(lnk *x)
234: {
235: aList->separate();
236: if (pred) {
237: x->init(pred, pred->nxt);
238: pred->nxt->prv = x;
239: pred->nxt = x;
240: for (register lstiter *other = aList->firstIt(); other;
241: other = other->nextIt)
242: if (this != other && index < other->index)
243: other->index++;
244: } else {
245: x->init(x, x);
246: for (register lstiter *other = aList->firstIt(); other;
247: other = other->nextIt)
248: other->pred = x;
249: }
250: if (atEnd())
251: aList->it->t = x;
252: pred = x;
253: index++;
254: aList->it->sz++;
255: }
256: void
257: lstiter::r_insert(lnk *x)
258: {
259: aList->separate();
260: for (register lstiter *other = aList->firstIt(); other;
261: other = other->nextIt)
262: if (other != this) {
263: if (other->pred == pred)
264: other->pred = x;
265: if (other->index >= index)
266: other->index++;
267: }
268: if (pred) {
269: x->init(pred, pred->nxt);
270: pred->nxt->prv = x;
271: pred->nxt = x;
272: } else {
273: x->init(x, x);
274: pred = x;
275: }
276: if (atEnd())
277: aList->it->t = x;
278: aList->it->sz++;
279: }
280: lnk *
281: lstiter::remove()
282: {
283: if (r_atEnd())
284: return NULL;
285: aList->separate();
286: lnk *doomed = pred;
287: int oldIndex = index;
288: if (pred == pred->nxt) { // this is only item
289: aList->it->t = 0;
290: for (register lstiter *anIter = aList->firstIt(); anIter;
291: anIter = anIter->nextIt) {
292: anIter->pred = 0;
293: anIter->index = 0;
294: }
295: } else {
296: if (doomed == aList->it->t) // deleting tail
297: aList->it->t = doomed->prv;
298: for (register lstiter *anIter = aList->firstIt(); anIter;
299: anIter = anIter->nextIt) {
300: if (anIter->pred == doomed)
301: anIter->pred = doomed->prv;
302: if (anIter->index >= oldIndex)
303: anIter->index--;
304: }
305: pred->nxt = doomed->nxt;
306: doomed->nxt->prv = pred;
307: }
308: aList->it->sz--;
309: return doomed;
310: }
311: lnk *
312: lstiter::r_remove()
313: {
314: if (atEnd())
315: return NULL;
316: aList->separate();
317: lnk *doomed = pred->nxt;
318: int deletingHead = doomed == aList->it->h();
319: if (pred == pred->nxt) { // this is only item
320: aList->it->t = 0;
321: for (register lstiter *anIter = aList->firstIt(); anIter;
322: anIter = anIter->nextIt) {
323: anIter->pred = 0;
324: anIter->index = 0;
325: }
326: } else {
327: if (doomed == aList->it->t) // deleting tail
328: aList->it->t = doomed->prv;
329: for (register lstiter *anIt = aList->firstIt(); anIt;
330: anIt = anIt->nextIt) {
331: if (anIt->pred == doomed)
332: anIt->pred = doomed->prv;
333: if (anIt->index > index) anIt->index--;
334: }
335: pred->nxt = doomed->nxt;
336: doomed->nxt->prv = pred;
337: }
338: aList->it->sz--;
339: return doomed;
340: }
341: lnk *
342: lstiter::next()
343: {
344: if (atEnd()) return NULL;
345: pred = pred->nxt;
346: index++;
347: return pred;
348: }
349: lnk *
350: lstiter::r_next()
351: {
352: if (r_atEnd()) return NULL;
353: lnk *op = pred;
354: pred = pred->prv;
355: index--;
356: return op;
357: }
358: lnk *
359: lstiter::r_peek()
360: {
361: if (r_atEnd())
362: return NULL;
363: return pred;
364: }
365: lnk *
366: lstiter::peek()
367: {
368: if (atEnd())
369: return NULL;
370: return pred->nxt;
371: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.