Initial revision
[dyninst.git] / pdutil / h / list.h
1 /*
2  *  Copyright 1993 Jeff Hollingsworth.  All rights reserved.
3  *
4  */
5
6 /*
7  * list.h - list ADT
8  *
9  * $Log: list.h,v $
10  * Revision 1.1  1993/05/07 20:21:15  hollings
11  * Initial revision
12  *
13  * Revision 1.1  1993/03/19  22:51:05  hollings
14  * Initial revision
15  *
16  *
17  */
18 #ifndef LIST_H
19 #define LIST_H
20 #include <stdio.h>
21
22 #define FALSE 0
23 #define TRUE  1
24
25 inline static int ListHash(void *ptr, int size)
26 {
27     return(((int)(ptr) % (int)(size)));
28 }
29
30 class List;
31
32 template <class Type> class ListItem {
33     friend class List<Type>;
34     private:
35         Type            data;
36         void            *key;
37         ListItem<Type>  *next;
38 };
39
40 template <class Type> class List {
41     public:
42         List() { head = NULL; }
43         void add(Type data, void *key);
44         void add(Type data) { add(data, (void *) data); }
45         Boolean addUnique(Type data) { return(addUnique(data, (void *) data)); }
46         Boolean addUnique(Type data, void *key) {
47             Type temp;
48
49             temp = find(key);
50             if (!temp) {
51                 add(data, key);
52                 return(TRUE);
53             } else {
54                 return(FALSE);
55             }
56         }
57         Type find(void *key);
58         void remove(Type data);
59         int count()     {
60             int c;
61             ListItem<Type> *curr;
62
63             for (curr=head,c=0; curr; curr=curr->next) c++;
64             return(c);
65         }
66         Type operator *() { 
67             if (head) 
68                 return(head->data); 
69             else
70                 return((Type) NULL);
71         }
72         void operator +=(List<Type> mergee) {
73             ListItem<Type> *curr;
74
75             for (curr=mergee.head; curr; curr=curr->next) {
76                 add(curr->data, curr->key);
77             }
78         }
79         Type operator ++() { 
80             Type ret = (Type) NULL;
81             if (head) {
82                 ret = head->data;
83                 head = head->next; 
84             }
85             return(ret); 
86         }
87     private:
88         ListItem<Type>  *head;
89 };
90
91
92 template <class Type> void List<Type>::add(Type data, void *key)
93 {
94     ListItem<Type> *ni;
95
96     ni = new(ListItem<Type>);
97     ni->data = data;
98     ni->key = key;
99
100     ni->next = head;
101     head = ni;
102 }
103
104 template <class Type> void List<Type>::remove(Type data)
105 {
106     ListItem<Type> *lag;
107     ListItem<Type> *curr;
108
109     for (curr=head, lag = NULL; curr; curr=curr->next) {
110         if (curr->data == data) {
111             break;
112         }
113         lag = curr;
114     }
115
116     if (curr) {
117         if (lag) {
118             lag->next = curr->next;
119         } else {
120             head = curr->next;
121         }
122         delete(curr);
123     } else {
124         abort();
125     }
126 }
127
128 template <class Type> Type List<Type>::find(void *data)
129 {
130     ListItem<Type> *curr;
131
132     for (curr=head; curr; curr=curr->next) {
133         if (curr->key == data) {
134             return(curr->data);
135         }
136     }
137     return((Type) 0);
138 }
139
140 template <class Type> class HTable {
141
142     public:
143         HTable(Type data) { HTable(); add(data, (void *) data); }
144         HTable(); 
145         void add(Type data, void *key);
146         Boolean addUnique(Type data, void *key) {
147             Type temp;
148
149             temp = find(key);
150             if (temp ) {
151                 return(0);
152             } else {
153                 add(data, key);
154                 return(1);
155             }
156         }
157         Type find(void *key);
158         // void remove(Type data);
159         Type operator *() {
160             Type curr;
161
162             curr = *currList;
163             if (curr) return(curr);
164             for (currHid++; currHid < tableSize; currHid++) {
165                 if (table[currHid]) {
166                     currList = *table[currHid];
167                     curr = *currList;
168                     if (curr) return(curr);
169                 }
170             }
171             return(NULL);
172         }
173         Type operator ++() {
174             Type curr;
175
176             curr = *currList;
177             currList++;
178             return(curr);
179         }
180         int count()     {
181             int i, total;
182
183             total = 0;
184             for (i=0; i < tableSize; i++) {
185                 if (table[i]) {
186                     total += table[i]->count();
187                 }
188             }
189             return(total);
190         }
191     private:
192         List<Type> **table;
193         List<Type> currList;
194         int currHid;
195         int tableSize;
196 };
197
198 template <class Type> HTable<Type>::HTable()
199
200     table = NULL;
201     currHid = 0;
202     tableSize = 0;
203 }
204
205 template <class Type> Type HTable<Type>::find(void *key)
206 {
207     int hid;
208
209     if (!tableSize) return(NULL);
210     hid = ListHash(key, tableSize);
211     if (!table[hid]) {
212         return(NULL);
213     } else {
214         return(table[hid]->find(key));
215     }
216 }
217
218 template <class Type> void HTable<Type>::add(Type data, void *key)
219 {
220     int hid;
221
222     if (!tableSize) {
223         tableSize = 97;
224         table = (List<Type>**) calloc(tableSize, sizeof(List<Type>*));
225     }
226     hid = ListHash(key, tableSize);
227     if (!table[hid]) {
228         table[hid] = new(List<Type>);
229     }
230     table[hid]->add(data, key);
231 }
232 #endif LIST_H