lib/gl_omap.hh

   1 /* Abstract ordered map data type as a C++ class.
   2    Copyright (C) 2006-2020 Free Software Foundation, Inc.
   3    Written by Bruno Haible <bruno@clisp.org>, 2018.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
  17
  18 #ifndef _GL_OMAP_HH
  19 #define _GL_OMAP_HH
  20
  21 #include "gl_omap.h"
  22 #include "gl_xomap.h"
  23
  24 /* gl_OMap is a C++ wrapper around the gl_omap data type.
  25    Its key type is 'KEYTYPE *'.  Its value type is 'VALUETYPE *'.
  26
  27    It is merely a pointer, not a smart pointer. In other words:
  28    it does NOT do reference-counting, and the destructor does nothing.  */
  29
  30 template <class K, class V> class gl_OMap;
  31
  32 template <class KEYTYPE, class VALUETYPE>
  33 class gl_OMap<KEYTYPE *, VALUETYPE *>
  34 {
  35 public:
  36   // ------------------------------ Constructors ------------------------------
  37
  38   gl_OMap ()
  39     : _ptr (NULL)
  40     {}
  41
  42   /* Creates an empty map.
  43      IMPLEMENTATION is one of GL_ARRAY_OMAP, GL_AVLTREE_OMAP, GL_RBTREE_OMAP.
  44      COMPAR_FN is a key comparison function or NULL.
  45      KDISPOSE_FN is a key disposal function or NULL.
  46      VDISPOSE_FN is a value disposal function or NULL.  */
  47   gl_OMap (gl_omap_implementation_t implementation,
  48            int (*compar_fn) (KEYTYPE * /*key1*/, KEYTYPE * /*key2*/),
  49            void (*kdispose_fn) (KEYTYPE *),
  50            void (*vdispose_fn) (VALUETYPE *))
  51     : _ptr (gl_omap_create_empty (implementation,
  52                                   reinterpret_cast<gl_mapkey_compar_fn>(compar_fn),
  53                                   reinterpret_cast<gl_mapkey_dispose_fn>(kdispose_fn),
  54                                   reinterpret_cast<gl_mapvalue_dispose_fn>(vdispose_fn)))
  55     {}
  56
  57   /* Copy constructor.  */
  58   gl_OMap (const gl_OMap& x)
  59     { _ptr = x._ptr; }
  60
  61   /* Assignment operator.  */
  62   gl_OMap& operator= (const gl_OMap& x)
  63     { _ptr = x._ptr; return *this; }
  64
  65   // ------------------------------- Destructor -------------------------------
  66
  67   ~gl_OMap ()
  68     { _ptr = NULL; }
  69
  70   // ----------------------- Read-only member functions -----------------------
  71
  72   /* Returns the current number of pairs in the ordered map.  */
  73   size_t size () const
  74     { return gl_omap_size (_ptr); }
  75
  76   /* Searches whether a pair with the given key is already in the ordered map.
  77      Returns the value if found, or NULL if not present in the map.  */
  78   VALUETYPE * get (KEYTYPE * key) const
  79     { return static_cast<VALUETYPE *>(gl_omap_get (_ptr, key)); }
  80
  81   /* Searches whether a pair with the given key is already in the ordered map.
  82      Returns true and sets VALUE to the value if found.
  83      Returns false if not present in the map.  */
  84   bool search (KEYTYPE * key, VALUETYPE *& value) const
  85     { return gl_omap_search (_ptr, key, &value); }
  86
  87   /* Searches the pair with the least key in the ordered map that compares
  88      greater or equal to the given THRESHOLD.  The representation of the
  89      THRESHOLD is defined by the THRESHOLD_FN.
  90      Returns true and stores the found pair in KEY and VALUE if found.
  91      Otherwise returns false.  */
  92   template <typename THT>
  93   bool search_atleast (bool (*threshold_fn) (KEYTYPE * /*key*/, THT * /*threshold*/),
  94                        THT * threshold,
  95                        KEYTYPE *& key, VALUETYPE *& value) const
  96   { return gl_omap_search_atleast (_ptr, reinterpret_cast<gl_mapkey_threshold_fn>(threshold_fn), threshold, &key, &value); }
  97
  98   // ----------------------- Modifying member functions -----------------------
  99
 100   /* Adds a pair to the ordered map.
 101      Returns true if a pair with the given key was not already in the map and so
 102      this pair was added.
 103      Returns false if a pair with the given key was already in the map and only
 104      its value was replaced.  */
 105   bool put (KEYTYPE * key, VALUETYPE * value)
 106     { return gl_omap_put (_ptr, key, value); }
 107
 108   /* Adds a pair to the ordered map and retrieves the previous value.
 109      Returns true if a pair with the given key was not already in the map and so
 110      this pair was added.
 111      Returns false and sets OLDVALUE to the previous value, if a pair with the
 112      given key was already in the map and only its value was replaced.  */
 113   bool getput (KEYTYPE * key, VALUETYPE * value, VALUETYPE *& oldvalue)
 114     { return gl_omap_getput (_ptr, key, value, &oldvalue); }
 115
 116   /* Removes a pair from the ordered map.
 117      Returns true if the key was found and its pair removed.
 118      Returns false otherwise.  */
 119   bool remove (KEYTYPE * key)
 120     { return gl_omap_remove (_ptr, key); }
 121
 122   /* Removes a pair from the ordered map and retrieves the previous value.
 123      Returns true and sets OLDVALUE to the previous value, if the key was found
 124      and its pair removed.
 125      Returns false otherwise.  */
 126   bool getremove (KEYTYPE * key, VALUETYPE *& oldvalue)
 127     { return gl_omap_getremove (_ptr, key, &oldvalue); }
 128
 129   /* Frees the entire ordered map.
 130      (But this call does not free the keys and values of the pairs in the map.
 131      It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
 132      of the pairs in the map.)  */
 133   void free ()
 134     { gl_omap_free (_ptr); _ptr = NULL; }
 135
 136   // ------------------------------ Private stuff ------------------------------
 137
 138 private:
 139   gl_omap_t _ptr;
 140
 141 public:
 142   // -------------------------------- Iterators --------------------------------
 143   // Only a forward iterator.
 144   // Does not implement the STL operations (++, *, and != .end()), but a simpler
 145   // interface that needs only one virtual function call per iteration instead
 146   // of three.
 147
 148   class iterator {
 149   public:
 150
 151     /* If there is a next pair, stores the next pair in KEY and VALUE, advances
 152        the iterator, and returns true.  Otherwise, returns false.  */
 153     bool next (KEYTYPE *& key, VALUETYPE *& value)
 154       {
 155         const void *next_key;
 156         const void *next_value;
 157         bool has_next = gl_omap_iterator_next (&_state, &next_key, &next_value);
 158         if (has_next)
 159           {
 160             key = static_cast<KEYTYPE *>(next_key);
 161             value = static_cast<VALUETYPE *>(next_value);
 162           }
 163         return has_next;
 164       }
 165
 166     ~iterator ()
 167       { gl_omap_iterator_free (&_state); }
 168
 169   #if defined __xlC__ || defined __HP_aCC || defined __SUNPRO_CC
 170   public:
 171   #else
 172   private:
 173     friend iterator gl_OMap::begin ();
 174   #endif
 175
 176     iterator (gl_omap_t ptr)
 177       : _state (gl_omap_iterator (ptr))
 178       {}
 179
 180   private:
 181
 182     gl_omap_iterator_t _state;
 183   };
 184
 185   /* Creates an iterator traversing the ordered map.
 186      The map's contents must not be modified while the iterator is in use,
 187      except for modifying the value of the last returned key or removing the
 188      last returned pair.  */
 189   iterator begin ()
 190     { return iterator (_ptr); }
 191 };
 192
 193 #endif /* _GL_OMAP_HH */