externals/grill/flext/source flmap.cpp, NONE, 1.1 flmap.h, 1.16, 1.17 - Pd-cvs

19 Apr 2005


      Update of /cvsroot/pure-data/externals/grill/flext/source
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv23509/source
Modified Files:
    flmap.h 
Added Files:
    flmap.cpp 
Log Message:
fixed typo
added profiling flags for OSX
small fixes
Index: flmap.h
===================================================================
RCS file: /cvsroot/pure-data/externals/grill/flext/source/flmap.h,v
retrieving revision 1.16
retrieving revision 1.17
diff -C2 -d -r1.16 -r1.17
*** flmap.h	18 Apr 2005 22:05:52 -0000	1.16
--- flmap.h	19 Apr 2005 13:29:56 -0000	1.17
***************
*** 10,14 ****
/*! \file flmap.h
! 	\brief special map class for all 32-bit key/value-pairs   
  */
--- 10,14 ----
/*! \file flmap.h
! 	\brief special map class (faster and less memory-consuming than std::map)   
  */
***************
*** 38,42 ****
      TableAnyMap(TableAnyMap *p,Data *dt)
          : data(dt)
!         , parent(p),left(NULL),right(NULL) 
          , n(0)
      {}
--- 38,42 ----
      TableAnyMap(TableAnyMap *p,Data *dt)
          : data(dt)
!         , parent(p),left(0),right(0) 
          , n(0)
      {}
***************
*** 44,48 ****
      virtual ~TableAnyMap();
! #if 0
      void check(int tsize) { if(n) _check(tsize); }
  #else
--- 44,48 ----
      virtual ~TableAnyMap();
! #if 0 // set 1 for asserting the map structure (very cpu-intensive!)
      void check(int tsize) { if(n) _check(tsize); }
  #else
***************
*** 57,61 ****
          else {
              data[n++](k,t);
!             r = NULL;
          }
          check(tsize);
--- 57,61 ----
          else {
              data[n++](k,t);
!             r = 0;
          }
          check(tsize);
***************
*** 63,69 ****
      }
!     void *find(int tsize,size_t k) const { return n?_find(tsize,k):NULL; }
!     void *remove(int tsize,size_t k) { void *r = n?_remove(tsize,k):NULL; check(tsize); return r; }
virtual void clear();
--- 63,74 ----
      }
!     void *find(int tsize,size_t k) const { return n?_find(tsize,k):0; }
!     void *remove(int tsize,size_t k) 
! 	{ 
! 		void *r = n?_remove(tsize,k):0; 
! 		check(tsize); 
! 		return r; 
! 	}
virtual void clear();
***************
*** 72,76 ****
      {
      public:
!         iterator(): map(NULL) {}
          iterator(const TableAnyMap &m): map(&m),ix(0) { leftmost(); }
          iterator(iterator &it): map(it.map),ix(it.ix) {}
--- 77,81 ----
      {
      public:
!         iterator(): map(0) {}
          iterator(const TableAnyMap &m): map(&m),ix(0) { leftmost(); }
          iterator(iterator &it): map(it.map),ix(it.ix) {}
***************
*** 91,99 ****
              // search smallest branch (go left as far as possible)
              const TableAnyMap *nmap;
!             while((nmap = map->left) != NULL) map = nmap;
          }
void forward();
const TableAnyMap *map;
          int ix;
--- 96,105 ----
              // search smallest branch (go left as far as possible)
              const TableAnyMap *nmap;
!             while((nmap = map->left) != 0) map = nmap;
          }
void forward();
+ 		// pointers to map and index within
          const TableAnyMap *map;
          int ix;
***************
*** 110,114 ****
          else {
              (left = _newmap(this))->_init(k,t);
!             return NULL;
          }
      }
--- 116,120 ----
          else {
              (left = _newmap(this))->_init(k,t);
!             return 0;
          }
      }
***************
*** 120,124 ****
          else {
              (right = _newmap(this))->_init(k,t);
!             return NULL;
          }
      }
--- 126,130 ----
          else {
              (right = _newmap(this))->_init(k,t);
!             return 0;
          }
      }
***************
*** 137,164 ****
      Data *const data;
      TableAnyMap *parent,*left,*right;
!     short n;
//! return index of data item with key <= k
      //! \note index can point past the last item!
!     int _tryix(size_t k) const
      {
!         int ix = 0;
!         {
!             int b = n;
!             while(ix != b) {
!                 const int c = (ix+b)/2;
!                 const size_t dk = data[c].key;
!                 if(k == dk)
!                     return c;
!                 else if(k < dk)
!                     b = c;
!                 else if(ix < c)
!                     ix = c;
!                 else {
!                     ix = b;
!                     break;
!                 }
!             }
!         }
          return ix;
      }
--- 143,165 ----
      Data *const data;
      TableAnyMap *parent,*left,*right;
!     int n;
//! return index of data item with key <= k
      //! \note index can point past the last item!
!     unsigned int _tryix(size_t k) const
      {
!         unsigned int ix = 0,b = n;
! 		while(ix != b) {
! 			const unsigned int c = (ix+b)>>1;
! 			const size_t dk = data[c].key;
! 			if(k == dk)
! 				return c;
! 			else if(k < dk)
! 				b = c;
! 			else if(ix < c)
! 				ix = c;
! 			else
! 				return b;
! 		}
          return ix;
      }
***************
*** 168,172 ****
          if(!b->n) { 
              // remove empty branch
!             _delmap(b); b = NULL; 
          }
      }
--- 169,173 ----
          if(!b->n) { 
              // remove empty branch
!             _delmap(b); b = 0; 
          }
      }
***************
*** 181,185 ****
  {
  public:
!     TablePtrMap(): TableAnyMap(NULL,slots),count(0) {}
      virtual ~TablePtrMap() { clear(); }
--- 182,186 ----
  {
  public:
!     TablePtrMap(): TableAnyMap(0,slots),count(0) {}
      virtual ~TablePtrMap() { clear(); }
--- NEW FILE: flmap.cpp ---
/*
flext - C++ layer for Max/MSP and pd (pure data) externals
Copyright (c) 2001-2005 Thomas Grill (gr@grrrr.org)
For information on usage and redistribution, and for a DISCLAIMER OF ALL
WARRANTIES, see the file, "license.txt," in this distribution.
*/
/*! \file flmap.cpp
    \brief flext container classes.
*/
#include "flext.h"
#include "flmap.h"
TableAnyMap::~TableAnyMap() { clear(); }
void TableAnyMap::clear() 
{
    if(left) { _delmap(left); left = NULL; }
    if(right) { _delmap(right); right = NULL; }
    n = 0;
}
void *TableAnyMap::_set(int tsize,size_t k,void *t)
{
    FLEXT_ASSERT(n);
if(n < tsize) {
        // fall through
    }
    else if(k < data[0].key)
        return _toleft(tsize,k,t);
    else if(k > data[tsize-1].key)
        return _toright(tsize,k,t);
int ix = _tryix(k);
    if(ix >= n) {
        FLEXT_ASSERT(ix == n);
        // after last entry
        data[n++](k,t);
        return NULL;
    }
size_t dk = data[ix].key;
    if(k == dk) {
        // update data in existing slot (same key)
        void *a = data[ix].value;
        data[ix] = t;
        return a;
    }
    else {
        // insert new slot by shifting the higher ones
        FLEXT_ASSERT(k < dk);
        void *a;
        if(n == tsize)
            a = _toright(tsize,data[tsize-1]);
        else {
            ++n;
            a = NULL;
        }
Data *tg = data+ix;
        for(Data *d = data+n-1; d > tg; d--) d[0] = d[-1];
        (*tg)(k,t);
        return a;
    }
}
void *TableAnyMap::_find(int tsize,size_t k) const
{
    FLEXT_ASSERT(n);
    if(n < tsize) {
        // fall through
    }
    else if(k < data[0].key)
        return left?left->_find(tsize,k):NULL;
    else if(k > data[n-1].key)
        return right?right->_find(tsize,k):NULL;
const int ix = _tryix(k);
    return ix < n && data[ix].key == k?data[ix].value:NULL;
}
#ifdef FLEXT_DEBUG
void TableAnyMap::_check(int tsize)
{
    FLEXT_ASSERT(n);
size_t k = data[0].key;
    for(int i = 1; i < n; ++i) {
        size_t k2 = data[i].key;
        FLEXT_ASSERT(k < k2);
        k = k2;
    }
if(left || right) FLEXT_ASSERT(n == tsize);
if(left) { 
        FLEXT_ASSERT(flext::MemCheck(left)); 
        left->_check(tsize); 
    }
    if(right) { 
        FLEXT_ASSERT(flext::MemCheck(right)); 
        right->_check(tsize); 
    }
}
#endif
void *TableAnyMap::_remove(int tsize,size_t k)
{
    FLEXT_ASSERT(n);
    if(n < tsize) {
        // fall through
    }
    else if(k < data[0].key) {
        void *r = left?left->_remove(tsize,k):NULL;
        if(r) _eraseempty(left);
        return r;
    }
    else if(k > data[n-1].key) {
        void *r = right?right->_remove(tsize,k):NULL;
        if(r) _eraseempty(right);
        return r;
    }
const int ix = _tryix(k);
    if(ix >= n || data[ix].key != k)
        return NULL;
    else {
        // found key in this map
        void *ret = data[ix].value;
Data dt;
        bool fnd,ins = false;
        if(n >= tsize) {
            // if this table is full get fill-in elements from branches
            if(left) {
                // try to get biggest element from left branch
                left->_getbig(dt);
                _eraseempty(left);
                fnd = true,ins = true;
            }
            else if(right) {
                // try to get smallest element from right branch
                right->_getsmall(dt);
                _eraseempty(right);
                fnd = true;
            }
            else
                fnd = false;
        }
        else fnd = false;
if(ins) {
            // insert smaller element from left
            for(int i = ix; i; --i) data[i] = data[i-1];
            data[0] = dt;
        }
        else {
            // shift elements
            for(int i = ix+1; i < n; ++i) data[i-1] = data[i];
            // insert bigger element from right or reduce table size
            if(fnd)
                data[n-1] = dt;
            else
                --n;
        }
return ret;
    }
}
void TableAnyMap::_getbig(Data &dt)
{
    FLEXT_ASSERT(n);
if(right) {
        right->_getbig(dt);
        _eraseempty(right);
    }
    else {
        dt = data[n-1];
        if(left) {
            for(int i = n-1; i; --i) data[i] = data[i-1];
            left->_getbig(data[0]);
            _eraseempty(left);
        }
        else
            --n;
    }
}
void TableAnyMap::_getsmall(Data &dt)
{
    FLEXT_ASSERT(n);
if(left) {
        left->_getsmall(dt);
        _eraseempty(left);
    }
    else {
        dt = data[0];
        for(int i = 1; i < n; ++i) data[i-1] = data[i];
        if(right) {
            right->_getsmall(data[n-1]);
            _eraseempty(right);
        }
        else
            --n;
    }
}
void TableAnyMap::iterator::forward() 
{ 
    if(map || ix >= map->n) {
        if(++ix >= map->n) {
            TableAnyMap *nmap;
// we reached the end of the slots
            if(map->right) {
                // climb up one
                map = map->right;
                leftmost();
                ix = 0;
            }
            else {
                // fall back
                for(;;) {
                    nmap = map->parent;
                    if(!nmap) break; // no parent
                    if(nmap->left == map) {
                        // ok, we are in front of the slots now
                        ix = 0;
                        map = nmap;
                        break;
                    }
                    else {
                        FLEXT_ASSERT(nmap->right == map);
                        ix = (map = nmap)->n;
                    }
                }
            }
        }
    }
}