1// This may look like C code, but it is really -*- C++ -*- 2/* 3Copyright (C) 1988 Free Software Foundation 4 written by Doug Lea (dl@rocky.oswego.edu) 5 6This file is part of GNU CC. 7 8GNU CC is distributed in the hope that it will be useful, 9but WITHOUT ANY WARRANTY. No author or distributor 10accepts responsibility to anyone for the consequences of using it 11or for whether it serves any particular purpose or works at all, 12unless he says so in writing. Refer to the GNU CC General Public 13License for full details. 14 15Everyone is granted permission to copy, modify and redistribute 16GNU CC, but only under the conditions described in the 17GNU CC General Public License. A copy of this license is 18supposed to have been given to you along with GNU CC so you 19can know your rights and responsibilities. It should be in a 20file named COPYING. Among other things, the copyright notice 21and this notice must be preserved on all copies. 22*/ 23 24#ifdef __GNUG__ 25#pragma implementation 26#endif 27#include <values.h> 28#include <stream.h> 29#include "<T>.SLList.h" 30 31 32void <T>SLList::error(const char* msg) 33{ 34 (*lib_error_handler)("SLList", msg); 35} 36 37int <T>SLList::length() 38{ 39 int l = 0; 40 <T>SLListNode* t = last; 41 if (t != 0) do { ++l; t = t->tl; } while (t != last); 42 return l; 43} 44 45<T>SLList::<T>SLList(<T>SLList& a) 46{ 47 if (a.last == 0) 48 last = 0; 49 else 50 { 51 <T>SLListNode* p = a.last->tl; 52 <T>SLListNode* h = new <T>SLListNode(p->hd); 53 last = h; 54 for (;;) 55 { 56 if (p == a.last) 57 { 58 last->tl = h; 59 return; 60 } 61 p = p->tl; 62 <T>SLListNode* n = new <T>SLListNode(p->hd); 63 last->tl = n; 64 last = n; 65 } 66 } 67} 68 69<T>SLList& <T>SLList::operator = (<T>SLList& a) 70{ 71 if (last != a.last) 72 { 73 clear(); 74 if (a.last != 0) 75 { 76 <T>SLListNode* p = a.last->tl; 77 <T>SLListNode* h = new <T>SLListNode(p->hd); 78 last = h; 79 for (;;) 80 { 81 if (p == a.last) 82 { 83 last->tl = h; 84 break; 85 } 86 p = p->tl; 87 <T>SLListNode* n = new <T>SLListNode(p->hd); 88 last->tl = n; 89 last = n; 90 } 91 } 92 } 93 return *this; 94} 95 96void <T>SLList::clear() 97{ 98 if (last == 0) 99 return; 100 101 <T>SLListNode* p = last->tl; 102 last->tl = 0; 103 last = 0; 104 105 while (p != 0) 106 { 107 <T>SLListNode* nxt = p->tl; 108 delete(p); 109 p = nxt; 110 } 111} 112 113 114Pix <T>SLList::prepend(<T&> item) 115{ 116 <T>SLListNode* t = new <T>SLListNode(item); 117 if (last == 0) 118 t->tl = last = t; 119 else 120 { 121 t->tl = last->tl; 122 last->tl = t; 123 } 124 return Pix(t); 125} 126 127 128Pix <T>SLList::prepend(<T>SLListNode* t) 129{ 130 if (t == 0) return 0; 131 if (last == 0) 132 t->tl = last = t; 133 else 134 { 135 t->tl = last->tl; 136 last->tl = t; 137 } 138 return Pix(t); 139} 140 141 142Pix <T>SLList::append(<T&> item) 143{ 144 <T>SLListNode* t = new <T>SLListNode(item); 145 if (last == 0) 146 t->tl = last = t; 147 else 148 { 149 t->tl = last->tl; 150 last->tl = t; 151 last = t; 152 } 153 return Pix(t); 154} 155 156Pix <T>SLList::append(<T>SLListNode* t) 157{ 158 if (t == 0) return 0; 159 if (last == 0) 160 t->tl = last = t; 161 else 162 { 163 t->tl = last->tl; 164 last->tl = t; 165 last = t; 166 } 167 return Pix(t); 168} 169 170void <T>SLList::join(<T>SLList& b) 171{ 172 <T>SLListNode* t = b.last; 173 b.last = 0; 174 if (last == 0) 175 last = t; 176 else if (t != 0) 177 { 178 <T>SLListNode* f = last->tl; 179 last->tl = t->tl; 180 t->tl = f; 181 last = t; 182 } 183} 184 185Pix <T>SLList::ins_after(Pix p, <T&> item) 186{ 187 <T>SLListNode* u = (<T>SLListNode*)p; 188 <T>SLListNode* t = new <T>SLListNode(item); 189 if (last == 0) 190 t->tl = last = t; 191 else if (u == 0) // ins_after 0 means prepend 192 { 193 t->tl = last->tl; 194 last->tl = t; 195 } 196 else 197 { 198 t->tl = u->tl; 199 u->tl = t; 200 if (u == last) 201 last = t; 202 } 203 return Pix(t); 204} 205 206 207void <T>SLList::del_after(Pix p) 208{ 209 <T>SLListNode* u = (<T>SLListNode*)p; 210 if (last == 0 || u == last) error("cannot del_after last"); 211 if (u == 0) u = last; // del_after 0 means delete first 212 <T>SLListNode* t = u->tl; 213 if (u == t) 214 last = 0; 215 else 216 { 217 u->tl = t->tl; 218 if (last == t) 219 last = u; 220 } 221 delete t; 222} 223 224int <T>SLList::owns(Pix p) 225{ 226 <T>SLListNode* t = last; 227 if (t != 0 && p != 0) 228 { 229 do 230 { 231 if (Pix(t) == p) return 1; 232 t = t->tl; 233 } while (t != last); 234 } 235 return 0; 236} 237 238<T> <T>SLList::remove_front() 239{ 240 if (last == 0) error("remove_front of empty list"); 241 <T>SLListNode* t = last->tl; 242 <T> res = t->hd; 243 if (t == last) 244 last = 0; 245 else 246 last->tl = t->tl; 247 delete t; 248 return res; 249} 250 251int <T>SLList::remove_front(<T>& x) 252{ 253 if (last == 0) 254 return 0; 255 else 256 { 257 <T>SLListNode* t = last->tl; 258 x = t->hd; 259 if (t == last) 260 last = 0; 261 else 262 last->tl = t->tl; 263 delete t; 264 return 1; 265 } 266} 267 268 269void <T>SLList::del_front() 270{ 271 if (last == 0) error("del_front of empty list"); 272 <T>SLListNode* t = last->tl; 273 if (t == last) 274 last = 0; 275 else 276 last->tl = t->tl; 277 delete t; 278} 279 280int <T>SLList::OK() 281{ 282 int v = 1; 283 if (last != 0) 284 { 285 <T>SLListNode* t = last; 286 long count = MAXLONG; // Lots of chances to find last! 287 do 288 { 289 count--; 290 t = t->tl; 291 } while (count > 0 && t != last); 292 v &= count > 0; 293 } 294 if (!v) error("invariant failure"); 295 return v; 296} 297