1 /* |
|
2 * Copyright (c) 2003 - 2004 Nokia Corporation and/or its subsidiary(-ies). |
|
3 * All rights reserved. |
|
4 * This component and the accompanying materials are made available |
|
5 * under the terms of the License "Eclipse Public License v1.0" |
|
6 * which accompanies this distribution, and is available |
|
7 * at the URL "http://www.eclipse.org/legal/epl-v10.html". |
|
8 * |
|
9 * Initial Contributors: |
|
10 * Nokia Corporation - initial contribution. |
|
11 * |
|
12 * Contributors: |
|
13 * |
|
14 * Description: |
|
15 * |
|
16 */ |
|
17 |
|
18 |
|
19 #include <xml/cxml/nw_tinytree.h> |
|
20 #include "cxml_internal.h" |
|
21 |
|
22 /* ------------------------------------------------------------------------- */ |
|
23 |
|
24 /* ------------------------------------------------------------------------- */ |
|
25 static |
|
26 CXML_Uint8* |
|
27 CXML_Vector_AllocateSegment (CXML_Vector_t* thisObj, NW_TinyTree_TreeNode_t* sentinel) |
|
28 { |
|
29 CXML_Uint8* buffer = NULL; |
|
30 if(sentinel) |
|
31 { |
|
32 buffer = (NW_Uint8*) NW_Mem_Malloc ((thisObj->segmentSize + 1) * thisObj->elementSize); |
|
33 if(buffer) |
|
34 { |
|
35 NW_Mem_memcpy(buffer, sentinel, sizeof(NW_TinyTree_TreeNode_t)); |
|
36 buffer += thisObj->elementSize; |
|
37 } |
|
38 } |
|
39 else |
|
40 { |
|
41 buffer = (NW_Uint8*) NW_Mem_Malloc (thisObj->segmentSize * thisObj->elementSize); |
|
42 } |
|
43 return buffer; |
|
44 } |
|
45 |
|
46 /* ------------------------------------------------------------------------- */ |
|
47 static |
|
48 NW_Status_t |
|
49 CXML_Vector_ResizeCapacity (CXML_Vector_t* thisObj, |
|
50 CXML_Vector_Metric_t capacityNeeded, |
|
51 NW_TinyTree_TreeNode_t* sentinel) |
|
52 { |
|
53 CXML_Vector_Metric_t newNumSegments; |
|
54 CXML_Vector_Metric_t newSegmentListSize; |
|
55 NW_Uint8** newSegmentList; |
|
56 // CXML_Vector_Metric_t index; |
|
57 |
|
58 /* calculate the new segmentList size */ |
|
59 newNumSegments = |
|
60 (CXML_Vector_Metric_t) ((capacityNeeded - 1) / thisObj->segmentSize + 1); |
|
61 newSegmentListSize = (CXML_Vector_Metric_t) |
|
62 (((newNumSegments - 1) / CXML_SEGMENT_LIST_INCREMENT + 1) * CXML_SEGMENT_LIST_INCREMENT); |
|
63 |
|
64 /* if we are shrinking the array, we must first deallocate all the segments |
|
65 that will be obsolete */ |
|
66 while (thisObj->numSegments > newNumSegments) { |
|
67 NW_Mem_Free (thisObj->segmentList[--thisObj->numSegments]); |
|
68 } |
|
69 thisObj->capacity = |
|
70 (CXML_Vector_Metric_t) (thisObj->numSegments * thisObj->segmentSize); |
|
71 |
|
72 /* allocate the new segmentList and copy the old segmentList entries into the |
|
73 new */ |
|
74 newSegmentList = |
|
75 (NW_Uint8**) NW_Mem_Malloc (newSegmentListSize * sizeof (*newSegmentList)); |
|
76 if (newSegmentList == NULL) { |
|
77 return NW_STAT_OUT_OF_MEMORY; |
|
78 } |
|
79 (void) NW_Mem_memcpy (newSegmentList, thisObj->segmentList, |
|
80 thisObj->numSegments * sizeof (*newSegmentList)); |
|
81 |
|
82 /* free the old segmentList and install the new */ |
|
83 NW_Mem_Free (thisObj->segmentList); |
|
84 |
|
85 thisObj->segmentList = newSegmentList; |
|
86 thisObj->segmentListSize = newSegmentListSize; |
|
87 |
|
88 /* if we are growing the array we need to allocate the new segments */ |
|
89 while (thisObj->numSegments < newNumSegments) { |
|
90 thisObj->segmentList[thisObj->numSegments] = |
|
91 CXML_Vector_AllocateSegment(thisObj, sentinel); |
|
92 if (thisObj->segmentList[thisObj->numSegments++] == NULL) { |
|
93 thisObj->numSegments -= 1; |
|
94 return NW_STAT_OUT_OF_MEMORY; |
|
95 } |
|
96 } |
|
97 thisObj->capacity = |
|
98 (CXML_Vector_Metric_t) (thisObj->numSegments * thisObj->segmentSize); |
|
99 |
|
100 /* successful completion */ |
|
101 return NW_STAT_SUCCESS; |
|
102 } |
|
103 |
|
104 /* ------------------------------------------------------------------------- */ |
|
105 static |
|
106 NW_Status_t |
|
107 CXML_Vector_MoveElements (CXML_Vector_t* thisObj, |
|
108 CXML_Vector_Metric_t srcIndex, |
|
109 CXML_Vector_Metric_t dstIndex, |
|
110 NW_TinyTree_TreeNode_t* sentinel) |
|
111 { |
|
112 NW_Int32 sizeDelta; |
|
113 CXML_Vector_Metric_t numElements; |
|
114 NW_Int32 index; |
|
115 |
|
116 /* */ |
|
117 if (dstIndex > srcIndex) { |
|
118 sizeDelta = dstIndex - srcIndex; |
|
119 } else { |
|
120 sizeDelta = - (NW_Int32) (srcIndex - dstIndex); |
|
121 } |
|
122 |
|
123 if (thisObj->size + sizeDelta > thisObj->capacity) { |
|
124 NW_Status_t status; |
|
125 |
|
126 status = CXML_Vector_ResizeCapacity (thisObj, |
|
127 (CXML_Vector_Metric_t) (thisObj->size + sizeDelta), sentinel); |
|
128 if (status != NW_STAT_SUCCESS) { |
|
129 return status; |
|
130 } |
|
131 } |
|
132 |
|
133 /* now do the actual move */ |
|
134 /* TODO: this is a very inefficient way of moving the data, we will probably |
|
135 need to implement a block move capability */ |
|
136 numElements = (CXML_Vector_Metric_t) (thisObj->size - srcIndex); |
|
137 if (srcIndex > dstIndex) { |
|
138 for (index = 0; index < NW_INT32_CAST(numElements); index++) { |
|
139 (void) NW_Mem_memcpy (CXML_Vector_AddressAt (thisObj, |
|
140 (CXML_Vector_Metric_t) (dstIndex + index)), CXML_Vector_AddressAt (thisObj, |
|
141 (CXML_Vector_Metric_t) (srcIndex + index)), thisObj->elementSize); |
|
142 } |
|
143 } else { |
|
144 for (index = numElements - 1; index >= 0; index--) { |
|
145 (void) NW_Mem_memcpy (CXML_Vector_AddressAt (thisObj, |
|
146 (CXML_Vector_Metric_t) (dstIndex + index)), CXML_Vector_AddressAt (thisObj, |
|
147 (CXML_Vector_Metric_t) (srcIndex + index)), thisObj->elementSize); |
|
148 } |
|
149 } |
|
150 |
|
151 /* successful completion */ |
|
152 return NW_STAT_SUCCESS; |
|
153 } |
|
154 |
|
155 CXML_Vector_t* |
|
156 CXML_Vector_Construct(CXML_Vector_Metric_t elementSize, |
|
157 CXML_Vector_Metric_t segmentSize) |
|
158 { |
|
159 CXML_Vector_t* vector = (CXML_Vector_t*) NW_Mem_Malloc(sizeof(CXML_Vector_t)); |
|
160 |
|
161 if(vector) |
|
162 { |
|
163 vector->elementSize = elementSize; |
|
164 vector->capacity = 0; |
|
165 vector->size = 0; |
|
166 |
|
167 vector->segmentSize = segmentSize; |
|
168 vector->segmentListSize = CXML_SEGMENT_LIST_INCREMENT; |
|
169 |
|
170 //Allocate memory for one segment here. For more memory the |
|
171 //function CXML_Vector_ResizeCapacity() will do the job. |
|
172 |
|
173 vector->segmentList = (NW_Uint8**) |
|
174 NW_Mem_Malloc (vector->segmentListSize * sizeof (*vector->segmentList)); |
|
175 |
|
176 if (vector->segmentList == NULL) { |
|
177 NW_Mem_Free(vector); |
|
178 return NULL; |
|
179 } |
|
180 vector->numSegments = 0; |
|
181 } |
|
182 return vector; |
|
183 } |
|
184 |
|
185 void |
|
186 CXML_Vector_Destruct(CXML_Vector_t* vector) |
|
187 { |
|
188 CXML_Vector_Metric_t index; |
|
189 for (index = 0; index < vector->numSegments; index++) { |
|
190 NW_Mem_Free (vector->segmentList[index]); |
|
191 } |
|
192 NW_Mem_Free (vector->segmentList); |
|
193 NW_Mem_Free(vector); |
|
194 } |
|
195 |
|
196 void |
|
197 CXML_Vector_AdjustSegment(CXML_Vector_t* vector) |
|
198 { |
|
199 CXML_Vector_Metric_t index; |
|
200 |
|
201 /* |
|
202 * Walk through segment list adjusting pointers to the |
|
203 * sentinel element at the beginning of each segment |
|
204 */ |
|
205 |
|
206 for (index = 0; index < vector->numSegments; index++) { |
|
207 vector->segmentList[index] -= vector->elementSize; |
|
208 } |
|
209 } |
|
210 |
|
211 NW_Uint8* |
|
212 CXML_Vector_AddressAt (const CXML_Vector_t* thisObj, |
|
213 CXML_Vector_Metric_t index) |
|
214 { |
|
215 CXML_Vector_Metric_t segmentIndex; |
|
216 |
|
217 /* determine the segment index and return the offset into that segment */ |
|
218 segmentIndex = |
|
219 (CXML_Vector_Metric_t) (index / thisObj->segmentSize); |
|
220 return |
|
221 (NW_Uint8*) thisObj->segmentList[segmentIndex] |
|
222 + (index % thisObj->segmentSize) * thisObj->elementSize; |
|
223 } |
|
224 |
|
225 /* ------------------------------------------------------------------------- */ |
|
226 void** |
|
227 CXML_Vector_InsertAt (CXML_Vector_t* thisObj, |
|
228 void* element, |
|
229 CXML_Vector_Metric_t where, |
|
230 void* sentinel) |
|
231 { |
|
232 NW_Status_t status; |
|
233 |
|
234 /* convert the where if CXML_Vector_AtEnd is specified */ |
|
235 if (where == CXML_Vector_AtEnd) { |
|
236 where = thisObj->size; |
|
237 } |
|
238 |
|
239 /* make sure that the where element is not out of bounds */ |
|
240 NW_ASSERT (where <= thisObj->size); |
|
241 |
|
242 /* move all the elements up by one, if this fails we simply return |
|
243 the error code passed to us */ |
|
244 status = |
|
245 CXML_Vector_MoveElements (thisObj, where, |
|
246 (CXML_Vector_Metric_t) (where + 1), |
|
247 (NW_TinyTree_TreeNode_t*) sentinel); |
|
248 if (status != NW_STAT_SUCCESS) { |
|
249 return NULL; |
|
250 } |
|
251 |
|
252 /* copy the element into vector */ |
|
253 if (element != NULL) { |
|
254 (void) NW_Mem_memcpy (CXML_Vector_AddressAt (thisObj, where), |
|
255 element, thisObj->elementSize); |
|
256 } else { |
|
257 /* |
|
258 * if element is NULL, then we need to zero out the memory block. This is necessary |
|
259 * because later code which fills in the values for this newly allocated vector |
|
260 * element may leave some bytes in the memory block un-assigned due to padding. |
|
261 */ |
|
262 NW_Mem_memset ( CXML_Vector_AddressAt (thisObj, where), |
|
263 0, thisObj->elementSize); |
|
264 } |
|
265 |
|
266 /* increment the size count */ |
|
267 thisObj->size += 1; |
|
268 |
|
269 /* successful completion */ |
|
270 return (void**) |
|
271 CXML_Vector_AddressAt (thisObj, where); |
|
272 } |
|
273 |
|
274 /* ------------------------------------------------------------------------- */ |
|
275 NW_Status_t |
|
276 CXML_Vector_RemoveAt (CXML_Vector_t* thisObj, |
|
277 CXML_Vector_Metric_t index) |
|
278 { |
|
279 NW_Status_t status; |
|
280 |
|
281 /* convert the index if CXML_Vector_AtEnd is specified */ |
|
282 if (index == CXML_Vector_AtEnd) { |
|
283 index = (CXML_Vector_Metric_t) (thisObj->size - 1); |
|
284 } |
|
285 |
|
286 /* make sure that the index element is not out of bounds */ |
|
287 if (index >= thisObj->size) { |
|
288 return NW_STAT_FAILURE; |
|
289 } |
|
290 |
|
291 /* don't bother to move anything if the resultant size is zero */ |
|
292 if (thisObj->size > 1) { |
|
293 /* move all the elements down by one, if this fails we simply return |
|
294 the error code passed to us */ |
|
295 status = |
|
296 CXML_Vector_MoveElements (thisObj, (CXML_Vector_Metric_t) (index + 1), |
|
297 index, NULL); |
|
298 if (status != NW_STAT_SUCCESS) { |
|
299 return status; |
|
300 } |
|
301 } |
|
302 |
|
303 /* increment the size count */ |
|
304 thisObj->size -= 1; |
|
305 |
|
306 /* successful completion */ |
|
307 return NW_STAT_SUCCESS; |
|
308 } |
|
309 |
|
310 /* ------------------------------------------------------------------------- */ |
|
311 void** |
|
312 CXML_Vector_ElementAt (const CXML_Vector_t* vector, |
|
313 CXML_Vector_Metric_t index) |
|
314 { |
|
315 if (index >= vector->size) { |
|
316 return NULL; |
|
317 } |
|
318 return (void**) CXML_Vector_AddressAt (vector, index); |
|
319 } |
|
320 |
|
321 /* ------------------------------------------------------------------------- */ |
|
322 CXML_Vector_Metric_t |
|
323 CXML_Vector_GetElementIndex (const CXML_Vector_t* vector, |
|
324 void* target) |
|
325 { |
|
326 CXML_Vector_Metric_t index; |
|
327 |
|
328 for (index = 0; index < vector->size; index++) { |
|
329 void* element; |
|
330 |
|
331 /* get and compare the element */ |
|
332 element = CXML_Vector_ElementAt (vector, index); |
|
333 if (NW_Mem_memcmp (target, element, vector->elementSize) == 0) { |
|
334 return index; |
|
335 } |
|
336 } |
|
337 |
|
338 /* no match found, return CXML_Vector_AtEnd */ |
|
339 return CXML_Vector_AtEnd; |
|
340 } |
|
341 |
|