aapl/sbstmap.h

   1 /*
   2  *  Copyright 2002 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 #ifndef _AAPL_SBSTMAP_H
  23 #define _AAPL_SBSTMAP_H
  24
  25 #include "compare.h"
  26 #include "svector.h"
  27
  28 #ifdef AAPL_NAMESPACE
  29 namespace Aapl {
  30 #endif
  31
  32 /**
  33  * \brief Element for BstMap.
  34  *
  35  * Stores the key and value pair.
  36  */
  37 template <class Key, class Value> struct SBstMapEl
  38 {
  39         SBstMapEl() {}
  40         SBstMapEl(const Key &key) : key(key) {}
  41         SBstMapEl(const Key &key, const Value &val) : key(key), value(val) {}
  42
  43         /** \brief The key */
  44         Key key;
  45
  46         /** \brief The value. */
  47         Value value;
  48 };
  49
  50 #ifdef AAPL_NAMESPACE
  51 }
  52 #endif
  53
  54 /**
  55  * \addtogroup bst
  56  * @{
  57  */
  58
  59 /**
  60  * \class SBstMap
  61  * \brief Copy-on-write binary search table for key and value pairs.
  62  *
  63  * This is a map style binary search table that employs the copy-on-write
  64  * mechanism for table data. BstMap stores key and value pairs in each
  65  * element. The key and value can be any type. A compare class for the key
  66  * must be supplied.
  67  */
  68
  69 /*@}*/
  70
  71 #define BST_TEMPL_DECLARE class Key, class Value, \
  72                 class Compare = CmpOrd<Key>, class Resize = ResizeExpn
  73 #define BST_TEMPL_DEF class Key, class Value, class Compare, class Resize
  74 #define BST_TEMPL_USE Key, Value, Compare, Resize
  75 #define GET_KEY(el) ((el).key)
  76 #define BstTable SBstMap
  77 #define Vector SVector
  78 #define Table STable
  79 #define Element SBstMapEl<Key, Value>
  80 #define BSTMAP
  81 #define SHARED_BST
  82
  83 #include "bstcommon.h"
  84
  85 #undef BST_TEMPL_DECLARE
  86 #undef BST_TEMPL_DEF
  87 #undef BST_TEMPL_USE
  88 #undef GET_KEY
  89 #undef BstTable
  90 #undef Vector
  91 #undef Table
  92 #undef Element
  93 #undef BSTMAP
  94 #undef SHARED_BST
  95
  96 /**
  97  * \fn SBstMap::insert(const Key &key, BstMapEl<Key, Value> **lastFound)
  98  * \brief Insert the given key.
  99  *
 100  * If the given key does not already exist in the table then a new element
 101  * having key is inserted. They key copy constructor and value default
 102  * constructor are used to place the pair in the table. If lastFound is given,
 103  * it is set to the new entry created. If the insert fails then lastFound is
 104  * set to the existing pair of the same key.
 105  *
 106  * \returns The new element created upon success, null upon failure.
 107  */
 108
 109 /**
 110  * \fn SBstMap::insertMulti(const Key &key)
 111  * \brief Insert the given key even if it exists already.
 112  *
 113  * If the key exists already then the new element having key is placed next
 114  * to some other pair of the same key. InsertMulti cannot fail. The key copy
 115  * constructor and the value default constructor are used to place the pair in
 116  * the table.
 117  *
 118  * \returns The new element created.
 119  */
 120
 121 #endif /* _AAPL_SBSTMAP_H */