|
1 /* |
|
2 * Copyright (c) 2000 - 2001 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 #include "cxml_internal.h" |
|
19 #include <xml/cxml/nw_tinytree_ebuffer.h> |
|
20 |
|
21 /* ------------------------------------------------------------------------- * |
|
22 private methods |
|
23 * ------------------------------------------------------------------------- */ |
|
24 |
|
25 /* Get the index corresponding to the first element in a segment. |
|
26 * This can be added to an offset within the segment to get the |
|
27 * index of any element |
|
28 */ |
|
29 |
|
30 static |
|
31 CXML_Vector_Metric_t |
|
32 NW_TinyTree_EBuffer_GetFirstIndex(NW_TinyTree_EBuffer_t* ebuffer, |
|
33 CXML_Vector_Metric_t segNum) |
|
34 { |
|
35 CXML_Vector_Metric_t currentSegment; |
|
36 NW_TinyTree_Segment_t* segment; |
|
37 CXML_Vector_Metric_t firstIndex = 0; |
|
38 |
|
39 NW_ASSERT(segNum < ebuffer->numSegments); |
|
40 |
|
41 for (currentSegment = 0; currentSegment < segNum; currentSegment++){ |
|
42 segment = &(ebuffer->segmentList[currentSegment]); |
|
43 firstIndex = (CXML_Vector_Metric_t)(firstIndex + segment->segmentSize); |
|
44 } |
|
45 |
|
46 return firstIndex; |
|
47 } |
|
48 |
|
49 /* Find a free block of a given size. This duplicates a bit of code from |
|
50 * GetFirstIndex in order to avoid repeated iteration over the buffer list. |
|
51 */ |
|
52 |
|
53 static |
|
54 NW_Uint8* |
|
55 NW_TinyTree_EBuffer_FindFreeBlock(NW_TinyTree_EBuffer_t* ebuffer, |
|
56 CXML_Vector_Metric_t size, |
|
57 CXML_Vector_Metric_t *index) /* OUT */ |
|
58 { |
|
59 CXML_Vector_Metric_t currentSegment; |
|
60 NW_TinyTree_Segment_t* segment; |
|
61 CXML_Vector_Metric_t firstIndex = 0; |
|
62 NW_Uint8* storage; |
|
63 |
|
64 *index = CXML_Vector_AtEnd; |
|
65 |
|
66 for (currentSegment = 0; currentSegment < ebuffer->numSegments; currentSegment++){ |
|
67 segment = &(ebuffer->segmentList[currentSegment]); |
|
68 |
|
69 if((segment->segmentSize - segment->freeOffset) >= size){ |
|
70 *index = (CXML_Vector_Metric_t)(firstIndex + segment->freeOffset); |
|
71 storage = segment->storage + segment->freeOffset; |
|
72 segment->freeOffset = (CXML_Vector_Metric_t)(segment->freeOffset + size); |
|
73 return storage; |
|
74 } |
|
75 firstIndex = (CXML_Vector_Metric_t)(firstIndex + segment->segmentSize); |
|
76 } |
|
77 return 0; |
|
78 } |
|
79 |
|
80 static |
|
81 NW_Status_t |
|
82 NW_TinyTree_EBuffer_GrowSegmentList(NW_TinyTree_EBuffer_t* ebuffer){ |
|
83 |
|
84 CXML_Vector_Metric_t newSegmentListSize; |
|
85 NW_TinyTree_Segment_t* newSegmentList; |
|
86 |
|
87 |
|
88 /* Since any new allocation is a continuous block contained in a |
|
89 * single segment, we grow the segment list by a constant amount |
|
90 */ |
|
91 |
|
92 newSegmentListSize = |
|
93 (NW_Uint8)(ebuffer->segmentListSize + CXML_SEGMENT_LIST_INCREMENT); |
|
94 |
|
95 /* if(newSegmentListSize == 0) then it means that there is overflow in the |
|
96 * newSegmentListSize so return with error here. |
|
97 */ |
|
98 |
|
99 if(newSegmentListSize == 0) |
|
100 { |
|
101 return NW_STAT_OUT_OF_MEMORY; |
|
102 } |
|
103 |
|
104 |
|
105 newSegmentList = |
|
106 (NW_TinyTree_Segment_t*) NW_Mem_Malloc (newSegmentListSize * sizeof (*newSegmentList)); |
|
107 |
|
108 if (newSegmentList == NULL) { |
|
109 return NW_STAT_OUT_OF_MEMORY; |
|
110 } |
|
111 |
|
112 /* Copy the old segment list */ |
|
113 |
|
114 (void) NW_Mem_memcpy (newSegmentList, ebuffer->segmentList, |
|
115 ebuffer->numSegments * sizeof (*newSegmentList)); |
|
116 |
|
117 /* Free the old segment list and install the new */ |
|
118 |
|
119 NW_Mem_Free (ebuffer->segmentList); |
|
120 ebuffer->segmentList = newSegmentList; |
|
121 ebuffer->segmentListSize = newSegmentListSize; |
|
122 return NW_STAT_SUCCESS; |
|
123 } |
|
124 |
|
125 |
|
126 /* |
|
127 * Allocate a new segment that holds a block of a given size. |
|
128 */ |
|
129 |
|
130 static |
|
131 NW_Uint8* |
|
132 NW_TinyTree_EBuffer_AllocSegment(NW_TinyTree_EBuffer_t* ebuffer, |
|
133 CXML_Vector_Metric_t size, |
|
134 CXML_Vector_Metric_t *index) /* OUT */ |
|
135 { |
|
136 NW_TinyTree_Segment_t* segment; |
|
137 |
|
138 *index = CXML_Vector_AtEnd; |
|
139 |
|
140 /* Make sure the segment list is big enough to hold the new segment */ |
|
141 |
|
142 if(ebuffer->numSegments == ebuffer->segmentListSize){ |
|
143 NW_TinyTree_EBuffer_GrowSegmentList(ebuffer); |
|
144 } |
|
145 |
|
146 /* The new segment is the first unused segment in the list */ |
|
147 segment = &(ebuffer->segmentList[ebuffer->numSegments]); |
|
148 |
|
149 /* Increment the segment count */ |
|
150 ebuffer->numSegments = (CXML_Vector_Metric_t)(ebuffer->numSegments + 1); |
|
151 |
|
152 /* Allocate segment storage with enough contiguous blocks to hold the requested size */ |
|
153 |
|
154 segment->segmentSize = |
|
155 (CXML_Vector_Metric_t)(((size - 1) / ebuffer->blockSize + 1) * ebuffer->blockSize); |
|
156 |
|
157 segment->storage = (NW_Uint8*)(NW_Mem_Malloc(segment->segmentSize)); |
|
158 |
|
159 if(segment->storage == 0){ |
|
160 segment->segmentSize = 0; |
|
161 return 0; |
|
162 } |
|
163 |
|
164 /* Free offset goes at end of allocated block */ |
|
165 segment->freeOffset = size; |
|
166 |
|
167 /* Get the first index of the newly allocated segment */ |
|
168 *index = NW_TinyTree_EBuffer_GetFirstIndex(ebuffer, (CXML_Vector_Metric_t)(ebuffer->numSegments - 1)); |
|
169 |
|
170 return segment->storage; |
|
171 } |
|
172 |
|
173 |
|
174 |
|
175 /* ------------------------------------------------------------------------- * |
|
176 virtual methods |
|
177 * ------------------------------------------------------------------------- */ |
|
178 |
|
179 /* ------------------------------------------------------------------------- */ |
|
180 NW_TinyTree_EBuffer_t* |
|
181 NW_TinyTree_EBuffer_Construct (NW_Uint8* initialBuffer, |
|
182 CXML_Vector_Metric_t initBuffSize, |
|
183 CXML_Vector_Metric_t blockSize, |
|
184 NW_Bool freeBuff) |
|
185 { |
|
186 NW_TinyTree_EBuffer_t* thisObj = (NW_TinyTree_EBuffer_t*) |
|
187 NW_Mem_Malloc(sizeof(NW_TinyTree_EBuffer_t)); |
|
188 |
|
189 if(thisObj) |
|
190 { |
|
191 /* initialize the object */ |
|
192 thisObj->blockSize = blockSize; |
|
193 thisObj->ownFirstBlock = freeBuff; |
|
194 thisObj->segmentListSize = CXML_SEGMENT_LIST_INCREMENT; |
|
195 NW_ASSERT(thisObj->segmentListSize > 0); |
|
196 thisObj->segmentList = (NW_TinyTree_Segment_t*) |
|
197 NW_Mem_Malloc (thisObj->segmentListSize * sizeof (*thisObj->segmentList)); |
|
198 if (thisObj->segmentList == NULL) |
|
199 { |
|
200 NW_Mem_Free(thisObj); |
|
201 return NULL; |
|
202 } |
|
203 if (initialBuffer != NULL) |
|
204 { |
|
205 NW_ASSERT(initBuffSize != 0); |
|
206 thisObj->segmentList[0].storage = initialBuffer; |
|
207 thisObj->segmentList[0].segmentSize = initBuffSize; |
|
208 thisObj->segmentList[0].freeOffset = initBuffSize; |
|
209 thisObj->numSegments = 1; |
|
210 } |
|
211 else |
|
212 { |
|
213 /* If there's no first block, then we ignore the free flag passed in |
|
214 * since we will be allocating the first block and thus must free it |
|
215 */ |
|
216 thisObj->ownFirstBlock = NW_TRUE; |
|
217 thisObj->numSegments = 0; |
|
218 } |
|
219 } |
|
220 return thisObj; |
|
221 } |
|
222 |
|
223 /* ------------------------------------------------------------------------- */ |
|
224 void |
|
225 NW_TinyTree_EBuffer_Destruct (NW_TinyTree_EBuffer_t* thisObj) |
|
226 { |
|
227 CXML_Vector_Metric_t index; |
|
228 |
|
229 /* release our resources */ |
|
230 for (index = 0; index < thisObj->numSegments; index++) { |
|
231 if((index == 0) && (thisObj->ownFirstBlock == NW_FALSE)){ |
|
232 continue; |
|
233 } |
|
234 NW_Mem_Free (thisObj->segmentList[index].storage); |
|
235 } |
|
236 NW_Mem_Free (thisObj->segmentList); |
|
237 NW_Mem_Free (thisObj); |
|
238 } |
|
239 |
|
240 |
|
241 /* ------------------------------------------------------------------------- * |
|
242 final methods |
|
243 * ------------------------------------------------------------------------- */ |
|
244 |
|
245 |
|
246 /* Get an unused block of a given size. Returns the address of the |
|
247 * block. Also returns an index (via the index OUT parameter) that can |
|
248 * be used for later lookups of the block. |
|
249 */ |
|
250 |
|
251 NW_Uint8* |
|
252 NW_TinyTree_EBuffer_GetWritableBlock(NW_TinyTree_EBuffer_t* ebuffer, |
|
253 CXML_Vector_Metric_t size, |
|
254 CXML_Vector_Metric_t *index) /* OUT */ |
|
255 { |
|
256 NW_Uint8* storage; |
|
257 |
|
258 NW_ASSERT(ebuffer != NULL); |
|
259 |
|
260 /* First try to get an existing free block that's big enough */ |
|
261 |
|
262 storage = NW_TinyTree_EBuffer_FindFreeBlock(ebuffer, size, index); |
|
263 if(storage != 0){ |
|
264 return storage; |
|
265 } |
|
266 |
|
267 /* Otherwise, allocate a new segment that holds a block of the right size */ |
|
268 |
|
269 return NW_TinyTree_EBuffer_AllocSegment(ebuffer, size, index); |
|
270 } |
|
271 |
|
272 |
|
273 /* Get a segment address and an offset corresponding to a given |
|
274 * index. Also returns the segment size. |
|
275 */ |
|
276 |
|
277 NW_Status_t |
|
278 NW_TinyTree_EBuffer_GetSegmentAndOffset(NW_TinyTree_EBuffer_t* ebuffer, |
|
279 CXML_Vector_Metric_t index, |
|
280 NW_Uint8 ** segmentAddr, /* OUT */ |
|
281 CXML_Vector_Metric_t* segSize, /* OUT */ |
|
282 CXML_Vector_Metric_t* offset){ /* OUT */ |
|
283 |
|
284 CXML_Vector_Metric_t currentSegment; |
|
285 NW_TinyTree_Segment_t* segment; |
|
286 CXML_Vector_Metric_t firstIndex = 0; |
|
287 |
|
288 NW_ASSERT(ebuffer != NULL); |
|
289 NW_ASSERT(segmentAddr != NULL); |
|
290 NW_ASSERT(segSize != NULL); |
|
291 NW_ASSERT(offset != NULL); |
|
292 |
|
293 for (currentSegment = 0; currentSegment < ebuffer->numSegments; currentSegment++){ |
|
294 segment = &(ebuffer->segmentList[currentSegment]); |
|
295 if(index < (firstIndex + segment->segmentSize)){ |
|
296 *segmentAddr = segment->storage; |
|
297 *segSize = segment->segmentSize; |
|
298 *offset = (CXML_Vector_Metric_t)(index - firstIndex); |
|
299 return NW_STAT_SUCCESS; |
|
300 } |
|
301 firstIndex = (CXML_Vector_Metric_t)(firstIndex + segment->segmentSize); |
|
302 } |
|
303 |
|
304 return NW_STAT_FAILURE; |
|
305 } |
|
306 |
|
307 /* Get an index from a segment and offset */ |
|
308 |
|
309 NW_Status_t |
|
310 NW_TinyTree_EBuffer_GetIndex(NW_TinyTree_EBuffer_t* ebuffer, |
|
311 NW_Uint8* segmentAddr, |
|
312 CXML_Vector_Metric_t offset, |
|
313 CXML_Vector_Metric_t* index) /* OUT */ |
|
314 |
|
315 { |
|
316 |
|
317 CXML_Vector_Metric_t currentSegment; |
|
318 NW_TinyTree_Segment_t* segment; |
|
319 CXML_Vector_Metric_t firstIndex = 0; |
|
320 |
|
321 NW_ASSERT(ebuffer != NULL); |
|
322 |
|
323 for (currentSegment = 0; currentSegment < ebuffer->numSegments; currentSegment++){ |
|
324 segment = &(ebuffer->segmentList[currentSegment]); |
|
325 if(segmentAddr == segment->storage){ |
|
326 *index = (CXML_Vector_Metric_t)(firstIndex + offset); |
|
327 return NW_STAT_SUCCESS; |
|
328 } |
|
329 firstIndex = (CXML_Vector_Metric_t)(firstIndex + segment->segmentSize); |
|
330 } |
|
331 |
|
332 return NW_STAT_FAILURE; |
|
333 } |
|
334 |
|
335 |
|
336 /* Get the address corresponding to a given index */ |
|
337 |
|
338 NW_Uint8* |
|
339 NW_TinyTree_EBuffer_AddressAt(NW_TinyTree_EBuffer_t* ebuffer, |
|
340 CXML_Vector_Metric_t index){ |
|
341 |
|
342 NW_Uint8* segmentAddr; |
|
343 CXML_Vector_Metric_t segSize; |
|
344 CXML_Vector_Metric_t offset; |
|
345 NW_Status_t status; |
|
346 |
|
347 NW_ASSERT(ebuffer != NULL); |
|
348 |
|
349 status = NW_TinyTree_EBuffer_GetSegmentAndOffset(ebuffer, index, &segmentAddr, &segSize, &offset); |
|
350 if(status == NW_STAT_SUCCESS){ |
|
351 return segmentAddr + offset; |
|
352 } |
|
353 return 0; |
|
354 |
|
355 } |