tpl_dynArray.H

/*
  This file is part of Aleph system

  Copyright (c) 2002, 2003, 2004, 2005, 2006
  UNIVERSITY LOS ANDES (ULA) Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA  

  - Center of Studies in Microelectronics & Distributed Systems (CEMISID) 
  - ULA Computer Science Department
  - FUNDACITE Mérida - Ministerio de Ciencia y Tecnología

  PERMISSION TO USE, COPY, MODIFY AND DISTRIBUTE THIS SOFTWARE AND ITS
  DOCUMENTATION IS HEREBY GRANTED, PROVIDED THAT BOTH THE COPYRIGHT
  NOTICE AND THIS PERMISSION NOTICE APPEAR IN ALL COPIES OF THE
  SOFTWARE, DERIVATIVE WORKS OR MODIFIED VERSIONS, AND ANY PORTIONS
  THEREOF, AND THAT BOTH NOTICES APPEAR IN SUPPORTING DOCUMENTATION.

  Aleph is distributed in the hope that it will be useful, but WITHOUT
  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  or FITNESS FOR A PARTICULAR PURPOSE.

  UNIVERSIDAD DE LOS ANDES requests users of this software to return to 

  Leandro Leon
  CEMISID 
  Ed La Hechicera 
  3er piso, ala sur
  Facultad de Ingenieria 
  Universidad de Los Andes 
  Merida - REPÚBLICA BOLIVARIANA DE VENEZUELA    or

  lrleon@ula.ve

  any improvements or extensions that they make and grant Universidad 
  de Los Andes (ULA) the rights to redistribute these changes. 

  Aleph is (or was) granted by: 
  - Consejo de Desarrollo Cientifico, Humanistico, Tecnico de la ULA 
    (CDCHT)
  - Fundacite Mérida
*/


# ifndef TPL_DYNARRAY_H
# define TPL_DYNARRAY_H

# include <string>
# include <cmath>
# include <aleph.H>

using namespace std;

# ifdef DEBUG
# include <math.h>
# endif /* DEBUG */

using namespace Aleph;

namespace Aleph {

    template <typename T>
class DynArray
{

private:

  static const size_t Default_Pow_Dir;  /* 16   */
  static const size_t Default_Pow_Seg;  /* 64   */
  static const size_t Default_Pow_Block; /* 4096 */
  static const size_t Max_Bits_Allowed; 
  static const size_t Max_Dim_Allowed;
  static const size_t Max_Pow_Block;
  mutable size_t pow_dir;
  mutable size_t pow_seg;
  mutable size_t pow_block;
  mutable size_t seg_plus_block_pow;
  mutable size_t mask_seg_plus_block;
  mutable size_t dir_size;    // = 2^pow_dir
  mutable size_t seg_size;    // = 2^pow_seg
  mutable size_t block_size;  // = 2^pow_block
  mutable size_t max_dim;   // 2^(pow_dir + pow_seg + pow_block) - 1
  static size_t two_raised(const size_t & n)
  {
    if (n >= Max_Bits_Allowed)
      throw std::overflow_error ("number of bits exceeds de maximun allowed");

    I((1 << n) == (int) pow((float) 2.0, (float) n)); 

    return 1 << n;
  }
  size_t mask_seg;
  size_t mask_block;
  size_t index_in_dir(const size_t & i) const
  {

    I( (pow_block + pow_seg) == seg_plus_block_pow );
    I( seg_size * block_size == two_raised(seg_plus_block_pow) );
    I( i >> seg_plus_block_pow == i/(seg_size*block_size) );

    return i >> seg_plus_block_pow;
  }

  size_t modulus_from_index_in_dir(const size_t & i) const
  {

    I( mask_seg_plus_block == seg_size*block_size - 1 );
    I( (i & mask_seg_plus_block) == i%(seg_size*block_size) );

    return (i & mask_seg_plus_block);
  }

  size_t index_in_seg(const size_t & i) const
  {

    I( two_raised(pow_block) == block_size );
    I( (modulus_from_index_in_dir(i) >> pow_block) == 
            (i%(seg_size*block_size))/block_size );

    return modulus_from_index_in_dir(i) >> pow_block;
  }
    
  size_t index_in_block(const size_t & i) const
  {

    I( mask_block == block_size - 1 );
    I( (modulus_from_index_in_dir(i) & mask_block) == 
            ((i%(seg_size*block_size))%block_size) );

    return modulus_from_index_in_dir(i) & mask_block;
  }
  size_t current_dim;  
  size_t num_segs;   
  size_t num_blocks;
  T *** dir;
  void fill_dir_to_null()
  {

    I(dir != NULL);

    for (size_t i = 0; i < dir_size; ++i)
      dir[i] = NULL;
  }

  void fill_seg_to_null(T ** seg)
  {

    I(seg != NULL);

    for (size_t i = 0; i < seg_size; ++i)
      seg[i] = NULL;
  }
  void allocate_dir()
  {

    try
      {

        dir = new T ** [dir_size]; 
        fill_dir_to_null();

      }
    catch (...) 
      { 
        dir = NULL; 
        throw;
      }

  }

  void allocate_segment(T **& seg)
  {

    I(seg == NULL);

    seg = new T* [seg_size];
    fill_seg_to_null(seg);
    ++num_segs;
  }
  T default_initial_value;

  T * default_initial_value_ptr;
  void allocate_block(T *& block)
  {

    I(block == NULL);

    block = new T [block_size];
    ++num_blocks;

    if (default_initial_value_ptr == NULL)
      return;

    for (size_t i = 0; i < block_size; ++i)
      block[i] = default_initial_value;
  }
  void release_segment(T **& seg)
  {

    I(seg != NULL);

    delete [] seg;
    seg = NULL;
    --num_segs;
  }

  void release_block(T *& block)
  {

    I(block != NULL);

    delete [] block;
    block = NULL;
    --num_blocks;
  }
  void release_blocks_and_segment(T ** & seg)
  {

    I(seg != NULL);

    for(size_t i = 0; i < seg_size ; ++i)
      if (seg[i] != NULL) 
        release_block(seg[i]);
    
    release_segment(seg);
  }

  void release_all_segments_and_blocks()
  {
    for(size_t i = 0; i < dir_size ; ++i)
      if (dir[i] != NULL)
        release_blocks_and_segment(dir[i]); 

    current_dim = 0;
  }

  void release_dir()
  {
    release_all_segments_and_blocks();

    delete [] dir; 
    dir = NULL;
    current_dim = 0;
  }
  static size_t next2Pow(const size_t & number) 
  {
    return static_cast<size_t>(ceil(log(static_cast<float>(number))/log(2.0)));
  }
  size_t divide_by_block_size(const size_t & number) const
  {

    I(number/block_size == number >> pow_block);

    return number >> pow_block;
  }

  size_t modulus_by_block_size(const size_t & number) const
  {

    I((number%block_size) == (number & mask_block));

    return number & mask_block;
  }

  void advance_block_index(size_t &       block_index, 
                           size_t &       seg_index, 
                           const size_t & len) const
  {
    if (block_index + len < block_size)
      {
        block_index += len;
        return;
      }

    seg_index += divide_by_block_size(len);
    block_index = modulus_by_block_size(len); 
  }
  class Proxy
  {
    size_t index;
    size_t pos_in_dir;
    size_t pos_in_seg;
    size_t pos_in_block;
    T**&         ref_seg;
    T*           block;
    DynArray&    array;

  public:

    Proxy(DynArray<T>& _array, const size_t & i)
      : index       ( i                            ),
        pos_in_dir  ( _array.index_in_dir(index)   ),
        pos_in_seg  ( _array.index_in_seg(index)   ),
        pos_in_block( _array.index_in_block(index) ),
        ref_seg     ( _array.dir[pos_in_dir]       ),
        block       ( NULL                         ),
        array       ( _array                       )
    {
      if (ref_seg != NULL)
        block = ref_seg[pos_in_seg]; // ya existe un bloque para la entrada i
    }
    operator T & () 
    {

      if (block == NULL)
        throw std::invalid_argument("accessed entry has not been still written");

      return block[pos_in_block];
    }
    T * operator -> ()
    {
      bool seg_was_allocated_in_current_call = false;

      if (ref_seg == NULL) // hay segmento?
      {     // No ==> apartarlo!
        array.allocate_segment(ref_seg);
        seg_was_allocated_in_current_call = true; 
      }
      if (block == NULL) // test if block is allocated
        {

        try // tratar apartar bloque
          {

            array.allocate_block(block);
            ref_seg[pos_in_seg] = block;

            I(array.dir[pos_in_dir] == ref_seg); 
          }
        catch (...) // Ocurre una falla en el apartado del bloque
          {
            if (seg_was_allocated_in_current_call)
              array.release_segment(ref_seg);

            throw;
          }

        }

      if (index >= array.current_dim)
        array.current_dim = index + 1; 

      return &block[pos_in_block]; 
    }
    Proxy & operator = (const T & data)
    {
      bool seg_was_allocated_in_current_call = false;

      if (ref_seg == NULL) // hay segmento?
      {     // No ==> apartarlo!
        array.allocate_segment(ref_seg);
        seg_was_allocated_in_current_call = true; 
      }
      if (block == NULL) // test if block is allocated
        {

        try // tratar apartar bloque
          {

            array.allocate_block(block);
            ref_seg[pos_in_seg] = block;

            I(array.dir[pos_in_dir] == ref_seg); 
          }
        catch (...) // Ocurre una falla en el apartado del bloque
          {
            if (seg_was_allocated_in_current_call)
              array.release_segment(ref_seg);

            throw;
          }

        }
      if (index >= array.current_dim)
        array.current_dim = index + 1; 

      block[pos_in_block] = data;

      return *this;
    }

    Proxy & operator = (const Proxy & proxy)
    {
      if (proxy.block == NULL) // ¿operando derecho puede leer?
        throw std::invalid_argument("right entry has not been still written");

      if (&proxy == this)
        return *this;


      bool seg_was_allocated_in_current_call = false;

      if (ref_seg == NULL) // hay segmento?
      {     // No ==> apartarlo!
        array.allocate_segment(ref_seg);
        seg_was_allocated_in_current_call = true; 
      }
      if (block == NULL) // test if block is allocated
        {

        try // tratar apartar bloque
          {

            array.allocate_block(block);
            ref_seg[pos_in_seg] = block;

            I(array.dir[pos_in_dir] == ref_seg); 
          }
        catch (...) // Ocurre una falla en el apartado del bloque
          {
            if (seg_was_allocated_in_current_call)
              array.release_segment(ref_seg);

            throw;
          }

        }
      if (index >= array.current_dim)
        array.current_dim = index + 1; 

      block[pos_in_block] = proxy.block[proxy.pos_in_block];

      return *this;
    }
  };

public:

  const size_t & get_dir_size() const { return dir_size; }
  const size_t & get_seg_size() const { return seg_size; }
  const size_t & get_block_size() const { return block_size; } 
  const size_t & size() const { return current_dim; }
  const size_t & max_size() const { return max_dim; }
  const size_t & get_num_blocks() const { return num_blocks; }
  void set_default_initial_value(const T & value)
  {
    default_initial_value     = value;
    default_initial_value_ptr = &default_initial_value;
  }
  DynArray(const size_t & _pow_dir, 
           const size_t & _pow_seg,
           const size_t & _pow_block)
    throw (std::exception, std::bad_alloc, 
           std::length_error, std::overflow_error) 
    : pow_dir             ( _pow_dir                                 ),
      pow_seg             ( _pow_seg                                 ),
      pow_block           ( _pow_block                               ),
      seg_plus_block_pow  ( _pow_seg + _pow_block                    ),
      mask_seg_plus_block ( two_raised(seg_plus_block_pow) - 1       ),
      dir_size            ( two_raised(pow_dir)                      ), 
      seg_size            ( two_raised(pow_seg)                      ), 
      block_size          ( two_raised(pow_block)                    ), 
      max_dim             ( two_raised(seg_plus_block_pow + pow_dir) ), 
      mask_seg            ( seg_size - 1                             ),
      mask_block          ( block_size - 1                           ),
      current_dim         ( 0                                        ),
      num_segs            ( 0                                        ),
      num_blocks          ( 0                                        ),
      default_initial_value_ptr (NULL)
  {
    I(Max_Dim_Allowed > 0);

    if (max_dim > Max_Dim_Allowed)
      throw std::length_error ("Dimension too large"); 

    allocate_dir();
  }
  DynArray(const size_t & dim = 10000) 

    throw (std::exception, std::bad_alloc, 
           std::length_error, std::overflow_error) 

    : pow_dir             ( Default_Pow_Dir                          ),
      pow_seg             ( Default_Pow_Seg                          ),
        pow_block       (std::min(std::max(next2Pow(dim/8), Default_Pow_Block), 
                                  Max_Pow_Block)
                         ), 
      seg_plus_block_pow  ( pow_seg + pow_block                      ),
      mask_seg_plus_block ( two_raised(seg_plus_block_pow) - 1       ),
      dir_size            ( two_raised(pow_dir)                      ), 
      seg_size            ( two_raised(pow_seg)                      ), 
      block_size          ( two_raised(pow_block)                    ), 
      max_dim             ( two_raised(seg_plus_block_pow + pow_dir) ),
      mask_seg            ( seg_size - 1                             ),
      mask_block          ( block_size - 1                           ),
      current_dim         ( 0                                        ),
      num_segs            ( 0                                        ),
      num_blocks          ( 0                                        ),
      default_initial_value_ptr (NULL)
  {

    I(Max_Dim_Allowed > 0);

    if (max_dim > Max_Dim_Allowed)
      throw std::length_error ("Dimension too large"); 

    allocate_dir();
  }
  ~DynArray() 
  { 
    I(dir != NULL);

    release_dir();
  }
  void copy_array(const DynArray<T> & src_array)
  {
    for (int i = 0; i < src_array.current_dim; ++i)
      if (src_array.exist(i))
        (*this)[i] = src_array.access(i);
  }
  DynArray(const DynArray<T> & array) 
      throw (std::exception, std::bad_alloc)
    : pow_dir                   (array.pow_dir),
      pow_seg                   (array.pow_seg),
      pow_block                 (array.pow_block),
      seg_plus_block_pow        (array.seg_plus_block_pow),
      mask_seg_plus_block       (array.mask_seg_plus_block),
      dir_size                  (array.dir_size),
      seg_size                  (array.seg_size),
      block_size                (array.block_size),
      max_dim                   (array.max_dim),
      mask_seg                  (array.mask_seg),
      mask_block                (array.mask_block),
      current_dim               (0),
      num_segs                  (0),
      num_blocks                (0),
      default_initial_value_ptr (NULL)
  {
    allocate_dir();
    copy_array(array);
  }

  DynArray<T> & operator = (const DynArray<T> & array) 
    throw (std::exception, std::bad_alloc)
  {
    if (this == &array)
      return *this;

    copy_array(array);
    
    if (array.current_dim < current_dim)
      cut(array.current_dim);

    current_dim = array.current_dim;

    return *this;
  }
  void swap(DynArray<T> & array)
  {
    Aleph::swap(dir, array.dir);
    Aleph::swap(pow_dir,  array.pow_dir);
    Aleph::swap(pow_seg, array.pow_seg);
    Aleph::swap(pow_block, array.pow_block);
    Aleph::swap(seg_plus_block_pow, array.seg_plus_block_pow);
    Aleph::swap(mask_seg_plus_block, array.mask_seg_plus_block);
    Aleph::swap(dir_size, array.dir_size);
    Aleph::swap(seg_size, array.seg_size);
    Aleph::swap(block_size, array.block_size);
    Aleph::swap(mask_seg, array.mask_seg);
    Aleph::swap(mask_block, array.mask_block);
    Aleph::swap(max_dim, array.max_dim);
    Aleph::swap(current_dim, array.current_dim);
    Aleph::swap(num_segs, array.num_segs);
    Aleph::swap(num_blocks, array.num_blocks);
  }
  T & access(const size_t & i) 
  {

    I(dir[index_in_dir(i)] != NULL);
    I(dir[index_in_dir(i)][index_in_seg(i)] != NULL);

    return dir[index_in_dir(i)][index_in_seg(i)][index_in_block(i)];
  }

  const T & access(const size_t & i) const
  {
    I(dir[index_in_dir(i)] != NULL);
    I(dir[index_in_dir(i)][index_in_seg(i)] != NULL);

    return dir[index_in_dir(i)][index_in_seg(i)][index_in_block(i)];
  }

  bool exist(const size_t & i) const 

    throw (std::exception, std::out_of_range)

  {

    if (i >= max_dim)
      throw std::out_of_range ("index out of maximun range");

    const size_t pos_in_dir = index_in_dir(i);
       

    I(pos_in_dir < dir_size);

    if (dir[pos_in_dir] == NULL)
      return false;

    const size_t pos_in_seg = index_in_seg(i);
       

    I(pos_in_seg < seg_size);

    if (dir[pos_in_dir][pos_in_seg] == NULL) 
      return false;

    return true;
  }  
  T * test(const size_t & i)
  {
    const size_t pos_in_dir = index_in_dir(i);
       
    if (dir[pos_in_dir] == NULL)
      return NULL;

    const size_t pos_in_seg = index_in_seg(i);
       
    if (dir[pos_in_dir][pos_in_seg] == NULL) 
      return NULL;

    return &dir[index_in_dir(i)][index_in_seg(i)][index_in_block(i)];
  }
  T & touch(const size_t & i) 

    throw (std::exception, std::bad_alloc, std::out_of_range)

  {

    if (i >= max_dim)
      throw std::out_of_range ("index out of maximun range");

    const size_t pos_in_dir = index_in_dir(i);

    if (dir[pos_in_dir] == NULL)
      allocate_segment(dir[pos_in_dir]);

    const size_t pos_in_seg = index_in_seg(i);

    if (dir[pos_in_dir][pos_in_seg] == NULL)

      {
        try
          {

            allocate_block(dir[pos_in_dir][pos_in_seg]);

          }
        catch (...)
          {
            release_segment(dir[pos_in_dir]);
            throw;
          }
      }

    if (i >= current_dim)
      current_dim = i + 1;

    return dir[pos_in_dir][pos_in_seg][index_in_block(i)];
  }
  void reserve(const size_t & l, const size_t & r) 

    throw (std::exception, std::bad_alloc, std::domain_error, std::length_error) 

  {

    if (l > r)
      throw std::domain_error("invalid range");

    if (r >= max_dim)
      throw std::length_error ("dimension too large"); 

    const size_t first_seg = index_in_dir(l);
    const size_t last_seg  = index_in_dir(r);

    const size_t first_block = index_in_seg(l);
    const size_t last_block  = index_in_seg(r);


    try
      {

        for (size_t seg_idx = first_seg; seg_idx <= last_seg; ++seg_idx)
          {
            if (dir[seg_idx] == NULL)
              allocate_segment(dir[seg_idx]);

            size_t block_idx = (seg_idx == first_seg) ? first_block : 0;

            const size_t final_block = 
              (seg_idx == last_seg) ? last_block : seg_size - 1;

            while (block_idx <= final_block)
              {
                if (dir[seg_idx][block_idx] == NULL)
                  allocate_block(dir[seg_idx][block_idx]);

                ++block_idx; 
              }
          } // end for (...) 

        if (r + 1 > current_dim)
          current_dim = r + 1;

      }
    catch (...)
      {
        if (r + 1 > current_dim)
          current_dim = r + 1;
        throw;
      }

  }
  void cut(const size_t & new_dim = 0) 

    throw (std::exception, std::domain_error) 

  {

    if (new_dim > current_dim)
      throw std::domain_error("new dimension is greater that current dimension");

    if (new_dim == 0) 
      {
        release_all_segments_and_blocks();
        current_dim = 0;
        return;
      }

    const size_t old_dim = current_dim; // guarda antigua dimensión

        // índices cotas de bloques
    const int idx_first_seg   = index_in_dir(old_dim - 1);
    const int idx_first_block = index_in_seg(old_dim - 1);
    
        // índices cotas de segmentos
    const int idx_last_seg   = index_in_dir(new_dim - 1);
    const int idx_last_block = index_in_seg(new_dim - 1);    
    
        // recorre descendentemente los segmentos 
    for (int idx_seg = index_in_dir(old_dim - 1); idx_seg >= idx_last_seg; 
         --idx_seg)
      {
        if (dir[idx_seg] == NULL) // ¿hay un segmento?
          continue; // no ==> avance al siguiente
            
            // primer bloque a liberar 
        int idx_block = idx_seg == idx_first_seg ? idx_first_block : seg_size - 1;
            // Libera descendentemente los bloques reservados del segmento
        while ( (idx_seg > idx_last_seg and idx_block >= 0) or
                (idx_seg == idx_last_seg and idx_block > idx_last_block) )
        {
          if (dir[idx_seg][idx_block] != NULL) // ¿Hay un bloque aquí?
            release_block(dir[idx_seg][idx_block]);
          --idx_block; 
        }
        if (idx_block < 0)
          release_segment(dir[idx_seg]);
      }

    I(dir[idx_last_seg] != NULL and dir[idx_last_seg][idx_last_block] != NULL);


    current_dim = new_dim; // actualiza nueva dimensión
  }

  Proxy operator [] (const size_t & i) const
    throw (std::exception, std::bad_alloc, std::length_error, 
           std::invalid_argument) 
  {
    if (i >= max_dim)
      throw std::out_of_range ("index out of maximun range");

    return Proxy (const_cast<DynArray<T>&>(*this), i);
  }

  Proxy operator [] (const size_t & i) 

    throw (std::exception, std::length_error, 
           std::invalid_argument, std::bad_alloc)

  {

    if (i >= max_dim)
      throw std::out_of_range ("index out of maximun range");

    return Proxy (const_cast<DynArray<T>&>(*this), i);
  }
};

template <typename T> const size_t DynArray<T>::Default_Pow_Dir   = 4;  /* 16   */
template <typename T> const size_t DynArray<T>::Default_Pow_Seg   = 6;  /* 64   */
template <typename T> const size_t DynArray<T>::Default_Pow_Block = 12; /* 4096 */
template <typename T> const size_t DynArray<T>::Max_Bits_Allowed  = 8 * sizeof(size_t); 
template <typename T> const size_t DynArray<T>::Max_Dim_Allowed   = 2*1024*1024*1024ul;

template <typename T> const size_t DynArray<T>::Max_Pow_Block =
(Max_Bits_Allowed - Default_Pow_Dir  - Default_Pow_Seg  - 1);

} // end namespace Aleph

# endif /* TPL_DYNARRAY_H */

---