ucx: src/cx/map.h@d7129285ac32

     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 #define CX_STORE_POINTERS 0

    51 #endif

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

    54 typedef struct cx_map_s CxMap;

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

    57 typedef struct cx_map_entry_s CxMapEntry;

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

    60 typedef struct cx_map_class_s cx_map_class;

    62 /** Structure for the UCX map. */

    63 struct cx_map_s {

    64     /** The map class definition. */

    65     cx_map_class *cl;

    66     /** An allocator that is used for the map elements. */

    67     CxAllocator *allocator;

    68     /** The number of elements currently stored. */

    69     size_t size;

    70     /**

    71      * The size of an element.

    72      */

    73     size_t itemsize;

    74     /**

    75      * True, if this map shall store pointers instead

    76      * of copies of objects.

    77      */

    78     bool store_pointers;

    79 };

    81 /**

    82  * The class definition for arbitrary maps.

    83  */

    84 struct cx_map_class_s {

    85     /**

    86      * Deallocates the entire memory.

    87      */

    88     __attribute__((__nonnull__))

    89     void (*destructor)(struct cx_map_s *map);

    91     /**

    92      * Removes all elements.

    93      */

    94     __attribute__((__nonnull__))

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

    97     /**

    98      * Add or overwrite an element.

    99      */

   100     __attribute__((__nonnull__))

   101     int (*put)(

   102             CxMap *map,

   103             CxHashKey key,

   104             void *value

   105     );

   107     /**

   108      * Returns an element.

   109      */

   110     __attribute__((__nonnull__, __warn_unused_result__))

   111     void *(*get)(

   112             CxMap const *map,

   113             CxHashKey key

   114     );

   116     /**

   117      * Removes an element.

   118      */

   119     __attribute__((__nonnull__))

   120     void *(*remove)(

   121             CxMap *map,

   122             CxHashKey key

   123     );

   125     /**

   126      * Iterator over the key/value pairs.

   127      */

   128     __attribute__((__nonnull__, __warn_unused_result__))

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

   131     /**

   132      * Iterator over the keys.

   133      */

   134     __attribute__((__nonnull__, __warn_unused_result__))

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

   137     /**

   138      * Iterator over the values.

   139      */

   140     __attribute__((__nonnull__, __warn_unused_result__))

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

   143     /**

   144      * Mutating iterator over the key/value pairs.

   145      */

   146     __attribute__((__nonnull__, __warn_unused_result__))

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

   149     /**

   150      * Mutating iterator over the keys.

   151      */

   152     __attribute__((__nonnull__, __warn_unused_result__))

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

   155     /**

   156      * Mutating iterator over the values.

   157      */

   158     __attribute__((__nonnull__, __warn_unused_result__))

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

   160 };

   162 /**

   163  * A map entry.

   164  */

   165 struct cx_map_entry_s {

   166     /**

   167      * A pointer to the key.

   168      */

   169     CxHashKey const *key;

   170     /**

   171      * A pointer to the value.

   172      */

   173     void *value;

   174 };

   176 /**

   177  * Advises the map to store copies of the objects (default mode of operation).

   178  *

   179  * Retrieving objects from this map will yield pointers to the copies stored

   180  * within this list.

   181  *

   182  * @param map the map

   183  * @see cxMapStorePointers()

   184  */

   185 __attribute__((__nonnull__))

   186 static inline void cxMapStoreObjects(CxMap *map) {

   187     map->store_pointers = false;

   188 }

   190 /**

   191  * Advises the map to only store pointers to the objects.

   192  *

   193  * Retrieving objects from this list will yield the original pointers stored.

   194  *

   195  * @note This function forcibly sets the element size to the size of a pointer.

   196  * Invoking this function on a non-empty map that already stores copies of

   197  * objects is undefined.

   198  *

   199  * @param map the map

   200  * @see cxMapStoreObjects()

   201  */

   202 __attribute__((__nonnull__))

   203 static inline void cxMapStorePointers(CxMap *map) {

   204     map->store_pointers = true;

   205     map->itemsize = sizeof(void *);

   206 }

   209 /**

   210  * Deallocates the memory of the specified map.

   211  *

   212  * @param map the map to be destroyed

   213  */

   214 __attribute__((__nonnull__))

   215 static inline void cxMapDestroy(CxMap *map) {

   216     // TODO: likely to add auto-free feature for contents in the future

   217     map->cl->destructor(map);

   218 }

   221 /**

   222  * Clears a map by removing all elements.

   223  *

   224  * @param map the map to be cleared

   225  */

   226 __attribute__((__nonnull__))

   227 static inline void cxMapClear(CxMap *map) {

   228     map->cl->clear(map);

   229 }

   231 /**

   232  * Puts a key/value-pair into the map.

   233  *

   234  * @param map the map

   235  * @param key the key

   236  * @param value the value

   237  * @return 0 on success, non-zero value on failure

   238  */

   239 __attribute__((__nonnull__))

   240 static inline int cxMapPut(

   241         CxMap *map,

   242         CxHashKey key,

   243         void *value

   244 ) {

   245     return map->cl->put(map, key, value);

   246 }

   248 /**

   249  * Retrieves a value by using a key.

   250  *

   251  * @param map the map

   252  * @param key the key

   253  * @return the value

   254  */

   255 __attribute__((__nonnull__, __warn_unused_result__))

   256 static inline void *cxMapGet(

   257         CxMap const *map,

   258         CxHashKey key

   259 ) {

   260     return map->cl->get(map, key);

   261 }

   263 /**

   264  * Removes a key/value-pair from the map by using the key.

   265  *

   266  * If this map is storing pointers, you should make sure that the map

   267  * is not the last location where this pointer is stored.

   268  * Otherwise, use cxMapRemoveAndGet() to retrieve the pointer while

   269  * removing it from the map.

   270  *

   271  * @param map the map

   272  * @param key the key

   273  * @see cxMapRemoveAndGet()

   274  */

   275 __attribute__((__nonnull__))

   276 static inline void cxMapRemove(

   277         CxMap *map,

   278         CxHashKey key

   279 ) {

   280     (void) map->cl->remove(map, key);

   281 }

   283 /**

   284  * Removes a key/value-pair from the map by using the key.

   285  *

   286  * This function should only be used when the map is storing pointers,

   287  * in order to retrieve the pointer you are about to remove.

   288  * In any other case, cxMapRemove() is sufficient.

   289  *

   290  * @param map the map

   291  * @param key the key

   292  * @return the stored pointer or \c NULL if either the key is not present

   293  * in the map or the map is not storing pointers

   294  * @see cxMapStorePointers()

   295  */

   296 __attribute__((__nonnull__, __warn_unused_result__))

   297 static inline void *cxMapRemoveAndGet(

   298         CxMap *map,

   299         CxHashKey key

   300 ) {

   301     return map->cl->remove(map, key);

   302 }

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

   306 /**

   307  * Creates a value iterator for a map.

   308  *

   309  * \note An iterator iterates over all elements successively. Therefore the order

   310  * highly depends on the map implementation and may change arbitrarily when the contents change.

   311  *

   312  * @param map the map to create the iterator for

   313  * @return an iterator for the currently stored values

   314  */

   315 __attribute__((__nonnull__, __warn_unused_result__))

   316 static inline CxIterator cxMapIteratorValues(CxMap *map) {

   317     return map->cl->iterator_values(map);

   318 }

   320 /**

   321  * Creates a key iterator for a map.

   322  *

   323  * The elements of the iterator are keys of type CxHashKey.

   324  *

   325  * \note An iterator iterates over all elements successively. Therefore the order

   326  * highly depends on the map implementation and may change arbitrarily when the contents change.

   327  *

   328  * @param map the map to create the iterator for

   329  * @return an iterator for the currently stored keys

   330  */

   331 __attribute__((__nonnull__, __warn_unused_result__))

   332 static inline CxIterator cxMapIteratorKeys(CxMap *map) {

   333     return map->cl->iterator_keys(map);

   334 }

   336 /**

   337  * Creates an iterator for a map.

   338  *

   339  * The elements of the iterator are key/value pairs of type CxMapEntry.

   340  *

   341  * \note An iterator iterates over all elements successively. Therefore the order

   342  * highly depends on the map implementation and may change arbitrarily when the contents change.

   343  *

   344  * @param map the map to create the iterator for

   345  * @return an iterator for the currently stored entries

   346  * @see cxMapIteratorKeys()

   347  * @see cxMapIteratorValues()

   348  */

   349 __attribute__((__nonnull__, __warn_unused_result__))

   350 static inline CxIterator cxMapIterator(CxMap *map) {

   351     return map->cl->iterator(map);

   352 }

   355 /**

   356  * Creates a mutating iterator over the values of a map.

   357  *

   358  * \note An iterator iterates over all elements successively. Therefore the order

   359  * highly depends on the map implementation and may change arbitrarily when the contents change.

   360  *

   361  * @param map the map to create the iterator for

   362  * @return an iterator for the currently stored values

   363  */

   364 __attribute__((__nonnull__, __warn_unused_result__))

   365 static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {

   366     return map->cl->mut_iterator_values(map);

   367 }

   369 /**

   370  * Creates a mutating iterator over the keys of a map.

   371  *

   372  * The elements of the iterator are keys of type CxHashKey.

   373  *

   374  * \note An iterator iterates over all elements successively. Therefore the order

   375  * highly depends on the map implementation and may change arbitrarily when the contents change.

   376  *

   377  * @param map the map to create the iterator for

   378  * @return an iterator for the currently stored keys

   379  */

   380 __attribute__((__nonnull__, __warn_unused_result__))

   381 static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {

   382     return map->cl->mut_iterator_keys(map);

   383 }

   385 /**

   386  * Creates a mutating iterator for a map.

   387  *

   388  * The elements of the iterator are key/value pairs of type CxMapEntry.

   389  *

   390  * \note An iterator iterates over all elements successively. Therefore the order

   391  * highly depends on the map implementation and may change arbitrarily when the contents change.

   392  *

   393  * @param map the map to create the iterator for

   394  * @return an iterator for the currently stored entries

   395  * @see cxMapMutIteratorKeys()

   396  * @see cxMapMutIteratorValues()

   397  */

   398 __attribute__((__nonnull__, __warn_unused_result__))

   399 static inline CxMutIterator cxMapMutIterator(CxMap *map) {

   400     return map->cl->mut_iterator(map);

   401 }

   403 #ifdef    __cplusplus

   404 }

   405 #endif

   407 #endif // UCX_MAP_H

Mercurial > hg > ucx / file revision

src/cx/map.h@d7129285ac32

src/cx/map.h