ucx: src/cx/map.h@64919f63f059

     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     CX_COLLECTION_MEMBERS

    60     /** The map class definition. */

    61     cx_map_class *cl;

    62 };

    64 /**

    65  * The class definition for arbitrary maps.

    66  */

    67 struct cx_map_class_s {

    68     /**

    69      * Deallocates the entire memory.

    70      */

    71     __attribute__((__nonnull__))

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

    74     /**

    75      * Removes all elements.

    76      */

    77     __attribute__((__nonnull__))

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

    80     /**

    81      * Add or overwrite an element.

    82      */

    83     __attribute__((__nonnull__))

    84     int (*put)(

    85             CxMap *map,

    86             CxHashKey key,

    87             void *value

    88     );

    90     /**

    91      * Returns an element.

    92      */

    93     __attribute__((__nonnull__, __warn_unused_result__))

    94     void *(*get)(

    95             CxMap const *map,

    96             CxHashKey key

    97     );

    99     /**

   100      * Removes an element.

   101      */

   102     __attribute__((__nonnull__))

   103     void *(*remove)(

   104             CxMap *map,

   105             CxHashKey key,

   106             bool destroy

   107     );

   109     /**

   110      * Iterator over the key/value pairs.

   111      */

   112     __attribute__((__nonnull__, __warn_unused_result__))

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

   115     /**

   116      * Iterator over the keys.

   117      */

   118     __attribute__((__nonnull__, __warn_unused_result__))

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

   121     /**

   122      * Iterator over the values.

   123      */

   124     __attribute__((__nonnull__, __warn_unused_result__))

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

   127     /**

   128      * Mutating iterator over the key/value pairs.

   129      */

   130     __attribute__((__nonnull__, __warn_unused_result__))

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

   133     /**

   134      * Mutating iterator over the keys.

   135      */

   136     __attribute__((__nonnull__, __warn_unused_result__))

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

   139     /**

   140      * Mutating iterator over the values.

   141      */

   142     __attribute__((__nonnull__, __warn_unused_result__))

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

   144 };

   146 /**

   147  * A map entry.

   148  */

   149 struct cx_map_entry_s {

   150     /**

   151      * A pointer to the key.

   152      */

   153     CxHashKey const *key;

   154     /**

   155      * A pointer to the value.

   156      */

   157     void *value;

   158 };

   160 /**

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

   162  *

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

   164  * within this list.

   165  *

   166  * @param map the map

   167  * @see cxMapStorePointers()

   168  */

   169 __attribute__((__nonnull__))

   170 static inline void cxMapStoreObjects(CxMap *map) {

   171     map->store_pointer = false;

   172 }

   174 /**

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

   176  *

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

   178  *

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

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

   181  * objects is undefined.

   182  *

   183  * @param map the map

   184  * @see cxMapStoreObjects()

   185  */

   186 __attribute__((__nonnull__))

   187 static inline void cxMapStorePointers(CxMap *map) {

   188     map->store_pointer = true;

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

   190 }

   193 /**

   194  * Deallocates the memory of the specified map.

   195  *

   196  * @param map the map to be destroyed

   197  */

   198 __attribute__((__nonnull__))

   199 static inline void cxMapDestroy(CxMap *map) {

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

   201 }

   204 /**

   205  * Clears a map by removing all elements.

   206  *

   207  * @param map the map to be cleared

   208  */

   209 __attribute__((__nonnull__))

   210 static inline void cxMapClear(CxMap *map) {

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

   212 }

   214 /**

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

   216  *

   217  * @param map the map

   218  * @param key the key

   219  * @param value the value

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

   221  */

   222 __attribute__((__nonnull__))

   223 static inline int cxMapPut(

   224         CxMap *map,

   225         CxHashKey key,

   226         void *value

   227 ) {

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

   229 }

   231 /**

   232  * Retrieves a value by using a key.

   233  *

   234  * @param map the map

   235  * @param key the key

   236  * @return the value

   237  */

   238 __attribute__((__nonnull__, __warn_unused_result__))

   239 static inline void *cxMapGet(

   240         CxMap const *map,

   241         CxHashKey key

   242 ) {

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

   244 }

   246 /**

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

   248  *

   249  * Always invokes the destructor function, if any, on the removed element.

   250  * If this map is storing pointers and you just want to retrieve the pointer

   251  * without invoking the destructor, use cxMapRemoveAndGet().

   252  * If you just want to detach the element from the map without invoking the

   253  * destructor or returning the element, use cxMapDetach().

   254  *

   255  * @param map the map

   256  * @param key the key

   257  * @see cxMapRemoveAndGet()

   258  * @see cxMapDetach()

   259  */

   260 __attribute__((__nonnull__))

   261 static inline void cxMapRemove(

   262         CxMap *map,

   263         CxHashKey key

   264 ) {

   265     (void) map->cl->remove(map, key, true);

   266 }

   268 /**

   269  * Detaches a key/value-pair from the map by using the key

   270  * without invoking the destructor.

   271  *

   272  * In general, you should only use this function if the map does not own

   273  * the data and there is a valid reference to the data somewhere else

   274  * in the program. In all other cases it is prefarable to use

   275  * cxMapRemove() or cxMapRemoveAndGet().

   276  *

   277  * @param map the map

   278  * @param key the key

   279  * @see cxMapRemove()

   280  * @see cxMapRemoveAndGet()

   281  */

   282 __attribute__((__nonnull__))

   283 static inline void cxMapDetach(

   284         CxMap *map,

   285         CxHashKey key

   286 ) {

   287     (void) map->cl->remove(map, key, false);

   288 }

   290 /**

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

   292  *

   293  * This function can be used when the map is storing pointers,

   294  * in order to retrieve the pointer from the map without invoking

   295  * any destructor function. Sometimes you do not want the pointer

   296  * to be returned - in that case (instead of suppressing the "unused

   297  * result" warning) you can use cxMapDetach().

   298  *

   299  * If this map is not storing pointers, this function behaves like

   300  * cxMapRemove() and returns \c NULL.

   301  *

   302  * @param map the map

   303  * @param key the key

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

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

   306  * @see cxMapStorePointers()

   307  * @see cxMapDetach()

   308  */

   309 __attribute__((__nonnull__, __warn_unused_result__))

   310 static inline void *cxMapRemoveAndGet(

   311         CxMap *map,

   312         CxHashKey key

   313 ) {

   314     return map->cl->remove(map, key, !map->store_pointer);

   315 }

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

   319 /**

   320  * Creates a value iterator for a map.

   321  *

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

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

   324  *

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

   326  * @return an iterator for the currently stored values

   327  */

   328 __attribute__((__nonnull__, __warn_unused_result__))

   329 static inline CxIterator cxMapIteratorValues(CxMap *map) {

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

   331 }

   333 /**

   334  * Creates a key iterator for a map.

   335  *

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

   337  *

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

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

   340  *

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

   342  * @return an iterator for the currently stored keys

   343  */

   344 __attribute__((__nonnull__, __warn_unused_result__))

   345 static inline CxIterator cxMapIteratorKeys(CxMap *map) {

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

   347 }

   349 /**

   350  * Creates an iterator for a map.

   351  *

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

   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 entries

   359  * @see cxMapIteratorKeys()

   360  * @see cxMapIteratorValues()

   361  */

   362 __attribute__((__nonnull__, __warn_unused_result__))

   363 static inline CxIterator cxMapIterator(CxMap *map) {

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

   365 }

   368 /**

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

   370  *

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

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

   373  *

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

   375  * @return an iterator for the currently stored values

   376  */

   377 __attribute__((__nonnull__, __warn_unused_result__))

   378 static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {

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

   380 }

   382 /**

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

   384  *

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

   386  *

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

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

   389  *

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

   391  * @return an iterator for the currently stored keys

   392  */

   393 __attribute__((__nonnull__, __warn_unused_result__))

   394 static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {

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

   396 }

   398 /**

   399  * Creates a mutating iterator for a map.

   400  *

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

   402  *

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

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

   405  *

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

   407  * @return an iterator for the currently stored entries

   408  * @see cxMapMutIteratorKeys()

   409  * @see cxMapMutIteratorValues()

   410  */

   411 __attribute__((__nonnull__, __warn_unused_result__))

   412 static inline CxMutIterator cxMapMutIterator(CxMap *map) {

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

   414 }

   416 #ifdef    __cplusplus

   417 }

   418 #endif

   420 #endif // UCX_MAP_H

Mercurial > hg > ucx / file revision

src/cx/map.h@64919f63f059

src/cx/map.h