lws-map.h (6664B)
1/* 2 * libwebsockets - small server side websockets and web server implementation 3 * 4 * Copyright (C) 2010 - 2021 Andy Green <andy@warmcat.com> 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a copy 7 * of this software and associated documentation files (the "Software"), to 8 * deal in the Software without restriction, including without limitation the 9 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 10 * sell copies of the Software, and to permit persons to whom the Software is 11 * furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice shall be included in 14 * all copies or substantial portions of the Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 22 * IN THE SOFTWARE. 23 */ 24 25/** \defgroup lws_map generic map apis 26 * ##Generic map structures and apis 27 * \ingroup lwsapi 28 * 29 * lws_map 30 * 31 * Discrete owner object represents the whole map, created with key-specific 32 * ops for hashing the key to a uint32_t and comparing two keys. Owns a list 33 * of hash tables whose size / modulo it set at creation time. 34 * 35 * Items in the map are contained in a lws_map_item_t that is indexed in a 36 * hash table. 37 * 38 * It's difficult to make a single compact map abstraction that fits all cases, 39 * this is useful to the extent you have the memory to trade off the number of 40 * hashtables needed for the amount of items and the lookup latency limit for 41 * your application, typically for hundreds or low thousands of items. 42 */ 43//@{ 44 45typedef struct lws_map lws_map_t; 46struct lws_map_item; 47 48typedef void * lws_map_key_t; 49typedef void * lws_map_value_t; 50typedef uint32_t lws_map_hash_t; 51 52typedef lws_map_hash_t (*lws_map_hash_from_key_t)(const lws_map_key_t key, 53 size_t kl); 54typedef int (*lws_map_compare_key_t)(const lws_map_key_t key1, size_t kl1, 55 const lws_map_value_t key2, size_t kl2); 56typedef void * (*lws_map_alloc_t)(struct lws_map *mo, size_t x); 57typedef void (*lws_map_free_t)(void *); 58 59/* 60 * Creation parameters for the map, copied into the map owner 61 */ 62 63typedef struct lws_map_info { 64 lws_map_hash_from_key_t _hash; 65 lws_map_compare_key_t _compare; 66 lws_map_alloc_t _alloc; /* NULL = lws_malloc */ 67 lws_map_free_t _free; /* NULL = lws_free */ 68 69 void *opaque; 70 /**< &lwsac if using lwsac allocator */ 71 void *aux; 72 /**< chunk size if using lwsac allocator */ 73 /**< this can be used by the alloc handler, eg for lws_ac */ 74 size_t modulo; 75 /**< number of hashed owner lists to create */ 76} lws_map_info_t; 77 78LWS_VISIBLE LWS_EXTERN const void * 79lws_map_item_key(struct lws_map_item *_item); 80LWS_VISIBLE LWS_EXTERN const void * 81lws_map_item_value(struct lws_map_item *_item); 82LWS_VISIBLE LWS_EXTERN size_t 83lws_map_item_key_len(struct lws_map_item *_item); 84LWS_VISIBLE LWS_EXTERN size_t 85lws_map_item_value_len(struct lws_map_item *_item); 86 87/* 88 * Helpers for C string keys case 89 */ 90 91#define lws_map_item_create_ks(_map, _str, _v, _vl) \ 92 lws_map_item_create(_map, (const lws_map_key_t)_str, \ 93 strlen(_str), (const lws_map_value_t)_v, \ 94 _vl) 95#define lws_map_item_lookup_ks(_map, _str) \ 96 lws_map_item_lookup(_map, (const lws_map_key_t)_str, strlen(_str)) 97 98/** 99 * lws_map_create() - create a map object and hashtables on heap 100 * 101 * \param info: description of map to create 102 * 103 * Creates a map object on heap, using lws_malloc(). 104 * 105 * \p info may be all zeros inside, if so, modulo defaults to 8, and the 106 * operation callbacks default to using lws_malloc() / _free() for item alloc, 107 * a default xor / shift based hash and simple linear memory key compare. 108 * 109 * For less typical use-cases, the provided \p info members can be tuned to 110 * control how the allocation of mapped items is done, lws provides two exports 111 * lws_map_alloc_lwsac() and lws_map_free_lwsac() that can be used for _alloc 112 * and _free to have items allocated inside an lwsac. 113 * 114 * The map itself is created on the heap directly, the info._alloc() op is only 115 * used when creating items. 116 * 117 * keys have individual memory sizes and do not need to all be the same length. 118 */ 119LWS_VISIBLE LWS_EXTERN lws_map_t * 120lws_map_create(const lws_map_info_t *info); 121 122/* 123 * helpers that can be used for info._alloc and info._free if using lwsac 124 * allocation for items, set info.opaque to point to the lwsac pointer, and 125 * aux to (void *)chunksize, or leave zero / NULL for the default 126 */ 127 128LWS_VISIBLE LWS_EXTERN void * 129lws_map_alloc_lwsac(struct lws_map *map, size_t x); 130 131LWS_VISIBLE LWS_EXTERN void 132lws_map_free_lwsac(void *v); 133 134/** 135 * lws_map_destroy() - deallocate all items and free map 136 * 137 * \param pmap: pointer to pointer map object to deallocate 138 * 139 * Frees all items in the map, using info._free(), and then frees the map 140 * from heap directly. \p *pmap is set to NULL. 141 */ 142LWS_VISIBLE LWS_EXTERN void 143lws_map_destroy(lws_map_t **pmap); 144 145/** 146 * lws_map_item_create() - allocate and map an item into an existing map 147 * 148 * \param map: the map to add items into 149 * \param key: the key, may be any kind of object 150 * \param keylen: the length of the key in bytes 151 * \param value: the value, may be any kind of object 152 * \param valuelen: the length of value 153 * 154 * Allocates space for the item, key and value using the map allocator, and 155 * if non-NULL, copies the key and value into the item. 156 * 157 * If an item with the same key exists, it is removed and destroyed before 158 * creating and adding the new one. 159 */ 160 161LWS_VISIBLE LWS_EXTERN struct lws_map_item * 162lws_map_item_create(lws_map_t *map, 163 const lws_map_key_t key, size_t keylen, 164 const lws_map_value_t value, size_t valuelen); 165 166/** 167 * lws_map_item_destroy() - remove item from map and free 168 * 169 * \param item: the item in the map to remove and free 170 */ 171LWS_VISIBLE LWS_EXTERN void 172lws_map_item_destroy(struct lws_map_item *item); 173 174/** 175 * lws_map_item_lookup() - look for a item with the given key in the map 176 * 177 * \param map: the map 178 * \param key: the key to look for 179 * \param keylen: the length of the key to look for 180 * 181 * Searches for the key in the map, using the map's key hash and key compare 182 * functions. 183 */ 184 185LWS_VISIBLE LWS_EXTERN struct lws_map_item * 186lws_map_item_lookup(lws_map_t *map, const lws_map_key_t key, size_t keylen); 187 188//@}