Added new classes: Cstring KeyList, KList
[dyninst.git] / pdutil / h / klist.h
1
2 #ifndef _KLIST_H
3 #define _KLIST_H
4
5 /*
6  * klist.h - list ADT - with a destructor and copy constructor
7  *           implements copy semantics
8  *           uses == 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 "klist.h" ' in 
15  *           a the file where you want the code generated
16  *       2) put '#include "<prefix>/klist.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  *            c) the == operator --> int Type::operator== (Type&)
27  *
28  *
29  * $Log: klist.h,v $
30  * Revision 1.1  1994/08/17 18:23:49  markc
31  * Added new classes: Cstring KeyList, KList
32  * Added new function: RPCgetArg
33  * Changed typedefs in machineType.h to #defines
34  *
35  */
36
37 #define KL_TRUE 1
38 #define KL_FALSE 0
39 typedef int KL_BOOL;
40
41 #ifdef KL_PRINT
42 #include <iostream.h>
43 #endif
44
45 #pragma interface
46
47
48 template <class Type> class KList;
49
50 template <class Type>
51 class KListItem {
52 friend class KList<Type>;
53 public:
54   KListItem(const Type &d) {
55     data =d;
56     next = (KListItem<Type>*) 0;
57   }
58   KListItem(const KListItem<Type> &it) {
59     data = it.data;
60     next = (KListItem<Type>*) 0;
61   }
62   ~KListItem() {;}
63   KListItem<Type> & operator = (const KListItem<Type> &it) {
64     if (this == &it)
65       return (*this);
66     else {
67       data = it.data;
68       return (*this);
69     }
70   }
71 private:
72   Type data;
73   KListItem<Type> *next;
74 };
75
76 template <class Type>
77 class KList {
78 public:
79   KList() { head = (KListItem<Type>*) 0; }
80   KList(const KList<Type> &from);
81   ~KList() { destroy(); }
82
83   KL_BOOL destroy();
84   KL_BOOL remove(const Type &it) {
85     int f;
86     find(it, f, 1);
87     return f;
88   }
89
90   int empty() const { return (head == (KListItem<Type>*) 0);}
91   int count() const;
92
93   void reverse();
94
95   KL_BOOL append(const Type &data);
96   KL_BOOL prepend(const Type &data);
97   KL_BOOL appendUnique (const Type &i3);
98   KL_BOOL prependUnique (const Type &i3);
99
100   KList<Type> & operator += (const KList<Type> &mergee);
101   KList<Type> & operator = (const KList<Type> &from);
102
103   KList<Type> pure_map(Type (*map_f)(const Type &it)) const;
104   void map (void (*map_function)(const Type &item)) const;
105
106   // iterates until map_func(i1, i2) != 0
107   void mapUntil (const Type &item, int (*map_func)(const Type &i1,
108                                                    const Type &i2)) const;
109
110   Type car(KL_BOOL &valid);
111   KList<Type> cdr();
112
113   // modifies the list elements in place
114   void modify(Type (*mod_func)(Type &input));
115
116   // gcc doesn't compile this when only the declaration is here
117   // removeMe == 0 --> the matched element is removed
118   // found --> signifies results of match
119   // you provide the cmp function, or the class uses == 
120   Type find(const Type &inE, KL_BOOL &found, int removeMe=0,
121             int (*cmp_f)(const Type &a, const Type &b)= 0)
122     {
123       KListItem<Type> *lag, *curr;
124       Type ret;
125
126       for (curr=head, lag = (KListItem<Type>*) 0; curr; curr=curr->next) {
127         if (cmp_f) {
128           if (cmp_f(curr->data, inE))
129             break;
130         } else if (curr->data == inE)
131           break;
132         lag = curr;
133       }
134
135       if (curr) {
136         found = KL_TRUE;
137         ret = curr->data;
138         if (removeMe) {
139           if (lag)
140             lag->next = curr->next;
141           else
142             head = curr->next;
143           delete(curr);
144         }
145       }
146       // this may not be data from a found element
147       return ret;
148     }
149
150
151 #ifdef KL_PRINT
152   friend ostream &operator << (ostream& os, const KList<Type>& S) {
153     KListItem<Type> *temp;
154     for (temp=S.head; temp; temp=temp->next)
155       os << " : " << temp->data << " : ";
156     return os;
157   }
158 #endif
159
160 protected:
161   KListItem<Type> *last() {
162     KListItem<Type> *tmp, *lag;
163     for (tmp=head, lag=0; tmp; lag=tmp, tmp=tmp->next)
164       ;
165     return lag;
166   }
167   KListItem<Type>       *head;
168 };
169
170
171 template <class Type>
172 KList<Type>::KList (const KList<Type> &from) {
173   KListItem<Type> *temp;
174   head = 0;
175   for (temp=from.head; temp; temp = temp-> next) {
176     prepend(temp->data);
177   }
178   reverse();
179 }
180
181 template <class Type>
182 int KList<Type>::count() const
183 {
184   int c=0;
185   KListItem<Type> *temp;
186   for (temp=head; temp; temp = temp->next)
187     c++;
188   return c;
189 }
190
191 template <class Type>
192 KL_BOOL KList<Type>::destroy()
193 {
194   KListItem<Type> *temp, *next;
195   
196   for (temp=head; temp; temp = next) {
197     next = temp->next;
198     delete (temp);
199   } 
200   head = 0;
201   return KL_TRUE; 
202 }
203
204 template <class Type>
205 KList<Type> &KList<Type>::operator = (const KList<Type> &from)
206 {
207   KListItem<Type> *temp;
208
209   if (this == &from)
210     return (*this);
211
212   destroy();
213   
214   for (temp=from.head; temp; temp = temp->next)
215     prepend(temp->data);
216
217   reverse();
218   return (*this);
219 }
220
221
222 template <class Type>
223 KList<Type> &KList<Type>::operator +=(const KList<Type> &mergee)
224 {
225   KListItem<Type> *curr;
226
227   if (this == &mergee)
228     return (*this);
229
230   for (curr=mergee.head; curr; curr=curr->next) {
231     append(curr->data);
232   }
233   return (*this);
234 }
235
236 template <class Type>
237 KList<Type> 
238 KList<Type>::pure_map(Type (*map_f)(const Type &it)) const
239 {
240   KListItem<Type> *temp;
241   KList<Type> Ret;
242   for (temp=head; temp; temp=temp->next) {
243     Ret.append(map_f(temp->data));
244   }
245   return Ret;
246 }
247
248 template <class Type>
249 void KList<Type>::map (void (*map_function)(const Type &item)) const
250 {
251   const KListItem<Type> *temp = 0;
252
253   if (!map_function) return;
254   for (temp = head; temp; temp = temp->next)
255     map_function (temp->data);
256 }
257
258 template <class Type>
259 void KList<Type>::modify (Type (*mod_f)(Type &item))
260 {
261   KListItem<Type> *temp = 0;
262
263   if (!mod_f) return;
264   for (temp = head; temp; temp = temp->next) 
265     temp->data = mod_f(temp->data);
266 }
267
268 template <class Type>
269 void KList<Type>::mapUntil (const Type &item,
270                             int (*map_func)(const Type &i1,
271                                             const Type &i2)) const
272 {
273   const KListItem<Type> *temp = 0;
274
275   if (!map_func) return;
276   for (temp = head; temp; temp = temp->next)
277     if (map_func (temp->data, item))
278       return;
279 }
280
281 template <class Type>
282 KL_BOOL KList<Type>::prependUnique (const Type &comp_me)
283 {
284   KListItem<Type> *temp = 0;
285
286   for (temp = head; temp; temp = temp->next)
287     if (temp->data == comp_me) {
288       temp->data = comp_me; 
289       return KL_TRUE;
290     }
291   // not found on list, so add it
292   return (prepend(comp_me));
293 }
294
295 template <class Type>
296 KL_BOOL KList<Type>::appendUnique (const Type &comp_me)
297 {
298   KListItem<Type> *temp = 0;
299
300   for (temp = head; temp; temp = temp->next)
301     if (temp->data == comp_me) {
302       temp->data = comp_me; 
303       return KL_TRUE;
304     }
305   // not found on list, so add it
306   return (append(comp_me));
307 }
308
309 template <class Type>
310 KL_BOOL KList<Type>::prepend (const Type &data) 
311
312   KListItem<Type> *ni;
313
314   ni = new KListItem<Type>(data);
315   if (!ni)
316     return KL_FALSE;
317
318   ni->next = head;
319   head = ni;
320   return KL_TRUE;
321 }
322
323
324 template <class Type>
325 KL_BOOL KList<Type>::append(const Type &data) 
326
327   KListItem<Type> *ni;
328   KListItem<Type> *tl;
329
330   ni = new KListItem<Type>(data);
331   if (!ni)
332     return KL_FALSE;
333
334   tl = last();
335   if (tl) {
336     tl->next = ni;
337   } else {
338     ni->next = head;
339     head = ni;
340   }
341   return KL_TRUE;
342 }
343
344 template <class Type>
345 Type KList<Type>::car(KL_BOOL &valid)
346 {
347   KListItem<Type> *nx;
348   Type ret;
349
350   if (head) {
351     nx = head;
352     ret = nx->data;
353     head = head->next;
354     delete nx;
355     valid = KL_TRUE;
356     return ret;
357   } else {
358     valid = KL_FALSE;
359     return ret;
360   }
361 }
362
363
364 template <class Type>
365 KList<Type> KList<Type>::cdr()
366 {
367   KList<Type> ret;
368   int val;
369
370   ret = *this;
371   ret.car(val);
372   return ret;
373 }
374
375 template <class Type>
376 void KList<Type>::reverse()
377 {
378   KListItem<Type> *curr, *lag=0, *ahead;
379
380   for (curr=head; curr; curr=ahead) {
381     ahead = curr->next;
382     curr->next = lag;
383     lag = curr;
384   }
385   head = lag;
386 }
387
388 #endif