summaryrefslogtreecommitdiff
path: root/lib/gl_omap.hh
blob: 042586ae040c6f896acaed29fad294028173b3b1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
/* Abstract ordered map data type as a C++ class.
   Copyright (C) 2006-2021 Free Software Foundation, Inc.
   Written by Bruno Haible <bruno@clisp.org>, 2018.

   This program is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 3 of the License, or
   (at your option) any later version.

   This program 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 General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */

#ifndef _GL_OMAP_HH
#define _GL_OMAP_HH

#include "gl_omap.h"
#include "gl_xomap.h"

#include <stdlib.h>     /* because Gnulib's <stdlib.h> may '#define free ...' */

/* gl_OMap is a C++ wrapper around the gl_omap data type.
   Its key type is 'KEYTYPE *'.  Its value type is 'VALUETYPE *'.

   It is merely a pointer, not a smart pointer. In other words:
   it does NOT do reference-counting, and the destructor does nothing.  */

template <class K, class V> class gl_OMap;

template <class KEYTYPE, class VALUETYPE>
class gl_OMap<KEYTYPE *, VALUETYPE *>
{
public:
  // ------------------------------ Constructors ------------------------------

  gl_OMap ()
    : _ptr (NULL)
    {}

  /* Creates an empty map.
     IMPLEMENTATION is one of GL_ARRAY_OMAP, GL_AVLTREE_OMAP, GL_RBTREE_OMAP.
     COMPAR_FN is a key comparison function or NULL.
     KDISPOSE_FN is a key disposal function or NULL.
     VDISPOSE_FN is a value disposal function or NULL.  */
  gl_OMap (gl_omap_implementation_t implementation,
           int (*compar_fn) (KEYTYPE * /*key1*/, KEYTYPE * /*key2*/),
           void (*kdispose_fn) (KEYTYPE *),
           void (*vdispose_fn) (VALUETYPE *))
    : _ptr (gl_omap_create_empty (implementation,
                                  reinterpret_cast<gl_mapkey_compar_fn>(compar_fn),
                                  reinterpret_cast<gl_mapkey_dispose_fn>(kdispose_fn),
                                  reinterpret_cast<gl_mapvalue_dispose_fn>(vdispose_fn)))
    {}

  /* Copy constructor.  */
  gl_OMap (const gl_OMap& x)
    { _ptr = x._ptr; }

  /* Assignment operator.  */
  gl_OMap& operator= (const gl_OMap& x)
    { _ptr = x._ptr; return *this; }

  // ------------------------------- Destructor -------------------------------

  ~gl_OMap ()
    { _ptr = NULL; }

  // ----------------------- Read-only member functions -----------------------

  /* Returns the current number of pairs in the ordered map.  */
  size_t size () const
    { return gl_omap_size (_ptr); }

  /* Searches whether a pair with the given key is already in the ordered map.
     Returns the value if found, or NULL if not present in the map.  */
  VALUETYPE * get (KEYTYPE * key) const
    { return static_cast<VALUETYPE *>(gl_omap_get (_ptr, key)); }

  /* Searches whether a pair with the given key is already in the ordered map.
     Returns true and sets VALUE to the value if found.
     Returns false if not present in the map.  */
  bool search (KEYTYPE * key, VALUETYPE *& value) const
    { return gl_omap_search (_ptr, key, &value); }

  /* Searches the pair with the least key in the ordered map that compares
     greater or equal to the given THRESHOLD.  The representation of the
     THRESHOLD is defined by the THRESHOLD_FN.
     Returns true and stores the found pair in KEY and VALUE if found.
     Otherwise returns false.  */
  template <typename THT>
  bool search_atleast (bool (*threshold_fn) (KEYTYPE * /*key*/, THT * /*threshold*/),
                       THT * threshold,
                       KEYTYPE *& key, VALUETYPE *& value) const
  { return gl_omap_search_atleast (_ptr, reinterpret_cast<gl_mapkey_threshold_fn>(threshold_fn), threshold, &key, &value); }

  // ----------------------- Modifying member functions -----------------------

  /* Adds a pair to the ordered map.
     Returns true if a pair with the given key was not already in the map and so
     this pair was added.
     Returns false if a pair with the given key was already in the map and only
     its value was replaced.  */
  bool put (KEYTYPE * key, VALUETYPE * value)
    { return gl_omap_put (_ptr, key, value); }

  /* Adds a pair to the ordered map and retrieves the previous value.
     Returns true if a pair with the given key was not already in the map and so
     this pair was added.
     Returns false and sets OLDVALUE to the previous value, if a pair with the
     given key was already in the map and only its value was replaced.  */
  bool getput (KEYTYPE * key, VALUETYPE * value, VALUETYPE *& oldvalue)
    { return gl_omap_getput (_ptr, key, value, &oldvalue); }

  /* Removes a pair from the ordered map.
     Returns true if the key was found and its pair removed.
     Returns false otherwise.  */
  bool remove (KEYTYPE * key)
    { return gl_omap_remove (_ptr, key); }

  /* Removes a pair from the ordered map and retrieves the previous value.
     Returns true and sets OLDVALUE to the previous value, if the key was found
     and its pair removed.
     Returns false otherwise.  */
  bool getremove (KEYTYPE * key, VALUETYPE *& oldvalue)
    { return gl_omap_getremove (_ptr, key, &oldvalue); }

  /* Frees the entire ordered map.
     (But this call does not free the keys and values of the pairs in the map.
     It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
     of the pairs in the map.)  */
  void free ()
    { gl_omap_free (_ptr); _ptr = NULL; }

  // ------------------------------ Private stuff ------------------------------

private:
  gl_omap_t _ptr;

public:
  // -------------------------------- Iterators --------------------------------
  // Only a forward iterator.
  // Does not implement the STL operations (++, *, and != .end()), but a simpler
  // interface that needs only one virtual function call per iteration instead
  // of three.

  class iterator {
  public:

    /* If there is a next pair, stores the next pair in KEY and VALUE, advances
       the iterator, and returns true.  Otherwise, returns false.  */
    bool next (KEYTYPE *& key, VALUETYPE *& value)
      {
        const void *next_key;
        const void *next_value;
        bool has_next = gl_omap_iterator_next (&_state, &next_key, &next_value);
        if (has_next)
          {
            key = static_cast<KEYTYPE *>(next_key);
            value = static_cast<VALUETYPE *>(next_value);
          }
        return has_next;
      }

    ~iterator ()
      { gl_omap_iterator_free (&_state); }

  #if defined __xlC__ || defined __HP_aCC || defined __SUNPRO_CC
  public:
  #else
  private:
    friend iterator gl_OMap::begin ();
  #endif

    iterator (gl_omap_t ptr)
      : _state (gl_omap_iterator (ptr))
      {}

  private:

    gl_omap_iterator_t _state;
  };

  /* Creates an iterator traversing the ordered map.
     The map's contents must not be modified while the iterator is in use,
     except for modifying the value of the last returned key or removing the
     last returned pair.  */
  iterator begin ()
    { return iterator (_ptr); }
};

#endif /* _GL_OMAP_HH */