ucx/cx/map.h

   1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
   3  *
   4  * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *
   9  *   1. Redistributions of source code must retain the above copyright
  10  *      notice, this list of conditions and the following disclaimer.
  11  *
  12  *   2. Redistributions in binary form must reproduce the above copyright
  13  *      notice, this list of conditions and the following disclaimer in the
  14  *      documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  19  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  20  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  21  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  22  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  23  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  24  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  25  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  26  * POSSIBILITY OF SUCH DAMAGE.
  27  */
  28 /**
  29  * \file map.h
  30  * \brief Interface for map implementations.
  31  * \author Mike Becker
  32  * \author Olaf Wintermann
  33  * \version 3.0
  34  * \copyright 2-Clause BSD License
  35  */
  36
  37 #ifndef UCX_MAP_H
  38 #define UCX_MAP_H
  39
  40 #include "common.h"
  41 #include "allocator.h"
  42 #include "iterator.h"
  43 #include "hash_key.h"
  44
  45 #ifdef    __cplusplus
  46 extern "C" {
  47 #endif
  48
  49 #ifndef CX_STORE_POINTERS
  50 /**
  51  * Special constant used for creating collections that are storing pointers.
  52  */
  53 #define CX_STORE_POINTERS 0
  54 #endif
  55
  56 /** Type for the UCX map. */
  57 typedef struct cx_map_s CxMap;
  58
  59 /** Type for a map entry. */
  60 typedef struct cx_map_entry_s CxMapEntry;
  61
  62 /** Type for map class definitions. */
  63 typedef struct cx_map_class_s cx_map_class;
  64
  65 /** Structure for the UCX map. */
  66 struct cx_map_s {
  67     /** The map class definition. */
  68     cx_map_class *cl;
  69     /** An allocator that is used for the map elements. */
  70     CxAllocator *allocator;
  71     /** The number of elements currently stored. */
  72     size_t size;
  73     /**
  74      * The size of an element.
  75      */
  76     size_t itemsize;
  77     /**
  78      * True, if this map shall store pointers instead
  79      * of copies of objects.
  80      */
  81     bool store_pointers;
  82 };
  83
  84 /**
  85  * The class definition for arbitrary maps.
  86  */
  87 struct cx_map_class_s {
  88     /**
  89      * Deallocates the entire memory.
  90      */
  91     __attribute__((__nonnull__))
  92     void (*destructor)(struct cx_map_s *map);
  93
  94     /**
  95      * Removes all elements.
  96      */
  97     __attribute__((__nonnull__))
  98     void (*clear)(struct cx_map_s *map);
  99
 100     /**
 101      * Add or overwrite an element.
 102      */
 103     __attribute__((__nonnull__))
 104     int (*put)(
 105             CxMap *map,
 106             CxHashKey key,
 107             void *value
 108     );
 109
 110     /**
 111      * Returns an element.
 112      */
 113     __attribute__((__nonnull__, __warn_unused_result__))
 114     void *(*get)(
 115             CxMap const *map,
 116             CxHashKey key
 117     );
 118
 119     /**
 120      * Removes an element.
 121      */
 122     __attribute__((__nonnull__))
 123     void *(*remove)(
 124             CxMap *map,
 125             CxHashKey key
 126     );
 127
 128     /**
 129      * Iterator over the key/value pairs.
 130      */
 131     __attribute__((__nonnull__, __warn_unused_result__))
 132     CxIterator (*iterator)(CxMap const *map);
 133
 134     /**
 135      * Iterator over the keys.
 136      */
 137     __attribute__((__nonnull__, __warn_unused_result__))
 138     CxIterator (*iterator_keys)(CxMap const *map);
 139
 140     /**
 141      * Iterator over the values.
 142      */
 143     __attribute__((__nonnull__, __warn_unused_result__))
 144     CxIterator (*iterator_values)(CxMap const *map);
 145
 146     /**
 147      * Mutating iterator over the key/value pairs.
 148      */
 149     __attribute__((__nonnull__, __warn_unused_result__))
 150     CxMutIterator (*mut_iterator)(CxMap *map);
 151
 152     /**
 153      * Mutating iterator over the keys.
 154      */
 155     __attribute__((__nonnull__, __warn_unused_result__))
 156     CxMutIterator (*mut_iterator_keys)(CxMap *map);
 157
 158     /**
 159      * Mutating iterator over the values.
 160      */
 161     __attribute__((__nonnull__, __warn_unused_result__))
 162     CxMutIterator (*mut_iterator_values)(CxMap *map);
 163 };
 164
 165 /**
 166  * A map entry.
 167  */
 168 struct cx_map_entry_s {
 169     /**
 170      * A pointer to the key.
 171      */
 172     CxHashKey const *key;
 173     /**
 174      * A pointer to the value.
 175      */
 176     void *value;
 177 };
 178
 179 /**
 180  * Advises the map to store copies of the objects (default mode of operation).
 181  *
 182  * Retrieving objects from this map will yield pointers to the copies stored
 183  * within this list.
 184  *
 185  * @param map the map
 186  * @see cxMapStorePointers()
 187  */
 188 __attribute__((__nonnull__))
 189 static inline void cxMapStoreObjects(CxMap *map) {
 190     map->store_pointers = false;
 191 }
 192
 193 /**
 194  * Advises the map to only store pointers to the objects.
 195  *
 196  * Retrieving objects from this list will yield the original pointers stored.
 197  *
 198  * @note This function forcibly sets the element size to the size of a pointer.
 199  * Invoking this function on a non-empty map that already stores copies of
 200  * objects is undefined.
 201  *
 202  * @param map the map
 203  * @see cxMapStoreObjects()
 204  */
 205 __attribute__((__nonnull__))
 206 static inline void cxMapStorePointers(CxMap *map) {
 207     map->store_pointers = true;
 208     map->itemsize = sizeof(void *);
 209 }
 210
 211
 212 /**
 213  * Deallocates the memory of the specified map.
 214  *
 215  * @param map the map to be destroyed
 216  */
 217 __attribute__((__nonnull__))
 218 static inline void cxMapDestroy(CxMap *map) {
 219     // TODO: likely to add auto-free feature for contents in the future
 220     map->cl->destructor(map);
 221 }
 222
 223
 224 /**
 225  * Clears a map by removing all elements.
 226  *
 227  * @param map the map to be cleared
 228  */
 229 __attribute__((__nonnull__))
 230 static inline void cxMapClear(CxMap *map) {
 231     map->cl->clear(map);
 232 }
 233
 234 /**
 235  * Puts a key/value-pair into the map.
 236  *
 237  * @param map the map
 238  * @param key the key
 239  * @param value the value
 240  * @return 0 on success, non-zero value on failure
 241  */
 242 __attribute__((__nonnull__))
 243 static inline int cxMapPut(
 244         CxMap *map,
 245         CxHashKey key,
 246         void *value
 247 ) {
 248     return map->cl->put(map, key, value);
 249 }
 250
 251 /**
 252  * Retrieves a value by using a key.
 253  *
 254  * @param map the map
 255  * @param key the key
 256  * @return the value
 257  */
 258 __attribute__((__nonnull__, __warn_unused_result__))
 259 static inline void *cxMapGet(
 260         CxMap const *map,
 261         CxHashKey key
 262 ) {
 263     return map->cl->get(map, key);
 264 }
 265
 266 /**
 267  * Removes a key/value-pair from the map by using the key.
 268  *
 269  * If this map is storing pointers, you should make sure that the map
 270  * is not the last location where this pointer is stored.
 271  * Otherwise, use cxMapRemoveAndGet() to retrieve the pointer while
 272  * removing it from the map.
 273  *
 274  * @param map the map
 275  * @param key the key
 276  * @see cxMapRemoveAndGet()
 277  */
 278 __attribute__((__nonnull__))
 279 static inline void cxMapRemove(
 280         CxMap *map,
 281         CxHashKey key
 282 ) {
 283     (void) map->cl->remove(map, key);
 284 }
 285
 286 /**
 287  * Removes a key/value-pair from the map by using the key.
 288  *
 289  * This function should only be used when the map is storing pointers,
 290  * in order to retrieve the pointer you are about to remove.
 291  * In any other case, cxMapRemove() is sufficient.
 292  *
 293  * @param map the map
 294  * @param key the key
 295  * @return the stored pointer or \c NULL if either the key is not present
 296  * in the map or the map is not storing pointers
 297  * @see cxMapStorePointers()
 298  */
 299 __attribute__((__nonnull__, __warn_unused_result__))
 300 static inline void *cxMapRemoveAndGet(
 301         CxMap *map,
 302         CxHashKey key
 303 ) {
 304     return map->cl->remove(map, key);
 305 }
 306
 307 // TODO: set-like map operations (union, intersect, difference)
 308
 309 /**
 310  * Creates a value iterator for a map.
 311  *
 312  * \note An iterator iterates over all elements successively. Therefore the order
 313  * highly depends on the map implementation and may change arbitrarily when the contents change.
 314  *
 315  * @param map the map to create the iterator for
 316  * @return an iterator for the currently stored values
 317  */
 318 __attribute__((__nonnull__, __warn_unused_result__))
 319 static inline CxIterator cxMapIteratorValues(CxMap *map) {
 320     return map->cl->iterator_values(map);
 321 }
 322
 323 /**
 324  * Creates a key iterator for a map.
 325  *
 326  * The elements of the iterator are keys of type CxHashKey.
 327  *
 328  * \note An iterator iterates over all elements successively. Therefore the order
 329  * highly depends on the map implementation and may change arbitrarily when the contents change.
 330  *
 331  * @param map the map to create the iterator for
 332  * @return an iterator for the currently stored keys
 333  */
 334 __attribute__((__nonnull__, __warn_unused_result__))
 335 static inline CxIterator cxMapIteratorKeys(CxMap *map) {
 336     return map->cl->iterator_keys(map);
 337 }
 338
 339 /**
 340  * Creates an iterator for a map.
 341  *
 342  * The elements of the iterator are key/value pairs of type CxMapEntry.
 343  *
 344  * \note An iterator iterates over all elements successively. Therefore the order
 345  * highly depends on the map implementation and may change arbitrarily when the contents change.
 346  *
 347  * @param map the map to create the iterator for
 348  * @return an iterator for the currently stored entries
 349  * @see cxMapIteratorKeys()
 350  * @see cxMapIteratorValues()
 351  */
 352 __attribute__((__nonnull__, __warn_unused_result__))
 353 static inline CxIterator cxMapIterator(CxMap *map) {
 354     return map->cl->iterator(map);
 355 }
 356
 357
 358 /**
 359  * Creates a mutating iterator over the values of a map.
 360  *
 361  * \note An iterator iterates over all elements successively. Therefore the order
 362  * highly depends on the map implementation and may change arbitrarily when the contents change.
 363  *
 364  * @param map the map to create the iterator for
 365  * @return an iterator for the currently stored values
 366  */
 367 __attribute__((__nonnull__, __warn_unused_result__))
 368 static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {
 369     return map->cl->mut_iterator_values(map);
 370 }
 371
 372 /**
 373  * Creates a mutating iterator over the keys of a map.
 374  *
 375  * The elements of the iterator are keys of type CxHashKey.
 376  *
 377  * \note An iterator iterates over all elements successively. Therefore the order
 378  * highly depends on the map implementation and may change arbitrarily when the contents change.
 379  *
 380  * @param map the map to create the iterator for
 381  * @return an iterator for the currently stored keys
 382  */
 383 __attribute__((__nonnull__, __warn_unused_result__))
 384 static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {
 385     return map->cl->mut_iterator_keys(map);
 386 }
 387
 388 /**
 389  * Creates a mutating iterator for a map.
 390  *
 391  * The elements of the iterator are key/value pairs of type CxMapEntry.
 392  *
 393  * \note An iterator iterates over all elements successively. Therefore the order
 394  * highly depends on the map implementation and may change arbitrarily when the contents change.
 395  *
 396  * @param map the map to create the iterator for
 397  * @return an iterator for the currently stored entries
 398  * @see cxMapMutIteratorKeys()
 399  * @see cxMapMutIteratorValues()
 400  */
 401 __attribute__((__nonnull__, __warn_unused_result__))
 402 static inline CxMutIterator cxMapMutIterator(CxMap *map) {
 403     return map->cl->mut_iterator(map);
 404 }
 405
 406 #ifdef    __cplusplus
 407 }
 408 #endif
 409
 410 #endif // UCX_MAP_H