Logo Search packages:      
Sourcecode: ragel version File versions

bstcommon.h

/*
 *  Copyright 2001 Adrian Thurston <adriant@ragel.ca>
 */

/*  This file is part of Aapl.
 *
 *  Aapl is free software; you can redistribute it and/or modify it under the
 *  terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 2.1 of the License, or (at your option)
 *  any later version.
 *
 *  Aapl 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 Lesser General Public License for
 *  more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
 *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */

/* This header is not wrapped in ifndefs because it is
 * not intended to be included by users directly. */

#ifdef AAPL_NAMESPACE
namespace Aapl {
#endif

/* Binary Search Table */
00030 template < BST_TEMPL_DECLARE > class BstTable :
            public Compare,
            public Vector< Element, Resize >
{
      typedef Vector<Element, Resize> BaseVector;
      typedef Table<Element> BaseTable;

public:
      /**
       * \brief Default constructor.
       *
       * Create an empty binary search table.
       */
00043       BstTable() { }

      BstTable(long allocLen);

      Element *insert(const Key &key, Element **lastFound = 0);
      Element *insertMulti(const Key &key);

      bool insert(const BstTable &other);
      void insertMulti(const BstTable &other);

#if defined( BSTMAP )
      Element *insert(const Key &key, const Value &val, 
                  Element **lastFound = 0);
      Element *insertMulti(const Key &key, const Value &val );
#endif

#if ! defined( BSTSET )
      Element *insert(const Element &el, Element **lastFound = 0);
      Element *insertMulti(const Element &el);
#endif

      Element *find(const Key &key, Element **lastFound = 0) const;
      bool findMulti( const Key &key, Element *&lower,
                  Element *&upper ) const;

      bool remove(const Key &key);
      bool remove(Element *item);
      long removeMulti(const Key &key);
      long removeMulti(Element *lower, Element *upper);
};


#if defined( SHARED_BST )
/**
 * \brief Construct a binary search table with an initial amount of
 * allocation.
 *
 * The table is initialized to have room for allocLength elements. The
 * table starts empty.
 */
template <BST_TEMPL_DEF> BstTable<BST_TEMPL_USE>::
		BstTable( long allocLen ) 
{
      /* Allocate the space if we are given a positive allocLen. */
      if ( allocLen > 0 ) {
            /* Allocate the data needed. */
            STabHead *head = (STabHead*) 
                        malloc( sizeof(STabHead) + sizeof(Element) * allocLen );
            if ( head == 0 )
                  throw std::bad_alloc();

            /* Set up the header and save the data pointer. */
            head->refCount = 1;
            head->allocLen = allocLen;
            head->tabLen = 0;
            BaseTable::data = (Element*) (head + 1);
      }
}
#else
/**
 * \brief Construct a binary search table with an initial amount of
 * allocation.
 *
 * The table is initialized to have room for allocLength elements. The
 * table starts empty.
 */
template <BST_TEMPL_DEF> BstTable<BST_TEMPL_USE>::
00110 		BstTable( long allocLen ) 
{
      /* Allocate the space if we are given a positive allocLen. */
      BaseTable::allocLen = allocLen;
      if ( BaseTable::allocLen > 0 ) {
            BaseTable::data = (Element*) malloc(sizeof(Element) * BaseTable::allocLen);
            if ( BaseTable::data == NULL )
                  throw std::bad_alloc();
      }
}

#endif

/**
 * \brief Find the element with the given key and remove it.
 *
 * If multiple elements with the given key exist, then it is unspecified which
 * element will be removed.
 *
 * \returns True if an element is found and consequently removed, false
 * otherwise.
 */
template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
00133 		remove(const Key &key)
{
      Element *el = find(key);
      if ( el != 0 ) {
            Vector< Element >::remove(el - BaseTable::data);
            return true;
      }
      return false;
}

/**
 * \brief Remove the element pointed to by item.
 *
 * If item does not point to an element in the tree, then undefined behaviour
 * results. If item is null, then remove has no effect.
 *
 * \returns True if item is not null, false otherwise.
 */
template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
00152 		remove( Element *item )
{
      if ( item != 0 ) {
            Vector< Element >::remove(item - BaseTable::data);
            return true;
      }
      return false;
}

/**
 * \brief Find and remove the entire range of elements with the given key.
 *
 * \returns The number of elements removed.
 */
template <BST_TEMPL_DEF> long BstTable<BST_TEMPL_USE>::
00167 		removeMulti(const Key &key)
{
      Element *low, *high;
      if ( findMulti(key, low, high) ) {
            /* Get the length of the range. */
            long num = high - low + 1;
            Vector< Element >::remove(low - BaseTable::data, num);
            return num;
      }

      return 0;
}

template <BST_TEMPL_DEF> long BstTable<BST_TEMPL_USE>::
		removeMulti(Element *lower, Element *upper)
{
      /* Get the length of the range. */
      long num = upper - lower + 1;
      Vector< Element >::remove(lower - BaseTable::data, num);
      return num;
}


/**
 * \brief Find a range of elements with the given key.
 *
 * If any elements with the given key exist then lower and upper are set to
 * the low and high ends of the continous range of elements with the key.
 * Lower and upper will point to the first and last elements with the key.
 *
 * \returns True if any elements are found, false otherwise.
 */
template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
00200 		findMulti(const Key &key, Element *&low, Element *&high ) const
{
      const Element *lower, *mid, *upper;
      long keyRelation;
      const long tblLen = BaseTable::length();

      if ( BaseTable::data == 0 )
            return false;

      lower = BaseTable::data;
      upper = BaseTable::data + tblLen - 1;
      while ( true ) {
            if ( upper < lower ) {
                  /* Did not find the fd in the array. */
                  return false;
            }

            mid = lower + ((upper-lower)>>1);
            keyRelation = compare(key, GET_KEY(*mid));

            if ( keyRelation < 0 )
                  upper = mid - 1;
            else if ( keyRelation > 0 )
                  lower = mid + 1;
            else {
                  Element *lowEnd = BaseTable::data - 1;
                  Element *highEnd = BaseTable::data + tblLen;

                  lower = mid - 1;
                  while ( lower != lowEnd && 
                              compare(key, GET_KEY(*lower)) == 0 )
                        lower--;

                  upper = mid + 1;
                  while ( upper != highEnd && 
                              compare(key, GET_KEY(*upper)) == 0 )
                        upper++;
                  
                  low = (Element*)lower + 1;
                  high = (Element*)upper - 1;
                  return true;
            }
      }
}

/**
 * \brief Find an element with the given key.
 *
 * If the find succeeds then lastFound is set to the element found. If the
 * find fails then lastFound is set the location where the key would be
 * inserted. If there is more than one element in the tree with the given key,
 * then it is unspecified which element is returned as the match.
 *
 * \returns The element found on success, null on failure.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
00256 		find( const Key &key, Element **lastFound ) const
{
      const Element *lower, *mid, *upper;
      long keyRelation;
      const long tblLen = BaseTable::length();

      if ( BaseTable::data == 0 )
            return 0;

      lower = BaseTable::data;
      upper = BaseTable::data + tblLen - 1;
      while ( true ) {
            if ( upper < lower ) {
                  /* Did not find the key. Last found gets the insert location. */
                  if ( lastFound != 0 )
                        *lastFound = (Element*)lower;
                  return 0;
            }

            mid = lower + ((upper-lower)>>1);
            keyRelation = compare(key, GET_KEY(*mid));

            if ( keyRelation < 0 )
                  upper = mid - 1;
            else if ( keyRelation > 0 )
                  lower = mid + 1;
            else {
                  /* Key is found. Last found gets the found record. */
                  if ( lastFound != 0 )
                        *lastFound = (Element*)mid;
                  return (Element*)mid;
            }
      }
}

template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
00292 		insert(const Key &key, Element **lastFound)
{
      const Element *lower, *mid, *upper;
      long keyRelation, insertPos;
      const long tblLen = BaseTable::length();

      if ( tblLen == 0 ) {
            /* If the table is empty then go straight to insert. */
            lower = BaseTable::data;
            goto insert;
      }

      lower = BaseTable::data;
      upper = BaseTable::data + tblLen - 1;
      while ( true ) {
            if ( upper < lower ) {
                  /* Did not find the key in the array.
                   * Place to insert at is lower. */
                  goto insert;
            }

            mid = lower + ((upper-lower)>>1);
            keyRelation = compare(key, GET_KEY(*mid));

            if ( keyRelation < 0 )
                  upper = mid - 1;
            else if ( keyRelation > 0 )
                  lower = mid + 1;
            else {
                  if ( lastFound != 0 )
                        *lastFound = (Element*)mid;
                  return 0;
            }
      }

insert:
      /* Get the insert pos. */
      insertPos = lower - BaseTable::data;

      /* Do the insert. After makeRawSpaceFor, lower pointer is no good. */
      BaseVector::makeRawSpaceFor(insertPos, 1);
      new(BaseTable::data + insertPos) Element(key);

      /* Set lastFound */
      if ( lastFound != 0 )
            *lastFound = BaseTable::data + insertPos;
      return BaseTable::data + insertPos;
}


template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
00343 		insertMulti(const Key &key)
{
      const Element *lower, *mid, *upper;
      long keyRelation, insertPos;
      const long tblLen = BaseTable::length();

      if ( tblLen == 0 ) {
            /* If the table is empty then go straight to insert. */
            lower = BaseTable::data;
            goto insert;
      }

      lower = BaseTable::data;
      upper = BaseTable::data + tblLen - 1;
      while ( true ) {
            if ( upper < lower ) {
                  /* Did not find the key in the array.
                   * Place to insert at is lower. */
                  goto insert;
            }

            mid = lower + ((upper-lower)>>1);
            keyRelation = compare(key, GET_KEY(*mid));

            if ( keyRelation < 0 )
                  upper = mid - 1;
            else if ( keyRelation > 0 )
                  lower = mid + 1;
            else {
                  lower = mid;
                  goto insert;
            }
      }

insert:
      /* Get the insert pos. */
      insertPos = lower - BaseTable::data;

      /* Do the insert. */
      BaseVector::makeRawSpaceFor(insertPos, 1);
      new(BaseTable::data + insertPos) Element(key);

      /* Return the element inserted. */
      return BaseTable::data + insertPos;
}

/**
 * \brief Insert each element from other.
 *
 * Always attempts to insert all elements even if the insert of some item from
 * other fails.
 *
 * \returns True if all items inserted successfully, false if any insert
 * failed.
 */
template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
00399 		insert(const BstTable &other)
{
      bool allSuccess = true;
      long otherLen = other.length();
      for ( long i = 0; i < otherLen; i++ ) {
            Element *el = insert( other.data[i] );
            if ( el == 0 )
                  allSuccess = false;
      }
      return allSuccess;
}

/**
 * \brief Insert each element from other even if the elements exist already.
 *
 * No individual insertMulti can fail.
 */
template <BST_TEMPL_DEF> void BstTable<BST_TEMPL_USE>::
00417 		insertMulti(const BstTable &other)
{
      long otherLen = other.length();
      for ( long i = 0; i < otherLen; i++ )
            insertMulti( other.data[i] );
}

#if ! defined( BSTSET )

/**
 * \brief Insert the given element.
 *
 * If the key in the given element does not already exist in the table then a
 * new element is inserted. They element copy constructor is used to place the
 * element into the table. If lastFound is given, it is set to the new element
 * created. If the insert fails then lastFound is set to the existing element
 * of the same key.
 *
 * \returns The new element created upon success, null upon failure.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
00438 		insert(const Element &el, Element **lastFound )
{
      const Element *lower, *mid, *upper;
      long keyRelation, insertPos;
      const long tblLen = BaseTable::length();

      if ( tblLen == 0 ) {
            /* If the table is empty then go straight to insert. */
            lower = BaseTable::data;
            goto insert;
      }

      lower = BaseTable::data;
      upper = BaseTable::data + tblLen - 1;
      while ( true ) {
            if ( upper < lower ) {
                  /* Did not find the key in the array.
                   * Place to insert at is lower. */
                  goto insert;
            }

            mid = lower + ((upper-lower)>>1);
            keyRelation = compare(GET_KEY(el), GET_KEY(*mid));

            if ( keyRelation < 0 )
                  upper = mid - 1;
            else if ( keyRelation > 0 )
                  lower = mid + 1;
            else {
                  if ( lastFound != 0 )
                        *lastFound = (Element*)mid;
                  return 0;
            }
      }

insert:
      /* Get the insert pos. */
      insertPos = lower - BaseTable::data;

      /* Do the insert. After makeRawSpaceFor, lower pointer is no good. */
      BaseVector::makeRawSpaceFor(insertPos, 1);
      new(BaseTable::data + insertPos) Element(el);

      /* Set lastFound */
      if ( lastFound != 0 )
            *lastFound = BaseTable::data + insertPos;
      return BaseTable::data + insertPos;
}

/**
 * \brief Insert the given element even if it exists already.
 *
 * If the key in the given element exists already then the new element is
 * placed next to some other element of the same key. InsertMulti cannot fail.
 * The element copy constructor is used to place the element in the table.
 *
 * \returns The new element created.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
00497 		insertMulti(const Element &el)
{
      const Element *lower, *mid, *upper;
      long keyRelation, insertPos;
      const long tblLen = BaseTable::length();

      if ( tblLen == 0 ) {
            /* If the table is empty then go straight to insert. */
            lower = BaseTable::data;
            goto insert;
      }

      lower = BaseTable::data;
      upper = BaseTable::data + tblLen - 1;
      while ( true ) {
            if ( upper < lower ) {
                  /* Did not find the fd in the array.
                   * Place to insert at is lower. */
                  goto insert;
            }

            mid = lower + ((upper-lower)>>1);
            keyRelation = compare(GET_KEY(el), GET_KEY(*mid));

            if ( keyRelation < 0 )
                  upper = mid - 1;
            else if ( keyRelation > 0 )
                  lower = mid + 1;
            else {
                  lower = mid;
                  goto insert;
            }
      }

insert:
      /* Get the insert pos. */
      insertPos = lower - BaseTable::data;

      /* Do the insert. */
      BaseVector::makeRawSpaceFor(insertPos, 1);
      new(BaseTable::data + insertPos) Element(el);

      /* Return the element inserted. */
      return BaseTable::data + insertPos;
}
#endif


#if defined( BSTMAP )

/**
 * \brief Insert the given key-value pair.
 *
 * If the given key does not already exist in the table then the key-value
 * pair is inserted. Copy constructors are used to place the pair in the
 * table. If lastFound is given, it is set to the new entry created. If the
 * insert fails then lastFound is set to the existing pair of the same key.
 *
 * \returns The new element created upon success, null upon failure.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
		insert(const Key &key, const Value &val, Element **lastFound)
{
      const Element *lower, *mid, *upper;
      long keyRelation, insertPos;
      const long tblLen = BaseTable::length();

      if ( tblLen == 0 ) {
            /* If the table is empty then go straight to insert. */
            lower = BaseTable::data;
            goto insert;
      }

      lower = BaseTable::data;
      upper = BaseTable::data + tblLen - 1;
      while ( true ) {
            if ( upper < lower ) {
                  /* Did not find the fd in the array.
                   * Place to insert at is lower. */
                  goto insert;
            }

            mid = lower + ((upper-lower)>>1);
            keyRelation = Compare::compare(key, mid->key);

            if ( keyRelation < 0 )
                  upper = mid - 1;
            else if ( keyRelation > 0 )
                  lower = mid + 1;
            else {
                  if ( lastFound != NULL )
                        *lastFound = (Element*)mid;
                  return 0;
            }
      }

insert:
      /* Get the insert pos. */
      insertPos = lower - BaseTable::data;

      /* Do the insert. */
      BaseVector::makeRawSpaceFor(insertPos, 1);
      new(BaseTable::data + insertPos) Element(key, val);

      /* Set lastFound */
      if ( lastFound != NULL )
            *lastFound = BaseTable::data + insertPos;
      return BaseTable::data + insertPos;
}


/**
 * \brief Insert the given key-value pair even if the key exists already.
 *
 * If the key exists already then the key-value pair is placed next to some
 * other pair of the same key. InsertMulti cannot fail. Copy constructors are
 * used to place the pair in the table.
 *
 * \returns The new element created.
 */
template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
		insertMulti(const Key &key, const Value &val)
{
      const Element *lower, *mid, *upper;
      long keyRelation, insertPos;
      const long tblLen = BaseTable::length();

      if ( tblLen == 0 ) {
            /* If the table is empty then go straight to insert. */
            lower = BaseTable::data;
            goto insert;
      }

      lower = BaseTable::data;
      upper = BaseTable::data + tblLen - 1;
      while ( true ) {
            if ( upper < lower ) {
                  /* Did not find the key in the array. 
                   * Place to insert at is lower. */
                  goto insert;
            }

            mid = lower + ((upper-lower)>>1);
            keyRelation = Compare::compare(key, mid->key);

            if ( keyRelation < 0 )
                  upper = mid - 1;
            else if ( keyRelation > 0 )
                  lower = mid + 1;
            else {
                  lower = mid;
                  goto insert;
            }
      }

insert:
      /* Get the insert pos. */
      insertPos = lower - BaseTable::data;

      /* Do the insert. */
      BaseVector::makeRawSpaceFor(insertPos, 1);
      new(BaseTable::data + insertPos) Element(key, val);

      /* Return the element inserted. */
      return BaseTable::data + insertPos;
}

#endif

#ifdef AAPL_NAMESPACE
}
#endif

Generated by  Doxygen 1.6.0   Back to index