common/h/list.h

   1 /*
   2  * Copyright (c) 1996 Barton P. Miller
   3  *
   4  * We provide the Paradyn Parallel Performance Tools (below
   5  * described as Paradyn") on an AS IS basis, and do not warrant its
   6  * validity or performance.  We reserve the right to update, modify,
   7  * or discontinue this software at any time.  We shall have no
   8  * obligation to supply such updates or modifications or any other
   9  * form of support to you.
  10  *
  11  * This license is for research uses.  For such uses, there is no
  12  * charge. We define "research use" to mean you may freely use it
  13  * inside your organization for whatever purposes you see fit. But you
  14  * may not re-distribute Paradyn or parts of Paradyn, in any form
  15  * source or binary (including derivatives), electronic or otherwise,
  16  * to any other organization or entity without our permission.
  17  *
  18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
  19  *
  20  * All warranties, including without limitation, any warranty of
  21  * merchantability or fitness for a particular purpose, are hereby
  22  * excluded.
  23  *
  24  * By your use of Paradyn, you understand and agree that we (or any
  25  * other person or entity with proprietary rights in Paradyn) are
  26  * under no obligation to provide either maintenance services,
  27  * update services, notices of latent defects, or correction of
  28  * defects for Paradyn.
  29  *
  30  * Even if advised of the possibility of such damages, under no
  31  * circumstances shall we (or any other person or entity with
  32  * proprietary rights in the software licensed hereunder) be liable
  33  * to you or any third party for direct, indirect, or consequential
  34  * damages of any character regardless of type of action, including,
  35  * without limitation, loss of profits, loss of use, loss of good
  36  * will, or computer failure or malfunction.  You agree to indemnify
  37  * us (and any other person or entity with proprietary rights in the
  38  * software licensed hereunder) for any and all liability it may
  39  * incur to third parties resulting from your use of Paradyn.
  40  */
  41
  42 /*
  43  * list.h - list ADT
  44  *
  45  * list.h,v
  46  * Revision 1.22  1995/02/16  09:27:07  markc
  47  * Modified code to remove compiler warnings.
  48  * Added #defines to simplify inlining.
  49  * Cleaned up Object file classes.
  50  *
  51  * Revision 1.21  1994/09/22  03:17:22  markc
  52  * added postfix ++ operator
  53  *
  54  * Revision 1.20  1994/08/17  18:22:54  markc
  55  * Moved the definitions of the << operator into the class declaration to
  56  * keep gcc happy.
  57  *
  58  * Revision 1.19  1994/07/26  20:07:42  hollings
  59  * added cast to ensure hash table pointers are positive.
  60  *
  61  * Revision 1.18  1994/07/11  23:00:57  jcargill
  62  * Fixed bug where added two lists with (+=) operator could result in
  63  * duplicate key entries
  64  *
  65  * Revision 1.17  1994/07/07  03:20:36  markc
  66  * Added removeAll function to list class.
  67  * Added machineType headers to specify pvm, cm5, ...
  68  *
  69  * Revision 1.16  1994/05/30  19:37:39  hollings
  70  * added pragma for external g++ functions.
  71  *
  72  */
  73
  74 #ifndef LIST_H
  75 #define LIST_H
  76
  77 #include <iostream.h>
  78
  79 #if defined(external_templates)
  80 #pragma interface
  81 #endif
  82
  83 #if !defined(DO_INLINE_P)
  84 #define DO_INLINE_P
  85 #endif
  86
  87 #if !defined(DO_INLINE_F)
  88 #define DO_INLINE_F
  89 #endif
  90
  91 #define ListHash(ptr, size) (((unsigned int)(ptr) % (unsigned int)(size)))
  92
  93 template <class Type> class List;
  94 template <class Type> class StringList;
  95 template <class Type> class HTable;
  96
  97 template <class Type> class ListItem {
  98     friend class List<Type>;
  99     friend class StringList<Type>;
 100     private:
 101         Type            data;
 102         void            *key;
 103         ListItem<Type>  *next;
 104 };
 105
 106 template <class Type> class List {
 107     public:
 108         List() { head = NULL; }
 109         DO_INLINE_F int  empty();
 110         friend ostream &operator<<(ostream &os, List<Type> &data) {
 111           List<Type> curr;
 112           for (curr= data; *curr; ++curr) {
 113             os << *curr << endl;
 114           }
 115           return os;
 116         }
 117         DO_INLINE_F void add(Type data, void *key);
 118         DO_INLINE_F void add(Type data);
 119         DO_INLINE_F bool addUnique(Type data);
 120         bool addUnique(Type data, void *key) {
 121             Type temp;
 122
 123             temp = find(key);
 124             if (!temp) {
 125                 add(data, key);
 126                 return(true);
 127             } else {
 128                 return(false);
 129             }
 130         }
 131         DO_INLINE_F Type find(void *key);
 132         DO_INLINE_F bool remove(void *key);
 133         DO_INLINE_F void removeAll();
 134         int count()     {
 135             int c;
 136             ListItem<Type> *curr;
 137
 138             for (curr=head,c=0; curr; curr=curr->next) c++;
 139             return(c);
 140         }
 141         Type operator *() {
 142             if (head)
 143                 return(head->data);
 144             else
 145                 return((Type) NULL);
 146         }
 147         void operator +=(List<Type> mergee) {
 148             ListItem<Type> *curr;
 149
 150             for (curr=mergee.head; curr; curr=curr->next) {
 151                 addUnique(curr->data, curr->key);
 152             }
 153         }
 154         // postfix - the beauty of c++
 155         Type operator ++(int) {
 156             Type ret = (Type) NULL;
 157             if (head) {
 158                 ret = head->data;
 159                 head = head->next;
 160             }
 161             return(ret);
 162         }
 163         // prefix
 164         Type operator ++() {
 165             Type ret = (Type) NULL;
 166             if (head) {
 167                 ret = head->data;
 168                 head = head->next;
 169             }
 170             return(ret);
 171         }
 172         void map (void (*map_function)(const Type item)) {
 173           const ListItem<Type> *temp_ptr = 0;
 174
 175           if (!map_function) return;
 176           for (temp_ptr = head; temp_ptr && temp_ptr->data; temp_ptr = temp_ptr->next)
 177             map_function (temp_ptr->data);
 178         }
 179     protected:
 180         ListItem<Type>  *head;
 181 };
 182
 183 template <class Type> DO_INLINE_F int List<Type>::empty()
 184 {
 185     return (head == NULL);
 186 }
 187
 188 template <class Type> DO_INLINE_F void List<Type>::add(Type data, void *key)
 189 {
 190     ListItem<Type> *ni;
 191
 192     ni = new(ListItem<Type>);
 193     ni->data = data;
 194     ni->key = key;
 195
 196     ni->next = head;
 197     head = ni;
 198 }
 199
 200 template <class Type> DO_INLINE_F  void List<Type>::add(Type data)
 201 {
 202     add(data, (void *) data);
 203 }
 204
 205 template <class Type> DO_INLINE_F  bool List<Type>::addUnique(Type data)
 206 {
 207     return(addUnique(data, (void *) data));
 208 }
 209
 210 template <class Type> DO_INLINE_F  void List<Type>::removeAll()
 211 {
 212   ListItem<Type> *curr, *nx;
 213
 214   curr = head;
 215   while (curr) {
 216     nx = curr->next;
 217     delete (curr);
 218     curr = nx;
 219   }
 220   head = 0;
 221 }
 222
 223 template <class Type> DO_INLINE_F  bool List<Type>::remove(void *key)
 224 {
 225     ListItem<Type> *lag;
 226     ListItem<Type> *curr;
 227
 228     for (curr=head, lag = NULL; curr; curr=curr->next) {
 229         if (curr->key == key) {
 230             break;
 231         }
 232         lag = curr;
 233     }
 234
 235     if (curr) {
 236         if (lag) {
 237             lag->next = curr->next;
 238         } else {
 239             head = curr->next;
 240         }
 241         delete(curr);
 242         return(true);
 243     } else {
 244         return(false);
 245     }
 246 }
 247
 248 template <class Type> DO_INLINE_F  Type List<Type>::find(void *data)
 249 {
 250     ListItem<Type> *curr;
 251
 252     for (curr=head; curr; curr=curr->next) {
 253         if (curr->key == data) {
 254             return(curr->data);
 255         }
 256     }
 257     return((Type) 0);
 258 }
 259
 260 template <class Type> ostream &operator<<(ostream &os, HTable<Type> &data);
 261
 262 template <class Type> class HTable {
 263
 264     public:
 265         // placing function def here makes gcc happy
 266   // VG(06/15/02): that nonstandard hack doesn't work with gcc 3.1...
 267   // let's do this properly:
 268   // (1) the function needs to be already declared (above)
 269   // (2) add <> after name here, so only that instantiation is friended
 270   // (3) the function is defined after this class
 271   // Of course, old broken compilers don't like the standard, so we just
 272   // write something that compiles (as was the case before).
 273 #if defined(i386_unknown_nt4_0) && _MSC_VER < 1300
 274   friend ostream& operator<< (ostream &os, HTable<Type> &data);
 275 #else
 276   friend ostream& operator<< <> (ostream &os, HTable<Type> &data);
 277 #endif
 278
 279         HTable(Type data) { (void) HTable(); add(data, (void *) data); }
 280         DO_INLINE_F void add(Type data, void *key);
 281         DO_INLINE_F HTable();
 282         bool addUnique(Type data, void *key) {
 283             Type temp;
 284
 285             temp = find(key);
 286             if (temp ) {
 287                 return(false);
 288             } else {
 289                 add(data, key);
 290                 return(true);
 291             }
 292         }
 293         DO_INLINE_F Type find(void *key);
 294         DO_INLINE_F bool remove(void *key);
 295         DO_INLINE_F HTable<Type> operator =(HTable<Type> arg);
 296         Type operator *() {
 297             return(*currList);
 298         }
 299         // postfix
 300         Type operator ++(int) {
 301           Type curr;
 302
 303           ++currList;
 304           curr = *currList;
 305           if (curr) return(curr);
 306           for (currHid++; currHid < tableSize; currHid++) {
 307             if (table[currHid]) {
 308               currList = *table[currHid];
 309               curr = *currList;
 310               if (curr) return(curr);
 311             }
 312           }
 313           return(NULL);
 314         }
 315         // prefix
 316         Type operator ++() {
 317             Type curr;
 318
 319             ++currList;
 320             curr = *currList;
 321             if (curr) return(curr);
 322             for (currHid++; currHid < tableSize; currHid++) {
 323                 if (table[currHid]) {
 324                     currList = *table[currHid];
 325                     curr = *currList;
 326                     if (curr) return(curr);
 327                 }
 328             }
 329             return(NULL);
 330         }
 331         int count()     {
 332             int i, total;
 333
 334             total = 0;
 335             for (i=0; i < tableSize; i++) {
 336                 if (table[i]) {
 337                     total += table[i]->count();
 338                 }
 339             }
 340             return(total);
 341         }
 342
 343     private:
 344         List<Type> **table;
 345         List<Type> currList;
 346         int currHid;
 347         int tableSize;
 348 };
 349
 350
 351 template <class Type> ostream &operator<<(ostream &os,
 352                                           HTable<Type> &data) {
 353   int i, total;
 354
 355   total = 0;
 356   for (i=0; i < data.tableSize; i++) {
 357     if (data.table[i]) {
 358       os << *data.table[i];
 359     }
 360   }
 361   return os;
 362 }
 363
 364
 365 template <class Type> DO_INLINE_F HTable<Type> HTable<Type>::operator =(HTable<Type> arg) {
 366     table = arg.table;
 367     tableSize = arg.tableSize;
 368
 369     // find the first item.
 370     currHid = -1;
 371     ++(*this);
 372     return(*this);
 373 }
 374
 375 template <class Type> DO_INLINE_F  HTable<Type>::HTable()
 376 {
 377     table = NULL;
 378     currHid = 0;
 379     tableSize = 0;
 380 }
 381
 382 template <class Type> DO_INLINE_F  Type HTable<Type>::find(void *key)
 383 {
 384     int hid;
 385
 386     if (!tableSize) return(NULL);
 387     hid = ListHash(key, tableSize);
 388     if (hid <0 || hid > tableSize) abort();
 389     if (!table[hid]) {
 390         return(NULL);
 391     } else {
 392         return(table[hid]->find(key));
 393     }
 394 }
 395
 396 template <class Type> DO_INLINE_F  void HTable<Type>::add(Type data, void *key)
 397 {
 398     int hid;
 399
 400     if (!tableSize) {
 401         tableSize = 97;
 402         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
 403     }
 404     hid = ListHash(key, tableSize);
 405     if (hid <0 || hid > tableSize) abort();
 406     if (!table[hid]) {
 407         table[hid] = new(List<Type>);
 408     }
 409     table[hid]->add(data, key);
 410 }
 411
 412
 413 template <class Type> DO_INLINE_F  bool HTable<Type>::remove(void *key)
 414 {
 415     int hid;
 416
 417     hid = ListHash(key, tableSize);
 418     if (hid <0 || hid > tableSize) abort();
 419     if (table[hid]) {
 420         return(table[hid]->remove(key));
 421     }
 422     return(false);
 423 }
 424
 425 template <class Type> class StringList: public List<Type> {
 426     public:
 427         DO_INLINE_F Type find(void *key);
 428 };
 429
 430 template <class Type> DO_INLINE_F Type StringList<Type>::find(void *data)
 431 {
 432     ListItem<Type> *curr;
 433
 434     for (curr=head; curr; curr=curr->next) {
 435         if (!strcmp((char *) curr->key, (char *) data)) {
 436             return(curr->data);
 437         }
 438     }
 439     return((Type) 0);
 440 }
 441
 442 #endif /* LIST_H */