Added new classes: Cstring KeyList, KList
[dyninst.git] / common / h / keylist.h
1
2 #ifndef _KEYLIST_H
3 #define _KEYLIST_H
4
5 /*
6  * keylist.h - list ADT - with a destructor and copy constructor
7  *             implements copy semantics
8  *             uses void * key for comparison
9  *             this class has been purified
10  *           
11  * See the tests subdirectory for examples of its use.
12  *
13  * To use this class: 
14  *       1) put 'pragma implementation "keylist.h" ' in 
15  *           a the file where you want the code generated
16  *       2) put '#include "<prefix>/keylist.h" after line 1
17  *           in the same file
18  *       3) this class is instantiated with class Type
19  *          if class Type is not a basic Type (int, char)
20  *          then you need to implement the following for
21  *          class Type if copy semantics are to be upheld
22  *          if this is not done, purify will complain and
23  *          the class behavior will be incorrect
24  *            a) a copy constructor --> Type::Type(Type &c)
25  *            b) the = operator --> Type & Type::operator =(Type&)
26  *
27  *
28  * $Log: keylist.h,v $
29  * Revision 1.1  1994/08/17 18:23:48  markc
30  * Added new classes: Cstring KeyList, KList
31  * Added new function: RPCgetArg
32  * Changed typedefs in machineType.h to #defines
33  *
34  */
35
36 #define KYL_TRUE 1
37 #define KYL_FALSE 0
38 typedef int KYL_BOOL;
39
40 #ifdef KYL_PRINT
41 #include <iostream.h>
42 #endif
43
44 #pragma interface
45
46 #define ListHash(ptr, size) (((unsigned int)(ptr) % (unsigned int)(size)))
47
48 template <class Type> class KeyList;
49
50 template <class Type>
51 class KeyListItem {
52 friend class KeyList<Type>;
53 public:
54   KeyListItem(const Type &d, const void *k) {
55     data =d;
56     next = (KeyListItem<Type>*) 0;
57     key = k;
58   }
59   KeyListItem(const KeyListItem<Type> &it) {
60     data = it.data;
61     key = it.key;
62     next = (KeyListItem<Type>*) 0;
63   }
64   ~KeyListItem() {;}
65   KeyListItem<Type> & operator = (const KeyListItem<Type> &it) {
66     if (this == &it)
67       return (*this);
68     else {
69       data = it.data;
70       key = it.key;
71       return (*this);
72     }
73   }
74 private:
75   Type data;
76   void *key;
77   KeyListItem<Type> *next;
78 };
79
80 template <class Type>
81 class KeyList {
82 public:
83   KeyList() { head = (KeyListItem<Type>*) 0; }
84   KeyList(const KeyList<Type> &from);
85   ~KeyList() { destroy(); }
86
87   KYL_BOOL destroy();
88   KYL_BOOL remove (void *key) {
89     int f;
90     find(key, f, 1);
91     return f;
92   }
93
94   int empty() const { return (head == (KeyListItem<Type>*) 0);}
95   int count() const;
96
97   KYL_BOOL inList(const void *key);
98   void reverse();
99
100   KYL_BOOL append(const Type &data, const void *key);
101   KYL_BOOL prepend(const Type &data, const void *key);
102   KYL_BOOL appendUnique (const Type &i3, const void *key);
103   KYL_BOOL prependUnique (const Type &i3, const void *key);
104
105   KeyList<Type> & operator += (const KeyList<Type> &mergee);
106   KeyList<Type> & operator = (const KeyList<Type> &from);
107
108   void map (void (*map_function)(const Type &item)) const;
109
110   Type car(KYL_BOOL &valid);
111   KeyList<Type> cdr();
112
113   // modifies the list elements in place
114   void modify(Type (*mod_func)(Type &input));
115
116   // removeMe == 0 --> the matched element is removed
117   // found --> signifies results of match
118   Type find(const void *key, KYL_BOOL &found, const int removeMe=0);
119
120 #ifdef KYL_PRINT
121   friend ostream &operator << (ostream& os, const KeyList<Type>& S) {
122     KeyListItem<Type> *temp;
123     for (temp=S.head; temp; temp=temp->next)
124       os << " : d=" << temp->data << "  k=" << temp->key << " : " << endl;
125     return os;
126   }
127 #endif
128
129 protected:
130   KeyListItem<Type> *last() {
131     KeyListItem<Type> *tmp, *lag;
132     for (tmp=head, lag=0; tmp; lag=tmp, tmp=tmp->next)
133       ;
134     return lag;
135   }
136   KeyListItem<Type>     *head;
137 };
138
139
140 template <class Type>
141 KeyList<Type>::KeyList (const KeyList<Type> &from) {
142   KeyListItem<Type> *temp;
143   head = 0;
144   for (temp=from.head; temp; temp = temp-> next) {
145     prepend(temp->data, temp->key);
146   }
147   reverse();
148 }
149
150 template <class Type>
151 void KeyList<Type>::reverse() 
152 {
153   KeyListItem<Type> *curr, *lag=0, *ahead;
154
155   for (curr=head; curr; curr=ahead) {
156     ahead = curr->next;
157     curr->next = lag;
158     lag = curr;
159   }
160   head = lag;
161 }
162
163 template <class Type>
164 int KeyList<Type>::count() const
165 {
166   int c=0;
167   KeyListItem<Type> *temp;
168   for (temp=head; temp; temp = temp->next)
169     c++;
170   return c;
171 }
172
173 template <class Type>
174 KYL_BOOL KeyList<Type>::destroy()
175 {
176   KeyListItem<Type> *temp, *next;
177   
178   for (temp=head; temp; temp = next) {
179     next = temp->next;
180     delete (temp);
181   } 
182   head = 0;
183   return KYL_TRUE;
184 }
185
186 template <class Type>
187 KeyList<Type> &KeyList<Type>::operator = (const KeyList<Type> &from)
188 {
189   KeyListItem<Type> *temp;
190
191   if (this == &from)
192     return (*this);
193
194   destroy();
195   
196   for (temp=from.head; temp; temp = temp->next)
197     prepend(temp->data, temp->key);
198   reverse();
199   return (*this);
200 }
201
202
203 template <class Type>
204 KeyList<Type> &KeyList<Type>::operator +=(const KeyList<Type> &mergee)
205 {
206   KeyListItem<Type> *curr;
207
208   if (this == &mergee)
209     return (*this);
210
211   for (curr=mergee.head; curr; curr=curr->next) {
212     append(curr->data, curr->key);
213   }
214   return (*this);
215 }
216
217 template <class Type>
218 void KeyList<Type>::map (void (*map_function)(const Type &item)) const
219 {
220   const KeyListItem<Type> *temp = 0;
221
222   if (!map_function) return;
223   for (temp = head; temp; temp = temp->next)
224     map_function (temp->data);
225 }
226
227 template <class Type>
228 void KeyList<Type>::modify (Type (*mod_f)(Type &item))
229 {
230   KeyListItem<Type> *temp = 0;
231
232   if (!mod_f) return;
233   for (temp = head; temp; temp = temp->next) 
234     temp->data = mod_f(temp->data);
235 }
236
237 template <class Type>
238 KYL_BOOL KeyList<Type>::prependUnique (const Type &comp_me, const void *key)
239 {
240   KeyListItem<Type> *temp = 0;
241
242   for (temp = head; temp; temp = temp->next)
243     if (temp->key == key) {
244       temp->data = comp_me; 
245       return KYL_TRUE;
246     }
247   // not found on list, so add it
248   return (prepend(comp_me, key));
249 }
250
251 template <class Type>
252 KYL_BOOL KeyList<Type>::appendUnique (const Type &comp_me, const void *key)
253 {
254   KeyListItem<Type> *temp = 0;
255
256   for (temp = head; temp; temp = temp->next)
257     if (temp->key == key) {
258       temp->data = comp_me; 
259       return KYL_TRUE;
260     }
261   // not found on list, so add it
262   return (append(comp_me, key));
263 }
264
265 template <class Type>
266 KYL_BOOL KeyList<Type>::prepend (const Type &data, const void *key) 
267
268   KeyListItem<Type> *ni;
269
270   ni = new KeyListItem<Type>(data, key);
271   if (!ni)
272     return KYL_FALSE;
273
274   ni->next = head;
275   head = ni;
276   return KYL_TRUE;
277 }
278
279
280 template <class Type>
281 KYL_BOOL KeyList<Type>::append(const Type &data, const void *key) 
282
283   KeyListItem<Type> *ni;
284   KeyListItem<Type> *tl;
285
286   ni = new KeyListItem<Type>(data, key);
287   if (!ni)
288     return KYL_FALSE;
289
290   tl = last();
291   if (tl) {
292     tl->next = ni;
293   } else {
294     ni->next = head;
295     head = ni;
296   }
297   return KYL_TRUE;
298 }
299
300 template <class Type>
301 KYL_BOOL KeyList<Type>::inList (const void *key)
302 {
303   KeyListItem<Type> *curr;
304   for (curr=head; curr; curr=curr->next) {
305     if (curr->key == key)
306       return KYL_TRUE;
307   }
308   return KYL_FALSE;
309 }
310
311 template <class Type>
312 Type KeyList<Type>::find(const void *key, KYL_BOOL &found, const int removeMe)
313 {
314   KeyListItem<Type> *lag, *curr;
315   Type ret;
316
317   for (curr=head, lag = (KeyListItem<Type>*) 0; curr; curr=curr->next) {
318     if (curr->key == key)
319       break;
320     lag = curr;
321   }
322
323   if (curr) {
324     found = KYL_TRUE;
325     ret = curr->data;
326     if (removeMe) {
327       if (lag)
328         lag->next = curr->next;
329       else
330         head = curr->next;
331       delete(curr);
332     }
333   }
334   // this may not be data from a found element
335   return ret;
336 }
337
338 template <class Type>
339 Type KeyList<Type>::car(KYL_BOOL &valid)
340 {
341   KeyListItem<Type> *nx;
342   Type ret;
343
344   if (head) {
345     nx = head;
346     ret = nx->data;
347     head = head->next;
348     delete nx;
349     valid = KYL_TRUE;
350     return ret;
351   } else {
352     valid = KYL_FALSE;
353     return ret;
354   }
355 }
356
357
358 template <class Type>
359 KeyList<Type> KeyList<Type>::cdr()
360 {
361   KeyList<Type> ret;
362   int val;
363
364   ret = *this;
365   ret.car(val);
366   return ret;
367 }
368
369
370 // Hash table using KLists
371 template <class Type> class KHTable {
372 public:
373   // placing function def here makes gcc happy 
374 #ifdef KYL_PRINT
375 friend ostream &operator<<(ostream &os, KHTable<Type> &data) {
376   int i;
377   for (i=0; i < data.tableSize; i++) {
378     if (data.table[i]) {
379       os << " list # " << i << endl;
380       os << *data.table[i];
381     }
382   }
383   return os;
384 }
385 #endif
386
387   KHTable(const int size=97) {
388     int s;
389     tableSize = size;
390     if (tableSize <= 0) tableSize = 97;
391     table = new KeyList<Type>*[tableSize];
392     for (s=0; s<size; ++s)
393       table[s] = 0;
394   }
395
396   KHTable(const KHTable<Type> &data) {
397     int j;
398     tableSize = data.tableSize;
399     table = new KeyList<Type>*[tableSize];
400     for (j=0; j < tableSize; ++j)
401       table[j] = data.table[j];
402   }
403
404   ~KHTable() {delete [] table;}
405   KYL_BOOL destroy();
406
407   Type find(const void *key, int &valid, const int removeMe=0);
408   KYL_BOOL add(const Type &data, const void *key);
409   KYL_BOOL addUnique(const Type &data, const void *key);
410
411   KYL_BOOL remove(const void *key) {
412     int val;
413     find(key, val, 1);
414     return(val);
415   }
416
417   KHTable<Type> & operator =(const KHTable<Type> & arg);
418   KYL_BOOL operator == (const KHTable<Type> & arg);
419
420   KYL_BOOL inTable(const void *key);
421   int count() const;
422
423 private:
424   KeyList<Type> **table;
425   int tableSize;
426 };
427
428
429 template <class Type>
430 KYL_BOOL KHTable<Type>::destroy()
431 {
432   int j;
433   for (j=0; j<tableSize; ++j) 
434     if (table[j]) {
435       delete (table[j]);
436       table[j] = 0;
437     }
438   return KYL_TRUE;
439 }
440
441 template <class Type>
442 Type KHTable<Type>::find(const void *key, int &valid, const int removeMe)
443 {
444   int hid;
445   Type ret;
446
447   hid = ListHash(key, tableSize);
448   if ((hid < 0) ||
449       (hid > tableSize)) {
450     valid = KYL_FALSE;
451     return ret;
452   } else if (!table[hid]) {
453     valid = KYL_FALSE;
454     return ret;
455   } else {
456     return(table[hid]->find(key, valid, removeMe));
457   }
458 }
459
460 template <class Type>
461 KYL_BOOL KHTable<Type>::add(const Type &data, const void *key)
462 {
463   int hid;
464
465   hid = ListHash(key, tableSize);
466   if (hid <0 || hid > tableSize) 
467     return KYL_FALSE;
468
469   if (!table[hid])
470     table[hid] = new(KeyList<Type>);
471
472   return (table[hid]->prepend(data, key));
473 }
474
475 template <class Type>
476 KHTable<Type> & KHTable<Type>::operator = (const KHTable<Type> &arg)
477 {
478   int j;
479
480   if (this == &arg)
481     return (*this);
482
483   destroy();
484   tableSize = arg.tableSize;
485   table = new KeyList<Type>*[tableSize];
486   for (j=0; j < arg.tableSize; ++j)
487     table[j] = arg.table[j];
488   return(*this);
489 }
490
491 template <class Type>
492 KYL_BOOL KHTable<Type>::operator == (const KHTable<Type> &arg)
493 {
494   int i;
495   if (tableSize != arg.tableSize)
496     return KYL_FALSE;
497   else {
498     for (i=0; i<tableSize; ++i) {
499       if (!(table[i] == arg.table[i]))
500         return KYL_FALSE;
501     }
502   }
503   return KYL_TRUE;
504 }
505
506 template <class Type> 
507 KYL_BOOL KHTable<Type>::addUnique(const Type &data, const void *key)
508 {
509   if (inTable(key))
510     return KYL_FALSE;
511   else
512     return (add(data, key));
513 }
514
515 template <class Type>
516 int KHTable<Type>::count() const {
517   int i, total=0;
518   for (i=0; i < tableSize; i++) {
519     if (table[i]) {
520       total += table[i]->count();
521     }
522   }
523   return(total);
524 }
525
526 template <class Type>
527 KYL_BOOL KHTable<Type>::inTable(const void *key)
528 {
529   int hid;
530
531   hid = ListHash(key, tableSize);
532   if ((hid < 0) ||
533       (hid > tableSize))
534     return KYL_FALSE;
535   else if (!table[hid])
536     return KYL_FALSE;
537   else
538     return(table[hid]->inList(key));
539 }
540
541 #endif