diff options
Diffstat (limited to 'aapl/bstcommon.h')
| -rw-r--r-- | aapl/bstcommon.h | 814 |
1 files changed, 814 insertions, 0 deletions
diff --git a/aapl/bstcommon.h b/aapl/bstcommon.h new file mode 100644 index 0000000..624b072 --- /dev/null +++ b/aapl/bstcommon.h @@ -0,0 +1,814 @@ +/* + * Copyright 2001 Adrian Thurston <thurston@complang.org> + */ + +/* 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 */ +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. + */ + BstTable() { } + + /** + * \brief Construct with initial value. + * + * Constructs a binary search table with an initial item. Uses the default + * constructor for initializing Value. + */ + BstTable(const Key &key) + { insert(key); } + +#if defined( BSTMAP ) + /** + * \brief Construct with initial value. + * + * Constructs a binary search table with an initial key/value pair. + */ + BstTable(const Key &key, const Value &val) + { insert(key, val); } +#endif + +#if ! defined( BSTSET ) + /** + * \brief Construct with initial value. + * + * Constructs a binary search table with an initial Element. + */ + BstTable(const Element &el) + { insert(el); } +#endif + + 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); + + /* The following provide access to the underlying insert and remove + * functions that my be hidden by the BST insert and remove. The insertDup + * and insertNew functions will never be hidden. They are provided for + * consistency. The difference between the non-shared and the shared + * tables is the documentation reference to the invoked function. */ + +#if !defined( SHARED_BST ) + /*@{*/ + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes Vector::insert( long pos, const T &val ). + */ + void vinsert(long pos, const Element &val) + { Vector< Element, Resize >::insert( pos, &val, 1 ); } + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes Vector::insert( long pos, const T *val, long len ). + */ + void vinsert(long pos, const Element *val, long len) + { Vector< Element, Resize >::insert( pos, val, len ); } + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes Vector::insert( long pos, const Vector &v ). + */ + void vinsert(long pos, const BstTable &v) + { Vector< Element, Resize >::insert( pos, v.data, v.tabLen ); } + + /*@}*/ + + /*@{*/ + + /** \brief Call the remove of the underlying vector. + * + * Provides access to the vector remove, which may become hidden. + * Invokes Vector::remove( long pos ). + */ + void vremove(long pos) + { Vector< Element, Resize >::remove( pos, 1 ); } + + /** \brief Call the remove of the underlying vector. + * + * Proves access to the vector remove, which may become hidden. + * Invokes Vector::remove( long pos, long len ). + */ + void vremove(long pos, long len) + { Vector< Element, Resize >::remove( pos, len ); } + + /*@}*/ +#else /* SHARED_BST */ + /*@{*/ + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes SVector::insert( long pos, const T &val ). + */ + void vinsert(long pos, const Element &val) + { Vector< Element, Resize >::insert( pos, &val, 1 ); } + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes SVector::insert( long pos, const T *val, long len ). + */ + void vinsert(long pos, const Element *val, long len) + { Vector< Element, Resize >::insert( pos, val, len ); } + + /** \brief Call the insert of the underlying vector. + * + * Provides to access to the vector insert, which may become hidden. Care + * should be taken to ensure that after the insert the ordering of + * elements is preserved. + * Invokes SVector::insert( long pos, const SVector &v ). + */ + void vinsert(long pos, const BstTable &v) + { Vector< Element, Resize >::insert( pos, v.data, v.length() ); } + + /*@}*/ + + /*@{*/ + + /** \brief Call the remove of the underlying vector. + * + * Provides access to the vector remove, which may become hidden. + * Invokes SVector::remove( long pos ). + */ + void vremove(long pos) + { Vector< Element, Resize >::remove( pos, 1 ); } + + /** \brief Call the remove of the underlying vector. + * + * Proves access to the vector remove, which may become hidden. + * Invokes SVector::remove( long pos, long len ). + */ + void vremove(long pos, long len) + { Vector< Element, Resize >::remove( pos, len ); } + + /*@}*/ + +#endif /* SHARED_BST */ +}; + + +#if 0 +#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>:: + 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 +#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>:: + 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>:: + 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>:: + 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>:: + 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 = this->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 && + this->compare(key, GET_KEY(*lower)) == 0 ) + lower--; + + upper = mid + 1; + while ( upper != highEnd && + this->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>:: + 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 = this->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>:: + 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 = this->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>:: + 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>:: + 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>:: + 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>:: + 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>:: + 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 = this->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 |