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