Public API Reference

                 

---

csutil/array.h

/*
  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__

// Hack: Work around problems caused by #defining 'new'.
#if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
# undef new
#endif
#include <new>

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

template <class T1, class T2>
class csOrdering
{
public:
  static int Compare(T1 const &r1, T2 const &r2)
  {
    if (r1 < r2) return -1;
    else if (r2 < r1) return 1;
    else return 0;
  }
};

// Define CSARRAY_INHIBIT_TYPED_KEYS if the compiler is too old or too buggy to
// properly support templated functions within a templated class.  When this is
// defined, rather than using a properly typed "key" argument, search methods
// fall back to dealing with opaque void* for the "key" argument.  Note,
// however, that this fact is completely hidden from the client; the client
// simply creates csArrayCmp<> functors using correct types for the keys
// regardless of whether the compiler actually supports this feature.  (The
// MSVC6 compiler, for example, does support templated functions within a
// template class but crashes and burns horribly when a function pointer or
// functor is thrown into the mix; thus this should be defined for MSVC6.)
#if !defined(CSARRAY_INHIBIT_TYPED_KEYS)

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 csOrdering<T,K>::Compare(r,k); }
private:
  K key;
  CF cmp;
};

#define csArrayTemplate(K) template <class K>
#define csArrayCmpDecl(T1,T2) csArrayCmp<T1,T2>
#define csArrayCmpInvoke(C,R) C(R)

#else // CSARRAY_INHIBIT_TYPED_KEYS

class csArrayCmpAbstract
{
public:
  typedef int(*CF)(void const*, void const*);
  virtual int operator()(void const*) const = 0;
  virtual operator CF() const = 0;
};

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

#define csArrayTemplate(K)
#define csArrayCmpDecl(T1,T2) csArrayCmpAbstract const&
#define csArrayCmpInvoke(C,R) C(&(R))

#endif // CSARRAY_INHIBIT_TYPED_KEYS

template <class T>
class csArrayElementHandler
{
public:
  static void Construct (T* address, T const& src)
  {
    new (CS_STATIC_CAST(void*,address)) T(src);
  }

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

  static void InitRegion (T* address, int count)
  {
    for (int i = 0 ; i < count ; i++)
      Construct (address + i, T ());
  }
};

template <class T>
class csArrayMemoryAllocator
{
public:
  static T* Alloc (int count)
  {
    return (T*)malloc (count * sizeof(T));
  }

  static void Free (T* mem)
  {
    free (mem);
  }

  // The 'relevantcount' parameter should be the number of items
  // in the old array that are initialized.
  static T* Realloc (T* mem, int relevantcount, int oldcount, int newcount)
  {
    (void)relevantcount; (void)oldcount;
    return (T*)realloc (mem, newcount * sizeof(T));
  }

  // Move memory.
  static void MemMove (T* mem, int dest, int src, int count)
  {
    memmove (mem + dest, mem + src, count * sizeof(T));
  }
};

template <class T, class ElementHandler = csArrayElementHandler<T> >
class csSafeCopyArrayMemoryAllocator
{
public:
  static T* Alloc (int count)
  {
    return (T*)malloc (count * sizeof(T));
  }

  static void Free (T* mem)
  {
    free (mem);
  }

  static T* Realloc (T* mem, int relevantcount, int oldcount, int newcount)
  {
    if (newcount <= oldcount)
    {
      // Realloc is safe.
      T* newmem = (T*)realloc (mem, newcount * sizeof (T));
      CS_ASSERT (newmem == mem);
      return newmem;
    }

    T* newmem = Alloc (newcount);
    int i;
    for (i = 0 ; i < relevantcount ; i++)
    {
      ElementHandler::Construct (newmem + i, mem[i]);
      ElementHandler::Destroy (mem + i);
    }
    Free (mem);
    return newmem;
  }

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


template <class T,
        class ElementHandler = csArrayElementHandler<T>,
        class MemoryAllocator = csArrayMemoryAllocator<T> >
class csArray
{
private:
  int count;
  int capacity;
  int threshold;
  T* root;
# ifdef CS_MEMORY_TRACKER
  MemTrackerInfo* mti;
  void UpdateMti (int dn, int curcapacity)
  {
    if (!mti)
    {
      if (!curcapacity) return;
      char buf[255];
      sprintf (buf, "csArray<%s>", typeid (T).name());
      mti = mtiRegisterAlloc (1 * sizeof (T), buf);
      if (!mti) return;
      curcapacity--;
      if (curcapacity)
        mtiUpdateAmount (mti, curcapacity, curcapacity * sizeof (T));
      return;
    }
    mtiUpdateAmount (mti, dn, dn * sizeof (T));
  }
# endif

protected:
  void InitRegion (int start, int count)
  {
    ElementHandler::InitRegion (root+start, count);
  }

private:
  void CopyFrom (const csArray& source)
  {
    if (&source != this)
    {
      DeleteAll ();
      threshold = source.threshold;
      SetLengthUnsafe (source.Length ());
      for (int i=0 ; i<source.Length() ; i++)
        ElementHandler::Construct (root + i, source[i]);
    }
  }

  // Adjust internal capacity of this array.
  void AdjustCapacity (int n)
  {
    if (n > capacity || (capacity > threshold && n < capacity - threshold))
    {
      n = ((n + threshold - 1) / threshold ) * threshold;
      if (root == 0)
      {
        root = MemoryAllocator::Alloc (n);
#       ifdef CS_MEMORY_TRACKER
        UpdateMti (n, n);
#       endif
      }
      else
      {
        root = MemoryAllocator::Realloc (root, count, capacity, n);
#       ifdef CS_MEMORY_TRACKER
        UpdateMti (n-capacity, n);
#       endif
      }
      capacity = n;
    }
  }

  // Set array length.  NOTE: Do not make this public since it does not
  // properly construct/destroy elements.  To safely truncate the array, use
  // Truncate().  To safely set the capacity, use SetCapacity().
  void SetLengthUnsafe (int n)
  {
    if (n > capacity)
      AdjustCapacity (n);
    count = n;
  }

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

  csArray (int icapacity = 0, int ithreshold = 0)
  {
#   ifdef CS_MEMORY_TRACKER
    mti = 0;
#   endif
    count = 0;
    capacity = (icapacity > 0 ? icapacity : 0);
    threshold = (ithreshold > 0 ? ithreshold : 16);
    if (capacity != 0)
    {
      root = MemoryAllocator::Alloc (capacity);
#     ifdef CS_MEMORY_TRACKER
      UpdateMti (capacity, capacity);
#     endif
    }
    else
    {
      root = 0;
    }
  }

  ~csArray ()
  {
    DeleteAll ();
  }

  csArray (const csArray& source)
  {
#   ifdef CS_MEMORY_TRACKER
    mti = 0;
#   endif
    root = 0;
    capacity = 0;
    count = 0;
    CopyFrom (source);
  }
  
  csArray<T,ElementHandler>& operator= (const csArray& other)
  {
    CopyFrom (other);
    return *this;
  }

  int Length () const
  {
    return count;
  }

  int Capacity () const
  {
    return capacity;
  }

  void TransferTo (csArray& destination)
  {
    if (&destination != this)
    {
      destination.DeleteAll ();
      destination.root = root;
      destination.count = count;
      destination.capacity = capacity;
      destination.threshold = threshold;
#     ifdef CS_MEMORY_TRACKER
      destination.mti = mti;
      mti = 0;
#     endif
      root = 0;
      capacity = count = 0;
    }
  }

  void SetLength (int n, T const& what)
  {
    if (n <= count)
    {
      Truncate (n);
    }
    else
    {
      int old_len = Length ();
      SetLengthUnsafe (n);
      for (int i = old_len ; i < n ; i++)
        ElementHandler::Construct (root + i, what);
    }
  }

  void SetLength (int n)
  {
    if (n <= count)
    {
      Truncate (n);
    }
    else
    {
      int old_len = Length ();
      SetLengthUnsafe (n);
      ElementHandler::InitRegion (root + old_len, n-old_len);
    }
  }

  T& Get (int n)
  {
    CS_ASSERT (n >= 0 && n < count);
    return root[n];
  }

  T const& Get (int n) const
  {
    CS_ASSERT (n >= 0 && n < count);
    return root[n];
  }

  T& GetExtend (int n)
  {
    CS_ASSERT (n >= 0);
    if (n >= count)
      SetLength (n+1);
    return root[n];
  }

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

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

  void Put (int n, T const& what)
  {
    CS_ASSERT (n >= 0);
    if (n >= count)
      SetLength (n+1);
    ElementHandler::Destroy (root + n);
    ElementHandler::Construct (root + n, what);
  }

  csArrayTemplate(K)
  int FindKey (csArrayCmpDecl(T,K) comparekey) const
  {
    for (int i = 0 ; i < Length () ; i++)
      if (csArrayCmpInvoke(comparekey, root[i]) == 0)
        return i;
    return -1;
  }

  int Push (T const& what)
  {
    if (((&what >= root) && (&what < root + Length())) && 
      (capacity < 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.
       */
      int whatIndex = &what - root;
      SetLengthUnsafe (count + 1);
      ElementHandler::Construct (root + count - 1, root[whatIndex]);
    }
    else
    {
      SetLengthUnsafe (count + 1);
      ElementHandler::Construct (root + count - 1, what);
    }
    return count - 1;
  }

  /*
   * Push a element onto the tail end of the array if not already present.
   * Returns index of newly pushed element or index of already present element.
   */
  int PushSmart (T const& what)
  {
    int const n = Find (what);
    return (n < 0) ? Push (what) : n;
  }

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

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

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

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

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

  csArrayTemplate(K)
  int FindSortedKey (csArrayCmpDecl(T,K) comparekey, int* candidate = 0) const
  {
    int m = 0, l = 0, r = Length () - 1;
    while (l <= r)
    {
      m = (l + r) / 2;
      int cmp = csArrayCmpInvoke(comparekey, root[m]);
      if (cmp == 0)
      {
        if (candidate) *candidate = -1;
        return m;
      }
      else if (cmp < 0)
        l = m + 1;
      else
        r = m - 1;
    }
    if (candidate) *candidate = m;
    return -1;
  }

  int InsertSorted (const T& item,
    int (*compare)(T const&, T const&) = DefaultCompare,
    int* equal_index = 0)
  {
    int m = 0, l = 0, r = Length () - 1;
    while (l <= r)
    {
      m = (l + r) / 2;
      int cmp = compare (root [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 - 1;
    }
    if (r == m)
      m++;
    if (equal_index) *equal_index = -1;
    Insert (m, item);
    return m;
  }

  int Find (T const& which) const
  {
    for (int i = 0 ; i < Length () ; i++)
      if (root[i] == which)
        return i;
    return -1;
  }

  int GetIndex (const T* which) const
  {
    return which-root;
  }

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

  void DeleteAll ()
  {
    if (root)
    {
      int i;
      for (i = 0 ; i < count ; i++)
        ElementHandler::Destroy (root + i);
      MemoryAllocator::Free (root);
#     ifdef CS_MEMORY_TRACKER
      UpdateMti (-capacity, 0);
#     endif
      root = 0;
      capacity = count = 0;
    }
  }

  void Truncate (int n)
  {
    CS_ASSERT(n >= 0);
    CS_ASSERT(n <= count);
    if (n < count)
    {
      for (int i = n; i < count; i++)
        ElementHandler::Destroy (root + i);
      SetLengthUnsafe(n);
    }
  }

  void Empty ()
  {
    Truncate (0);
  }

  void SetCapacity (int n)
  {
    if (n > Length ())
      AdjustCapacity (n);
  }

  void ShrinkBestFit ()
  {
    if (count == 0)
    {
      DeleteAll ();
    }
    else if (count != capacity)
    {
      root = MemoryAllocator::Realloc (root, count, capacity, count);
#     ifdef CS_MEMORY_TRACKER
      UpdateMti (count-capacity, count);
#     endif
      capacity = count;
    }
  }

  bool DeleteIndex (int n)
  {
    if (n >= 0 && n < count)
    {
      int const ncount = count - 1;
      int const nmove = ncount - n;
      ElementHandler::Destroy (root + n);
      if (nmove > 0)
        MemoryAllocator::MemMove (root, n, n+1, nmove);
      SetLengthUnsafe (ncount);
      return true;
    }
    else
      return false;
  }

  void DeleteRange (int start, int end)
  {
    if (start >= count) return;
    if (end < 0) return;
    if (start < 0) start = 0;
    if (end >= count) end = count - 1;
    int i;
    for (i = start ; i <= end ; i++)
      ElementHandler::Destroy (root + i);

    int const range_size = end - start + 1;
    int const ncount = count - range_size;
    int const nmove = count - end - 1;
    if (nmove > 0)
      MemoryAllocator::MemMove (root, start, start + range_size, nmove);
    SetLengthUnsafe (ncount);
  }

  bool Delete (T const& item)
  {
    int const n = Find (item);
    if (n >= 0)
      return DeleteIndex (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()
    { return currentelem < array.Length(); }

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

    void Reset()
    { currentelem = 0; }
  protected:
    Iterator(const csArray<T, ElementHandler>& newarray)
        : currentelem(0), array(newarray)
    { }
    friend class csArray<T, ElementHandler>;
    
  private:
    int currentelem;
    const csArray<T, ElementHandler>& array;
  };

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

template <class T>
class csSafeCopyArray
        : public csArray<T,
                csArrayElementHandler<T>,
                csSafeCopyArrayMemoryAllocator<T> >
{
public:
  csSafeCopyArray (int ilimit = 0, int ithreshold = 0)
        : csArray<T, csArrayElementHandler<T>,
                     csSafeCopyArrayMemoryAllocator<T> > (ilimit, ithreshold)
  {
  }
};

#if defined(CS_EXTENSIVE_MEMDEBUG) || defined(CS_MEMORY_TRACKER)
# define new CS_EXTENSIVE_MEMDEBUG_NEW
#endif

#endif

---