diff options
| -rw-r--r-- | Makefile.in | 2 | ||||
| -rw-r--r-- | connection.c | 6 | ||||
| -rw-r--r-- | connection.h | 2 | ||||
| -rw-r--r-- | wayland-client.c | 15 | ||||
| -rw-r--r-- | wayland-hash.c | 296 | ||||
| -rw-r--r-- | wayland-util.c | 76 | ||||
| -rw-r--r-- | wayland-util.h | 15 | ||||
| -rw-r--r-- | wayland.c | 12 |
8 files changed, 326 insertions, 98 deletions
diff --git a/Makefile.in b/Makefile.in index 3f666e2..04538ab 100644 --- a/Makefile.in +++ b/Makefile.in @@ -17,12 +17,14 @@ libwayland-server.so : \ event-loop.o \ connection.o \ wayland-util.o \ + wayland-hash.o \ wayland-protocol.o libwayland.so : \ wayland-client.o \ connection.o \ wayland-util.o \ + wayland-hash.o \ wayland-protocol.o $(libs) : CFLAGS += -fPIC @FFI_CFLAGS@ diff --git a/connection.c b/connection.c index b37e940..264c6ab 100644 --- a/connection.c +++ b/connection.c @@ -280,7 +280,7 @@ wl_connection_vmarshal(struct wl_connection *connection, void wl_connection_demarshal(struct wl_connection *connection, uint32_t size, - struct wl_hash *objects, + struct wl_hash_table *objects, void (*func)(void), void *data, struct wl_object *target, const struct wl_message *message) @@ -342,7 +342,7 @@ wl_connection_demarshal(struct wl_connection *connection, break; case 'o': types[i] = &ffi_type_pointer; - object = wl_hash_lookup(objects, *p); + object = wl_hash_table_lookup(objects, *p); if (object == NULL && *p != 0) printf("unknown object (%d)\n", *p); values[i].object = object; @@ -351,7 +351,7 @@ wl_connection_demarshal(struct wl_connection *connection, case 'n': types[i] = &ffi_type_uint32; values[i].new_id = *p; - object = wl_hash_lookup(objects, *p); + object = wl_hash_table_lookup(objects, *p); if (object != NULL) printf("object already exists (%d)\n", *p); p++; diff --git a/connection.h b/connection.h index 3db07ee..30e82e1 100644 --- a/connection.h +++ b/connection.h @@ -50,7 +50,7 @@ void wl_connection_vmarshal(struct wl_connection *connection, void wl_connection_demarshal(struct wl_connection *connection, uint32_t size, - struct wl_hash *objects, + struct wl_hash_table *objects, void (*func)(void), void *data, struct wl_object *target, const struct wl_message *message); diff --git a/wayland-client.c b/wayland-client.c index 80e2832..8cabbb2 100644 --- a/wayland-client.c +++ b/wayland-client.c @@ -95,7 +95,7 @@ struct wl_display { int fd; uint32_t id, id_count, next_range; uint32_t mask; - struct wl_hash *objects; + struct wl_hash_table *objects; struct wl_list global_list; struct wl_listener listener; struct wl_list global_listener_list; @@ -184,7 +184,7 @@ wl_proxy_create_for_global(struct wl_display *display, proxy->display = display; global->proxy = proxy; wl_list_init(&proxy->listener_list); - wl_hash_insert(display->objects, &proxy->base); + wl_hash_table_insert(display->objects, proxy->base.id, proxy); wl_list_for_each(listener, &display->global_listener_list, link) (*listener->handler)(display, &proxy->base, listener->data); @@ -311,7 +311,8 @@ display_handle_global(void *data, wl_list_insert(display->global_list.prev, &global->link); if (strcmp(global->interface, "display") == 0) - wl_hash_insert(display->objects, &display->proxy.base); + wl_hash_table_insert(display->objects, + id, &display->proxy.base); else if (strcmp(global->interface, "compositor") == 0) display->compositor = (struct wl_compositor *) wl_proxy_create_for_global(display, global, @@ -383,7 +384,7 @@ wl_display_create(const char *name, size_t name_size) return NULL; } - display->objects = wl_hash_create(); + display->objects = wl_hash_table_create(); wl_list_init(&display->global_list); wl_list_init(&display->global_listener_list); @@ -448,7 +449,8 @@ handle_event(struct wl_display *display, if (id == 1) proxy = &display->proxy; else - proxy = (struct wl_proxy *) wl_hash_lookup(display->objects, id); + proxy = (struct wl_proxy *) + wl_hash_table_lookup(display->objects, id); if (proxy != NULL) { if (wl_list_empty(&proxy->listener_list)) { @@ -544,7 +546,8 @@ wl_compositor_create_surface(struct wl_compositor *compositor) surface->proxy.base.interface = &wl_surface_interface; surface->proxy.base.id = wl_display_allocate_id(compositor->proxy.display); surface->proxy.display = compositor->proxy.display; - wl_hash_insert(compositor->proxy.display->objects, &surface->proxy.base); + wl_hash_table_insert(compositor->proxy.display->objects, + surface->proxy.base.id, surface); wl_proxy_marshal(&compositor->proxy, WL_COMPOSITOR_CREATE_SURFACE, surface); diff --git a/wayland-hash.c b/wayland-hash.c new file mode 100644 index 0000000..b299a33 --- /dev/null +++ b/wayland-hash.c @@ -0,0 +1,296 @@ +/* + * Copyright © 2009 Intel Corporation + * Copyright © 1988-2004 Keith Packard and Bart Massey. + * + * 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. + * + * Except as contained in this notice, the names of the authors + * or their institutions shall not be used in advertising or + * otherwise to promote the sale, use or other dealings in this + * Software without prior written authorization from the + * authors. + * + * Authors: + * Eric Anholt <eric@anholt.net> + * Keith Packard <keithp@keithp.com> + */ + +#include <stdlib.h> + +#include "wayland-util.h" + +struct hash_entry { + uint32_t hash; + void *data; +}; + +struct wl_hash_table { + struct hash_entry *table; + uint32_t size; + uint32_t rehash; + uint32_t max_entries; + uint32_t size_index; + uint32_t entries; + uint32_t deleted_entries; +}; + +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) + +/* + * From Knuth -- a good choice for hash/rehash values is p, p-2 where + * p and p-2 are both prime. These tables are sized to have an extra 10% + * free to avoid exponential performance degradation as the hash table fills + */ + +static const uint32_t deleted_data; + +static const struct { + uint32_t max_entries, size, rehash; +} hash_sizes[] = { + { 2, 5, 3 }, + { 4, 7, 5 }, + { 8, 13, 11 }, + { 16, 19, 17 }, + { 32, 43, 41 }, + { 64, 73, 71 }, + { 128, 151, 149 }, + { 256, 283, 281 }, + { 512, 571, 569 }, + { 1024, 1153, 1151 }, + { 2048, 2269, 2267 }, + { 4096, 4519, 4517 }, + { 8192, 9013, 9011 }, + { 16384, 18043, 18041 }, + { 32768, 36109, 36107 }, + { 65536, 72091, 72089 }, + { 131072, 144409, 144407 }, + { 262144, 288361, 288359 }, + { 524288, 576883, 576881 }, + { 1048576, 1153459, 1153457 }, + { 2097152, 2307163, 2307161 }, + { 4194304, 4613893, 4613891 }, + { 8388608, 9227641, 9227639 }, + { 16777216, 18455029, 18455027 }, + { 33554432, 36911011, 36911009 }, + { 67108864, 73819861, 73819859 }, + { 134217728, 147639589, 147639587 }, + { 268435456, 295279081, 295279079 }, + { 536870912, 590559793, 590559791 }, + { 1073741824, 1181116273, 1181116271}, + { 2147483648ul, 2362232233ul, 2362232231ul} +}; + +static int +entry_is_free(struct hash_entry *entry) +{ + return entry->data == NULL; +} + +static int +entry_is_deleted(struct hash_entry *entry) +{ + return entry->data == &deleted_data; +} + +static int +entry_is_present(struct hash_entry *entry) +{ + return entry->data != NULL && entry->data != &deleted_data; +} + +WL_EXPORT struct wl_hash_table * +wl_hash_table_create(void) +{ + struct wl_hash_table *ht; + + ht = malloc(sizeof(*ht)); + if (ht == NULL) + return NULL; + + ht->size_index = 0; + ht->size = hash_sizes[ht->size_index].size; + ht->rehash = hash_sizes[ht->size_index].rehash; + ht->max_entries = hash_sizes[ht->size_index].max_entries; + ht->table = calloc(ht->size, sizeof(*ht->table)); + ht->entries = 0; + ht->deleted_entries = 0; + + if (ht->table == NULL) { + free(ht); + return NULL; + } + + return ht; +} + +/** + * Frees the given hash table. + */ +WL_EXPORT void +wl_hash_table_destroy(struct wl_hash_table *ht) +{ + if (!ht) + return; + + free(ht->table); + free(ht); +} + +/** + * Finds a hash table entry with the given key and hash of that key. + * + * Returns NULL if no entry is found. Note that the data pointer may be + * modified by the user. + */ +static void * +hash_table_search(struct wl_hash_table *ht, uint32_t hash) +{ + uint32_t hash_address; + + hash_address = hash % ht->size; + do { + uint32_t double_hash; + + struct hash_entry *entry = ht->table + hash_address; + + if (entry_is_free(entry)) { + return NULL; + } else if (entry_is_present(entry) && entry->hash == hash) { + return entry; + } + + double_hash = hash % ht->rehash; + if (double_hash == 0) + double_hash = 1; + + hash_address = (hash_address + double_hash) % ht->size; + } while (hash_address != hash % ht->size); + + return NULL; +} + +WL_EXPORT void * +wl_hash_table_lookup(struct wl_hash_table *ht, uint32_t hash) +{ + struct hash_entry *entry; + + entry = hash_table_search(ht, hash); + if (entry != NULL) + return entry->data; + + return NULL; +} + +static void +hash_table_rehash(struct wl_hash_table *ht, int new_size_index) +{ + struct wl_hash_table old_ht; + struct hash_entry *table, *entry; + + if (new_size_index >= ARRAY_SIZE(hash_sizes)) + return; + + table = calloc(hash_sizes[new_size_index].size, sizeof(*ht->table)); + if (table == NULL) + return; + + old_ht = *ht; + + ht->table = table; + ht->size_index = new_size_index; + ht->size = hash_sizes[ht->size_index].size; + ht->rehash = hash_sizes[ht->size_index].rehash; + ht->max_entries = hash_sizes[ht->size_index].max_entries; + ht->entries = 0; + ht->deleted_entries = 0; + + for (entry = old_ht.table; + entry != old_ht.table + old_ht.size; + entry++) { + if (entry_is_present(entry)) { + wl_hash_table_insert(ht, entry->hash, entry->data); + } + } + + free(old_ht.table); +} + +/** + * Inserts the data with the given hash into the table. + * + * Note that insertion may rearrange the table on a resize or rehash, + * so previously found hash_entries are no longer valid after this function. + */ +WL_EXPORT int +wl_hash_table_insert(struct wl_hash_table *ht, uint32_t hash, void *data) +{ + uint32_t hash_address; + + if (ht->entries >= ht->max_entries) { + hash_table_rehash(ht, ht->size_index + 1); + } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { + hash_table_rehash(ht, ht->size_index); + } + + hash_address = hash % ht->size; + do { + struct hash_entry *entry = ht->table + hash_address; + uint32_t double_hash; + + if (!entry_is_present(entry)) { + if (entry_is_deleted(entry)) + ht->deleted_entries--; + entry->hash = hash; + entry->data = data; + ht->entries++; + return 0; + } + + double_hash = hash % ht->rehash; + if (double_hash == 0) + double_hash = 1; + + hash_address = (hash_address + double_hash) % ht->size; + } while (hash_address != hash % ht->size); + + /* We could hit here if a required resize failed. An unchecked-malloc + * application could ignore this result. + */ + return -1; +} + +/** + * This function deletes the given hash table entry. + * + * Note that deletion doesn't otherwise modify the table, so an iteration over + * the table deleting entries is safe. + */ +WL_EXPORT void +wl_hash_table_remove(struct wl_hash_table *ht, uint32_t hash) +{ + struct hash_entry *entry; + + entry = hash_table_search(ht, hash); + if (entry != NULL) { + entry->data = (void *) &deleted_data; + ht->entries--; + ht->deleted_entries++; + } +} diff --git a/wayland-util.c b/wayland-util.c index cd73542..a287cce 100644 --- a/wayland-util.c +++ b/wayland-util.c @@ -25,82 +25,6 @@ #include <string.h> #include "wayland-util.h" -struct wl_hash { - struct wl_object **objects; - uint32_t count, alloc; -}; - -struct wl_hash * -wl_hash_create(void) -{ - struct wl_hash *hash; - - hash = malloc(sizeof *hash); - if (hash == NULL) - return hash; - - memset(hash, 0, sizeof *hash); - - return hash; -} - -void -wl_hash_destroy(struct wl_hash *hash) -{ - free(hash); -} - -int wl_hash_insert(struct wl_hash *hash, struct wl_object *object) -{ - struct wl_object **objects; - uint32_t alloc; - - if (hash->count == hash->alloc) { - if (hash->alloc == 0) - alloc = 16; - else - alloc = hash->alloc * 2; - objects = realloc(hash->objects, alloc * sizeof *objects); - if (objects == NULL) - return -1; - - hash->objects = objects; - hash->alloc = alloc; - } - - hash->objects[hash->count] = object; - hash->count++; - - return 0; -} - -struct wl_object * -wl_hash_lookup(struct wl_hash *hash, uint32_t id) -{ - int i; - - for (i = 0; i < hash->count; i++) { - if (hash->objects[i]->id == id) - return hash->objects[i]; - } - - return NULL; -} - -void -wl_hash_remove(struct wl_hash *hash, struct wl_object *object) -{ - int i; - - for (i = 0; i < hash->count; i++) { - if (hash->objects[i]->id == object->id) { - hash->objects[i] = hash->objects[hash->count - 1]; - hash->count--; - break; - } - } -} - WL_EXPORT void wl_list_init(struct wl_list *list) { diff --git a/wayland-util.h b/wayland-util.h index 0233cb3..ed4acbc 100644 --- a/wayland-util.h +++ b/wayland-util.h @@ -23,6 +23,8 @@ #ifndef WAYLAND_UTIL_H #define WAYLAND_UTIL_H +#include <inttypes.h> + /* GCC visibility */ #if defined(__GNUC__) && __GNUC__ >= 4 #define WL_EXPORT __attribute__ ((visibility("default"))) @@ -64,12 +66,13 @@ struct wl_object { uint32_t id; }; -struct wl_hash; -struct wl_hash *wl_hash_create(void); -void wl_hash_destroy(struct wl_hash *hash); -int wl_hash_insert(struct wl_hash *hash, struct wl_object *object); -struct wl_object *wl_hash_lookup(struct wl_hash *hash, uint32_t id); -void wl_hash_remove(struct wl_hash *hash, struct wl_object *object); +struct wl_hash_table; +struct wl_hash_table *wl_hash_table_create(void); +void wl_hash_table_destroy(struct wl_hash_table *ht); +void *wl_hash_table_lookup(struct wl_hash_table *ht, uint32_t hash); +int wl_hash_table_insert(struct wl_hash_table *ht, uint32_t hash, void *data); +void wl_hash_table_remove(struct wl_hash_table *ht, uint32_t hash); + struct wl_list { struct wl_list *prev; @@ -50,7 +50,7 @@ struct wl_client { struct wl_display { struct wl_object base; struct wl_event_loop *loop; - struct wl_hash *objects; + struct wl_hash_table *objects; struct wl_list pending_frame_list; uint32_t client_id_range; @@ -109,7 +109,7 @@ wl_client_connection_data(int fd, uint32_t mask, void *data) if (len < size) break; - object = wl_hash_lookup(client->display->objects, p[0]); + object = wl_hash_table_lookup(client->display->objects, p[0]); if (object == NULL) { wl_client_post_event(client, &client->display->base, WL_DISPLAY_INVALID_OBJECT, p[0]); @@ -247,7 +247,7 @@ wl_client_add_surface(struct wl_client *client, surface->base.implementation = (void (**)(void)) implementation; surface->client = client; - wl_hash_insert(display->objects, &surface->base); + wl_hash_table_insert(display->objects, id, surface); wl_list_insert(client->surface_list.prev, &surface->link); return 0; @@ -259,7 +259,7 @@ wl_client_remove_surface(struct wl_client *client, { struct wl_display *display = client->display; - wl_hash_remove(display->objects, &surface->base); + wl_hash_table_remove(display->objects, surface->base.id); wl_list_remove(&surface->link); } @@ -305,7 +305,7 @@ wl_display_create(void) return NULL; } - display->objects = wl_hash_create(); + display->objects = wl_hash_table_create(); if (display->objects == NULL) { free(display); return NULL; @@ -333,7 +333,7 @@ WL_EXPORT void wl_display_add_object(struct wl_display *display, struct wl_object *object) { object->id = display->id++; - wl_hash_insert(display->objects, object); + wl_hash_table_insert(display->objects, object->id, object); } WL_EXPORT int |