Public API Reference

csutil/array.h

Go to the documentation of this file.

/*
  Crystal Space Generic Array Template
  Copyright (C) 2003 by Matze Braun
  Copyright (C) 2003 by Jorrit Tyberghein
  Copyright (C) 2003,2004 by Eric Sunshine

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Library General Public
  License as published by the Free Software Foundation; either
  version 2 of the License, or (at your option) any later version.

  This library 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.  See the GNU
  Library General Public License for more details.

  You should have received a copy of the GNU Library General Public
  License along with this library; if not, write to the Free
  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#ifndef __CSUTIL_ARRAY_H__
#define __CSUTIL_ARRAY_H__

#include "csutil/allocator.h"
#include "csutil/comparator.h"

#include "csutil/custom_new_disable.h"

#if defined(CS_MEMORY_TRACKER)
#include "csutil/memdebug.h"
#include "csutil/snprintf.h"
#include <typeinfo>
#endif

template <class T, class K>
class csArrayCmp
{
public:
  typedef int(*CF)(T const&, K const&);
  csArrayCmp(K const& k, CF c = DefaultCompare) : key(k), cmp(c) {}
  csArrayCmp(csArrayCmp const& o) : key(o.key), cmp(o.cmp) {}
  csArrayCmp& operator=(csArrayCmp const& o)
    { key = o.key; cmp = o.cmp; return *this; }
  int operator()(T const& r) const { return cmp(r, key); }
  operator CF() const { return cmp; }
  operator K const&() const { return key; }
  static int DefaultCompare(T const& r, K const& k)
    { return csComparator<T,K>::Compare(r,k); }
private:
  K key;
  CF cmp;
};

template <class T>
class csArrayElementHandler
{
public:
  static void Construct (T* address)
  {
    new (static_cast<void*> (address)) T();
  }

  static void Construct (T* address, T const& src)
  {
    new (static_cast<void*> (address)) T(src);
  }

  static void Destroy (T* address)
  {
    address->~T();
  }

  static void InitRegion (T* address, size_t count)
  {
    for (size_t i = 0 ; i < count ; i++)
      Construct (address + i);
  }
  
  template<typename Allocator>
  static T* ResizeRegion (Allocator& alloc, T* mem, size_t relevantcount, 
    size_t oldcount, size_t newcount)
  {
    (void)relevantcount; (void)oldcount;
    return (T*)alloc.Realloc (mem, newcount * sizeof(T));
  }

  static void MoveElements (T* mem, size_t dest, size_t src, size_t count)
  {
    memmove (mem + dest, mem + src, count * sizeof(T));
  }
};

template <class T>
class csArraySafeCopyElementHandler
{
public:
  static void Construct (T* address)
  {
    new (static_cast<void*> (address)) T();
  }

  static void Construct (T* address, T const& src)
  {
    new (static_cast<void*> (address)) T(src);
  }

  static void Destroy (T* address)
  {
    address->~T();
  }

  static void InitRegion (T* address, size_t count)
  {
    for (size_t i = 0 ; i < count ; i++)
      Construct (address + i);
  }
  
  template<typename Allocator>
  static T* ResizeRegion (Allocator& alloc, T* mem, size_t relevantcount, 
    size_t oldcount, size_t newcount)
  {
    if (newcount <= oldcount)
    {
      // Realloc is safe.
      T* newmem = (T*)alloc.Realloc (mem, newcount * sizeof (T));
      CS_ASSERT (newmem == mem);
      return newmem;
    }

    T* newmem = (T*)alloc.Alloc (newcount * sizeof (T));
    size_t i;
    for (i = 0 ; i < relevantcount ; i++)
    {
      Construct (newmem + i, mem[i]);
      Destroy (mem + i);
    }
    alloc.Free (mem);
    return newmem;
  }

  static void MoveElements (T* mem, size_t dest, size_t src, size_t count)
  {
    size_t i;
    if (dest < src)
    {
      for (i = 0 ; i < count ; i++)
      {
        Construct (mem + dest + i, mem[src + i]);
        Destroy (mem + src + i);
      }
    }
    else
    {
      i = count;
      while (i > 0)
      {
        i--;
        Construct (mem + dest + i, mem[src + i]);
        Destroy (mem + src + i);
      }
    }
  }
};


class csArrayThresholdVariable
{
  size_t threshold;
public:
  csArrayThresholdVariable (size_t in_threshold = 0)
  { threshold = (in_threshold > 0 ? in_threshold : 16); }
  size_t GetThreshold() const { return threshold; }
};

template<int N>
class csArrayThresholdFixed
{
public:
  csArrayThresholdFixed (size_t x = 0)
  { (void)x; }
  size_t GetThreshold() const { return N; }
  // Work around VC7 bug apparently incorrectly copying this empty class
  csArrayThresholdFixed& operator= (const csArrayThresholdFixed&) 
  { return *this; }
};

template<typename Threshold = csArrayThresholdVariable>
class csArrayCapacityLinear : public Threshold
{
public:

  csArrayCapacityLinear () : Threshold () {}
  csArrayCapacityLinear (const Threshold& threshold) : Threshold (threshold)
  {}

  csArrayCapacityLinear (const size_t x) : Threshold (x)
  {}

  bool IsCapacityExcessive (size_t capacity, size_t count) const
  {
    return (capacity > this->GetThreshold() 
      && count < capacity - this->GetThreshold());
  }
  size_t GetCapacity (size_t count) const
  {
    return ((count + this->GetThreshold() - 1) / this->GetThreshold()) * 
      this->GetThreshold();
  }
};

// Alias for csArrayCapacityLinear<csArrayThresholdVariable> to keep
// SWIG generated Java classes (and thus filenames) short enough for Windows.
// Note that a typedef wont work because SWIG would expand it.
struct csArrayCapacityDefault :
  public csArrayCapacityLinear<csArrayThresholdVariable>
{
  csArrayCapacityDefault () :
    csArrayCapacityLinear<csArrayThresholdVariable> () {}
  csArrayCapacityDefault (const csArrayThresholdVariable& threshold) :
    csArrayCapacityLinear<csArrayThresholdVariable> (threshold) {}
  csArrayCapacityDefault (const size_t x) :
    csArrayCapacityLinear<csArrayThresholdVariable> (x) {}
} ;

const size_t csArrayItemNotFound = (size_t)-1;

template <class T,
        class ElementHandler = csArrayElementHandler<T>,
        class MemoryAllocator = CS::Memory::AllocatorMalloc,
        class CapacityHandler = csArrayCapacityDefault>
class csArray
{
public:
  typedef csArray<T, ElementHandler, MemoryAllocator, CapacityHandler> ThisType;
  typedef T ValueType;
  typedef ElementHandler ElementHandlerType;
  typedef MemoryAllocator AllocatorType;
  typedef CapacityHandler CapacityHandlerType;

private:
  size_t count;
  struct ArrayCapacity : public CapacityHandler
  {
    size_t c;
    ArrayCapacity (size_t in_capacity)
    { c = (in_capacity > 0 ? in_capacity : 0); }
    ArrayCapacity (size_t in_capacity, const CapacityHandler& ch) : 
      CapacityHandler (ch) 
    { c = (in_capacity > 0 ? in_capacity : 0); }
    void CopyFrom (const CapacityHandler& source)
    {
      CapacityHandler::operator= (source);
    }
  };
  ArrayCapacity capacity;
  CS::Memory::AllocatorPointerWrapper<T, MemoryAllocator> root;

protected:
  void InitRegion (size_t start, size_t count)
  {
    ElementHandler::InitRegion (root.p+start, count);
  }

private:
  void CopyFrom (const csArray& source)
  {
    capacity.CopyFrom (source.capacity);
    SetSizeUnsafe (source.Length ());
    for (size_t i=0 ; i<source.Length() ; i++)
      ElementHandler::Construct (root.p + i, source[i]);
  }

  void InternalSetCapacity (size_t n)
  {
    if (root.p == 0)
    {
      root.p = (T*)root.Alloc (n * sizeof (T));
    }
    else
    {
      root.p = ElementHandler::ResizeRegion (root, root.p, count, capacity.c, n);
    }
    capacity.c = n;
  }

  void AdjustCapacity (size_t n)
  {
    if (n > capacity.c || capacity.IsCapacityExcessive (capacity.c, n))
    {
      InternalSetCapacity (capacity.GetCapacity (n));
    }
  }

  void SetSizeUnsafe (size_t n)
  {
    if (n > capacity.c)
      AdjustCapacity (n);
    count = n;
  }

public:
  static int DefaultCompare(T const& r1, T const& r2)
  {
    return csComparator<T,T>::Compare(r1,r2);
  }

  csArray (size_t in_capacity = 0,
    const CapacityHandler& ch = CapacityHandler()) : count (0), 
    capacity (in_capacity, ch)
  {
#ifdef CS_MEMORY_TRACKER
    root.SetMemTrackerInfo (typeid(*this).name());
#endif
    if (capacity.c != 0)
    {
      root.p = (T*)root.Alloc (capacity.c * sizeof (T));
    }
    else
    {
      root.p = 0;
    }
  }
  csArray (size_t in_capacity, 
    const MemoryAllocator& alloc,
    const CapacityHandler& ch) : count (0), 
    capacity (in_capacity, ch), root (alloc)
  {
#ifdef CS_MEMORY_TRACKER
    root.SetMemTrackerInfo (typeid(*this).name());
#endif
    if (capacity.c != 0)
    {
      root.p = (T*)root.Alloc (capacity.c * sizeof (T));
    }
    else
    {
      root.p = 0;
    }
  }

  ~csArray ()
  {
    DeleteAll ();
  }

  csArray (const csArray& source) : count (0), capacity (0), root (0)
  {
#ifdef CS_MEMORY_TRACKER
    root.SetMemTrackerInfo (typeid(*this).name());
#endif
    CopyFrom (source);
  }

  csArray<T,ElementHandler,MemoryAllocator,CapacityHandler>& operator= (
    const csArray& other)
  {
    if (&other != this)
    {
      DeleteAll ();
      CopyFrom (other);
    }
    return *this;
  }

  size_t GetSize () const
  {
    return count;
  }

  /*CS_DEPRECATED_METHOD_MSG("Use GetSize() instead.")*/
  size_t Length () const
  {
    return GetSize();
  }

  size_t Capacity () const
  {
    return capacity.c;
  }

  // @@@ FIXME: What about custom allocators?
  void TransferTo (csArray& destination)
  {
    if (&destination != this)
    {
      destination.DeleteAll ();
      destination.root.p = root.p;
      destination.count = count;
      destination.capacity = capacity;
      root.p = 0;
      capacity.c = count = 0;
    }
  }

  void SetSize (size_t n, T const& what)
  {
    if (n <= count)
    {
      Truncate (n);
    }
    else
    {
      size_t old_len = Length ();
      SetSizeUnsafe (n);
      for (size_t i = old_len ; i < n ; i++)
        ElementHandler::Construct (root.p + i, what);
    }
  }

  void SetSize (size_t n)
  {
    if (n <= count)
    {
      Truncate (n);
    }
    else
    {
      size_t old_len = Length ();
      SetSizeUnsafe (n);
      ElementHandler::InitRegion (root.p + old_len, n-old_len);
    }
  }

  /*CS_DEPRECATED_METHOD_MSG("Use SetSize() instead.")*/
  void SetLength (size_t n, T const& what) { SetSize(n, what); }
  /*CS_DEPRECATED_METHOD_MSG("Use SetSize() instead.")*/
  void SetLength (size_t n) { SetSize(n); }

  T& Get (size_t n)
  {
    CS_ASSERT (n < count);
    return root.p[n];
  }

  T const& Get (size_t n) const
  {
    CS_ASSERT (n < count);
    return root.p[n];
  }

  T& GetExtend (size_t n)
  {
    if (n >= count)
      SetSize (n+1);
    return root.p[n];
  }

  T& operator [] (size_t n)
  {
    return Get(n);
  }

  T const& operator [] (size_t n) const
  {
    return Get(n);
  }

  void Put (size_t n, T const& what)
  {
    if (n >= count)
      SetSize (n+1);
    ElementHandler::Destroy (root.p + n);
    ElementHandler::Construct (root.p + n, what);
  }

  template <class K>
  size_t FindKey (csArrayCmp<T,K> comparekey) const
  {
    for (size_t i = 0 ; i < Length () ; i++)
      if (comparekey (root.p[i]) == 0)
        return i;
    return csArrayItemNotFound;
  }

  size_t Push (T const& what)
  {
    if (((&what >= root.p) && (&what < root.p + Length())) &&
      (capacity.c < count + 1))
    {
      /*
        Special case: An element from this very array is pushed, and a
        reallocation is needed. This could cause the passed ref to the
        element to be pushed to be read from deleted memory. Work
        around this.
       */
      size_t whatIndex = &what - root.p;
      SetSizeUnsafe (count + 1);
      ElementHandler::Construct (root.p + count - 1, root.p[whatIndex]);
    }
    else
    {
      SetSizeUnsafe (count + 1);
      ElementHandler::Construct (root.p + count - 1, what);
    }
    return count - 1;
  }

  size_t PushSmart (T const& what)
  {
    size_t const n = Find (what);
    return (n == csArrayItemNotFound) ? Push (what) : n;
  }

  T Pop ()
  {
    CS_ASSERT (count > 0);
    T ret(root.p [count - 1]);
    ElementHandler::Destroy (root.p + count - 1);
    SetSizeUnsafe (count - 1);
    return ret;
  }

  T const& Top () const
  {
    CS_ASSERT (count > 0);
    return root.p [count - 1];
  }

  T& Top ()
  {
    CS_ASSERT (count > 0);
    return root.p [count - 1];
  }

  bool Insert (size_t n, T const& item)
  {
    if (n <= count)
    {
      SetSizeUnsafe (count + 1); // Increments 'count' as a side-effect.
      size_t const nmove = (count - n - 1);
      if (nmove > 0)
        ElementHandler::MoveElements (root.p, n+1, n, nmove);
      ElementHandler::Construct (root.p + n, item);
      return true;
    }
    else
      return false;
  }

  csArray<T> Section (size_t low, size_t high) const
  {
    CS_ASSERT (high < count && high >= low);
    csArray<T> sect (high - low + 1);
    for (size_t i = low; i <= high; i++) sect.Push (root.p[i]);
    return sect;
  }

  template <class K>
  size_t FindSortedKey (csArrayCmp<T,K> comparekey,
                        size_t* candidate = 0) const
  {
    size_t m = 0, l = 0, r = Length ();
    while (l < r)
    {
      m = (l + r) / 2;
      int cmp = comparekey (root.p[m]);
      if (cmp == 0)
      {
        if (candidate) *candidate = csArrayItemNotFound;
        return m;
      }
      else if (cmp < 0)
        l = m + 1;
      else
        r = m;
    }
    if ((m + 1) == r)
      m++;
    if (candidate) *candidate = m;
    return csArrayItemNotFound;
  }

  size_t InsertSorted (const T& item,
    int (*compare)(T const&, T const&) = DefaultCompare,
    size_t* equal_index = 0)
  {
    size_t m = 0, l = 0, r = Length ();
    while (l < r)
    {
      m = (l + r) / 2;
      int cmp = compare (root.p [m], item);

      if (cmp == 0)
      {
        if (equal_index) *equal_index = m;
        Insert (++m, item);
        return m;
      }
      else if (cmp < 0)
        l = m + 1;
      else
        r = m;
    }
    if ((m + 1) == r)
      m++;
    if (equal_index) *equal_index = csArrayItemNotFound;
    Insert (m, item);
    return m;
  }

  size_t Find (T const& which) const
  {
    for (size_t i = 0 ; i < Length () ; i++)
      if (root.p[i] == which)
        return i;
    return csArrayItemNotFound;
  }

  size_t Contains(T const& which) const
  { return Find(which); }

  size_t GetIndex (const T* which) const
  {
    CS_ASSERT (which >= root.p);
    CS_ASSERT (which < (root.p + count));
    return which-root.p;
  }

  void Sort (int (*compare)(T const&, T const&) = DefaultCompare)
  {
    qsort (root.p, Length(), sizeof(T),
      (int (*)(void const*, void const*))compare);
  }

  void DeleteAll ()
  {
    if (root.p)
    {
      size_t i;
      for (i = 0 ; i < count ; i++)
        ElementHandler::Destroy (root.p + i);
      root.Free (root.p);
      root.p = 0;
      capacity.c = count = 0;
    }
  }

  void Truncate (size_t n)
  {
    CS_ASSERT(n <= count);
    if (n < count)
    {
      for (size_t i = n; i < count; i++)
        ElementHandler::Destroy (root.p + i);
      SetSizeUnsafe(n);
    }
  }

  void Empty ()
  {
    Truncate (0);
  }

  bool IsEmpty() const
  {
    return GetSize() == 0;
  }

  void SetCapacity (size_t n)
  {
    if (n > Length ())
      InternalSetCapacity (n);
  }

  void SetMinimalCapacity (size_t n)
  {
    if (n < Capacity ()) return;
    if (n > Length ())
      InternalSetCapacity (n);
  }

  void ShrinkBestFit ()
  {
    if (count == 0)
    {
      DeleteAll ();
    }
    else if (count != capacity.c)
    {
      root.p = ElementHandler::ResizeRegion (root, root.p, count, capacity.c, count);
      capacity.c = count;
    }
  }

  bool DeleteIndex (size_t n)
  {
    if (n < count)
    {
      size_t const ncount = count - 1;
      size_t const nmove = ncount - n;
      ElementHandler::Destroy (root.p + n);
      if (nmove > 0)
        ElementHandler::MoveElements (root.p, n, n+1, nmove);
      SetSizeUnsafe (ncount);
      return true;
    }
    else
      return false;
  }

  bool DeleteIndexFast (size_t n)
  {
    if (n < count)
    {
      size_t const ncount = count - 1;
      size_t const nmove = ncount - n;
      ElementHandler::Destroy (root.p + n);
      if (nmove > 0)
        ElementHandler::MoveElements (root.p, n, ncount, 1);
      SetSizeUnsafe (ncount);
      return true;
    }
    else
      return false;
  }

  bool DeleteRange (size_t start, size_t end)
  {
    if (start >= count) return false;
    // Treat 'csArrayItemNotFound' as invalid indices, do nothing.
    if (end == csArrayItemNotFound) return false;
    if (start == csArrayItemNotFound) return false;//start = 0;
    if (end >= count) end = count - 1;
    size_t i;
    for (i = start ; i <= end ; i++)
      ElementHandler::Destroy (root.p + i);

    size_t const range_size = end - start + 1;
    size_t const ncount = count - range_size;
    size_t const nmove = count - end - 1;
    if (nmove > 0)
      ElementHandler::MoveElements (root.p, start, start + range_size, nmove);
    SetSizeUnsafe (ncount);
    return true;
  }

  bool Delete (T const& item)
  {
    size_t const n = Find (item);
    if (n != csArrayItemNotFound)
      return DeleteIndex (n);
    return false;
  }

  CS_DEPRECATED_METHOD_MSG("'Fast' is illusory. See documentation")
  bool DeleteFast (T const& item)
  {
    size_t const n = Find (item);
    if (n != csArrayItemNotFound)
      return DeleteIndexFast (n);
    return false;
  }

  class Iterator
  {
  public:
    Iterator(Iterator const& r) :
      currentelem(r.currentelem), array(r.array) {}

    Iterator& operator=(Iterator const& r)
    { currentelem = r.currentelem; array = r.array; return *this; }

    bool HasNext() const
    { return currentelem < array.Length(); }

    T& Next()
    { return array.Get(currentelem++); }

    void Reset()
    { currentelem = 0; }

  protected:
    Iterator(csArray<T, ElementHandler>& newarray)
        : currentelem(0), array(newarray) {}
    friend class csArray<T, ElementHandler>;

  private:
    size_t currentelem;
    csArray<T, ElementHandler>& array;
  };

  class ConstIterator
  {
  public:
    ConstIterator(ConstIterator const& r) :
      currentelem(r.currentelem), array(r.array) {}

    ConstIterator& operator=(ConstIterator const& r)
    { currentelem = r.currentelem; array = r.array; return *this; }

    bool HasNext() const
    { return currentelem < array.Length(); }

    const T& Next()
    { return array.Get(currentelem++); }

    void Reset()
    { currentelem = 0; }

  protected:
    ConstIterator(const csArray<T, ElementHandler>& newarray)
      : currentelem(0), array(newarray) {}
    friend class csArray<T, ElementHandler>;

  private:
    size_t currentelem;
    const csArray<T, ElementHandler>& array;
  };

  Iterator GetIterator()
  { return Iterator(*this); }

  ConstIterator GetIterator() const
  { return ConstIterator(*this); }
  
  bool operator== (const csArray& other) const
  {
    if (other.GetSize() != GetSize()) return false;
    for (size_t i = 0; i < GetSize(); i++)
      if (Get (i) != other[i]) return false;
    return true;
  }

  bool operator!= (const csArray& other) const { return !(*this==other); }

  const MemoryAllocator& GetAllocator() const
  {
    return root;
  }
};

template <class T>
class csSafeCopyArray
        : public csArray<T,
                csArraySafeCopyElementHandler<T> >
{
public:
  csSafeCopyArray (size_t limit = 0, size_t threshold = 0)
        : csArray<T, csArraySafeCopyElementHandler<T> > (limit, threshold)
  {
  }
};

#include "csutil/custom_new_enable.h"

#endif

---