ucx: src/cx/map.h@4a06fd63909a

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

   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  * If this map is storing pointers, you should make sure that the map

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

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

   265  * removing it from the map.

   266  *

   267  * @param map the map

   268  * @param key the key

   269  * @see cxMapRemoveAndGet()

   270  */

   271 __attribute__((__nonnull__))

   272 static inline void cxMapRemove(

   273         CxMap *map,

   274         CxHashKey key

   275 ) {

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

   277 }

   279 /**

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

   281  *

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

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

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

   285  *

   286  * @param map the map

   287  * @param key the key

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

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

   290  * @see cxMapStorePointers()

   291  */

   292 __attribute__((__nonnull__, __warn_unused_result__))

   293 static inline void *cxMapRemoveAndGet(

   294         CxMap *map,

   295         CxHashKey key

   296 ) {

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

   298 }

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

   302 /**

   303  * Creates a value iterator for a map.

   304  *

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

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

   307  *

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

   309  * @return an iterator for the currently stored values

   310  */

   311 __attribute__((__nonnull__, __warn_unused_result__))

   312 static inline CxIterator cxMapIteratorValues(CxMap *map) {

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

   314 }

   316 /**

   317  * Creates a key iterator for a map.

   318  *

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

   320  *

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

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

   323  *

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

   325  * @return an iterator for the currently stored keys

   326  */

   327 __attribute__((__nonnull__, __warn_unused_result__))

   328 static inline CxIterator cxMapIteratorKeys(CxMap *map) {

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

   330 }

   332 /**

   333  * Creates an iterator for a map.

   334  *

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

   336  *

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

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

   339  *

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

   341  * @return an iterator for the currently stored entries

   342  * @see cxMapIteratorKeys()

   343  * @see cxMapIteratorValues()

   344  */

   345 __attribute__((__nonnull__, __warn_unused_result__))

   346 static inline CxIterator cxMapIterator(CxMap *map) {

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

   348 }

   351 /**

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

   353  *

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

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

   356  *

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

   358  * @return an iterator for the currently stored values

   359  */

   360 __attribute__((__nonnull__, __warn_unused_result__))

   361 static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {

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

   363 }

   365 /**

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

   367  *

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

   369  *

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

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

   372  *

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

   374  * @return an iterator for the currently stored keys

   375  */

   376 __attribute__((__nonnull__, __warn_unused_result__))

   377 static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {

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

   379 }

   381 /**

   382  * Creates a mutating iterator for a map.

   383  *

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

   385  *

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

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

   388  *

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

   390  * @return an iterator for the currently stored entries

   391  * @see cxMapMutIteratorKeys()

   392  * @see cxMapMutIteratorValues()

   393  */

   394 __attribute__((__nonnull__, __warn_unused_result__))

   395 static inline CxMutIterator cxMapMutIterator(CxMap *map) {

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

   397 }

   399 #ifdef    __cplusplus

   400 }

   401 #endif

   403 #endif // UCX_MAP_H

Mercurial > hg > ucx / file revision

src/cx/map.h@4a06fd63909a

src/cx/map.h