src/wayland-util.c

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