map.h

Go to the documentation of this file.

/* PipeWire
 *
 * Copyright © 2018 Wim Taymans
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 */
 
#ifndef PIPEWIRE_MAP_H
#define PIPEWIRE_MAP_H
 
#ifdef __cplusplus
extern "C" {
#endif
 
#include <string.h>
#include <errno.h>
 
#include <spa/utils/defs.h>
#include <pipewire/array.h>
 
union pw_map_item {
        uintptr_t next; /* next free index */
        void *data;     /* data of this item, must be an even address */
};
 
struct pw_map {
        struct pw_array items;  /* an array with the map items */
        uint32_t free_list;     /* first free index */
};
 
#define PW_MAP_INIT(extend) (struct pw_map) { PW_ARRAY_INIT(extend), SPA_ID_INVALID }
 
#define pw_map_get_size(m)            pw_array_get_len(&(m)->items, union pw_map_item)
#define pw_map_get_item(m,id)         pw_array_get_unchecked(&(m)->items,id,union pw_map_item)
#define pw_map_item_is_free(item)     ((item)->next & 0x1)
#define pw_map_id_is_free(m,id)       (pw_map_item_is_free(pw_map_get_item(m,id)))
#define pw_map_check_id(m,id)         ((id) < pw_map_get_size(m))
#define pw_map_has_item(m,id)         (pw_map_check_id(m,id) && !pw_map_id_is_free(m, id))
#define pw_map_lookup_unchecked(m,id) pw_map_get_item(m,id)->data
 
#define PW_MAP_ID_TO_PTR(id)          (SPA_UINT32_TO_PTR((id)<<1))
#define PW_MAP_PTR_TO_ID(p)           (SPA_PTR_TO_UINT32(p)>>1)
 
static inline void pw_map_init(struct pw_map *map, size_t size, size_t extend)
{
        pw_array_init(&map->items, extend * sizeof(union pw_map_item));
        pw_array_ensure_size(&map->items, size * sizeof(union pw_map_item));
        map->free_list = SPA_ID_INVALID;
}
 
static inline void pw_map_clear(struct pw_map *map)
{
        pw_array_clear(&map->items);
}
 
static inline void pw_map_reset(struct pw_map *map)
{
        pw_array_reset(&map->items);
        map->free_list = SPA_ID_INVALID;
}
 
static inline uint32_t pw_map_insert_new(struct pw_map *map, void *data)
{
        union pw_map_item *start, *item;
        uint32_t id;
 
        if (map->free_list != SPA_ID_INVALID) {
                start = (union pw_map_item *) map->items.data;
                item = &start[map->free_list >> 1]; /* lsb always 1, see pw_map_remove */
                map->free_list = item->next;
        } else {
                item = (union pw_map_item *) pw_array_add(&map->items, sizeof(union pw_map_item));
                if (item == NULL)
                        return SPA_ID_INVALID;
                start = (union pw_map_item *) map->items.data;
        }
        item->data = data;
        id = (item - start);
        return id;
}
 
static inline int pw_map_insert_at(struct pw_map *map, uint32_t id, void *data)
{
        size_t size = pw_map_get_size(map);
        union pw_map_item *item;
 
        if (id > size)
                return -ENOSPC;
        else if (id == size) {
                item = (union pw_map_item *) pw_array_add(&map->items, sizeof(union pw_map_item));
                if (item == NULL)
                        return -errno;
        } else {
                item = pw_map_get_item(map, id);
                if (pw_map_item_is_free(item))
                        return -EINVAL;
        }
        item->data = data;
        return 0;
}
 
static inline void pw_map_remove(struct pw_map *map, uint32_t id)
{
        if (pw_map_id_is_free(map, id))
                return;
 
        pw_map_get_item(map, id)->next = map->free_list;
        map->free_list = (id << 1) | 1;
}
 
static inline void *pw_map_lookup(struct pw_map *map, uint32_t id)
{
        if (SPA_LIKELY(pw_map_check_id(map, id))) {
                union pw_map_item *item = pw_map_get_item(map, id);
                if (!pw_map_item_is_free(item))
                        return item->data;
        }
        return NULL;
}
 
static inline int pw_map_for_each(struct pw_map *map,
                                   int (*func) (void *item_data, void *data), void *data)
{
        union pw_map_item *item;
        int res = 0;
 
        pw_array_for_each(item, &map->items) {
                if (!pw_map_item_is_free(item))
                        if ((res = func(item->data, data)) != 0)
                                break;
        }
        return res;
}
 
#ifdef __cplusplus
}  /* extern "C" */
#endif
 
#endif /* PIPEWIRE_MAP_H */