PipeWire  1.4.6
map.h
Go to the documentation of this file.
1 /* PipeWire */
2 /* SPDX-FileCopyrightText: Copyright © 2018 Wim Taymans */
3 /* SPDX-License-Identifier: MIT */
4 
5 #ifndef PIPEWIRE_MAP_H
6 #define PIPEWIRE_MAP_H
7 
8 #ifdef __cplusplus
9 extern "C" {
10 #endif
11 
12 #include <string.h>
13 #include <errno.h>
14 
15 #include <spa/utils/defs.h>
16 #include <pipewire/array.h>
17 
18 #ifndef PW_API_MAP
19 #define PW_API_MAP static inline
20 #endif
21 
60 union pw_map_item {
61  uintptr_t next; /* next free index */
62  void *data; /* data of this item, must be an even address */
63 };
64 
66 struct pw_map {
67  struct pw_array items; /* an array with the map items */
68  uint32_t free_list; /* first free index */
69 };
70 
72 #define PW_MAP_INIT(extend) ((struct pw_map) { PW_ARRAY_INIT(extend), SPA_ID_INVALID })
73 
80 #define pw_map_get_size(m) pw_array_get_len(&(m)->items, union pw_map_item)
81 #define pw_map_get_item(m,id) pw_array_get_unchecked(&(m)->items,id,union pw_map_item)
82 #define pw_map_item_is_free(item) ((item)->next & 0x1)
83 #define pw_map_id_is_free(m,id) (pw_map_item_is_free(pw_map_get_item(m,id)))
85 #define pw_map_check_id(m,id) ((id) < pw_map_get_size(m))
87 #define pw_map_has_item(m,id) (pw_map_check_id(m,id) && !pw_map_id_is_free(m, id))
88 #define pw_map_lookup_unchecked(m,id) pw_map_get_item(m,id)->data
89 
91 #define PW_MAP_ID_TO_PTR(id) (SPA_UINT32_TO_PTR((id)<<1))
93 #define PW_MAP_PTR_TO_ID(p) (SPA_PTR_TO_UINT32(p)>>1)
94 
100 PW_API_MAP void pw_map_init(struct pw_map *map, size_t size, size_t extend)
101 {
102  pw_array_init(&map->items, extend * sizeof(union pw_map_item));
103  pw_array_ensure_size(&map->items, size * sizeof(union pw_map_item));
104  map->free_list = SPA_ID_INVALID;
105 }
106 
110 PW_API_MAP void pw_map_clear(struct pw_map *map)
111 {
112  pw_array_clear(&map->items);
113 }
114 
118 PW_API_MAP void pw_map_reset(struct pw_map *map)
119 {
120  pw_array_reset(&map->items);
121  map->free_list = SPA_ID_INVALID;
122 }
123 
130 PW_API_MAP uint32_t pw_map_insert_new(struct pw_map *map, void *data)
131 {
132  union pw_map_item *start, *item;
133  uint32_t id;
134 
135  if (map->free_list != SPA_ID_INVALID) {
136  start = (union pw_map_item *) map->items.data;
137  item = &start[map->free_list >> 1]; /* lsb always 1, see pw_map_remove */
138  map->free_list = item->next;
139  } else {
140  item = (union pw_map_item *) pw_array_add(&map->items, sizeof(union pw_map_item));
141  if (item == NULL)
142  return SPA_ID_INVALID;
143  start = (union pw_map_item *) map->items.data;
144  }
145  item->data = data;
146  id = (item - start);
147  return id;
148 }
149 
157 PW_API_MAP int pw_map_insert_at(struct pw_map *map, uint32_t id, void *data)
158 {
159  size_t size = pw_map_get_size(map);
160  union pw_map_item *item;
161 
162  if (id > size)
163  return -ENOSPC;
164  else if (id == size) {
165  item = (union pw_map_item *) pw_array_add(&map->items, sizeof(union pw_map_item));
166  if (item == NULL)
167  return -errno;
168  } else {
169  item = pw_map_get_item(map, id);
170  if (pw_map_item_is_free(item))
171  return -EINVAL;
172  }
173  item->data = data;
174  return 0;
175 }
176 
182 PW_API_MAP void pw_map_remove(struct pw_map *map, uint32_t id)
183 {
184  if (pw_map_id_is_free(map, id))
185  return;
186 
187  pw_map_get_item(map, id)->next = map->free_list;
188  map->free_list = (id << 1) | 1;
189 }
190 
196 PW_API_MAP void *pw_map_lookup(const struct pw_map *map, uint32_t id)
197 {
198  if (SPA_LIKELY(pw_map_check_id(map, id))) {
199  union pw_map_item *item = pw_map_get_item(map, id);
200  if (!pw_map_item_is_free(item))
201  return item->data;
202  }
203  return NULL;
204 }
205 
214 PW_API_MAP int pw_map_for_each(const struct pw_map *map,
215  int (*func) (void *item_data, void *data), void *data)
216 {
217  union pw_map_item *item;
218  int res = 0;
219 
220  pw_array_for_each(item, &map->items) {
221  if (!pw_map_item_is_free(item))
222  if ((res = func(item->data, data)) != 0)
223  break;
224  }
225  return res;
226 }
227 
232 #ifdef __cplusplus
233 } /* extern "C" */
234 #endif
235 
236 #endif /* PIPEWIRE_MAP_H */
pipewire/array.h
spa/utils/defs.h
PW_API_ARRAY 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:115
PW_API_ARRAY void pw_array_reset(struct pw_array *arr)
Reset the array.
Definition: array.h:109
#define pw_array_for_each(pos, array)
Definition: array.h:66
PW_API_ARRAY void * pw_array_add(struct pw_array *arr, size_t size)
Add ref size bytes to arr.
Definition: array.h:138
PW_API_ARRAY void pw_array_clear(struct pw_array *arr)
Clear the array.
Definition: array.h:93
PW_API_ARRAY void pw_array_init(struct pw_array *arr, size_t extend)
Initialize the array with given extend.
Definition: array.h:85
uint32_t id
Definition: core.h:432
uint32_t int int res
Definition: core.h:433
#define pw_map_check_id(m, id)
Definition: map.h:91
PW_API_MAP void pw_map_clear(struct pw_map *map)
Clear a map and free the data storage.
Definition: map.h:118
PW_API_MAP void pw_map_reset(struct pw_map *map)
Reset a map but keep previously allocated storage.
Definition: map.h:126
PW_API_MAP void pw_map_remove(struct pw_map *map, uint32_t id)
Remove an item at index.
Definition: map.h:190
#define pw_map_get_size(m)
Get the number of currently allocated elements in the map.
Definition: map.h:86
PW_API_MAP uint32_t pw_map_insert_new(struct pw_map *map, void *data)
Insert data in the map.
Definition: map.h:138
PW_API_MAP void pw_map_init(struct pw_map *map, size_t size, size_t extend)
Initialize a map.
Definition: map.h:108
PW_API_MAP 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:165
PW_API_MAP int pw_map_for_each(const struct pw_map *map, int(*func)(void *item_data, void *data), void *data)
Iterate all map items.
Definition: map.h:222
PW_API_MAP void * pw_map_lookup(const struct pw_map *map, uint32_t id)
Find an item in the map.
Definition: map.h:204
#define pw_map_item_is_free(item)
Definition: map.h:88
#define pw_map_id_is_free(m, id)
Definition: map.h:89
#define pw_map_get_item(m, id)
Definition: map.h:87
#define SPA_ID_INVALID
Definition: defs.h:250
#define SPA_LIKELY(x)
Definition: defs.h:392
#define PW_API_MAP
Definition: map.h:24
spa/utils/string.h
Definition: array.h:38
size_t size
length of array in bytes
Definition: array.h:40
size_t extend
number of bytes to extend with, 0 when the data should not expand
Definition: array.h:42
void * data
pointer to array data
Definition: array.h:39
A map.
Definition: map.h:71
struct pw_array items
Definition: map.h:72
uint32_t free_list
Definition: map.h:73