1 /* PipeWire
2 *
3 * Copyright © 2018 Wim Taymans
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * 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
19 * THE 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
22 * DEALINGS IN THE SOFTWARE.
23 */
24
25 #ifndef PIPEWIRE_MAP_H
26 #define PIPEWIRE_MAP_H
27
28 #ifdef __cplusplus
29 extern "C" {
30 #endif
31
32 #include <string.h>
33 #include <errno.h>
34
35 #include <spa/utils/defs.h>
36 #include <pipewire/array.h>
37
38 /** \class pw_map
39 *
40 * A map that holds objects indexed by id
41 */
42
43 /** An entry in the map \memberof pw_map */
44 union pw_map_item {
45 uint32_t next; /**< next free index */
46 void *data; /**< data of this item, must be an even address */
47 };
48
49 /** A map \memberof pw_map */
50 struct pw_map {
51 struct pw_array items; /**< an array with the map items */
52 uint32_t free_list; /**< the free items */
53 };
54
55 #define PW_MAP_INIT(extend) (struct pw_map) { PW_ARRAY_INIT(extend), 0 }
56
57 #define pw_map_get_size(m) pw_array_get_len(&(m)->items, union pw_map_item)
58 #define pw_map_get_item(m,id) pw_array_get_unchecked(&(m)->items,id,union pw_map_item)
59 #define pw_map_item_is_free(item) ((item)->next & 0x1)
60 #define pw_map_id_is_free(m,id) (pw_map_item_is_free(pw_map_get_item(m,id)))
61 #define pw_map_check_id(m,id) ((id) < pw_map_get_size(m))
62 #define pw_map_has_item(m,id) (pw_map_check_id(m,id) && !pw_map_id_is_free(m, id))
63 #define pw_map_lookup_unchecked(m,id) pw_map_get_item(m,id)->data
64
65 /** Convert an id to a pointer that can be inserted into the map \memberof pw_map */
66 #define PW_MAP_ID_TO_PTR(id) (SPA_UINT32_TO_PTR((id)<<1))
67 /** Convert a pointer to an id that can be retrieved from the map \memberof pw_map */
68 #define PW_MAP_PTR_TO_ID(p) (SPA_PTR_TO_UINT32(p)>>1)
69
70 /** Initialize a map
71 * \param map the map to initialize
72 * \param size the initial size of the map
73 * \param extend the amount to bytes to grow the map with when needed
74 * \memberof pw_map
75 */
pw_map_init(struct pw_map * map,size_t size,size_t extend)76 static inline void pw_map_init(struct pw_map *map, size_t size, size_t extend)
77 {
78 pw_array_init(&map->items, extend);
79 pw_array_ensure_size(&map->items, size * sizeof(union pw_map_item));
80 map->free_list = SPA_ID_INVALID;
81 }
82
83 /** Clear a map
84 * \param map the map to clear
85 * \memberof pw_map
86 */
pw_map_clear(struct pw_map * map)87 static inline void pw_map_clear(struct pw_map *map)
88 {
89 pw_array_clear(&map->items);
90 }
91
pw_map_reset(struct pw_map * map)92 static inline void pw_map_reset(struct pw_map *map)
93 {
94 pw_array_reset(&map->items);
95 map->free_list = SPA_ID_INVALID;
96 }
97
98 /** Insert data in the map
99 * \param map the map to insert into
100 * \param data the item to add
101 * \return the id where the item was inserted or SPA_ID_INVALID when the
102 * item can not be inserted.
103 * \memberof pw_map
104 */
pw_map_insert_new(struct pw_map * map,void * data)105 static inline uint32_t pw_map_insert_new(struct pw_map *map, void *data)
106 {
107 union pw_map_item *start, *item;
108 uint32_t id;
109
110 if (map->free_list != SPA_ID_INVALID) {
111 start = (union pw_map_item *) map->items.data;
112 item = &start[map->free_list >> 1];
113 map->free_list = item->next;
114 } else {
115 item = (union pw_map_item *) pw_array_add(&map->items, sizeof(union pw_map_item));
116 if (item == NULL)
117 return SPA_ID_INVALID;
118 start = (union pw_map_item *) map->items.data;
119 }
120 item->data = data;
121 id = (item - start);
122 return id;
123 }
124
125 /** Insert data in the map at an index
126 * \param map the map to inser into
127 * \param id the index to insert at
128 * \param data the data to insert
129 * \return 0 on success, -ENOSPC value when the index is invalid or a < 0
130 * errno value.
131 * \memberof pw_map
132 */
pw_map_insert_at(struct pw_map * map,uint32_t id,void * data)133 static inline int pw_map_insert_at(struct pw_map *map, uint32_t id, void *data)
134 {
135 size_t size = pw_map_get_size(map);
136 union pw_map_item *item;
137
138 if (id > size)
139 return -ENOSPC;
140 else if (id == size) {
141 item = (union pw_map_item *) pw_array_add(&map->items, sizeof(union pw_map_item));
142 if (item == NULL)
143 return -errno;
144 }
145 else {
146 item = pw_map_get_item(map, id);
147 }
148 item->data = data;
149 return 0;
150 }
151
152 /** Remove an item at index
153 * \param map the map to remove from
154 * \param id the index to remove
155 * \memberof pw_map
156 */
pw_map_remove(struct pw_map * map,uint32_t id)157 static inline void pw_map_remove(struct pw_map *map, uint32_t id)
158 {
159 pw_map_get_item(map, id)->next = map->free_list;
160 map->free_list = (id << 1) | 1;
161 }
162
163 /** Find an item in the map
164 * \param map the map to use
165 * \param id the index to look at
166 * \return the item at \a id or NULL when no such item exists
167 * \memberof pw_map
168 */
pw_map_lookup(struct pw_map * map,uint32_t id)169 static inline void *pw_map_lookup(struct pw_map *map, uint32_t id)
170 {
171 if (SPA_LIKELY(pw_map_check_id(map, id))) {
172 union pw_map_item *item = pw_map_get_item(map, id);
173 if (!pw_map_item_is_free(item))
174 return item->data;
175 }
176 return NULL;
177 }
178
179 /** Iterate all map items
180 * \param map the map to iterate
181 * \param func the function to call for each item, the item data and \a data is
182 * passed to the function. When \a func returns a non-zero result,
183 * iteration ends and the result is returned.
184 * \param data data to pass to \a func
185 * \return the result of the last call to \a func or 0 when all callbacks returned 0.
186 * \memberof pw_map
187 */
pw_map_for_each(struct pw_map * map,int (* func)(void * item_data,void * data),void * data)188 static inline int pw_map_for_each(struct pw_map *map,
189 int (*func) (void *item_data, void *data), void *data)
190 {
191 union pw_map_item *item;
192 int res = 0;
193
194 pw_array_for_each(item, &map->items) {
195 if (!pw_map_item_is_free(item))
196 if ((res = func(item->data, data)) != 0)
197 break;
198 }
199 return res;
200 }
201
202 #ifdef __cplusplus
203 } /* extern "C" */
204 #endif
205
206 #endif /* PIPEWIRE_MAP_H */
207