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 }