aapl/bstcommon.h

   1 /*
   2  *  Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Aapl.
   6  *
   7  *  Aapl is free software; you can redistribute it and/or modify it under the
   8  *  terms of the GNU Lesser General Public License as published by the Free
   9  *  Software Foundation; either version 2.1 of the License, or (at your option)
  10  *  any later version.
  11  *
  12  *  Aapl is distributed in the hope that it will be useful, but WITHOUT ANY
  13  *  WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  *  FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
  15  *  more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public License
  18  *  along with Aapl; if not, write to the Free Software Foundation, Inc., 59
  19  *  Temple Place, Suite 330, Boston, MA 02111-1307 USA
  20  */
  21
  22 /* This header is not wrapped in ifndefs because it is
  23  * not intended to be included by users directly. */
  24
  25 #ifdef AAPL_NAMESPACE
  26 namespace Aapl {
  27 #endif
  28
  29 /* Binary Search Table */
  30 template < BST_TEMPL_DECLARE > class BstTable :
  31                 public Compare,
  32                 public Vector< Element, Resize >
  33 {
  34         typedef Vector<Element, Resize> BaseVector;
  35         typedef Table<Element> BaseTable;
  36
  37 public:
  38         /**
  39          * \brief Default constructor.
  40          *
  41          * Create an empty binary search table.
  42          */
  43         BstTable() { }
  44
  45         /**
  46          * \brief Construct with initial value.
  47          *
  48          * Constructs a binary search table with an initial item. Uses the default
  49          * constructor for initializing Value.
  50          */
  51         BstTable(const Key &key)
  52                 { insert(key); }
  53
  54 #if defined( BSTMAP )
  55         /**
  56          * \brief Construct with initial value.
  57          *
  58          * Constructs a binary search table with an initial key/value pair.
  59          */
  60         BstTable(const Key &key, const Value &val)
  61                 { insert(key, val); }
  62 #endif
  63
  64 #if ! defined( BSTSET )
  65         /**
  66          * \brief Construct with initial value.
  67          *
  68          * Constructs a binary search table with an initial Element.
  69          */
  70         BstTable(const Element &el)
  71                 { insert(el); }
  72 #endif
  73
  74         Element *insert(const Key &key, Element **lastFound = 0);
  75         Element *insertMulti(const Key &key);
  76
  77         bool insert(const BstTable &other);
  78         void insertMulti(const BstTable &other);
  79
  80 #if defined( BSTMAP )
  81         Element *insert(const Key &key, const Value &val,
  82                         Element **lastFound = 0);
  83         Element *insertMulti(const Key &key, const Value &val );
  84 #endif
  85
  86 #if ! defined( BSTSET )
  87         Element *insert(const Element &el, Element **lastFound = 0);
  88         Element *insertMulti(const Element &el);
  89 #endif
  90
  91         Element *find(const Key &key, Element **lastFound = 0) const;
  92         bool findMulti( const Key &key, Element *&lower,
  93                         Element *&upper ) const;
  94
  95         bool remove(const Key &key);
  96         bool remove(Element *item);
  97         long removeMulti(const Key &key);
  98         long removeMulti(Element *lower, Element *upper);
  99
 100         /* The following provide access to the underlying insert and remove
 101          * functions that my be hidden by the BST insert and remove. The insertDup
 102          * and insertNew functions will never be hidden. They are provided for
 103          * consistency. The difference between the non-shared and the shared
 104          * tables is the documentation reference to the invoked function. */
 105
 106 #if !defined( SHARED_BST )
 107         /*@{*/
 108
 109         /** \brief Call the insert of the underlying vector.
 110          *
 111          * Provides to access to the vector insert, which may become hidden. Care
 112          * should be taken to ensure that after the insert the ordering of
 113          * elements is preserved.
 114          * Invokes Vector::insert( long pos, const T &val ).
 115          */
 116         void vinsert(long pos, const Element &val)
 117                 { Vector< Element, Resize >::insert( pos, &val, 1 ); }
 118
 119         /** \brief Call the insert of the underlying vector.
 120          *
 121          * Provides to access to the vector insert, which may become hidden. Care
 122          * should be taken to ensure that after the insert the ordering of
 123          * elements is preserved.
 124          * Invokes Vector::insert( long pos, const T *val, long len ).
 125          */
 126         void vinsert(long pos, const Element *val, long len)
 127                 { Vector< Element, Resize >::insert( pos, val, len ); }
 128
 129         /** \brief Call the insert of the underlying vector.
 130          *
 131          * Provides to access to the vector insert, which may become hidden. Care
 132          * should be taken to ensure that after the insert the ordering of
 133          * elements is preserved.
 134          * Invokes Vector::insert( long pos, const Vector &v ).
 135          */
 136         void vinsert(long pos, const BstTable &v)
 137                 { Vector< Element, Resize >::insert( pos, v.data, v.tabLen ); }
 138
 139         /*@}*/
 140
 141         /*@{*/
 142
 143         /** \brief Call the remove of the underlying vector.
 144          *
 145          *      Provides access to the vector remove, which may become hidden.
 146          *      Invokes Vector::remove( long pos ).
 147          */
 148         void vremove(long pos)
 149                 { Vector< Element, Resize >::remove( pos, 1 ); }
 150
 151         /** \brief Call the remove of the underlying vector.
 152          *
 153          * Proves access to the vector remove, which may become hidden.
 154          * Invokes Vector::remove( long pos, long len ).
 155          */
 156         void vremove(long pos, long len)
 157                 { Vector< Element, Resize >::remove( pos, len ); }
 158
 159         /*@}*/
 160 #else /* SHARED_BST */
 161         /*@{*/
 162
 163         /** \brief Call the insert of the underlying vector.
 164          *
 165          * Provides to access to the vector insert, which may become hidden. Care
 166          * should be taken to ensure that after the insert the ordering of
 167          * elements is preserved.
 168          * Invokes SVector::insert( long pos, const T &val ).
 169          */
 170         void vinsert(long pos, const Element &val)
 171                 { Vector< Element, Resize >::insert( pos, &val, 1 ); }
 172
 173         /** \brief Call the insert of the underlying vector.
 174          *
 175          * Provides to access to the vector insert, which may become hidden. Care
 176          * should be taken to ensure that after the insert the ordering of
 177          * elements is preserved.
 178          * Invokes SVector::insert( long pos, const T *val, long len ).
 179          */
 180         void vinsert(long pos, const Element *val, long len)
 181                 { Vector< Element, Resize >::insert( pos, val, len ); }
 182
 183         /** \brief Call the insert of the underlying vector.
 184          *
 185          * Provides to access to the vector insert, which may become hidden. Care
 186          * should be taken to ensure that after the insert the ordering of
 187          * elements is preserved.
 188          * Invokes SVector::insert( long pos, const SVector &v ).
 189          */
 190         void vinsert(long pos, const BstTable &v)
 191                 { Vector< Element, Resize >::insert( pos, v.data, v.length() ); }
 192
 193         /*@}*/
 194
 195         /*@{*/
 196
 197         /** \brief Call the remove of the underlying vector.
 198          *
 199          *      Provides access to the vector remove, which may become hidden.
 200          *      Invokes SVector::remove( long pos ).
 201          */
 202         void vremove(long pos)
 203                 { Vector< Element, Resize >::remove( pos, 1 ); }
 204
 205         /** \brief Call the remove of the underlying vector.
 206          *
 207          * Proves access to the vector remove, which may become hidden.
 208          * Invokes SVector::remove( long pos, long len ).
 209          */
 210         void vremove(long pos, long len)
 211                 { Vector< Element, Resize >::remove( pos, len ); }
 212
 213         /*@}*/
 214
 215 #endif /* SHARED_BST */
 216 };
 217
 218
 219 #if 0
 220 #if defined( SHARED_BST )
 221 /**
 222  * \brief Construct a binary search table with an initial amount of
 223  * allocation.
 224  *
 225  * The table is initialized to have room for allocLength elements. The
 226  * table starts empty.
 227  */
 228 template <BST_TEMPL_DEF> BstTable<BST_TEMPL_USE>::
 229                 BstTable( long allocLen )
 230 {
 231         /* Allocate the space if we are given a positive allocLen. */
 232         if ( allocLen > 0 ) {
 233                 /* Allocate the data needed. */
 234                 STabHead *head = (STabHead*)
 235                                 malloc( sizeof(STabHead) + sizeof(Element) * allocLen );
 236                 if ( head == 0 )
 237                         throw std::bad_alloc();
 238
 239                 /* Set up the header and save the data pointer. */
 240                 head->refCount = 1;
 241                 head->allocLen = allocLen;
 242                 head->tabLen = 0;
 243                 BaseTable::data = (Element*) (head + 1);
 244         }
 245 }
 246 #else
 247 /**
 248  * \brief Construct a binary search table with an initial amount of
 249  * allocation.
 250  *
 251  * The table is initialized to have room for allocLength elements. The
 252  * table starts empty.
 253  */
 254 template <BST_TEMPL_DEF> BstTable<BST_TEMPL_USE>::
 255                 BstTable( long allocLen )
 256 {
 257         /* Allocate the space if we are given a positive allocLen. */
 258         BaseTable::allocLen = allocLen;
 259         if ( BaseTable::allocLen > 0 ) {
 260                 BaseTable::data = (Element*) malloc(sizeof(Element) * BaseTable::allocLen);
 261                 if ( BaseTable::data == NULL )
 262                         throw std::bad_alloc();
 263         }
 264 }
 265
 266 #endif
 267 #endif
 268
 269 /**
 270  * \brief Find the element with the given key and remove it.
 271  *
 272  * If multiple elements with the given key exist, then it is unspecified which
 273  * element will be removed.
 274  *
 275  * \returns True if an element is found and consequently removed, false
 276  * otherwise.
 277  */
 278 template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
 279                 remove(const Key &key)
 280 {
 281         Element *el = find(key);
 282         if ( el != 0 ) {
 283                 Vector< Element >::remove(el - BaseTable::data);
 284                 return true;
 285         }
 286         return false;
 287 }
 288
 289 /**
 290  * \brief Remove the element pointed to by item.
 291  *
 292  * If item does not point to an element in the tree, then undefined behaviour
 293  * results. If item is null, then remove has no effect.
 294  *
 295  * \returns True if item is not null, false otherwise.
 296  */
 297 template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
 298                 remove( Element *item )
 299 {
 300         if ( item != 0 ) {
 301                 Vector< Element >::remove(item - BaseTable::data);
 302                 return true;
 303         }
 304         return false;
 305 }
 306
 307 /**
 308  * \brief Find and remove the entire range of elements with the given key.
 309  *
 310  * \returns The number of elements removed.
 311  */
 312 template <BST_TEMPL_DEF> long BstTable<BST_TEMPL_USE>::
 313                 removeMulti(const Key &key)
 314 {
 315         Element *low, *high;
 316         if ( findMulti(key, low, high) ) {
 317                 /* Get the length of the range. */
 318                 long num = high - low + 1;
 319                 Vector< Element >::remove(low - BaseTable::data, num);
 320                 return num;
 321         }
 322
 323         return 0;
 324 }
 325
 326 template <BST_TEMPL_DEF> long BstTable<BST_TEMPL_USE>::
 327                 removeMulti(Element *lower, Element *upper)
 328 {
 329         /* Get the length of the range. */
 330         long num = upper - lower + 1;
 331         Vector< Element >::remove(lower - BaseTable::data, num);
 332         return num;
 333 }
 334
 335
 336 /**
 337  * \brief Find a range of elements with the given key.
 338  *
 339  * If any elements with the given key exist then lower and upper are set to
 340  * the low and high ends of the continous range of elements with the key.
 341  * Lower and upper will point to the first and last elements with the key.
 342  *
 343  * \returns True if any elements are found, false otherwise.
 344  */
 345 template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
 346                 findMulti(const Key &key, Element *&low, Element *&high ) const
 347 {
 348         const Element *lower, *mid, *upper;
 349         long keyRelation;
 350         const long tblLen = BaseTable::length();
 351
 352         if ( BaseTable::data == 0 )
 353                 return false;
 354
 355         lower = BaseTable::data;
 356         upper = BaseTable::data + tblLen - 1;
 357         while ( true ) {
 358                 if ( upper < lower ) {
 359                         /* Did not find the fd in the array. */
 360                         return false;
 361                 }
 362
 363                 mid = lower + ((upper-lower)>>1);
 364                 keyRelation = compare(key, GET_KEY(*mid));
 365
 366                 if ( keyRelation < 0 )
 367                         upper = mid - 1;
 368                 else if ( keyRelation > 0 )
 369                         lower = mid + 1;
 370                 else {
 371                         Element *lowEnd = BaseTable::data - 1;
 372                         Element *highEnd = BaseTable::data + tblLen;
 373
 374                         lower = mid - 1;
 375                         while ( lower != lowEnd &&
 376                                         compare(key, GET_KEY(*lower)) == 0 )
 377                                 lower--;
 378
 379                         upper = mid + 1;
 380                         while ( upper != highEnd &&
 381                                         compare(key, GET_KEY(*upper)) == 0 )
 382                                 upper++;
 383
 384                         low = (Element*)lower + 1;
 385                         high = (Element*)upper - 1;
 386                         return true;
 387                 }
 388         }
 389 }
 390
 391 /**
 392  * \brief Find an element with the given key.
 393  *
 394  * If the find succeeds then lastFound is set to the element found. If the
 395  * find fails then lastFound is set the location where the key would be
 396  * inserted. If there is more than one element in the tree with the given key,
 397  * then it is unspecified which element is returned as the match.
 398  *
 399  * \returns The element found on success, null on failure.
 400  */
 401 template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
 402                 find( const Key &key, Element **lastFound ) const
 403 {
 404         const Element *lower, *mid, *upper;
 405         long keyRelation;
 406         const long tblLen = BaseTable::length();
 407
 408         if ( BaseTable::data == 0 )
 409                 return 0;
 410
 411         lower = BaseTable::data;
 412         upper = BaseTable::data + tblLen - 1;
 413         while ( true ) {
 414                 if ( upper < lower ) {
 415                         /* Did not find the key. Last found gets the insert location. */
 416                         if ( lastFound != 0 )
 417                                 *lastFound = (Element*)lower;
 418                         return 0;
 419                 }
 420
 421                 mid = lower + ((upper-lower)>>1);
 422                 keyRelation = compare(key, GET_KEY(*mid));
 423
 424                 if ( keyRelation < 0 )
 425                         upper = mid - 1;
 426                 else if ( keyRelation > 0 )
 427                         lower = mid + 1;
 428                 else {
 429                         /* Key is found. Last found gets the found record. */
 430                         if ( lastFound != 0 )
 431                                 *lastFound = (Element*)mid;
 432                         return (Element*)mid;
 433                 }
 434         }
 435 }
 436
 437 template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
 438                 insert(const Key &key, Element **lastFound)
 439 {
 440         const Element *lower, *mid, *upper;
 441         long keyRelation, insertPos;
 442         const long tblLen = BaseTable::length();
 443
 444         if ( tblLen == 0 ) {
 445                 /* If the table is empty then go straight to insert. */
 446                 lower = BaseTable::data;
 447                 goto insert;
 448         }
 449
 450         lower = BaseTable::data;
 451         upper = BaseTable::data + tblLen - 1;
 452         while ( true ) {
 453                 if ( upper < lower ) {
 454                         /* Did not find the key in the array.
 455                          * Place to insert at is lower. */
 456                         goto insert;
 457                 }
 458
 459                 mid = lower + ((upper-lower)>>1);
 460                 keyRelation = compare(key, GET_KEY(*mid));
 461
 462                 if ( keyRelation < 0 )
 463                         upper = mid - 1;
 464                 else if ( keyRelation > 0 )
 465                         lower = mid + 1;
 466                 else {
 467                         if ( lastFound != 0 )
 468                                 *lastFound = (Element*)mid;
 469                         return 0;
 470                 }
 471         }
 472
 473 insert:
 474         /* Get the insert pos. */
 475         insertPos = lower - BaseTable::data;
 476
 477         /* Do the insert. After makeRawSpaceFor, lower pointer is no good. */
 478         BaseVector::makeRawSpaceFor(insertPos, 1);
 479         new(BaseTable::data + insertPos) Element(key);
 480
 481         /* Set lastFound */
 482         if ( lastFound != 0 )
 483                 *lastFound = BaseTable::data + insertPos;
 484         return BaseTable::data + insertPos;
 485 }
 486
 487
 488 template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
 489                 insertMulti(const Key &key)
 490 {
 491         const Element *lower, *mid, *upper;
 492         long keyRelation, insertPos;
 493         const long tblLen = BaseTable::length();
 494
 495         if ( tblLen == 0 ) {
 496                 /* If the table is empty then go straight to insert. */
 497                 lower = BaseTable::data;
 498                 goto insert;
 499         }
 500
 501         lower = BaseTable::data;
 502         upper = BaseTable::data + tblLen - 1;
 503         while ( true ) {
 504                 if ( upper < lower ) {
 505                         /* Did not find the key in the array.
 506                          * Place to insert at is lower. */
 507                         goto insert;
 508                 }
 509
 510                 mid = lower + ((upper-lower)>>1);
 511                 keyRelation = compare(key, GET_KEY(*mid));
 512
 513                 if ( keyRelation < 0 )
 514                         upper = mid - 1;
 515                 else if ( keyRelation > 0 )
 516                         lower = mid + 1;
 517                 else {
 518                         lower = mid;
 519                         goto insert;
 520                 }
 521         }
 522
 523 insert:
 524         /* Get the insert pos. */
 525         insertPos = lower - BaseTable::data;
 526
 527         /* Do the insert. */
 528         BaseVector::makeRawSpaceFor(insertPos, 1);
 529         new(BaseTable::data + insertPos) Element(key);
 530
 531         /* Return the element inserted. */
 532         return BaseTable::data + insertPos;
 533 }
 534
 535 /**
 536  * \brief Insert each element from other.
 537  *
 538  * Always attempts to insert all elements even if the insert of some item from
 539  * other fails.
 540  *
 541  * \returns True if all items inserted successfully, false if any insert
 542  * failed.
 543  */
 544 template <BST_TEMPL_DEF> bool BstTable<BST_TEMPL_USE>::
 545                 insert(const BstTable &other)
 546 {
 547         bool allSuccess = true;
 548         long otherLen = other.length();
 549         for ( long i = 0; i < otherLen; i++ ) {
 550                 Element *el = insert( other.data[i] );
 551                 if ( el == 0 )
 552                         allSuccess = false;
 553         }
 554         return allSuccess;
 555 }
 556
 557 /**
 558  * \brief Insert each element from other even if the elements exist already.
 559  *
 560  * No individual insertMulti can fail.
 561  */
 562 template <BST_TEMPL_DEF> void BstTable<BST_TEMPL_USE>::
 563                 insertMulti(const BstTable &other)
 564 {
 565         long otherLen = other.length();
 566         for ( long i = 0; i < otherLen; i++ )
 567                 insertMulti( other.data[i] );
 568 }
 569
 570 #if ! defined( BSTSET )
 571
 572 /**
 573  * \brief Insert the given element.
 574  *
 575  * If the key in the given element does not already exist in the table then a
 576  * new element is inserted. They element copy constructor is used to place the
 577  * element into the table. If lastFound is given, it is set to the new element
 578  * created. If the insert fails then lastFound is set to the existing element
 579  * of the same key.
 580  *
 581  * \returns The new element created upon success, null upon failure.
 582  */
 583 template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
 584                 insert(const Element &el, Element **lastFound )
 585 {
 586         const Element *lower, *mid, *upper;
 587         long keyRelation, insertPos;
 588         const long tblLen = BaseTable::length();
 589
 590         if ( tblLen == 0 ) {
 591                 /* If the table is empty then go straight to insert. */
 592                 lower = BaseTable::data;
 593                 goto insert;
 594         }
 595
 596         lower = BaseTable::data;
 597         upper = BaseTable::data + tblLen - 1;
 598         while ( true ) {
 599                 if ( upper < lower ) {
 600                         /* Did not find the key in the array.
 601                          * Place to insert at is lower. */
 602                         goto insert;
 603                 }
 604
 605                 mid = lower + ((upper-lower)>>1);
 606                 keyRelation = compare(GET_KEY(el), GET_KEY(*mid));
 607
 608                 if ( keyRelation < 0 )
 609                         upper = mid - 1;
 610                 else if ( keyRelation > 0 )
 611                         lower = mid + 1;
 612                 else {
 613                         if ( lastFound != 0 )
 614                                 *lastFound = (Element*)mid;
 615                         return 0;
 616                 }
 617         }
 618
 619 insert:
 620         /* Get the insert pos. */
 621         insertPos = lower - BaseTable::data;
 622
 623         /* Do the insert. After makeRawSpaceFor, lower pointer is no good. */
 624         BaseVector::makeRawSpaceFor(insertPos, 1);
 625         new(BaseTable::data + insertPos) Element(el);
 626
 627         /* Set lastFound */
 628         if ( lastFound != 0 )
 629                 *lastFound = BaseTable::data + insertPos;
 630         return BaseTable::data + insertPos;
 631 }
 632
 633 /**
 634  * \brief Insert the given element even if it exists already.
 635  *
 636  * If the key in the given element exists already then the new element is
 637  * placed next to some other element of the same key. InsertMulti cannot fail.
 638  * The element copy constructor is used to place the element in the table.
 639  *
 640  * \returns The new element created.
 641  */
 642 template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
 643                 insertMulti(const Element &el)
 644 {
 645         const Element *lower, *mid, *upper;
 646         long keyRelation, insertPos;
 647         const long tblLen = BaseTable::length();
 648
 649         if ( tblLen == 0 ) {
 650                 /* If the table is empty then go straight to insert. */
 651                 lower = BaseTable::data;
 652                 goto insert;
 653         }
 654
 655         lower = BaseTable::data;
 656         upper = BaseTable::data + tblLen - 1;
 657         while ( true ) {
 658                 if ( upper < lower ) {
 659                         /* Did not find the fd in the array.
 660                          * Place to insert at is lower. */
 661                         goto insert;
 662                 }
 663
 664                 mid = lower + ((upper-lower)>>1);
 665                 keyRelation = compare(GET_KEY(el), GET_KEY(*mid));
 666
 667                 if ( keyRelation < 0 )
 668                         upper = mid - 1;
 669                 else if ( keyRelation > 0 )
 670                         lower = mid + 1;
 671                 else {
 672                         lower = mid;
 673                         goto insert;
 674                 }
 675         }
 676
 677 insert:
 678         /* Get the insert pos. */
 679         insertPos = lower - BaseTable::data;
 680
 681         /* Do the insert. */
 682         BaseVector::makeRawSpaceFor(insertPos, 1);
 683         new(BaseTable::data + insertPos) Element(el);
 684
 685         /* Return the element inserted. */
 686         return BaseTable::data + insertPos;
 687 }
 688 #endif
 689
 690
 691 #if defined( BSTMAP )
 692
 693 /**
 694  * \brief Insert the given key-value pair.
 695  *
 696  * If the given key does not already exist in the table then the key-value
 697  * pair is inserted. Copy constructors are used to place the pair in the
 698  * table. If lastFound is given, it is set to the new entry created. If the
 699  * insert fails then lastFound is set to the existing pair of the same key.
 700  *
 701  * \returns The new element created upon success, null upon failure.
 702  */
 703 template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
 704                 insert(const Key &key, const Value &val, Element **lastFound)
 705 {
 706         const Element *lower, *mid, *upper;
 707         long keyRelation, insertPos;
 708         const long tblLen = BaseTable::length();
 709
 710         if ( tblLen == 0 ) {
 711                 /* If the table is empty then go straight to insert. */
 712                 lower = BaseTable::data;
 713                 goto insert;
 714         }
 715
 716         lower = BaseTable::data;
 717         upper = BaseTable::data + tblLen - 1;
 718         while ( true ) {
 719                 if ( upper < lower ) {
 720                         /* Did not find the fd in the array.
 721                          * Place to insert at is lower. */
 722                         goto insert;
 723                 }
 724
 725                 mid = lower + ((upper-lower)>>1);
 726                 keyRelation = Compare::compare(key, mid->key);
 727
 728                 if ( keyRelation < 0 )
 729                         upper = mid - 1;
 730                 else if ( keyRelation > 0 )
 731                         lower = mid + 1;
 732                 else {
 733                         if ( lastFound != NULL )
 734                                 *lastFound = (Element*)mid;
 735                         return 0;
 736                 }
 737         }
 738
 739 insert:
 740         /* Get the insert pos. */
 741         insertPos = lower - BaseTable::data;
 742
 743         /* Do the insert. */
 744         BaseVector::makeRawSpaceFor(insertPos, 1);
 745         new(BaseTable::data + insertPos) Element(key, val);
 746
 747         /* Set lastFound */
 748         if ( lastFound != NULL )
 749                 *lastFound = BaseTable::data + insertPos;
 750         return BaseTable::data + insertPos;
 751 }
 752
 753
 754 /**
 755  * \brief Insert the given key-value pair even if the key exists already.
 756  *
 757  * If the key exists already then the key-value pair is placed next to some
 758  * other pair of the same key. InsertMulti cannot fail. Copy constructors are
 759  * used to place the pair in the table.
 760  *
 761  * \returns The new element created.
 762  */
 763 template <BST_TEMPL_DEF> Element *BstTable<BST_TEMPL_USE>::
 764                 insertMulti(const Key &key, const Value &val)
 765 {
 766         const Element *lower, *mid, *upper;
 767         long keyRelation, insertPos;
 768         const long tblLen = BaseTable::length();
 769
 770         if ( tblLen == 0 ) {
 771                 /* If the table is empty then go straight to insert. */
 772                 lower = BaseTable::data;
 773                 goto insert;
 774         }
 775
 776         lower = BaseTable::data;
 777         upper = BaseTable::data + tblLen - 1;
 778         while ( true ) {
 779                 if ( upper < lower ) {
 780                         /* Did not find the key in the array.
 781                          * Place to insert at is lower. */
 782                         goto insert;
 783                 }
 784
 785                 mid = lower + ((upper-lower)>>1);
 786                 keyRelation = Compare::compare(key, mid->key);
 787
 788                 if ( keyRelation < 0 )
 789                         upper = mid - 1;
 790                 else if ( keyRelation > 0 )
 791                         lower = mid + 1;
 792                 else {
 793                         lower = mid;
 794                         goto insert;
 795                 }
 796         }
 797
 798 insert:
 799         /* Get the insert pos. */
 800         insertPos = lower - BaseTable::data;
 801
 802         /* Do the insert. */
 803         BaseVector::makeRawSpaceFor(insertPos, 1);
 804         new(BaseTable::data + insertPos) Element(key, val);
 805
 806         /* Return the element inserted. */
 807         return BaseTable::data + insertPos;
 808 }
 809
 810 #endif
 811
 812 #ifdef AAPL_NAMESPACE
 813 }
 814 #endif