1) Cmake support for PPC64LE builds
[dyninst.git] / common / src / klist.h
1 /*
2  * See the dyninst/COPYRIGHT file for copyright information.
3  * 
4  * We provide the Paradyn Tools (below described as "Paradyn")
5  * on an AS IS basis, and do not warrant its validity or performance.
6  * We reserve the right to update, modify, or discontinue this
7  * software at any time.  We shall have no obligation to supply such
8  * updates or modifications or any other form of support to you.
9  * 
10  * By your use of Paradyn, you understand and agree that we (or any
11  * other person or entity with proprietary rights in Paradyn) are
12  * under no obligation to provide either maintenance services,
13  * update services, notices of latent defects, or correction of
14  * defects for Paradyn.
15  * 
16  * This library is free software; you can redistribute it and/or
17  * modify it under the terms of the GNU Lesser General Public
18  * License as published by the Free Software Foundation; either
19  * version 2.1 of the License, or (at your option) any later version.
20  * 
21  * This library is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24  * Lesser General Public License for more details.
25  * 
26  * You should have received a copy of the GNU Lesser General Public
27  * License along with this library; if not, write to the Free Software
28  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
29  */
30
31 #ifndef _KLIST_H
32 #define _KLIST_H
33
34 /*
35  * klist.h - list ADT - with a destructor and copy constructor
36  *           implements copy semantics
37  *           uses == for comparison
38  *           this class has been purified
39  *           
40  * See the tests subdirectory for examples of its use.
41  *
42  * To use this class: 
43  *       1) put 'pragma implementation "klist.h" ' in 
44  *           a the file where you want the code generated
45  *       2) put '#include "<prefix>/klist.h" after line 1
46  *           in the same file
47  *       3) this class is instantiated with class Type
48  *          if class Type is not a basic Type (int, char)
49  *          then you need to implement the following for
50  *          class Type if copy semantics are to be upheld
51  *          if this is not done, purify will complain and
52  *          the class behavior will be incorrect
53  *            a) a copy constructor --> Type::Type(Type &c)
54  *            b) the = operator --> Type & Type::operator =(Type&)
55  *            c) the == operator --> int Type::operator== (Type&)
56  *
57  *
58  * $Log: klist.h,v $
59  * Revision 1.1  1994/08/17 18:23:49  markc
60  * Added new classes: Cstring KeyList, KList
61  * Added new function: RPCgetArg
62  * Changed typedefs in machineType.h to #defines
63  *
64  */
65
66 #define KL_TRUE 1
67 #define KL_FALSE 0
68 typedef int KL_BOOL;
69
70 #ifdef KL_PRINT
71 #include <iostream.h>
72 #endif
73
74 #pragma interface
75
76
77 template <class Type> class KList;
78
79 template <class Type>
80 class KListItem {
81 friend class KList<Type>;
82 public:
83   KListItem(const Type &d) {
84     data =d;
85     next = (KListItem<Type>*) 0;
86   }
87   KListItem(const KListItem<Type> &it) {
88     data = it.data;
89     next = (KListItem<Type>*) 0;
90   }
91   ~KListItem() {;}
92   KListItem<Type> & operator = (const KListItem<Type> &it) {
93     if (this == &it)
94       return (*this);
95     else {
96       data = it.data;
97       return (*this);
98     }
99   }
100 private:
101   Type data;
102   KListItem<Type> *next;
103 };
104
105 template <class Type>
106 class KList {
107 public:
108   KList() { head = (KListItem<Type>*) 0; }
109   KList(const KList<Type> &from);
110   ~KList() { destroy(); }
111
112   KL_BOOL destroy();
113   KL_BOOL remove(const Type &it) {
114     int f;
115     find(it, f, 1);
116     return f;
117   }
118
119   int empty() const { return (head == (KListItem<Type>*) 0);}
120   int count() const;
121
122   void reverse();
123
124   KL_BOOL append(const Type &data);
125   KL_BOOL prepend(const Type &data);
126   KL_BOOL appendUnique (const Type &i3);
127   KL_BOOL prependUnique (const Type &i3);
128
129   KList<Type> & operator += (const KList<Type> &mergee);
130   KList<Type> & operator = (const KList<Type> &from);
131
132   KList<Type> pure_map(Type (*map_f)(const Type &it)) const;
133   void map (void (*map_function)(const Type &item)) const;
134
135   // iterates until map_func(i1, i2) != 0
136   void mapUntil (const Type &item, int (*map_func)(const Type &i1,
137                                                    const Type &i2)) const;
138
139   Type car(KL_BOOL &valid);
140   KList<Type> cdr();
141
142   // modifies the list elements in place
143   void modify(Type (*mod_func)(Type &input));
144
145   // gcc doesn't compile this when only the declaration is here
146   // removeMe == 0 --> the matched element is removed
147   // found --> signifies results of match
148   // you provide the cmp function, or the class uses == 
149   Type find(const Type &inE, KL_BOOL &found, int removeMe=0,
150             int (*cmp_f)(const Type &a, const Type &b)= 0)
151     {
152       KListItem<Type> *lag, *curr;
153       Type ret;
154
155       for (curr=head, lag = (KListItem<Type>*) 0; curr; curr=curr->next) {
156         if (cmp_f) {
157           if (cmp_f(curr->data, inE))
158             break;
159         } else if (curr->data == inE)
160           break;
161         lag = curr;
162       }
163
164       if (curr) {
165         found = KL_TRUE;
166         ret = curr->data;
167         if (removeMe) {
168           if (lag)
169             lag->next = curr->next;
170           else
171             head = curr->next;
172           delete(curr);
173         }
174       }
175       // this may not be data from a found element
176       return ret;
177     }
178
179
180 #ifdef KL_PRINT
181   friend ostream &operator << (ostream& os, const KList<Type>& S) {
182     KListItem<Type> *temp;
183     for (temp=S.head; temp; temp=temp->next)
184       os << " : " << temp->data << " : ";
185     return os;
186   }
187 #endif
188
189 protected:
190   KListItem<Type> *last() {
191     KListItem<Type> *tmp, *lag;
192     for (tmp=head, lag=0; tmp; lag=tmp, tmp=tmp->next)
193       ;
194     return lag;
195   }
196   KListItem<Type>       *head;
197 };
198
199
200 template <class Type>
201 KList<Type>::KList (const KList<Type> &from) {
202   KListItem<Type> *temp;
203   head = 0;
204   for (temp=from.head; temp; temp = temp-> next) {
205     prepend(temp->data);
206   }
207   reverse();
208 }
209
210 template <class Type>
211 int KList<Type>::count() const
212 {
213   int c=0;
214   KListItem<Type> *temp;
215   for (temp=head; temp; temp = temp->next)
216     c++;
217   return c;
218 }
219
220 template <class Type>
221 KL_BOOL KList<Type>::destroy()
222 {
223   KListItem<Type> *temp, *next;
224   
225   for (temp=head; temp; temp = next) {
226     next = temp->next;
227     delete (temp);
228   } 
229   head = 0;
230   return KL_TRUE; 
231 }
232
233 template <class Type>
234 KList<Type> &KList<Type>::operator = (const KList<Type> &from)
235 {
236   KListItem<Type> *temp;
237
238   if (this == &from)
239     return (*this);
240
241   destroy();
242   
243   for (temp=from.head; temp; temp = temp->next)
244     prepend(temp->data);
245
246   reverse();
247   return (*this);
248 }
249
250
251 template <class Type>
252 KList<Type> &KList<Type>::operator +=(const KList<Type> &mergee)
253 {
254   KListItem<Type> *curr;
255
256   if (this == &mergee)
257     return (*this);
258
259   for (curr=mergee.head; curr; curr=curr->next) {
260     append(curr->data);
261   }
262   return (*this);
263 }
264
265 template <class Type>
266 KList<Type> 
267 KList<Type>::pure_map(Type (*map_f)(const Type &it)) const
268 {
269   KListItem<Type> *temp;
270   KList<Type> Ret;
271   for (temp=head; temp; temp=temp->next) {
272     Ret.append(map_f(temp->data));
273   }
274   return Ret;
275 }
276
277 template <class Type>
278 void KList<Type>::map (void (*map_function)(const Type &item)) const
279 {
280   const KListItem<Type> *temp = 0;
281
282   if (!map_function) return;
283   for (temp = head; temp; temp = temp->next)
284     map_function (temp->data);
285 }
286
287 template <class Type>
288 void KList<Type>::modify (Type (*mod_f)(Type &item))
289 {
290   KListItem<Type> *temp = 0;
291
292   if (!mod_f) return;
293   for (temp = head; temp; temp = temp->next) 
294     temp->data = mod_f(temp->data);
295 }
296
297 template <class Type>
298 void KList<Type>::mapUntil (const Type &item,
299                             int (*map_func)(const Type &i1,
300                                             const Type &i2)) const
301 {
302   const KListItem<Type> *temp = 0;
303
304   if (!map_func) return;
305   for (temp = head; temp; temp = temp->next)
306     if (map_func (temp->data, item))
307       return;
308 }
309
310 template <class Type>
311 KL_BOOL KList<Type>::prependUnique (const Type &comp_me)
312 {
313   KListItem<Type> *temp = 0;
314
315   for (temp = head; temp; temp = temp->next)
316     if (temp->data == comp_me) {
317       temp->data = comp_me; 
318       return KL_TRUE;
319     }
320   // not found on list, so add it
321   return (prepend(comp_me));
322 }
323
324 template <class Type>
325 KL_BOOL KList<Type>::appendUnique (const Type &comp_me)
326 {
327   KListItem<Type> *temp = 0;
328
329   for (temp = head; temp; temp = temp->next)
330     if (temp->data == comp_me) {
331       temp->data = comp_me; 
332       return KL_TRUE;
333     }
334   // not found on list, so add it
335   return (append(comp_me));
336 }
337
338 template <class Type>
339 KL_BOOL KList<Type>::prepend (const Type &data) 
340
341   KListItem<Type> *ni;
342
343   ni = new KListItem<Type>(data);
344   if (!ni)
345     return KL_FALSE;
346
347   ni->next = head;
348   head = ni;
349   return KL_TRUE;
350 }
351
352
353 template <class Type>
354 KL_BOOL KList<Type>::append(const Type &data) 
355
356   KListItem<Type> *ni;
357   KListItem<Type> *tl;
358
359   ni = new KListItem<Type>(data);
360   if (!ni)
361     return KL_FALSE;
362
363   tl = last();
364   if (tl) {
365     tl->next = ni;
366   } else {
367     ni->next = head;
368     head = ni;
369   }
370   return KL_TRUE;
371 }
372
373 template <class Type>
374 Type KList<Type>::car(KL_BOOL &valid)
375 {
376   KListItem<Type> *nx;
377   Type ret;
378
379   if (head) {
380     nx = head;
381     ret = nx->data;
382     head = head->next;
383     delete nx;
384     valid = KL_TRUE;
385     return ret;
386   } else {
387     valid = KL_FALSE;
388     return ret;
389   }
390 }
391
392
393 template <class Type>
394 KList<Type> KList<Type>::cdr()
395 {
396   KList<Type> ret;
397   int val;
398
399   ret = *this;
400   ret.car(val);
401   return ret;
402 }
403
404 template <class Type>
405 void KList<Type>::reverse()
406 {
407   KListItem<Type> *curr, *lag=0, *ahead;
408
409   for (curr=head; curr; curr=ahead) {
410     ahead = curr->next;
411     curr->next = lag;
412     lag = curr;
413   }
414   head = lag;
415 }
416
417 #endif