ucx: src/cx/map.h@b09aae58bba4

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

    41 #include "hash_key.h"

    43 #ifdef    __cplusplus

    44 extern "C" {

    45 #endif

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

    48 typedef struct cx_map_s CxMap;

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

    51 typedef struct cx_map_entry_s CxMapEntry;

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

    54 typedef struct cx_map_class_s cx_map_class;

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

    57 struct cx_map_s {

    58     /** The map class definition. */

    59     cx_map_class *cl;

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

    61     CxAllocator *allocator;

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

    63     size_t size;

    64     /**

    65      * The size of an element.

    66      */

    67     size_t item_size;

    68     /**

    69      * True, if this map shall store pointers instead

    70      * of copies of objects.

    71      */

    72     bool store_pointers;

    73 };

    75 /**

    76  * The class definition for arbitrary maps.

    77  */

    78 struct cx_map_class_s {

    79     /**

    80      * Deallocates the entire memory.

    81      */

    82     __attribute__((__nonnull__))

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

    85     /**

    86      * Removes all elements.

    87      */

    88     __attribute__((__nonnull__))

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

    91     /**

    92      * Add or overwrite an element.

    93      */

    94     __attribute__((__nonnull__))

    95     int (*put)(

    96             CxMap *map,

    97             CxHashKey key,

    98             void *value

    99     );

   101     /**

   102      * Returns an element.

   103      */

   104     __attribute__((__nonnull__, __warn_unused_result__))

   105     void *(*get)(

   106             CxMap const *map,

   107             CxHashKey key

   108     );

   110     /**

   111      * Removes an element.

   112      */

   113     __attribute__((__nonnull__))

   114     void *(*remove)(

   115             CxMap *map,

   116             CxHashKey key

   117     );

   119     /**

   120      * Iterator over the key/value pairs.

   121      */

   122     __attribute__((__nonnull__, __warn_unused_result__))

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

   125     /**

   126      * Iterator over the keys.

   127      */

   128     __attribute__((__nonnull__, __warn_unused_result__))

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

   131     /**

   132      * Iterator over the values.

   133      */

   134     __attribute__((__nonnull__, __warn_unused_result__))

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

   137     /**

   138      * Mutating iterator over the key/value pairs.

   139      */

   140     __attribute__((__nonnull__, __warn_unused_result__))

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

   143     /**

   144      * Mutating iterator over the keys.

   145      */

   146     __attribute__((__nonnull__, __warn_unused_result__))

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

   149     /**

   150      * Mutating iterator over the values.

   151      */

   152     __attribute__((__nonnull__, __warn_unused_result__))

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

   154 };

   156 /**

   157  * A map entry.

   158  */

   159 struct cx_map_entry_s {

   160     /**

   161      * A pointer to the key.

   162      */

   163     CxHashKey const *key;

   164     /**

   165      * A pointer to the value.

   166      */

   167     void *value;

   168 };

   170 /**

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

   172  *

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

   174  * within this list.

   175  *

   176  * @param map the map

   177  * @see cxMapStorePointers()

   178  */

   179 __attribute__((__nonnull__))

   180 static inline void cxMapStoreObjects(CxMap *map) {

   181     map->store_pointers = false;

   182 }

   184 /**

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

   186  *

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

   188  *

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

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

   191  * objects is undefined.

   192  *

   193  * @param map the map

   194  * @see cxMapStoreObjects()

   195  */

   196 __attribute__((__nonnull__))

   197 static inline void cxMapStorePointers(CxMap *map) {

   198     map->store_pointers = true;

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

   200 }

   203 /**

   204  * Deallocates the memory of the specified map.

   205  *

   206  * @param map the map to be destroyed

   207  */

   208 __attribute__((__nonnull__))

   209 static inline void cxMapDestroy(CxMap *map) {

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

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

   212 }

   215 /**

   216  * Clears a map by removing all elements.

   217  *

   218  * @param map the map to be cleared

   219  */

   220 __attribute__((__nonnull__))

   221 static inline void cxMapClear(CxMap *map) {

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

   223 }

   225 /**

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

   227  *

   228  * @param map the map

   229  * @param key the key

   230  * @param value the value

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

   232  */

   233 __attribute__((__nonnull__))

   234 static inline int cxMapPut(

   235         CxMap *map,

   236         CxHashKey key,

   237         void *value

   238 ) {

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

   240 }

   242 /**

   243  * Retrieves a value by using a key.

   244  *

   245  * @param map the map

   246  * @param key the key

   247  * @return the value

   248  */

   249 __attribute__((__nonnull__, __warn_unused_result__))

   250 static inline void *cxMapGet(

   251         CxMap const *map,

   252         CxHashKey key

   253 ) {

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

   255 }

   257 /**

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

   259  *

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

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

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

   263  * removing it from the map.

   264  *

   265  * @param map the map

   266  * @param key the key

   267  * @see cxMapRemoveAndGet()

   268  */

   269 __attribute__((__nonnull__))

   270 static inline void cxMapRemove(

   271         CxMap *map,

   272         CxHashKey key

   273 ) {

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

   275 }

   277 /**

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

   279  *

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

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

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

   283  *

   284  * @param map the map

   285  * @param key the key

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

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

   288  * @see cxMapStorePointers()

   289  */

   290 __attribute__((__nonnull__, __warn_unused_result__))

   291 static inline void *cxMapRemoveAndGet(

   292         CxMap *map,

   293         CxHashKey key

   294 ) {

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

   296 }

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

   300 /**

   301  * Creates a value iterator for a map.

   302  *

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

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

   305  *

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

   307  * @return an iterator for the currently stored values

   308  */

   309 __attribute__((__nonnull__, __warn_unused_result__))

   310 static inline CxIterator cxMapIteratorValues(CxMap *map) {

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

   312 }

   314 /**

   315  * Creates a key iterator for a map.

   316  *

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

   318  *

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

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

   321  *

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

   323  * @return an iterator for the currently stored keys

   324  */

   325 __attribute__((__nonnull__, __warn_unused_result__))

   326 static inline CxIterator cxMapIteratorKeys(CxMap *map) {

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

   328 }

   330 /**

   331  * Creates an iterator for a map.

   332  *

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

   334  *

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

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

   337  *

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

   339  * @return an iterator for the currently stored entries

   340  * @see cxMapIteratorKeys()

   341  * @see cxMapIteratorValues()

   342  */

   343 __attribute__((__nonnull__, __warn_unused_result__))

   344 static inline CxIterator cxMapIterator(CxMap *map) {

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

   346 }

   349 /**

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

   351  *

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

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

   354  *

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

   356  * @return an iterator for the currently stored values

   357  */

   358 __attribute__((__nonnull__, __warn_unused_result__))

   359 static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {

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

   361 }

   363 /**

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

   365  *

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

   367  *

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

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

   370  *

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

   372  * @return an iterator for the currently stored keys

   373  */

   374 __attribute__((__nonnull__, __warn_unused_result__))

   375 static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {

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

   377 }

   379 /**

   380  * Creates a mutating iterator for a map.

   381  *

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

   383  *

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

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

   386  *

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

   388  * @return an iterator for the currently stored entries

   389  * @see cxMapMutIteratorKeys()

   390  * @see cxMapMutIteratorValues()

   391  */

   392 __attribute__((__nonnull__, __warn_unused_result__))

   393 static inline CxMutIterator cxMapMutIterator(CxMap *map) {

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

   395 }

   397 #ifdef    __cplusplus

   398 }

   399 #endif

   401 #endif // UCX_MAP_H

Mercurial > hg > ucx / file revision

src/cx/map.h@b09aae58bba4

src/cx/map.h