1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/cx/hash_map.h Wed May 18 16:26:32 2022 +0200
1.3 @@ -0,0 +1,123 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
1.6 + *
1.7 + * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
1.8 + *
1.9 + * Redistribution and use in source and binary forms, with or without
1.10 + * modification, are permitted provided that the following conditions are met:
1.11 + *
1.12 + * 1. Redistributions of source code must retain the above copyright
1.13 + * notice, this list of conditions and the following disclaimer.
1.14 + *
1.15 + * 2. Redistributions in binary form must reproduce the above copyright
1.16 + * notice, this list of conditions and the following disclaimer in the
1.17 + * documentation and/or other materials provided with the distribution.
1.18 + *
1.19 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
1.20 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1.21 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
1.22 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
1.23 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
1.24 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
1.25 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
1.26 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
1.27 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
1.28 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
1.29 + * POSSIBILITY OF SUCH DAMAGE.
1.30 + */
1.31 +/**
1.32 + * \file map.h
1.33 + * \brief Interface for map implementations.
1.34 + * \author Mike Becker
1.35 + * \author Olaf Wintermann
1.36 + * \version 3.0
1.37 + * \copyright 2-Clause BSD License
1.38 + */
1.39 +
1.40 +#ifndef UCX_HASH_MAP_H
1.41 +#define UCX_HASH_MAP_H
1.42 +
1.43 +#include "map.h"
1.44 +
1.45 +#ifdef __cplusplus
1.46 +extern "C" {
1.47 +#endif
1.48 +
1.49 +/** Internal structure for a key within a hash map. */
1.50 +struct cx_hash_map_key_s {
1.51 + /** The key data. */
1.52 + CxDataPtr data;
1.53 + /** The hash value of the key data. */
1.54 + unsigned hash;
1.55 +};
1.56 +
1.57 +/** Internal structure for an element of a hash map. */
1.58 +struct cx_hash_map_element_s {
1.59 + /** The value data. */
1.60 + void *data;
1.61 +
1.62 + /** A pointer to the next element in the current bucket. */
1.63 + struct cx_hash_map_element_s *next;
1.64 +
1.65 + /** The corresponding key. */
1.66 + struct cx_hash_map_key_s key;
1.67 +};
1.68 +
1.69 +
1.70 +/**
1.71 + * Creates a new hash map with the specified size using a UcxAllocator.
1.72 + *
1.73 + * @param allocator the allocator to use
1.74 + * @param buckets the initial number of buckets in this hash map
1.75 + * @return a pointer to the new hash map
1.76 + */
1.77 +CxMap *cxHashMapCreate(
1.78 + CxAllocator *allocator,
1.79 + size_t buckets
1.80 +);
1.81 +
1.82 +/**
1.83 + * Increases the number of buckets, if necessary.
1.84 + *
1.85 + * The load value is \c loadFactor*buckets. If the element count exceeds the load
1.86 + * value, the map needs to be rehashed. Otherwise, no action is performed and
1.87 + * this function simply returns 0.
1.88 + *
1.89 + * The rehashing process ensures, that the number of buckets is at least
1.90 + * \p bucketFactor times the number of stored items. So there is enough room for additional
1.91 + * elements without the need of another soon rehashing.
1.92 + *
1.93 + * You can use this function after filling a map to dramatically increase access performance.
1.94 + *
1.95 + * @note If the specified map is not a hash map, the behavior is undefined.
1.96 + *
1.97 + * @param map the map to rehash
1.98 + * @param loadFactor a percentage threshold for the load of the map
1.99 + * @param bucketFactor a factor for the number of buckets that shall be available after rehashing
1.100 + * @return zero on success, non-zero if a memory allocation error occurred
1.101 + */
1.102 +__attribute__((__nonnull__))
1.103 +int cxMapRehash2(
1.104 + CxMap *map,
1.105 + float loadFactor,
1.106 + float bucketFactor
1.107 +);
1.108 +
1.109 +/**
1.110 + * Rehashes the map with load factor 0.75 and bucket factor 2.5.
1.111 + *
1.112 + * @param map the map to rehash
1.113 + * @return zero on success, non-zero if a memory allocation error occurred
1.114 + * @see cxMapRehash2()
1.115 + */
1.116 +__attribute__((__nonnull__))
1.117 +static inline int cxMapRehash(CxMap *map) {
1.118 + return cxMapRehash2(map, 0.75f, 2.5f);
1.119 +}
1.120 +
1.121 +
1.122 +#ifdef __cplusplus
1.123 +} // extern "C"
1.124 +#endif
1.125 +
1.126 +#endif // UCX_HASH_MAP_H
