lib/gl_omap.hh

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