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
  28 #include "wayland-util.h"
  29 #include "wayland-private.h"
  30
  31 WL_EXPORT void
  32 wl_list_init(struct wl_list *list)
  33 {
  34         list->prev = list;
  35         list->next = list;
  36 }
  37
  38 WL_EXPORT void
  39 wl_list_insert(struct wl_list *list, struct wl_list *elm)
  40 {
  41         elm->prev = list;
  42         elm->next = list->next;
  43         list->next = elm;
  44         elm->next->prev = elm;
  45 }
  46
  47 WL_EXPORT void
  48 wl_list_remove(struct wl_list *elm)
  49 {
  50         elm->prev->next = elm->next;
  51         elm->next->prev = elm->prev;
  52 }
  53
  54 WL_EXPORT int
  55 wl_list_length(struct wl_list *list)
  56 {
  57         struct wl_list *e;
  58         int count;
  59
  60         count = 0;
  61         e = list->next;
  62         while (e != list) {
  63                 e = e->next;
  64                 count++;
  65         }
  66
  67         return count;
  68 }
  69
  70 WL_EXPORT int
  71 wl_list_empty(struct wl_list *list)
  72 {
  73         return list->next == list;
  74 }
  75
  76 WL_EXPORT void
  77 wl_list_insert_list(struct wl_list *list, struct wl_list *other)
  78 {
  79         other->next->prev = list;
  80         other->prev->next = list->next;
  81         list->next->prev = other->prev;
  82         list->next = other->next;
  83 }
  84
  85 WL_EXPORT void
  86 wl_array_init(struct wl_array *array)
  87 {
  88         memset(array, 0, sizeof *array);
  89 }
  90
  91 WL_EXPORT void
  92 wl_array_release(struct wl_array *array)
  93 {
  94         free(array->data);
  95 }
  96
  97 WL_EXPORT void *
  98 wl_array_add(struct wl_array *array, int size)
  99 {
 100         int alloc;
 101         void *data, *p;
 102
 103         if (array->alloc > 0)
 104                 alloc = array->alloc;
 105         else
 106                 alloc = 16;
 107
 108         while (alloc < array->size + size)
 109                 alloc *= 2;
 110
 111         if (array->alloc < alloc) {
 112                 if (array->alloc > 0)
 113                         data = realloc(array->data, alloc);
 114                 else
 115                         data = malloc(alloc);
 116
 117                 if (data == NULL)
 118                         return 0;
 119                 array->data = data;
 120                 array->alloc = alloc;
 121         }
 122
 123         p = array->data + array->size;
 124         array->size += size;
 125
 126         return p;
 127 }
 128
 129 WL_EXPORT void
 130 wl_array_copy(struct wl_array *array, struct wl_array *source)
 131 {
 132         array->size = 0;
 133         wl_array_add(array, source->size);
 134         memcpy(array->data, source->data, source->size);
 135 }
 136
 137 union map_entry {
 138         uintptr_t next;
 139         void *data;
 140 };
 141
 142 WL_EXPORT void
 143 wl_map_init(struct wl_map *map)
 144 {
 145         memset(map, 0, sizeof *map);
 146 }
 147
 148 WL_EXPORT void
 149 wl_map_release(struct wl_map *map)
 150 {
 151         wl_array_release(&map->client_entries);
 152         wl_array_release(&map->server_entries);
 153 }
 154
 155 WL_EXPORT uint32_t
 156 wl_map_insert_new(struct wl_map *map, uint32_t side, void *data)
 157 {
 158         union map_entry *start, *entry;
 159         struct wl_array *entries;
 160         uint32_t base;
 161
 162         if (side == WL_MAP_CLIENT_SIDE) {
 163                 entries = &map->client_entries;
 164                 base = 0;
 165         } else {
 166                 entries = &map->server_entries;
 167                 base = WL_SERVER_ID_START;
 168         }
 169
 170         if (map->free_list) {
 171                 start = entries->data;
 172                 entry = &start[map->free_list >> 1];
 173                 map->free_list = entry->next;
 174         } else {
 175                 entry = wl_array_add(entries, sizeof *entry);
 176                 start = entries->data;
 177         }
 178
 179         entry->data = data;
 180
 181         return (entry - start) + base;
 182 }
 183
 184 WL_EXPORT int
 185 wl_map_insert_at(struct wl_map *map, uint32_t i, void *data)
 186 {
 187         union map_entry *start;
 188         uint32_t count;
 189         struct wl_array *entries;
 190
 191         if (i < WL_SERVER_ID_START) {
 192                 entries = &map->client_entries;
 193         } else {
 194                 entries = &map->server_entries;
 195                 i -= WL_SERVER_ID_START;
 196         }
 197
 198         count = entries->size / sizeof *start;
 199         if (count < i)
 200                 return -1;
 201
 202         if (count == i)
 203                 wl_array_add(entries, sizeof *start);
 204
 205         start = entries->data;
 206         start[i].data = data;
 207
 208         return 0;
 209 }
 210
 211 WL_EXPORT void
 212 wl_map_remove(struct wl_map *map, uint32_t i)
 213 {
 214         union map_entry *start;
 215         struct wl_array *entries;
 216
 217         if (i < WL_SERVER_ID_START) {
 218                 entries = &map->client_entries;
 219         } else {
 220                 entries = &map->server_entries;
 221                 i -= WL_SERVER_ID_START;
 222         }
 223
 224         start = entries->data;
 225         start[i].next = map->free_list;
 226         map->free_list = (i << 1) | 1;
 227 }
 228
 229 WL_EXPORT void *
 230 wl_map_lookup(struct wl_map *map, uint32_t i)
 231 {
 232         union map_entry *start;
 233         uint32_t count;
 234         struct wl_array *entries;
 235
 236         if (i < WL_SERVER_ID_START) {
 237                 entries = &map->client_entries;
 238         } else {
 239                 entries = &map->server_entries;
 240                 i -= WL_SERVER_ID_START;
 241         }
 242
 243         start = entries->data;
 244         count = entries->size / sizeof *start;
 245
 246         if (i < count && !(start[i].next & 1))
 247                 return start[i].data;
 248
 249         return NULL;
 250 }
 251
 252 static void
 253 for_each_helper(struct wl_array *entries, wl_iterator_func_t func, void *data)
 254 {
 255         union map_entry *start, *end, *p;
 256
 257         start = entries->data;
 258         end = (union map_entry *) ((char *) entries->data + entries->size);
 259
 260         for (p = start; p < end; p++)
 261                 if (p->data && !(p->next & 1))
 262                         func(p->data, data);
 263 }
 264
 265 WL_EXPORT void
 266 wl_map_for_each(struct wl_map *map, wl_iterator_func_t func, void *data)
 267 {
 268         for_each_helper(&map->client_entries, func, data);
 269         for_each_helper(&map->server_entries, func, data);
 270 }