src/apps/glteapot/util.h

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