--- 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 <xml/cxml/nw_tinytree.h>
-#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 <limits.h>
-#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;
-}
-
-
-
-
-
-
-
-
-
-
-