Branch data Line data Source code
1 : : // $Id: List.cc 1905 2005-12-14 03:27:33Z vern $
2 : :
3 : : #include "config.h"
4 : :
5 : : #include <stdio.h>
6 : : #include <stdlib.h>
7 : :
8 : : #include "List.h"
9 : : #include "util.h"
10 : :
11 : : static const int DEFAULT_CHUNK_SIZE = 10;
12 : :
13 : 730827 : BaseList::BaseList(int size)
14 : : {
15 : 730827 : chunk_size = DEFAULT_CHUNK_SIZE;
16 : :
17 [ # # ][ - + ]: 730827 : if ( size < 0 )
18 : : {
19 : 0 : num_entries = max_entries = 0;
20 : 0 : entry = 0;
21 : : }
22 : : else
23 : : {
24 [ # # ][ + + ]: 730827 : if ( size > 0 )
25 : 245830 : chunk_size = size;
26 : :
27 : 730827 : num_entries = 0;
28 : 730827 : entry = (ent *) safe_malloc(chunk_size * sizeof(ent));
29 : 730827 : max_entries = chunk_size;
30 : : }
31 : 730827 : }
32 : :
33 : :
34 : 0 : BaseList::BaseList(BaseList& b)
35 : : {
36 : 0 : max_entries = b.max_entries;
37 : 0 : chunk_size = b.chunk_size;
38 : 0 : num_entries = b.num_entries;
39 : :
40 [ # # ][ # # ]: 0 : if ( max_entries )
41 : 0 : entry = (ent *) safe_malloc(max_entries * sizeof(ent));
42 : : else
43 : 0 : entry = 0;
44 : :
45 [ # # ][ # # ]: 0 : for ( int i = 0; i < num_entries; ++i )
46 : 0 : entry[i] = b.entry[i];
47 : 0 : }
48 : :
49 : 787 : void BaseList::sort(list_cmp_func cmp_func)
50 : : {
51 : 787 : qsort(entry, num_entries, sizeof(ent), cmp_func);
52 : 787 : }
53 : :
54 : 0 : void BaseList::operator=(BaseList& b)
55 : : {
56 [ # # ]: 0 : if ( this == &b )
57 : 0 : return; // i.e., this already equals itself
58 : :
59 [ # # ]: 0 : if ( entry )
60 : 0 : free(entry);
61 : :
62 : 0 : max_entries = b.max_entries;
63 : 0 : chunk_size = b.chunk_size;
64 : 0 : num_entries = b.num_entries;
65 : :
66 [ # # ]: 0 : if ( max_entries )
67 : 0 : entry = (ent *) safe_malloc(max_entries * sizeof(ent));
68 : : else
69 : 0 : entry = 0;
70 : :
71 [ # # ]: 0 : for ( int i = 0; i < num_entries; ++i )
72 : 0 : entry[i] = b.entry[i];
73 : : }
74 : :
75 : 0 : void BaseList::insert(ent a)
76 : : {
77 [ # # ]: 0 : if ( num_entries == max_entries )
78 : : {
79 : 0 : resize(max_entries + chunk_size); // make more room
80 : 0 : chunk_size *= 2;
81 : : }
82 : :
83 [ # # ]: 0 : for ( int i = num_entries; i > 0; --i )
84 : 0 : entry[i] = entry[i-1]; // move all pointers up one
85 : :
86 : 0 : ++num_entries;
87 : 0 : entry[0] = a;
88 : 0 : }
89 : :
90 : : #include <stdio.h>
91 : :
92 : 35933 : void BaseList::sortedinsert(ent a, list_cmp_func cmp_func)
93 : : {
94 : : // We optimize for the case that the new element is
95 : : // larger than most of the current entries.
96 : :
97 : : // First append element.
98 [ + + ]: 35933 : if ( num_entries == max_entries )
99 : : {
100 : 1752 : resize(max_entries + chunk_size);
101 : 1752 : chunk_size *= 2;
102 : : }
103 : :
104 : 35933 : entry[num_entries++] = a;
105 : :
106 : : // Then move it to the correct place.
107 : : ent tmp;
108 [ + + ]: 85133 : for ( int i = num_entries - 1; i > 0; --i )
109 : : {
110 [ + + ]: 82094 : if ( cmp_func(entry[i],entry[i-1]) <= 0 )
111 : 32894 : break;
112 : :
113 : 49200 : tmp = entry[i];
114 : 49200 : entry[i] = entry[i-1];
115 : 49200 : entry[i-1] = tmp;
116 : : }
117 : 35933 : }
118 : :
119 : 47785 : ent BaseList::remove(ent a)
120 : : {
121 : : int i;
122 [ + + ][ + + ]: 71720 : for ( i = 0; i < num_entries && a != entry[i]; ++i )
123 : : ;
124 : :
125 : 47785 : return remove_nth(i);
126 : : }
127 : :
128 : 52588 : ent BaseList::remove_nth(int n)
129 : : {
130 [ + - ][ + + ]: 52588 : if ( n < 0 || n >= num_entries )
131 : 19860 : return 0;
132 : :
133 : 32728 : ent old_ent = entry[n];
134 : 32728 : --num_entries;
135 : :
136 [ + + ]: 41550 : for ( ; n < num_entries; ++n )
137 : 8822 : entry[n] = entry[n+1];
138 : :
139 : 32728 : entry[n] = 0; // for debugging
140 : 52588 : return old_ent;
141 : : }
142 : :
143 : 1316160 : void BaseList::append(ent a)
144 : : {
145 [ + + ]: 1316160 : if ( num_entries == max_entries )
146 : : {
147 : 2960 : resize(max_entries + chunk_size); // make more room
148 : 2960 : chunk_size *= 2;
149 : : }
150 : :
151 : 1316160 : entry[num_entries++] = a;
152 : 1316160 : }
153 : :
154 : : // Get and remove from the end of the list.
155 : 16 : ent BaseList::get()
156 : : {
157 [ - + ]: 16 : if ( num_entries == 0 )
158 : 0 : return 0;
159 : :
160 : 16 : return entry[--num_entries];
161 : : }
162 : :
163 : :
164 : 635520 : void BaseList::clear()
165 : : {
166 [ + + ]: 635520 : if ( entry )
167 : : {
168 : 626830 : free(entry);
169 : 626830 : entry = 0;
170 : : }
171 : :
172 : 635520 : num_entries = max_entries = 0;
173 : 635520 : chunk_size = DEFAULT_CHUNK_SIZE;
174 : 635520 : }
175 : :
176 : 228402 : ent BaseList::replace(int ent_index, ent new_ent)
177 : : {
178 [ - + ]: 228402 : if ( ent_index < 0 )
179 : 0 : return 0;
180 : :
181 : : ent old_ent;
182 : :
183 [ + + ]: 228402 : if ( ent_index > num_entries - 1 )
184 : : { // replacement beyond the end of the list
185 : 2 : resize(ent_index + 1);
186 : :
187 [ + + ]: 8 : for ( int i = num_entries; i < max_entries; ++i )
188 : 6 : entry[i] = 0;
189 : 2 : num_entries = max_entries;
190 : :
191 : 2 : old_ent = 0;
192 : : }
193 : : else
194 : 228400 : old_ent = entry[ent_index];
195 : :
196 : 228402 : entry[ent_index] = new_ent;
197 : :
198 : 228402 : return old_ent;
199 : : }
200 : :
201 : 7156 : int BaseList::resize(int new_size)
202 : : {
203 [ + + ]: 7156 : if ( new_size < num_entries )
204 : 2402 : new_size = num_entries; // do not lose any entries
205 : :
206 [ + + ]: 7156 : if ( new_size != max_entries )
207 : : {
208 : 7123 : entry = (ent*) safe_realloc((void*) entry, sizeof(ent) * new_size);
209 [ + - ]: 7123 : if ( entry )
210 : 7123 : max_entries = new_size;
211 : : else
212 : 0 : max_entries = 0;
213 : : }
214 : :
215 : 7156 : return max_entries;
216 : : }
217 : :
218 : 0 : ent BaseList::is_member(ent e) const
219 : : {
220 : : int i;
221 [ # # ][ # # ]: 0 : for ( i = 0; i < length() && e != entry[i]; ++i )
[ # # ]
222 : : ;
223 : :
224 [ # # ]: 0 : return (i == length()) ? 0 : e;
225 : : }
226 : :
227 : 0 : int BaseList::member_pos(ent e) const
228 : : {
229 : : int i;
230 [ # # ][ # # ]: 0 : for ( i = 0; i < length() && e != entry[i]; ++i )
[ # # ]
231 : : ;
232 : :
233 [ # # ]: 0 : return (i == length()) ? -1 : i;
234 : : }
|
