ucx: src/cx/map.h@dce9b8450656

     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  */

    37 #ifndef UCX_MAP_H

    38 #define UCX_MAP_H

    40 #include "common.h"

    41 #include "allocator.h"

    42 #include "iterator.h"

    43 #include "hash_key.h"

    45 #ifdef    __cplusplus

    46 extern "C" {

    47 #endif

    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

    56 /** Type for the UCX map. */

    57 typedef struct cx_map_s CxMap;

    59 /** Type for a map entry. */

    60 typedef struct cx_map_entry_s CxMapEntry;

    62 /** Type for map class definitions. */

    63 typedef struct cx_map_class_s cx_map_class;

    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 };

    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);

    94     /**

    95      * Removes all elements.

    96      */

    97     __attribute__((__nonnull__))

    98     void (*clear)(struct cx_map_s *map);

   100     /**

   101      * Add or overwrite an element.

   102      */

   103     __attribute__((__nonnull__))

   104     int (*put)(

   105             CxMap *map,

   106             CxHashKey key,

   107             void *value

   108     );

   110     /**

   111      * Returns an element.

   112      */

   113     __attribute__((__nonnull__, __warn_unused_result__))

   114     void *(*get)(

   115             CxMap const *map,

   116             CxHashKey key

   117     );

   119     /**

   120      * Removes an element.

   121      */

   122     __attribute__((__nonnull__))

   123     void *(*remove)(

   124             CxMap *map,

   125             CxHashKey key

   126     );

   128     /**

   129      * Iterator over the key/value pairs.

   130      */

   131     __attribute__((__nonnull__, __warn_unused_result__))

   132     CxIterator (*iterator)(CxMap const *map);

   134     /**

   135      * Iterator over the keys.

   136      */

   137     __attribute__((__nonnull__, __warn_unused_result__))

   138     CxIterator (*iterator_keys)(CxMap const *map);

   140     /**

   141      * Iterator over the values.

   142      */

   143     __attribute__((__nonnull__, __warn_unused_result__))

   144     CxIterator (*iterator_values)(CxMap const *map);

   146     /**

   147      * Mutating iterator over the key/value pairs.

   148      */

   149     __attribute__((__nonnull__, __warn_unused_result__))

   150     CxMutIterator (*mut_iterator)(CxMap *map);

   152     /**

   153      * Mutating iterator over the keys.

   154      */

   155     __attribute__((__nonnull__, __warn_unused_result__))

   156     CxMutIterator (*mut_iterator_keys)(CxMap *map);

   158     /**

   159      * Mutating iterator over the values.

   160      */

   161     __attribute__((__nonnull__, __warn_unused_result__))

   162     CxMutIterator (*mut_iterator_values)(CxMap *map);

   163 };

   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 };

   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 }

   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 }

   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 }

   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 }

   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 }

   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 }

   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 }

   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 }

   307 // TODO: set-like map operations (union, intersect, difference)

   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 }

   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 }

   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 }

   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 }

   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 }

   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 }

   406 #ifdef    __cplusplus

   407 }

   408 #endif

   410 #endif // UCX_MAP_H

Mercurial > hg > ucx / file revision

src/cx/map.h@dce9b8450656

src/cx/map.h