libwebsockets
Lightweight C library for HTML5 websockets
lws-map.h
Go to the documentation of this file.
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 
45 typedef struct lws_map lws_map_t;
46 struct lws_map_item;
47 
48 typedef void * lws_map_key_t;
49 typedef void * lws_map_value_t;
51 
52 typedef lws_map_hash_t (*lws_map_hash_from_key_t)(const lws_map_key_t key,
53  size_t kl);
54 typedef 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);
56 typedef void * (*lws_map_alloc_t)(struct lws_map *mo, size_t x);
57 typedef void (*lws_map_free_t)(void *);
58 
59 /*
60  * Creation parameters for the map, copied into the map owner
61  */
62 
63 typedef struct lws_map_info {
64  lws_map_hash_from_key_t _hash;
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 */
75  /**< number of hashed owner lists to create */
76 } lws_map_info_t;
77 
78 LWS_VISIBLE LWS_EXTERN const void *
79 lws_map_item_key(struct lws_map_item *_item);
80 LWS_VISIBLE LWS_EXTERN const void *
81 lws_map_item_value(struct lws_map_item *_item);
82 LWS_VISIBLE LWS_EXTERN size_t
83 lws_map_item_key_len(struct lws_map_item *_item);
84 LWS_VISIBLE LWS_EXTERN size_t
85 lws_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  */
119 LWS_VISIBLE LWS_EXTERN lws_map_t *
120 lws_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 
128 LWS_VISIBLE LWS_EXTERN void *
129 lws_map_alloc_lwsac(struct lws_map *map, size_t x);
130 
131 LWS_VISIBLE LWS_EXTERN void
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  */
142 LWS_VISIBLE LWS_EXTERN void
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 
161 LWS_VISIBLE LWS_EXTERN struct lws_map_item *
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  */
171 LWS_VISIBLE LWS_EXTERN void
172 lws_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 
185 LWS_VISIBLE LWS_EXTERN struct lws_map_item *
186 lws_map_item_lookup(lws_map_t *map, const lws_map_key_t key, size_t keylen);
187 
188 //@}