collections/PublicHeader/collections_map.h

   1 /*
   2 * Copyright (c) 2019 Apple Inc. All rights reserved.
   3 *
   4 * @APPLE_LICENSE_HEADER_START@
   5 *
   6 * This file contains Original Code and/or Modifications of Original Code
   7 * as defined in and that are subject to the Apple Public Source License
   8 * Version 2.0 (the 'License'). You may not use this file except in
   9 * compliance with the License. Please obtain a copy of the License at
  10 * http://www.opensource.apple.com/apsl/ and read it before using this
  11 * file.
  12 *
  13 * The Original Code and all software distributed under the License are
  14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18 * Please see the License for the specific language governing rights and
  19 * limitations under the License.
  20 *
  21 * @APPLE_LICENSE_HEADER_END@
  22 */
  23
  24 #ifndef _OS_COLLECTIONS_MAP_H
  25 #define _OS_COLLECTIONS_MAP_H
  26
  27 #include <os/base.h>
  28 #include <stdint.h>
  29 #include <stdbool.h>
  30 #include <TargetConditionals.h>
  31 #include <sys/types.h>
  32
  33 OS_ASSUME_NONNULL_BEGIN
  34
  35 struct os_map_config_s
  36 {
  37         const char *name; // Only used when DEBUG is set
  38         uint32_t initial_size; // If 0, default will be used
  39 };
  40
  41 // Increment this when changing os_map_config_s
  42 #define OS_MAP_CONFIG_S_VERSION 1
  43
  44 typedef struct os_map_config_s os_map_config_t;
  45
  46
  47 // *** HASH MAPS ***
  48 // Stores values for keys. Not safe for concurrent use.
  49
  50
  51 struct os_map_128_key_s {
  52         uint64_t x[2];
  53 };
  54
  55 typedef struct os_map_128_key_s os_map_128_key_t;
  56
  57 #if TARGET_RT_64_BIT
  58 #define OPAQUE_MAP_SIZE 3
  59 #else
  60 #define OPAQUE_MAP_SIZE 4
  61 #endif
  62
  63 struct _os_opaque_str_map_s {
  64         void *data[OPAQUE_MAP_SIZE];
  65 };
  66
  67 struct _os_opaque_32_map_s {
  68         void *data[OPAQUE_MAP_SIZE];
  69 };
  70
  71 struct _os_opaque_64_map_s {
  72         void *data[OPAQUE_MAP_SIZE];
  73 };
  74
  75 struct _os_opaque_128_map_s {
  76         void *data[OPAQUE_MAP_SIZE];
  77 };
  78
  79 // Map with string keys and void * values
  80 // Keys must be valid pointers.
  81 typedef struct _os_opaque_str_map_s os_map_str_t ;
  82 // Map with uint32_t keys and void * values
  83 typedef struct _os_opaque_32_map_s os_map_32_t ;
  84 // Map with uint64_t keys and void * values
  85 typedef struct _os_opaque_64_map_s os_map_64_t ;
  86 // Map with os_map_128_key_t keys and void * values
  87 typedef struct _os_opaque_128_map_s os_map_128_t ;
  88
  89 /*!
  90 * @function os_map_init
  91 * Initialize a map.
  92 *
  93 * @param t
  94 * The table to initialize
  95 *
  96 * @param config
  97 * The configuration to use for this table
  98 *
  99 * @discussion
 100 * An initialized map will use additional memory which can be freed with
 101 * os_map_destroy.
 102 */
 103 OS_OVERLOADABLE OS_ALWAYS_INLINE
 104 static inline void
 105 os_map_init(os_map_64_t *m, os_map_config_t * _Nullable config);
 106
 107 /*!
 108 * @function os_map_destroy
 109 * Destroy a map.
 110 *
 111 * @param t
 112 * The table to destroy.
 113 *
 114 * @discussion
 115 * This will free all memory used by the map, but will not take any action
 116 * on the keys/values that were in the map at the time.
 117 */
 118 OS_OVERLOADABLE OS_ALWAYS_INLINE
 119 static inline void
 120 os_map_destroy(os_map_64_t *m);
 121
 122 /*!
 123 * @function os_map_insert
 124 * Insert an element into a map.
 125 *
 126 * @param t
 127 * The table to initialize
 128 *
 129 * @param key
 130 * The key to insert the value at
 131 *
 132 * @param val
 133 * The value to insert; cannot be NULL (use os_map_delete to remove entries)
 134 *
 135 * @discussion
 136 * This will insert an element into the map, growing the map if needed. Does not
 137 * support replacing an existing key, so inserting twice without a remove will
 138 * cause undefined behavior.
 139 */
 140 OS_OVERLOADABLE OS_ALWAYS_INLINE
 141 static inline void
 142 os_map_insert(os_map_64_t *m, uint64_t key, void *val);
 143
 144 /*!
 145 * @function os_map_find
 146 * Find an element in a map.
 147 *
 148 * @param t
 149 * The map to search
 150 *
 151 * @param key
 152 * The key to search for
 153 *
 154 * @result
 155 * The value stored at key, or NULL if no value is present.
 156 *
 157 */
 158 OS_OVERLOADABLE OS_ALWAYS_INLINE
 159 static inline void * _Nullable
 160 os_map_find(os_map_64_t *m, uint64_t key);
 161
 162 /*!
 163 * @function os_map_delete
 164 * Remove an element from a map.
 165 *
 166 * @param t
 167 * The map to remove the element from
 168 *
 169 * @param key
 170 * The key of the element to be removed
 171 *
 172 * @result
 173 * The value stored at key, or NULL if no value is present.
 174 *
 175 * @discussion
 176 * Has no effect if the key is not present
 177 */
 178 OS_OVERLOADABLE OS_ALWAYS_INLINE
 179 static inline void * _Nullable
 180 os_map_delete(os_map_64_t *m, uint64_t key);
 181
 182 typedef bool (^os_map_64_payload_handler_t) (uint64_t, void *);
 183
 184 /*!
 185 * @function os_map_clear
 186 * Removes all elements from a map.
 187 *
 188 * @param t
 189 * The map to remove the elements from
 190 *
 191 * @param handler
 192 * A handler that will be called for all elements in the table. Handler may be
 193 * NULL.
 194 *
 195 * @discussion
 196 * Has no effect if the key is not present
 197 */
 198 OS_OVERLOADABLE OS_ALWAYS_INLINE
 199 static inline void
 200 os_map_clear(os_map_64_t *m,
 201                   OS_NOESCAPE os_map_64_payload_handler_t _Nullable handler);
 202
 203 /*!
 204 * @function os_map_count
 205 * Gets the number of items present in a map
 206 *
 207 * @param t
 208 * The map to get the count of
 209 *
 210 * @result
 211 * Returns the number of items present in the map
 212 */
 213 OS_OVERLOADABLE OS_ALWAYS_INLINE
 214 static inline size_t
 215 os_map_count(os_map_64_t *m);
 216
 217 /*!
 218 * @function os_map_foreach
 219 *Iterate over the key/value pairs in a map.
 220 *
 221 * @param t
 222 * The map to iterate over
 223 *
 224 * @param handler
 225 * The handler to call for each entry in the map.
 226 *
 227 * @discussion
 228 * Will invoke handler for each key/value pair in the map. Modifying the map
 229 * during this iteration is not permitted. The handler may be called on the
 230 * entries in any order.
 231 */
 232 OS_OVERLOADABLE OS_ALWAYS_INLINE
 233 static inline void
 234 os_map_foreach(os_map_64_t *m,
 235                  OS_NOESCAPE os_map_64_payload_handler_t handler);
 236
 237 /*!
 238 * @function os_map_entry
 239 * Gets the exact entry, if present, for a given key and NULL otherwise.
 240 *
 241 * @param t
 242 * The map to search
 243 *
 244 * @param key
 245 * The key to search for
 246 *
 247 * @discussion
 248 * Only available for os_map_str_t.
 249 * Gets the exact entry, if present, for a given key and NULL otherwise. So, for
 250 * two equal strings a, b where a != b. We guarentee that
 251 * os_map_entry(t, a) == os_map_entry(t, b)
 252 */
 253 OS_OVERLOADABLE OS_ALWAYS_INLINE
 254 static inline const char *
 255 os_map_entry(os_map_str_t *m, const char *key);
 256
 257 OS_ASSUME_NONNULL_END
 258
 259 #include <os/_collections_map.h>
 260
 261 #endif /* _OS_COLLECTIONS_MAP_H */