src/wayland-util.c

   1 /*
   2  * Copyright © 2008 Kristian Høgsberg
   3  *
   4  * Permission to use, copy, modify, distribute, and sell this software and its
   5  * documentation for any purpose is hereby granted without fee, provided that
   6  * the above copyright notice appear in all copies and that both that copyright
   7  * notice and this permission notice appear in supporting documentation, and
   8  * that the name of the copyright holders not be used in advertising or
   9  * publicity pertaining to distribution of the software without specific,
  10  * written prior permission.  The copyright holders make no representations
  11  * about the suitability of this software for any purpose.  It is provided "as
  12  * is" without express or implied warranty.
  13  *
  14  * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  15  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  16  * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  17  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  18  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  19  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
  20  * OF THIS SOFTWARE.
  21  */
  22
  23 #include <stdlib.h>
  24 #include <stdint.h>
  25 #include <string.h>
  26 #include "wayland-util.h"
  27
  28 WL_EXPORT void
  29 wl_list_init(struct wl_list *list)
  30 {
  31         list->prev = list;
  32         list->next = list;
  33 }
  34
  35 WL_EXPORT void
  36 wl_list_insert(struct wl_list *list, struct wl_list *elm)
  37 {
  38         elm->prev = list;
  39         elm->next = list->next;
  40         list->next = elm;
  41         elm->next->prev = elm;
  42 }
  43
  44 WL_EXPORT void
  45 wl_list_remove(struct wl_list *elm)
  46 {
  47         elm->prev->next = elm->next;
  48         elm->next->prev = elm->prev;
  49 }
  50
  51 WL_EXPORT int
  52 wl_list_length(struct wl_list *list)
  53 {
  54         struct wl_list *e;
  55         int count;
  56
  57         count = 0;
  58         e = list->next;
  59         while (e != list) {
  60                 e = e->next;
  61                 count++;
  62         }
  63
  64         return count;
  65 }
  66
  67 WL_EXPORT int
  68 wl_list_empty(struct wl_list *list)
  69 {
  70         return list->next == list;
  71 }
  72
  73 WL_EXPORT void
  74 wl_list_insert_list(struct wl_list *list, struct wl_list *other)
  75 {
  76         other->next->prev = list;
  77         other->prev->next = list->next;
  78         list->next->prev = other->prev;
  79         list->next = other->next;
  80 }
  81
  82 WL_EXPORT void
  83 wl_array_init(struct wl_array *array)
  84 {
  85         memset(array, 0, sizeof *array);
  86 }
  87
  88 WL_EXPORT void
  89 wl_array_release(struct wl_array *array)
  90 {
  91         free(array->data);
  92 }
  93
  94 WL_EXPORT void *
  95 wl_array_add(struct wl_array *array, int size)
  96 {
  97         int alloc;
  98         void *data, *p;
  99
 100         if (array->alloc > 0)
 101                 alloc = array->alloc;
 102         else
 103                 alloc = 16;
 104
 105         while (alloc < array->size + size)
 106                 alloc *= 2;
 107
 108         if (array->alloc < alloc) {
 109                 if (array->alloc > 0)
 110                         data = realloc(array->data, alloc);
 111                 else
 112                         data = malloc(alloc);
 113
 114                 if (data == NULL)
 115                         return 0;
 116                 array->data = data;
 117                 array->alloc = alloc;
 118         }
 119
 120         p = array->data + array->size;
 121         array->size += size;
 122
 123         return p;
 124 }
 125
 126 WL_EXPORT void
 127 wl_array_copy(struct wl_array *array, struct wl_array *source)
 128 {
 129         array->size = 0;
 130         wl_array_add(array, source->size);
 131         memcpy(array->data, source->data, source->size);
 132 }
 133
 134 union map_entry {
 135         uintptr_t next;
 136         void *data;
 137 };
 138
 139 WL_EXPORT void
 140 wl_map_init(struct wl_map *map)
 141 {
 142         memset(map, 0, sizeof *map);
 143 }
 144
 145 WL_EXPORT void
 146 wl_map_release(struct wl_map *map)
 147 {
 148         wl_array_release(&map->entries);
 149 }
 150
 151 WL_EXPORT uint32_t
 152 wl_map_insert_new(struct wl_map *map, void *data)
 153 {
 154         union map_entry *start, *entry;
 155
 156         if (map->free_list) {
 157                 start = map->entries.data;
 158                 entry = &start[map->free_list >> 1];
 159                 map->free_list = entry->next;
 160         } else {
 161                 entry = wl_array_add(&map->entries, sizeof *entry);
 162                 start = map->entries.data;
 163         }
 164
 165         entry->data = data;
 166
 167         return entry - start;
 168 }
 169
 170 WL_EXPORT int
 171 wl_map_insert_at(struct wl_map *map, uint32_t i, void *data)
 172 {
 173         union map_entry *start;
 174         uint32_t count;
 175
 176         /* assert(map->free_list == NULL */
 177         count = map->entries.size / sizeof *start;
 178
 179         if (count < i)
 180                 return -1;
 181
 182         if (count == i)
 183                 wl_array_add(&map->entries, sizeof *start);
 184
 185         start = map->entries.data;
 186         start[i].data = data;
 187
 188         return 0;
 189 }
 190
 191 WL_EXPORT void
 192 wl_map_remove(struct wl_map *map, uint32_t i)
 193 {
 194         union map_entry *start;
 195         uint32_t count;
 196
 197         start = map->entries.data;
 198         count = map->entries.size / sizeof *start;
 199
 200         start[i].next = map->free_list;
 201         map->free_list = (i << 1) | 1;
 202 }
 203
 204 WL_EXPORT void *
 205 wl_map_lookup(struct wl_map *map, uint32_t i)
 206 {
 207         union map_entry *start;
 208         uint32_t count;
 209
 210         start = map->entries.data;
 211         count = map->entries.size / sizeof *start;
 212
 213         if (i < count && !(start[i].next & 1))
 214                 return start[i].data;
 215
 216         return NULL;
 217 }
 218
 219 WL_EXPORT void
 220 wl_map_for_each(struct wl_map *map, wl_iterator_func_t func, void *data)
 221 {
 222         union map_entry *start, *end, *p;
 223
 224         start = map->entries.data;
 225         end = (union map_entry *) ((char *) map->entries.data + map->entries.size);
 226
 227         for (p = start; p < end; p++)
 228                 if (p->data && !(p->next & 1))
 229                         func(p->data, data);
 230 }