PipeWire  0.3.61
map.h
Go to the documentation of this file.
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 
76 union pw_map_item {
77  uintptr_t next; /* next free index */
78  void *data; /* data of this item, must be an even address */
79 };
80 
82 struct pw_map {
83  struct pw_array items; /* an array with the map items */
84  uint32_t free_list; /* first free index */
85 };
86 
88 #define PW_MAP_INIT(extend) ((struct pw_map) { PW_ARRAY_INIT(extend), SPA_ID_INVALID })
89 
96 #define pw_map_get_size(m) pw_array_get_len(&(m)->items, union pw_map_item)
97 #define pw_map_get_item(m,id) pw_array_get_unchecked(&(m)->items,id,union pw_map_item)
98 #define pw_map_item_is_free(item) ((item)->next & 0x1)
99 #define pw_map_id_is_free(m,id) (pw_map_item_is_free(pw_map_get_item(m,id)))
101 #define pw_map_check_id(m,id) ((id) < pw_map_get_size(m))
103 #define pw_map_has_item(m,id) (pw_map_check_id(m,id) && !pw_map_id_is_free(m, id))
104 #define pw_map_lookup_unchecked(m,id) pw_map_get_item(m,id)->data
105 
107 #define PW_MAP_ID_TO_PTR(id) (SPA_UINT32_TO_PTR((id)<<1))
109 #define PW_MAP_PTR_TO_ID(p) (SPA_PTR_TO_UINT32(p)>>1)
110 
116 static inline void pw_map_init(struct pw_map *map, size_t size, size_t extend)
117 {
118  pw_array_init(&map->items, extend * sizeof(union pw_map_item));
119  pw_array_ensure_size(&map->items, size * sizeof(union pw_map_item));
120  map->free_list = SPA_ID_INVALID;
121 }
122 
126 static inline void pw_map_clear(struct pw_map *map)
127 {
128  pw_array_clear(&map->items);
129 }
130 
134 static inline void pw_map_reset(struct pw_map *map)
135 {
136  pw_array_reset(&map->items);
137  map->free_list = SPA_ID_INVALID;
138 }
139 
146 static inline uint32_t pw_map_insert_new(struct pw_map *map, void *data)
147 {
148  union pw_map_item *start, *item;
149  uint32_t id;
150 
151  if (map->free_list != SPA_ID_INVALID) {
152  start = (union pw_map_item *) map->items.data;
153  item = &start[map->free_list >> 1]; /* lsb always 1, see pw_map_remove */
154  map->free_list = item->next;
155  } else {
156  item = (union pw_map_item *) pw_array_add(&map->items, sizeof(union pw_map_item));
157  if (item == NULL)
158  return SPA_ID_INVALID;
159  start = (union pw_map_item *) map->items.data;
160  }
161  item->data = data;
162  id = (item - start);
163  return id;
164 }
165 
173 static inline int pw_map_insert_at(struct pw_map *map, uint32_t id, void *data)
174 {
175  size_t size = pw_map_get_size(map);
176  union pw_map_item *item;
177 
178  if (id > size)
179  return -ENOSPC;
180  else if (id == size) {
181  item = (union pw_map_item *) pw_array_add(&map->items, sizeof(union pw_map_item));
182  if (item == NULL)
183  return -errno;
184  } else {
185  item = pw_map_get_item(map, id);
186  if (pw_map_item_is_free(item))
187  return -EINVAL;
188  }
189  item->data = data;
190  return 0;
191 }
192 
198 static inline void pw_map_remove(struct pw_map *map, uint32_t id)
199 {
200  if (pw_map_id_is_free(map, id))
201  return;
202 
203  pw_map_get_item(map, id)->next = map->free_list;
204  map->free_list = (id << 1) | 1;
205 }
206 
212 static inline void *pw_map_lookup(struct pw_map *map, uint32_t id)
213 {
214  if (SPA_LIKELY(pw_map_check_id(map, id))) {
215  union pw_map_item *item = pw_map_get_item(map, id);
216  if (!pw_map_item_is_free(item))
217  return item->data;
218  }
219  return NULL;
220 }
221 
230 static inline int pw_map_for_each(struct pw_map *map,
231  int (*func) (void *item_data, void *data), void *data)
232 {
233  union pw_map_item *item;
234  int res = 0;
235 
236  pw_array_for_each(item, &map->items) {
238  if ((res = func(item->data, data)) != 0)
239  break;
240  }
241  return res;
242 }
243 
248 #ifdef __cplusplus
249 } /* extern "C" */
250 #endif
251 
252 #endif /* PIPEWIRE_MAP_H */
pipewire/array.h
spa/utils/defs.h
static int pw_array_ensure_size(struct pw_array *arr, size_t size)
Make sure size bytes can be added to the array.
Definition: array.h:116
static void pw_array_init(struct pw_array *arr, size_t extend)
Initialize the array with given extend.
Definition: array.h:95
static void * pw_array_add(struct pw_array *arr, size_t size)
Add ref size bytes to arr.
Definition: array.h:139
static void pw_array_clear(struct pw_array *arr)
Clear the array.
Definition: array.h:103
#define pw_array_for_each(pos, array)
Definition: array.h:77
static void pw_array_reset(struct pw_array *arr)
Reset the array.
Definition: array.h:110
static void pw_map_remove(struct pw_map *map, uint32_t id)
Remove an item at index.
Definition: map.h:205
#define pw_map_check_id(m, id)
Definition: map.h:106
static void * pw_map_lookup(struct pw_map *map, uint32_t id)
Find an item in the map.
Definition: map.h:219
static int pw_map_insert_at(struct pw_map *map, uint32_t id, void *data)
Replace the data in the map at an index.
Definition: map.h:180
#define pw_map_get_size(m)
Get the number of currently allocated elements in the map.
Definition: map.h:101
static uint32_t pw_map_insert_new(struct pw_map *map, void *data)
Insert data in the map.
Definition: map.h:153
static void pw_map_reset(struct pw_map *map)
Reset a map but keep previously allocated storage.
Definition: map.h:141
static void pw_map_clear(struct pw_map *map)
Clear a map and free the data storage.
Definition: map.h:133
#define pw_map_item_is_free(item)
Definition: map.h:103
#define pw_map_id_is_free(m, id)
Definition: map.h:104
static void pw_map_init(struct pw_map *map, size_t size, size_t extend)
Initialize a map.
Definition: map.h:123
static int pw_map_for_each(struct pw_map *map, int(*func)(void *item_data, void *data), void *data)
Iterate all map items.
Definition: map.h:237
#define pw_map_get_item(m, id)
Definition: map.h:102
#define SPA_ID_INVALID
Definition: defs.h:244
#define SPA_LIKELY(x)
Definition: defs.h:353
spa/utils/string.h
Definition: array.h:52
size_t size
length of array in bytes
Definition: array.h:54
size_t extend
number of bytes to extend with
Definition: array.h:56
void * data
pointer to array data
Definition: array.h:53
A map.
Definition: map.h:86
struct pw_array items
Definition: map.h:87
uint32_t free_list
Definition: map.h:88