/*
* 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 "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;
}











