Branch data Line data Source code
1 : : //- Class: ArrayBasedContainer
2 : : //- Owner: Paul Kinney
3 : : //- Checked by:
4 : : //- Version: $Id:
5 : :
6 : : #include "ArrayBasedContainer.hpp"
7 : : #include "CubitDefines.h"
8 : : #include <cstring>
9 : : #include <cassert>
10 : :
11 : : unsigned int ArrayBasedContainer::currentAllocatedMemory = 0;
12 : : unsigned int ArrayBasedContainer::maxAllocatedMemory = 0;
13 : :
14 : : //- Constructor: Create a list with initial size {increment}. The list
15 : : //- will be grown by {increment} each time it is filled. Memory for the
16 : : //- list is not allocated until the first element is inserted using
17 : : //- {insertLink}.
18 : : //- If {increment} is zero, the default increment ({INCREMENT}) will be used
19 : : //- From an efficiency standpoint, it is very important that the
20 : : //- increment be set large enough to reduce the number of list
21 : : //- growths, but small enough to not waste memory.
22 : : //- It is more efficient to sligthly overestimate the increment than
23 : : //- to underestimate the increment.
24 : 294 : ArrayBasedContainer::ArrayBasedContainer ( int increment )
25 : : {
26 [ - + ]: 294 : if ( increment > 0)
27 : : {
28 : 0 : listIncrement = increment;
29 : : }
30 : : else
31 : : {
32 : 294 : listIncrement = INCREMENT;
33 : : }
34 : 294 : itemCount = 0;
35 : 294 : listLength = 0;
36 : 294 : listArray = 0;
37 : 294 : poolAllocated = CUBIT_FALSE;
38 : 294 : listIsSorted = CUBIT_FALSE;
39 : 294 : }
40 : :
41 : : //- Copy Constructor
42 : : //- Uses memory from ArrayMemory if size is default
43 : 0 : ArrayBasedContainer::ArrayBasedContainer(const ArrayBasedContainer& from)
44 : : {
45 : 0 : listLength = from.listLength;
46 : 0 : listIncrement = from.listIncrement;
47 : 0 : poolAllocated = from.poolAllocated;
48 : 0 : listIsSorted = from.listIsSorted;
49 : 0 : listArray = NULL;
50 : :
51 [ # # ]: 0 : if (listLength)
52 : : {
53 [ # # ][ # # ]: 0 : if (listLength == INCREMENT && (int)listIncrement == INCREMENT) {
54 [ # # ]: 0 : listArray = (void **)new ArrayMemory;
55 : 0 : poolAllocated = CUBIT_TRUE;
56 : : }
57 : : else {
58 [ # # ]: 0 : listArray = new void* [listLength];
59 : 0 : poolAllocated = CUBIT_FALSE;
60 : 0 : currentAllocatedMemory += listLength;
61 [ # # ]: 0 : if (currentAllocatedMemory > maxAllocatedMemory)
62 : 0 : maxAllocatedMemory = currentAllocatedMemory;
63 : : }
64 [ # # ]: 0 : assert(listArray != 0);
65 : : }
66 : :
67 : 0 : itemCount = from.itemCount;
68 : :
69 [ # # ]: 0 : if (itemCount)
70 : 0 : memcpy (listArray, from.listArray, itemCount*sizeof(void*));
71 : 0 : }
72 : :
73 : 294 : ArrayBasedContainer::~ArrayBasedContainer()
74 : : {
75 [ + + ]: 294 : if ( listLength )
76 : : {
77 [ + + ]: 96 : if (poolAllocated) {
78 : 76 : delete ((ArrayMemory*) listArray);
79 : : }
80 : : else {
81 [ + - ]: 20 : delete [] listArray;
82 : 20 : currentAllocatedMemory -= listLength;
83 : : }
84 : 96 : listArray = NULL;
85 : : }
86 [ - + ]: 294 : }
87 : :
88 : :
89 : 126 : void ArrayBasedContainer::lengthen_list()
90 : : {
91 : 126 : void **tempArray = 0;
92 [ + + ][ + - ]: 126 : if (listLength == 0 && (int)listIncrement == INCREMENT)
93 : : {
94 : 96 : poolAllocated = CUBIT_TRUE;
95 [ + - ]: 96 : listArray = (void **)new ArrayMemory;
96 [ - + ]: 96 : assert(listArray != 0);
97 : 96 : listLength = listIncrement;
98 : 126 : return;
99 : : }
100 : :
101 : : // Normal allocation from here to end.
102 : :
103 [ + - ]: 30 : tempArray = new void* [listLength + listIncrement];
104 : 30 : currentAllocatedMemory += (listLength + listIncrement);
105 [ + + ]: 30 : if (currentAllocatedMemory > maxAllocatedMemory)
106 : 20 : maxAllocatedMemory = currentAllocatedMemory;
107 [ - + ]: 30 : assert(tempArray != 0);
108 : :
109 : : // copy the old stuff into the new array
110 [ + - ]: 30 : if (listLength)
111 : : {
112 : 30 : memcpy ( tempArray, listArray, listLength*sizeof(void*) );
113 : : // delete the old array
114 [ + + ]: 30 : if (poolAllocated)
115 : : {
116 : 20 : delete ((ArrayMemory*) listArray);
117 : : }
118 : : else {
119 [ + - ]: 10 : delete [] listArray;
120 : 30 : currentAllocatedMemory -= listLength;
121 : : }
122 : : }
123 : :
124 : : // set the new equal to the old
125 : 30 : listArray = tempArray;
126 : :
127 : : // update data
128 : 30 : poolAllocated = CUBIT_FALSE;
129 : 30 : listLength += listIncrement;
130 : 30 : listIncrement *= 2;
131 [ + - ]: 30 : listIncrement = listIncrement > 1000000 ? 1000000 : listIncrement;
132 : : }
133 : :
134 : : ArrayBasedContainer&
135 : 0 : ArrayBasedContainer::operator=(const ArrayBasedContainer& from)
136 : : {
137 [ # # ]: 0 : if (this == &from)
138 : 0 : return *this;
139 : :
140 : : // See if the existing listArray length is equal to the from listArray
141 : : // length. If it is, we can reuse it without deleting and newing.
142 [ # # ]: 0 : if (listLength != from.listLength) {
143 [ # # ]: 0 : if (listLength) {
144 [ # # ]: 0 : if (poolAllocated) {
145 : 0 : delete ((ArrayMemory*) listArray);
146 : : } else {
147 [ # # ]: 0 : delete [] listArray;
148 : 0 : currentAllocatedMemory -= listLength;
149 : : }
150 : : }
151 : :
152 : 0 : listLength = from.listLength;
153 [ # # ]: 0 : if (listLength)
154 : : {
155 [ # # ][ # # ]: 0 : if (listLength == INCREMENT && (int)listIncrement == INCREMENT)
156 : : {
157 [ # # ]: 0 : listArray = (void **)new ArrayMemory;
158 : 0 : poolAllocated = CUBIT_TRUE;
159 : : }
160 : : else
161 : : {
162 [ # # ]: 0 : listArray = new void* [listLength];
163 : 0 : poolAllocated = CUBIT_FALSE;
164 : 0 : currentAllocatedMemory += listLength;
165 [ # # ]: 0 : if (currentAllocatedMemory > maxAllocatedMemory)
166 : 0 : maxAllocatedMemory = currentAllocatedMemory;
167 : : }
168 [ # # ]: 0 : assert(listArray != 0);
169 : : }
170 : : }
171 : 0 : itemCount = from.itemCount;
172 : 0 : listIncrement = from.listIncrement;
173 : 0 : listIsSorted = from.listIsSorted;
174 : :
175 [ # # ]: 0 : if (itemCount)
176 : 0 : memcpy (listArray, from.listArray, itemCount*sizeof(void*));
177 : :
178 : 0 : return *this;
179 : : }
180 : :
181 : : ArrayBasedContainer&
182 : 0 : ArrayBasedContainer::operator+=(const ArrayBasedContainer& from)
183 : : {
184 : 0 : int tmp_itemCount = itemCount + from.itemCount;
185 [ # # ]: 0 : if (tmp_itemCount >= listLength)
186 : : {
187 [ # # ]: 0 : if ((listLength + (int)listIncrement) < tmp_itemCount)
188 : : {
189 : 0 : listIncrement = tmp_itemCount - listLength;
190 : : }
191 : 0 : lengthen_list();
192 : : }
193 [ # # ]: 0 : if (from.itemCount == 1)
194 : : {
195 : 0 : listArray[itemCount] = from.listArray[0];
196 : : }
197 : : else
198 : : {
199 [ # # ]: 0 : if (from.itemCount)
200 : 0 : memcpy (&listArray[itemCount], from.listArray,
201 : 0 : from.itemCount*sizeof(void*));
202 : : }
203 : 0 : itemCount += from.itemCount;
204 [ # # ][ # # ]: 0 : listIsSorted = listIsSorted && from.listIsSorted;
205 : 0 : return *this;
206 : : }
207 : :
208 : : ArrayBasedContainer&
209 : 0 : ArrayBasedContainer::operator-=(const ArrayBasedContainer& from)
210 : : {
211 [ # # ]: 0 : if ( !itemCount )
212 : 0 : return *this;
213 : : int i, j;
214 : : void *item;
215 [ # # ]: 0 : for ( i = 0; i < itemCount; i++ )
216 : : {
217 : 0 : item = listArray[i];
218 [ # # ]: 0 : for ( j = from.itemCount; j--; )
219 [ # # ]: 0 : if ( from.listArray[j] == item )
220 : : {
221 : 0 : listArray[i] = NULL;
222 : 0 : break;
223 : : }
224 : : }
225 : : // compress, virtual
226 : 0 : compress();
227 : 0 : return *this;
228 : : }
229 : :
230 : 0 : void ArrayBasedContainer::compress()
231 : : {
232 : : int i, j;
233 : : void *item;
234 [ # # ]: 0 : for ( i = j = 0; i < itemCount; i++ )
235 [ # # ]: 0 : if ((item = listArray[i]) != NULL) // = is ok
236 : 0 : listArray[j++] = item;
237 : 0 : }
238 : :
239 : 0 : unsigned int ArrayBasedContainer::current_allocated_memory()
240 : : {
241 : 0 : return currentAllocatedMemory;
242 : : }
243 : :
244 : 0 : unsigned int ArrayBasedContainer::maximum_allocated_memory()
245 : : {
246 : 0 : return maxAllocatedMemory;
247 : : }
248 : :
|
