1 /* 2 Copyright 1999, Be Incorporated. All Rights Reserved. 3 This file may be used under the terms of the Be Sample Code License. 4 */ 5 6 #ifndef list_h 7 #define list_h 8 9 #include <memory.h> 10 #include "error.h" 11 12 template <class contents> 13 struct LispNode 14 { 15 contents *car; 16 LispNode *cdr; 17 18 /* Create a node with no next */ 19 inline LispNode(contents *value) 20 : car(value), cdr(0) { } 21 22 /* Create a node with specified next */ 23 inline LispNode(contents *value, LispNode *next) 24 : car (value), cdr(next) { } 25 26 /* Create a node and insert it in a list right after `prev' */ 27 inline LispNode(LispNode *prev, contents *value) 28 : car(value), cdr(prev->cdr) { prev->cdr = this; } 29 30 }; 31 32 33 template <class contents> 34 struct LispList 35 { 36 LispNode<contents> *first; 37 38 39 /* -------- List creation --------------- */ 40 /* Create an empty list */ 41 inline LispList() 42 { first = 0; } 43 44 /* Create a list pointing to the specified node */ 45 inline LispList(LispNode<contents> *_first) 46 { first = _first; } 47 48 /* ?? */ 49 inline LispList(LispList &init) 50 { first = init.first; } 51 52 /* ---------- List queries ------------- */ 53 inline int is_empty() 54 { return first == 0; } 55 56 /* Determines if a thing is on the list */ 57 inline int is_present(contents *element) 58 { 59 for (LispNode<contents> *node = first; node; node = node->cdr) 60 if (node->car == element) 61 return 1; 62 return 0; 63 } 64 65 /* Returns the length of the list */ 66 inline int count() 67 { 68 int n = 0; 69 for (LispNode<contents> *node = first; node; node = node->cdr) 70 n++; 71 return n; 72 } 73 74 /* ----------- Adding "nodes" to the list ------------ */ 75 /* Add a specified node to the head of the list. */ 76 inline void add_head(LispNode<contents> *new_element) 77 { 78 new_element->cdr = first; 79 first = new_element; 80 } 81 82 /* Add a specified node anywhere on the list */ 83 inline void add(LispNode<contents> *new_element) 84 { 85 add_head (new_element); 86 } 87 88 inline void add_tail(LispNode<contents> *new_element) 89 { 90 LispNode<contents>** pred = &first; 91 while( *pred ) 92 pred = &(*pred)->cdr; 93 *pred = new_element; 94 new_element->cdr = 0; 95 } 96 97 /* ----------- Adding "contents" to the list ------------ */ 98 /* ----- (Which in my opinion is far more useful) ------ */ 99 /* Create new node pointing to thing, & add to head of list. */ 100 inline void add_head_new(contents *new_element) 101 { 102 first = new LispNode<contents>(new_element, first); 103 } 104 inline void add_head(contents *new_element) 105 { add_head_new(new_element); } 106 107 /* Create new node pointing to thing, & add to end of list. */ 108 inline void add_tail_new(contents *new_element) 109 { 110 LispNode< contents > **pred = &first; 111 while (*pred) 112 pred = &(*pred)->cdr; 113 *pred = new LispNode< contents >(new_element); 114 } 115 inline void add_tail(contents *new_element) 116 { add_tail_new(new_element); } 117 118 /* Create new node pointing to thing, & add anywhere on list */ 119 inline void add_new(contents *new_element) 120 { add_head_new(new_element); } 121 inline void add(contents *new_element) 122 { add_new(new_element); } 123 124 /* Create and add a new node for a specified element, 125 but only if it's not already on the list. */ 126 inline void add_new_once(contents *new_element) 127 { 128 if (!is_present(new_element)) 129 add_head_new(new_element); 130 } 131 inline void add_tail_once(contents *new_element) 132 { 133 if (!is_present(new_element)) 134 add_tail_new(new_element); 135 } 136 137 /* ------- Removing things from the list ------------ */ 138 /* Remove and return the first node on the list j.h. */ 139 inline LispNode<contents> *rem_head () 140 { 141 LispNode<contents> *n = first; 142 if (n) 143 { 144 first = first->cdr; 145 } 146 return n; 147 } 148 149 /* Remove and return any node on the list. */ 150 inline LispNode<contents> *remove () 151 { return( rem_head() ); } 152 153 /* Remove a specified node from the list. */ 154 inline void remove (LispNode<contents> *node) 155 { 156 for (LispNode<contents> **pp = &first; *pp; pp = &(*pp)->cdr) 157 if (*pp == node) 158 { 159 *pp = (*pp)->cdr; 160 return; 161 } 162 } 163 164 /* Remove & delete all nodes pointing to a particular element. */ 165 inline void rem_del (contents *element) 166 { 167 LispNode<contents> **pp = &first; 168 while (*pp) 169 { 170 if ((*pp)->car == element) 171 { 172 LispNode<contents> *o = *pp; 173 *pp = o->cdr; 174 delete o; 175 } 176 else 177 pp = &(*pp)->cdr; 178 } 179 } 180 181 /* Remove and delete all nodes on the list. */ 182 inline void rem_del_all() 183 { 184 while (first) 185 { 186 LispNode<contents> *old = first; 187 first = first->cdr; 188 delete old; 189 } 190 } 191 192 193 /* -------- Simple list storage (by j.h.) ------------ */ 194 /* When you just want to hold a bunch of stuff on a list and 195 then pull them off later. Note that these calls do NOT check 196 for to see if a thing is already on the list. Use is_present() 197 before adding. 198 */ 199 /* Put something anywhere on the list */ 200 inline void put( contents *c ) 201 { add_tail( c ); } 202 203 /* Put something at beginning of list */ 204 inline void put_head( contents *c ) 205 { add_head( c ); } 206 207 /* Put something at end of the list */ 208 inline void put_tail( contents *c ) 209 { add_tail( c ); } 210 211 #if 0 /* leaks memory */ 212 /* Take a specific thing off the list */ 213 inline contents *get(contents *element) 214 { 215 contents *c = 0; 216 for (LispNode<contents> *node = first; node; node = node->cdr) 217 { 218 if (node->car == element) 219 { 220 c = node->car; 221 remove(node); 222 break; 223 } 224 } 225 return c; 226 } 227 #endif 228 229 /* Take the first thing off the list */ 230 inline contents *get_head() 231 { 232 contents *c = 0; 233 if(first) 234 { 235 c = first->car; 236 delete rem_head(); 237 } 238 return c; 239 } 240 241 /* Take something off the list */ 242 inline contents *get() 243 { return(get_head()); } 244 245 /* XXX inline contents *get_tail() { } */ 246 247 /* -------- Stack simulation (by j.h.) ------------ */ 248 /* Put a thing onto the head of the list */ 249 inline void push( contents *c ) 250 { put_head( c ); } 251 252 /* Remove a thing from the head of the list */ 253 inline contents *pop() 254 { return(get_head()); } 255 256 /* Pop everything off the stack. Empty the stack/list. */ 257 inline void pop_all() 258 { rem_del_all(); } 259 260 261 /* ----------- list/list manipulations ------------ */ 262 /* Add all elements present on another list to this list also. */ 263 inline void add_new(LispList other) 264 { 265 for (LispNode<contents> *n = other.first; n; n = n->cdr) 266 add_new(n->car); 267 } 268 inline void add_new_once(LispList other) 269 { 270 for (LispNode<contents> *n = other.first; n; n = n->cdr) 271 add_new_once(n->car); 272 } 273 274 /* Remove and delete all nodes whose contents are also present 275 in a different list (set disjunction). */ 276 inline void rem_del(LispList other) 277 { 278 for (LispNode<contents> *n = other.first; n; n = n->cdr) 279 rem_del(n->car); 280 } 281 }; 282 283 template <class thetype> 284 struct DoubleLinkedNode 285 { 286 thetype *next,*prev; 287 288 DoubleLinkedNode() { next = prev = NULL; }; 289 290 void insert_after(thetype *n) 291 { 292 if (next != NULL) 293 next->prev = n; 294 n->next = next; 295 n->prev = (thetype*)this; 296 next = n; 297 }; 298 299 void insert_before(thetype *n) 300 { 301 prev->next = n; 302 n->next = (thetype*)this; 303 n->prev = prev; 304 prev = n; 305 }; 306 307 void remove() 308 { 309 assert(prev != NULL); 310 prev->next = next; 311 if (next != NULL) 312 next->prev = prev; 313 }; 314 }; 315 316 template <class thetype> 317 struct DoubleLinkedList : public DoubleLinkedNode<thetype> 318 { 319 DoubleLinkedList() : DoubleLinkedNode<thetype>() {}; 320 321 void insert(thetype *n) 322 { 323 insert_after(n); 324 }; 325 326 void add(thetype *n) 327 { 328 insert_after(n); 329 }; 330 }; 331 332 template <class T> 333 struct BufferArray 334 { 335 T * items; 336 int num_items; 337 int num_slots; 338 int slot_inc; 339 340 void resize(int i) 341 { 342 items = (T*)realloc(items,sizeof(T)*i); 343 num_slots = i; 344 }; 345 346 T & operator [](int index) 347 { 348 assert(index < num_items); 349 return items[index]; 350 }; 351 352 T & get(int index) 353 { 354 assert(index < num_items); 355 return items[index]; 356 }; 357 358 void add(T &item) 359 { 360 if (num_items == num_slots) 361 resize(num_slots+slot_inc); 362 memcpy(items+num_items,&item,sizeof(item)); 363 num_items++; 364 }; 365 366 BufferArray(int start_slots, int _slot_inc) 367 { 368 num_slots = start_slots; 369 slot_inc = _slot_inc; 370 assert(slot_inc > 0); 371 num_items = 0; 372 items = (T*)malloc(sizeof(T)*num_slots); 373 }; 374 375 ~BufferArray() 376 { 377 free(items); 378 }; 379 }; 380 381 #endif 382