diff -r 889504eac4fb -r 604ca70b6235 xml/cxmllibrary/src/tinytree/src/tree_alloc.c --- a/xml/cxmllibrary/src/tinytree/src/tree_alloc.c Tue Aug 31 17:02:56 2010 +0300 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,291 +0,0 @@ -/* -* Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies). -* All rights reserved. -* This component and the accompanying materials are made available -* under the terms of the License "Eclipse Public License v1.0" -* which accompanies this distribution, and is available -* at the URL "http://www.eclipse.org/legal/epl-v10.html". -* -* Initial Contributors: -* Nokia Corporation - initial contribution. -* -* Contributors: -* -* Description: -* -*/ -#include "cxml_internal.h" -#include -#include "nw_tinytree_alloc.h" - -/* -* This is not a generalized allocator. It is intended to support -* dynamic extension of the node array or storage buffers associated -* with a tiny tree. The goal of the design is to provide a kind of -* virtual array whose storage can be allocated in several -* non-contiguous segments located anywhere in memory. Since there -* will be gaps between segments and segments may be allocated in -* out-of-order locations (for example a second segment may be -* allocated at an address lower than the first segment) simple -* pointer arithmetic and array indexing cannot be used to address -* array elements. However, rather than trying to provide a totally -* general non-contiguous array package here, certain limitations have -* been imposed. These simplify the implementation but mean that this -* module can only be used with certain constraints. These constraints -* are not currently a problem for the tiny dom parser, but any change -* in the way the parser uses this module must be done with extreme -* care. Eventually, we may want to generalize this package if this -* can be done without adding too much to the footprint of computing -* burden. -* -* The main constraint is that any code which writes to or reads from -* a dynamically extended array must be sure that operations involving -* ordinary pointer arithmetic and array indexing always occur within -* the boudaries of a single segment. Operations that may result in -* crossing a segment boundary must use the supplied address and -* offset increment methods (which can be thought of as operator -* overloads for the += operator). Furthermore, it needs to be -* understood that any increment which results in crossing a segment -* boundary may result in the allocation of a new segment if the -* resulting address is not within an existing segment. When an -* address or offset is incremented to a new segment the result will -* be adjusted to the new segment and may have an unexpected value -* (for example, incrementing address x by a positive increment may -* result in an address that is less than x.). One important rule is -* that the result of incrementing x by some value i is not guaranteed -* to be idempotent if the increment crosses a segment boundary: i.e -* addressIncrement(x,i) == addressIncrement(x,i) is not guaranteed to -* be true. Future references to an address that results from an -* increment operations must always use the result of the -* operation. So, for example, (j = addressIncrement(x,i)) == -* addressIncrement(x,x+j) is guaranteed to be true. -* -* Segment storage addresses are always padded to align with the size -* of the data object to be stored. This means that segments allocated -* for a specific object type must be treated as as arrays of that -* object type (or as arrays of bytes). -* -* The parser code always uses this module according to these rules. -* Specifically, no tree node crosses a segment boundary and no -* parsable fragment of wbxml (a fragment which the parser can -* complete) every crosses a segment boundary. This latter condition -* allows the parser to treat its current buffer as a simple array of -* bytes. Another rule is that all of the offsets stored in tree -* nodes are guaranteed to address an allocated segment. For example, -* when writing a node, the storage offset is incremented using the -* offset increment * operation. The resulting offsets (stored in -* nodes) can then be safely used to address the written-to storage. -* -*/ - -/* -* Allocate segments for buffer and node array storage. The base -* segment address is the one from which all relative offsets are -* calculated. Segments are probably not contiguous, and, given that -* new segments might be allocated anywhere relative to existing -* segments, the offset must be a relative one. This limits the -* maximum relative offset to the beginning of a new segment to be a -* signed integer of the offset type. -*/ - -#include -#define MAX_REL_OFFSET INT_MAX - -static -NW_TinyTree_SegHeader_t* -NW_TinyTree_findLastSegment(NW_TinyTree_SegHeader_t *base){ - NW_TinyTree_SegHeader_t *last_seg = base; - while(last_seg->next != 0) - { - last_seg = (NW_TinyTree_SegHeader_t*)((NW_Byte*)base + last_seg->next); - } - return last_seg; -} - - -NW_TinyTree_Offset_t -NW_TinyTree_segmentGetFreeSpace(NW_TinyTree_SegHeader_t *segment){ - return (NW_TinyTree_Offset_t)(segment->size-segment->free_offset); -} - - -NW_TinyTree_Offset_t -NW_TinyTree_getFreeStorageSpace(NW_TinyTree_SegHeader_t *base){ - NW_TinyTree_SegHeader_t *last_seg = NW_TinyTree_findLastSegment(base); - return NW_TinyTree_segmentGetFreeSpace(last_seg); -} - -NW_TinyTree_SegHeader_t* -NW_TinyTree_addSegment(NW_TinyTree_SegHeader_t *base, - NW_TinyTree_Offset_t size){ - NW_TinyTree_SegHeader_t *new_seg; - NW_TinyTree_SegHeader_t *last_seg = NW_TinyTree_findLastSegment(base); - NW_Int32 offset; - - /* The extra node is added to make sure we have space to pad the segment storage to an even node boundary */ - NW_Uint32 alloc_size = size + sizeof(NW_TinyTree_SegHeader_t) + sizeof(NW_TinyTree_Node_t); - new_seg = (NW_TinyTree_SegHeader_t*)NW_Mem_Malloc(alloc_size); - - if(new_seg != 0){ - offset = (NW_Byte*)new_seg - (NW_Byte*)base; - if(abs(offset) > MAX_REL_OFFSET){ - NW_Mem_Free(new_seg); - return 0; - } - NW_Mem_memset(new_seg, 0, alloc_size); - /* Shift the storage pointer to an even boundary of a node so we can use this as an array of nodes */ - new_seg->initializer = base->initializer; - last_seg->next = (NW_TinyTree_RelativeOffset_t)offset; - new_seg->size = size; - new_seg->free_offset = 0; - new_seg->storage = (NW_Uint8*) - (((((NW_Uint32) new_seg) + sizeof(NW_TinyTree_SegHeader_t) - 1) - / sizeof (NW_TinyTree_Node_t) + 1) - * sizeof (NW_TinyTree_Node_t)); - if(new_seg->initializer) - (*(new_seg->initializer))(new_seg->storage, size); - } - return new_seg; -} - -/* -* Free segments allocated by addSegment only. -*/ - -void -NW_TinyTree_freeSegments(NW_TinyTree_SegHeader_t *base){ - NW_TinyTree_SegHeader_t *lastSegment = NULL; - NW_TinyTree_SegHeader_t *current = base; - NW_TinyTree_SegHeader_t *previous = NULL; - - NW_Uint16 totalAdditionalSegments = 0; - NW_Uint16 index = 0; - NW_Uint16 i = 0; - - while (current->next != 0) - { - totalAdditionalSegments++; - current = (NW_TinyTree_SegHeader_t*)((NW_Byte*)base + current->next); - } - lastSegment = current; - - while(index< totalAdditionalSegments) - { - current = base; - i = 0; - while (i < (totalAdditionalSegments - index)) - { - previous = current; - current = (NW_TinyTree_SegHeader_t*)((NW_Byte*)base + current->next); - i++; - } - NW_Mem_Free(lastSegment); - lastSegment = previous; - index++; - } - -} - - -/* -* Get the segment header associated with an offset. This allocates a new -* segment if the offset is beyond any currently allocated segment. If a new -* segment is allocated, the offset is readjusted to the beginning of the new -* segment. -*/ - -NW_TinyTree_SegHeader_t* -NW_TinyTree_addressGetSegment(NW_TinyTree_SegHeader_t *base, - NW_Byte **address){ - - NW_TinyTree_SegHeader_t *segment = base; - while(segment != 0){ - if ((*address > segment->storage) && (*address < (segment->storage + segment->size))) - return segment; - if (segment->next == 0){ /* Add new segment */ - segment = NW_TinyTree_addSegment(base, segment->size); /* Same size as last segment */ - if(segment == 0){ - break; - } - /* - * Reset address to beginning of new segment storage. - */ - *address = segment->storage; - return segment; - } - segment = (NW_TinyTree_SegHeader_t*)((NW_Byte*)base + segment->next); - } - return 0; -} - - -NW_Byte* -NW_TinyTree_addressIncrement(NW_TinyTree_SegHeader_t *base, - NW_Byte *address, - NW_TinyTree_Offset_t delta){ - NW_Byte* new_address = address + delta; - NW_TinyTree_SegHeader_t *segment = NW_TinyTree_addressGetSegment(base, &new_address); - if(new_address >= (segment->storage + segment->free_offset)) /* Haven't touched this memory before */ - { - segment->free_offset = (NW_TinyTree_Offset_t)(new_address - segment->storage); - } - return new_address; -} - -/* -* Get the segment header associated with an offset. This allocates a new -* segment if the offset is beyond any currently allocated segment. If a new -* segment is allocated, the offset is readjusted to the beginning of the new -* segment. -*/ - -NW_TinyTree_SegHeader_t* -NW_TinyTree_offsetGetSegment(NW_TinyTree_SegHeader_t *base, - NW_TinyTree_Offset_t *offset){ - - NW_TinyTree_SegHeader_t *segment = base; - while(segment != 0){ - if (((base->storage + *offset) > segment->storage) && ((base->storage + *offset) < (segment->storage + segment->size))) - return segment; - if (segment->next == 0){ /* Add new segment */ - if (segment->size > MIN_SEGMENT_SIZE) - segment = NW_TinyTree_addSegment(base, segment->size); /* Same size as last segment */ - else - segment = NW_TinyTree_addSegment(base, MIN_SEGMENT_SIZE); - if(segment == 0){ - break; - } - /* - * Reset offset to beginning of new segment storage. - */ - *offset = (NW_TinyTree_Offset_t)(segment->storage - base->storage); - return segment; - } - segment = (NW_TinyTree_SegHeader_t*)((NW_Byte*)base + segment->next); - } - return 0; -} - -NW_TinyTree_Offset_t -NW_TinyTree_offsetIncrement(NW_TinyTree_SegHeader_t *base, - NW_TinyTree_Offset_t offset, - NW_TinyTree_Offset_t delta){ - NW_TinyTree_Offset_t new_offset = (NW_TinyTree_Offset_t)(offset + delta); - NW_TinyTree_SegHeader_t *segment = NW_TinyTree_offsetGetSegment(base, &new_offset); - if(base->storage + new_offset >= (segment->storage + segment->free_offset)) /* Haven't touched this memory before */ - { - segment->free_offset = (NW_TinyTree_Offset_t)(base->storage + new_offset - segment->storage); - } - return new_offset; -} - - - - - - - - - - -