Windows test suite & build fixes. VC2003 and VC2008 should both now build. Known...
[dyninst.git] / 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 // $Id: List.h,v
43
44 #ifndef LIST_H
45 #define LIST_H
46
47 #include "common/h/language.h"
48
49 #include <ostream>
50
51 #if !defined(DO_INLINE_P)
52 #define DO_INLINE_P
53 #endif
54
55 #if !defined(DO_INLINE_F)
56 #define DO_INLINE_F
57 #endif
58
59 #define ListHash(ptr, size) (((unsigned int)(ptr) % (unsigned int)(size)))
60
61 template <class DataType> class List;
62 template <class DataType, class KeyType> class ListBase;
63 template <class Type> class StringList;
64 template <class Type> class HTable;
65
66
67 template <class DataType, class KeyType> class _list_node {
68  public: 
69    friend class ListBase<DataType, KeyType>;
70    friend class StringList<DataType>;
71    const KeyType      key;
72    DataType           data;
73    _list_node<DataType, KeyType>   *next;
74
75    _list_node() : next(NULL) { }
76    _list_node(DataType &dataA, const KeyType &keyA, 
77               _list_node<DataType, KeyType> *nextA) : key(keyA), 
78       data(dataA), next(nextA) { }
79    explicit _list_node(const _list_node<DataType, KeyType> &from) :
80       key(from.key), data(from.data), next(NULL) {
81       // key and next need to be set after constructor
82    }
83    _list_node<DataType, KeyType> *get_next_node() { return next; }
84 };
85
86
87 template <class DataType, class KeyType> class _list_iterator {
88   typedef _list_node<DataType, KeyType> node;
89   mutable node *cur;
90
91   void move_to_next() const {
92     cur = cur->get_next_node();
93   }
94
95  public:
96   _list_iterator(node *cur_) :
97      cur(cur_) {    
98   }
99   node *getNode() { return cur; }
100   // returns undefined result if iterator is the ending iterator
101   DataType &operator*() {
102     return cur->data;
103   }
104   const DataType &operator*() const {
105     return cur->data;
106   }
107
108   _list_iterator operator++(int) const {  // postfix
109     _list_iterator result = *this;
110     move_to_next();
111     return result;
112   }
113
114   _list_iterator operator++() const { // prefix
115     move_to_next();
116     return *this;
117   }
118   _list_iterator operator+(unsigned n) const {
119      _list_iterator current = *this;
120      for(unsigned i=0; i<n; i++) {
121         current++;
122      }
123      return current;
124   }
125   bool operator==(const _list_iterator &iter) const {
126      return (cur == iter.cur);
127   }
128   bool operator!=(const _list_iterator &iter) const {
129      return (cur != iter.cur);
130   }
131 };
132
133
134 template <class DataType, class KeyType> class ListBase {
135  public:
136    typedef _list_iterator<DataType, KeyType> iterator;
137    typedef const _list_iterator<DataType, KeyType> const_iterator;
138    typedef _list_node<DataType, KeyType> node;
139
140    ListBase()  { head = NULL; }
141    ListBase(const ListBase &fromList) {
142       node *lastCopiedNode = NULL;
143       node *headCopiedNode = NULL;
144       for(const node *cur = fromList.head; cur; cur=cur->next) {
145          node *curCopiedNode = new node(*cur);  // copy constructor
146          if(lastCopiedNode)
147             lastCopiedNode->next = curCopiedNode;
148          else
149             headCopiedNode = curCopiedNode;
150       }
151       head = headCopiedNode;
152    }
153    ~ListBase() {
154       clear();
155    }
156    friend std::ostream &operator<<(std::ostream &os, 
157                               const ListBase<DataType, KeyType> &data);
158
159    // returns the first element
160    DataType &front() { return *(begin()); }  
161    const DataType &front() const { return *(begin()); }
162    
163    // returns the last element
164    DataType &back() { return getLastNode()->data; }
165
166    void __push_front(DataType &data, const KeyType &key);
167    void __push_back(DataType &data, const KeyType &key);
168    bool __addIfUniqueKey(DataType &data, const KeyType &key) {
169       DataType temp;
170     
171       bool foundIt = __find_with_key(key, &temp);
172       if (!foundIt) {
173          __push_front(data, key);
174          return(true);
175       } else {
176          return(false);
177       }
178    }
179    bool __addIfUniqueVal(DataType &data, const KeyType &key) {
180       bool foundIt = __find_with_val(data);
181       if (!foundIt) {
182          __push_front(data, key);
183          return(true);
184       } else {
185          return(false);
186       }
187    }
188    bool __find_with_key(const KeyType &key, DataType *saveVal);
189    bool __find_with_val(const DataType &saveVal) const;
190    bool __remove_with_key(const KeyType &key);
191    bool __remove_with_val(const DataType &val);
192    void clear();
193    iterator begin() {
194       return iterator(head);
195    }
196    const_iterator begin() const {
197       return iterator(head);
198    }
199
200    iterator end() {
201       return iterator(NULL);  // a hypothetical element after the last element
202    }
203    const_iterator end() const {
204       return iterator(NULL);  // a hypothetical element after the last element
205    }
206
207    int count()  const {
208       int c;
209       node *curr;
210       
211       for (curr=head,c=0; curr; curr=curr->next) c++;
212       return(c);
213    }
214    bool isEmpty() { return (head == NULL); }
215
216    // inserts an item before position at pos
217    void insert(iterator &, DataType &) {
218       // not implemented yet
219    }
220    void map (void (*map_function)(const DataType item)) {
221       const node *temp_ptr = 0;
222       
223       if (!map_function) return;
224       for (temp_ptr = head; temp_ptr; temp_ptr = temp_ptr->next)
225          map_function (temp_ptr->data);
226    }
227    
228  protected:
229    node *getLastNode();
230
231    node *head;
232 };
233
234 template <class DataType, class KeyType>
235 inline std::ostream &operator<<(std::ostream &os, 
236                            const ListBase<DataType, KeyType> &data) {
237    TYPENAME ListBase<DataType, KeyType>::iterator curr = data.begin();
238    TYPENAME ListBase<DataType, KeyType>::iterator endMarker = data.end();
239    
240    for(; curr != endMarker; ++curr) {
241       os << *curr << std::endl;
242    }
243    return os;
244 }
245
246 template <class DataType> class List : public ListBase<DataType, void*> {
247    typedef void* KeyType;
248  public:
249    List() : ListBase<DataType, KeyType>() { };
250    List(const List &fromList) : ListBase<DataType, KeyType>(fromList) { }
251    ~List() { }  // ~ListBase will be called
252    friend std::ostream &operator<<(std::ostream &os, 
253                               const List<DataType> &data) {
254       return operator<<(os, static_cast<ListBase<DataType, KeyType> >(data));
255    }
256
257    void push_front(DataType &data) {
258       __push_front(data, static_cast<KeyType>(NULL));
259    }
260    void push_back(DataType &data) {
261       __push_back(data, static_cast<KeyType>(NULL));
262    }
263    bool addIfUniqueVal(DataType &data) {
264       return __addIfUniqueVal(data, NULL);
265    }
266    bool find(const DataType &val) const {
267       return __find_with_val(val);
268    }
269    bool remove(const DataType &data) {
270       return __remove_with_val(data);
271    }
272 };
273
274
275 template <class DataType, class KeyType> class ListWithKey : 
276 public ListBase<DataType, KeyType> {
277  public:
278    ListWithKey() : ListBase<DataType, KeyType>() { };
279    ListWithKey(const ListWithKey &fromList) : 
280       ListBase<DataType, KeyType>(fromList) {}
281    ~ListWithKey() { }  // ~ListBase will be called
282    friend std::ostream &operator<<(std::ostream &os,
283                               const ListWithKey<DataType, KeyType> &data)
284    {
285       return operator<<(os, static_cast<ListBase<DataType, KeyType> >(data));
286    }
287
288    void push_front(DataType &data, KeyType &key) {
289       __push_front(data, key);
290    }
291    void push_back(DataType &data, KeyType &key) {
292       __push_back(data, key);
293    }
294    bool addIfUniqueKey(DataType &data, KeyType &key) {
295       return __addIfUniqueKey(data, key);
296    }
297    bool find_with_key(KeyType &key, DataType *saveVal) {
298       return __find_with_key(key, saveVal);
299    }
300    bool find_with_val(const DataType &val) const {
301       return __find_with_val(val);
302    }
303    bool remove_with_key(KeyType &key) {
304       return __remove_with_key(key);
305    }
306    bool remove_with_val(const DataType &data) {
307       return __remove_with_val(data);
308    }
309 };
310
311
312 template <class Type> std::ostream &operator<<(std::ostream &os, 
313                                           HTable<Type> &data);
314
315 template <class Type> class HTable {
316     public:
317         // placing function def here makes gcc happy 
318   // VG(06/15/02): that nonstandard hack doesn't work with gcc 3.1...
319   // let's do this properly:
320   // (1) the function needs to be already declared (above)
321   // (2) add <> after name here, so only that instantiation is friended
322   // (3) the function is defined after this class
323   // Of course, old broken compilers don't like the standard, so we just
324   // write something that compiles (as was the case before).
325   // BTW, is this operator used anywhere?
326 #if (defined(i386_unknown_nt4_0) && _MSC_VER < 1300) || defined(mips_sgi_irix6_4)
327   friend std::ostream& operator<< (std::ostream &os, HTable<Type> &data);
328 #else
329   friend std::ostream& operator<< <> (std::ostream &os, HTable<Type> &data);
330 #endif
331
332         HTable(Type data) { (void) HTable(); add(data, (void *) data); }
333         DO_INLINE_F void add(Type data, void *key);
334         DO_INLINE_F HTable(); 
335         bool addUnique(Type data, void *key) {
336             Type temp;
337
338             bool foundIt = find(key, &temp);
339             if (foundIt) {
340                 return(false);
341             } else {
342                 add(data, key);
343                 return(true);
344             }
345         }
346         DO_INLINE_F Type find(void *key);
347         DO_INLINE_F bool remove(void *key);
348         DO_INLINE_F HTable<Type> operator =(HTable<Type> arg); 
349         Type operator *() {
350             return(*currList);
351         }
352         // postfix
353         Type operator ++(int) {
354           Type curr;
355           
356           ++currList;
357           curr = *currList;
358           if (curr) return(curr);
359           for (currHid++; currHid < tableSize; currHid++) {
360             if (table[currHid]) {
361               currList = *table[currHid];
362               curr = *currList;
363               if (curr) return(curr);
364             }
365           }
366           return(NULL);
367         }
368         // prefix
369         Type operator ++() {
370             Type curr;
371
372             ++currList;
373             curr = *currList;
374             if (curr) return(curr);
375             for (currHid++; currHid < tableSize; currHid++) {
376                 if (table[currHid]) {
377                     currList = *table[currHid];
378                     curr = *currList;
379                     if (curr) return(curr);
380                 }
381             }
382             return(NULL);
383         }
384         int count()     {
385             int i, total;
386
387             total = 0;
388             for (i=0; i < tableSize; i++) {
389                 if (table[i]) {
390                     total += table[i]->count();
391                 }
392             }
393             return(total);
394         }
395
396     private:
397         List<Type> **table;
398         List<Type> currList;
399         int currHid;
400         int tableSize;
401 };
402
403
404 template <class Type> std::ostream &operator<<(std::ostream &os,
405                                           HTable<Type> &data) {
406   int i, total;
407   
408   total = 0;
409   for (i=0; i < data.tableSize; i++) {
410     if (data.table[i]) {
411       os << *data.table[i];
412     }
413   }
414   return os;
415 }
416
417
418 template <class Type> DO_INLINE_F HTable<Type> HTable<Type>::operator =(HTable<Type> arg) {
419     table = arg.table;
420     tableSize = arg.tableSize;
421
422     // find the first item.
423     currHid = -1;
424     ++(*this);
425     return(*this);
426 }
427
428 template <class Type> DO_INLINE_F  HTable<Type>::HTable()
429
430     table = NULL;
431     currHid = 0;
432     tableSize = 0;
433 }
434
435 template <class Type> DO_INLINE_F  Type HTable<Type>::find(void *key)
436 {
437     int hid;
438
439     if (!tableSize) return(NULL);
440     hid = ListHash(key, tableSize);
441     if (hid <0 || hid > tableSize) abort();
442     if (!table[hid]) {
443         return(NULL);
444     } else {
445         return(table[hid]->find(key));
446     }
447 }
448
449 template <class Type> DO_INLINE_F  void HTable<Type>::add(Type data, void *key)
450 {
451     int hid;
452
453     if (!tableSize) {
454         tableSize = 97;
455         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
456     }
457     hid = ListHash(key, tableSize);
458     if (hid <0 || hid > tableSize) abort();
459     if (!table[hid]) {
460         table[hid] = new(List<Type>);
461     }
462     table[hid]->add(data, key);
463 }
464
465
466 template <class Type> DO_INLINE_F  bool HTable<Type>::remove(void *key)
467 {
468     int hid;
469
470     hid = ListHash(key, tableSize);
471     if (hid <0 || hid > tableSize) abort();
472     if (table[hid]) {
473         return(table[hid]->remove(key));
474     }
475     return(false);
476 }
477
478 template <class Type> class StringList: public List<Type> {
479     public:
480         DO_INLINE_F Type find(void *key)
481         {
482           // This didn't use to have StringList<Type>::, but it barfs without it, 
483           //so... - TLM (2002/08/06)
484           typename StringList<Type>::node *it;
485           
486           for (it=this->head; it; it=it->next) {
487             if (!strcmp((char *) it->key, (char *) key)) {
488               return(it->data);
489             }
490           }
491           return((Type) 0);
492         }
493 };
494
495
496 #endif /* LIST_H */