ucx: src/cx/map.h@56c62780582e

     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 /** Type for the UCX map. */

    50 typedef struct cx_map_s CxMap;

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

    53 typedef struct cx_map_entry_s CxMapEntry;

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

    56 typedef struct cx_map_class_s cx_map_class;

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

    59 struct cx_map_s {

    60     /** The map class definition. */

    61     cx_map_class *cl;

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

    63     CxAllocator *allocator;

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

    65     size_t size;

    66     /**

    67      * The size of an element.

    68      */

    69     size_t itemsize;

    70     /**

    71      * True, if this map shall store pointers instead

    72      * of copies of objects.

    73      */

    74     bool store_pointers;

    75 };

    77 /**

    78  * The class definition for arbitrary maps.

    79  */

    80 struct cx_map_class_s {

    81     /**

    82      * Deallocates the entire memory.

    83      */

    84     __attribute__((__nonnull__))

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

    87     /**

    88      * Removes all elements.

    89      */

    90     __attribute__((__nonnull__))

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

    93     /**

    94      * Add or overwrite an element.

    95      */

    96     __attribute__((__nonnull__))

    97     int (*put)(

    98             CxMap *map,

    99             CxHashKey key,

   100             void *value

   101     );

   103     /**

   104      * Returns an element.

   105      */

   106     __attribute__((__nonnull__, __warn_unused_result__))

   107     void *(*get)(

   108             CxMap const *map,

   109             CxHashKey key

   110     );

   112     /**

   113      * Removes an element.

   114      */

   115     __attribute__((__nonnull__, __warn_unused_result__))

   116     void *(*remove)(

   117             CxMap *map,

   118             CxHashKey key

   119     );

   121     /**

   122      * Iterator over the key/value pairs.

   123      */

   124     __attribute__((__nonnull__, __warn_unused_result__))

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

   127     /**

   128      * Iterator over the keys.

   129      */

   130     __attribute__((__nonnull__, __warn_unused_result__))

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

   133     /**

   134      * Iterator over the values.

   135      */

   136     __attribute__((__nonnull__, __warn_unused_result__))

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

   139     /**

   140      * Mutating iterator over the key/value pairs.

   141      */

   142     __attribute__((__nonnull__, __warn_unused_result__))

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

   145     /**

   146      * Mutating iterator over the keys.

   147      */

   148     __attribute__((__nonnull__, __warn_unused_result__))

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

   151     /**

   152      * Mutating iterator over the values.

   153      */

   154     __attribute__((__nonnull__, __warn_unused_result__))

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

   156 };

   158 /**

   159  * A map entry.

   160  */

   161 struct cx_map_entry_s {

   162     /**

   163      * A pointer to the key.

   164      */

   165     CxHashKey const *key;

   166     /**

   167      * A pointer to the value.

   168      */

   169     void *value;

   170 };

   172 /**

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

   174  *

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

   176  * within this list.

   177  *

   178  * @param map the map

   179  * @see cxMapStorePointers()

   180  */

   181 __attribute__((__nonnull__))

   182 static inline void cxMapStoreObjects(CxMap *map) {

   183     map->store_pointers = false;

   184 }

   186 /**

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

   188  *

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

   190  *

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

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

   193  * objects is undefined.

   194  *

   195  * @param map the map

   196  * @see cxMapStoreObjects()

   197  */

   198 __attribute__((__nonnull__))

   199 static inline void cxMapStorePointers(CxMap *map) {

   200     map->store_pointers = true;

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

   202 }

   205 /**

   206  * Deallocates the memory of the specified map.

   207  *

   208  * @param map the map to be destroyed

   209  */

   210 __attribute__((__nonnull__))

   211 static inline void cxMapDestroy(CxMap *map) {

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

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

   214 }

   217 /**

   218  * Clears a map by removing all elements.

   219  *

   220  * @param map the map to be cleared

   221  */

   222 __attribute__((__nonnull__))

   223 static inline void cxMapClear(CxMap *map) {

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

   225 }

   227 /**

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

   229  *

   230  * @param map the map

   231  * @param key the key

   232  * @param value the value

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

   234  */

   235 __attribute__((__nonnull__))

   236 static inline int cxMapPut(

   237         CxMap *map,

   238         CxHashKey key,

   239         void *value

   240 ) {

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

   242 }

   244 /**

   245  * Retrieves a value by using a key.

   246  *

   247  * @param map the map

   248  * @param key the key

   249  * @return the value

   250  */

   251 __attribute__((__nonnull__, __warn_unused_result__))

   252 static inline void *cxMapGet(

   253         CxMap const *map,

   254         CxHashKey key

   255 ) {

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

   257 }

   259 /**

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

   261  *

   262  * @param map the map

   263  * @param key the key

   264  * @return if this map is storing pointers, the removed value, \c NULL otherwise

   265  * @see cxMapStorePointers()

   266  */

   267 __attribute__((__nonnull__, __warn_unused_result__))

   268 static inline void *cxMapRemove(

   269         CxMap *map,

   270         CxHashKey key

   271 ) {

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

   273 }

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

   277 /**

   278  * Creates a value iterator for a map.

   279  *

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

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

   282  *

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

   284  * @return an iterator for the currently stored values

   285  */

   286 __attribute__((__nonnull__, __warn_unused_result__))

   287 static inline CxIterator cxMapIteratorValues(CxMap *map) {

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

   289 }

   291 /**

   292  * Creates a key iterator for a map.

   293  *

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

   295  *

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

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

   298  *

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

   300  * @return an iterator for the currently stored keys

   301  */

   302 __attribute__((__nonnull__, __warn_unused_result__))

   303 static inline CxIterator cxMapIteratorKeys(CxMap *map) {

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

   305 }

   307 /**

   308  * Creates an iterator for a map.

   309  *

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

   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 entries

   317  * @see cxMapIteratorKeys()

   318  * @see cxMapIteratorValues()

   319  */

   320 __attribute__((__nonnull__, __warn_unused_result__))

   321 static inline CxIterator cxMapIterator(CxMap *map) {

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

   323 }

   326 /**

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

   328  *

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

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

   331  *

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

   333  * @return an iterator for the currently stored values

   334  */

   335 __attribute__((__nonnull__, __warn_unused_result__))

   336 static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {

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

   338 }

   340 /**

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

   342  *

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

   344  *

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

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

   347  *

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

   349  * @return an iterator for the currently stored keys

   350  */

   351 __attribute__((__nonnull__, __warn_unused_result__))

   352 static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {

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

   354 }

   356 /**

   357  * Creates a mutating iterator for a map.

   358  *

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

   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 entries

   366  * @see cxMapMutIteratorKeys()

   367  * @see cxMapMutIteratorValues()

   368  */

   369 __attribute__((__nonnull__, __warn_unused_result__))

   370 static inline CxMutIterator cxMapMutIterator(CxMap *map) {

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

   372 }

   374 #ifdef    __cplusplus

   375 }

   376 #endif

   378 #endif // UCX_MAP_H

Mercurial > hg > ucx / file revision

src/cx/map.h@56c62780582e

src/cx/map.h