ucx: src/cx/map.h@502105523db7

     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 "collection.h"

    42 #include "hash_key.h"

    44 #ifdef    __cplusplus

    45 extern "C" {

    46 #endif

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

    49 typedef struct cx_map_s CxMap;

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

    52 typedef struct cx_map_entry_s CxMapEntry;

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

    55 typedef struct cx_map_class_s cx_map_class;

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

    58 struct cx_map_s {

    59     /** The map class definition. */

    60     cx_map_class *cl;

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

    62     CxAllocator *allocator;

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

    64     size_t size;

    65     /**

    66      * The size of an element.

    67      */

    68     size_t item_size;

    69     /**

    70      * True, if this map shall store pointers instead

    71      * of copies of objects.

    72      */

    73     bool store_pointers;

    74 };

    76 /**

    77  * The class definition for arbitrary maps.

    78  */

    79 struct cx_map_class_s {

    80     /**

    81      * Deallocates the entire memory.

    82      */

    83     __attribute__((__nonnull__))

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

    86     /**

    87      * Removes all elements.

    88      */

    89     __attribute__((__nonnull__))

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

    92     /**

    93      * Add or overwrite an element.

    94      */

    95     __attribute__((__nonnull__))

    96     int (*put)(

    97             CxMap *map,

    98             CxHashKey key,

    99             void *value

   100     );

   102     /**

   103      * Returns an element.

   104      */

   105     __attribute__((__nonnull__, __warn_unused_result__))

   106     void *(*get)(

   107             CxMap const *map,

   108             CxHashKey key

   109     );

   111     /**

   112      * Removes an element.

   113      */

   114     __attribute__((__nonnull__))

   115     void *(*remove)(

   116             CxMap *map,

   117             CxHashKey key

   118     );

   120     /**

   121      * Iterator over the key/value pairs.

   122      */

   123     __attribute__((__nonnull__, __warn_unused_result__))

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

   126     /**

   127      * Iterator over the keys.

   128      */

   129     __attribute__((__nonnull__, __warn_unused_result__))

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

   132     /**

   133      * Iterator over the values.

   134      */

   135     __attribute__((__nonnull__, __warn_unused_result__))

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

   138     /**

   139      * Mutating iterator over the key/value pairs.

   140      */

   141     __attribute__((__nonnull__, __warn_unused_result__))

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

   144     /**

   145      * Mutating iterator over the keys.

   146      */

   147     __attribute__((__nonnull__, __warn_unused_result__))

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

   150     /**

   151      * Mutating iterator over the values.

   152      */

   153     __attribute__((__nonnull__, __warn_unused_result__))

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

   155 };

   157 /**

   158  * A map entry.

   159  */

   160 struct cx_map_entry_s {

   161     /**

   162      * A pointer to the key.

   163      */

   164     CxHashKey const *key;

   165     /**

   166      * A pointer to the value.

   167      */

   168     void *value;

   169 };

   171 /**

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

   173  *

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

   175  * within this list.

   176  *

   177  * @param map the map

   178  * @see cxMapStorePointers()

   179  */

   180 __attribute__((__nonnull__))

   181 static inline void cxMapStoreObjects(CxMap *map) {

   182     map->store_pointers = false;

   183 }

   185 /**

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

   187  *

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

   189  *

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

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

   192  * objects is undefined.

   193  *

   194  * @param map the map

   195  * @see cxMapStoreObjects()

   196  */

   197 __attribute__((__nonnull__))

   198 static inline void cxMapStorePointers(CxMap *map) {

   199     map->store_pointers = true;

   200     map->item_size = sizeof(void *);

   201 }

   204 /**

   205  * Deallocates the memory of the specified map.

   206  *

   207  * @param map the map to be destroyed

   208  */

   209 __attribute__((__nonnull__))

   210 static inline void cxMapDestroy(CxMap *map) {

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

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

   213 }

   216 /**

   217  * Clears a map by removing all elements.

   218  *

   219  * @param map the map to be cleared

   220  */

   221 __attribute__((__nonnull__))

   222 static inline void cxMapClear(CxMap *map) {

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

   224 }

   226 /**

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

   228  *

   229  * @param map the map

   230  * @param key the key

   231  * @param value the value

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

   233  */

   234 __attribute__((__nonnull__))

   235 static inline int cxMapPut(

   236         CxMap *map,

   237         CxHashKey key,

   238         void *value

   239 ) {

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

   241 }

   243 /**

   244  * Retrieves a value by using a key.

   245  *

   246  * @param map the map

   247  * @param key the key

   248  * @return the value

   249  */

   250 __attribute__((__nonnull__, __warn_unused_result__))

   251 static inline void *cxMapGet(

   252         CxMap const *map,

   253         CxHashKey key

   254 ) {

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

   256 }

   258 /**

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

   260  *

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

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

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

   264  * removing it from the map.

   265  *

   266  * @param map the map

   267  * @param key the key

   268  * @see cxMapRemoveAndGet()

   269  */

   270 __attribute__((__nonnull__))

   271 static inline void cxMapRemove(

   272         CxMap *map,

   273         CxHashKey key

   274 ) {

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

   276 }

   278 /**

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

   280  *

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

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

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

   284  *

   285  * @param map the map

   286  * @param key the key

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

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

   289  * @see cxMapStorePointers()

   290  */

   291 __attribute__((__nonnull__, __warn_unused_result__))

   292 static inline void *cxMapRemoveAndGet(

   293         CxMap *map,

   294         CxHashKey key

   295 ) {

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

   297 }

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

   301 /**

   302  * Creates a value iterator for a map.

   303  *

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

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

   306  *

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

   308  * @return an iterator for the currently stored values

   309  */

   310 __attribute__((__nonnull__, __warn_unused_result__))

   311 static inline CxIterator cxMapIteratorValues(CxMap *map) {

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

   313 }

   315 /**

   316  * Creates a key iterator for a map.

   317  *

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

   319  *

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

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

   322  *

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

   324  * @return an iterator for the currently stored keys

   325  */

   326 __attribute__((__nonnull__, __warn_unused_result__))

   327 static inline CxIterator cxMapIteratorKeys(CxMap *map) {

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

   329 }

   331 /**

   332  * Creates an iterator for a map.

   333  *

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

   335  *

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

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

   338  *

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

   340  * @return an iterator for the currently stored entries

   341  * @see cxMapIteratorKeys()

   342  * @see cxMapIteratorValues()

   343  */

   344 __attribute__((__nonnull__, __warn_unused_result__))

   345 static inline CxIterator cxMapIterator(CxMap *map) {

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

   347 }

   350 /**

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

   352  *

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

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

   355  *

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

   357  * @return an iterator for the currently stored values

   358  */

   359 __attribute__((__nonnull__, __warn_unused_result__))

   360 static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {

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

   362 }

   364 /**

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

   366  *

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

   368  *

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

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

   371  *

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

   373  * @return an iterator for the currently stored keys

   374  */

   375 __attribute__((__nonnull__, __warn_unused_result__))

   376 static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {

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

   378 }

   380 /**

   381  * Creates a mutating iterator for a map.

   382  *

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

   384  *

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

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

   387  *

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

   389  * @return an iterator for the currently stored entries

   390  * @see cxMapMutIteratorKeys()

   391  * @see cxMapMutIteratorValues()

   392  */

   393 __attribute__((__nonnull__, __warn_unused_result__))

   394 static inline CxMutIterator cxMapMutIterator(CxMap *map) {

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

   396 }

   398 #ifdef    __cplusplus

   399 }

   400 #endif

   402 #endif // UCX_MAP_H

Mercurial > hg > ucx / file revision

src/cx/map.h@502105523db7

src/cx/map.h