glib-mini.c revision f3f3c9b864a902e10cefb0e666f2354672352fca
1// Copyright 2014 The Android Open Source Project 2// 3// This software is licensed under the terms of the GNU General Public 4// License version 2, as published by the Free Software Foundation, and 5// may be copied, distributed, and modified under those terms. 6// 7// This program is distributed in the hope that it will be useful, 8// but WITHOUT ANY WARRANTY; without even the implied warranty of 9// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10// GNU General Public License for more details. 11 12#include <glib.h> 13 14#include <limits.h> 15#include <stdarg.h> 16#include <stdio.h> 17#include <stdlib.h> 18#include <string.h> 19 20// Print a panic message then exit the program immediately. 21void g_panic(const char* fmt, ...) { 22 va_list args; 23 fprintf(stderr, "MiniGLib:PANIC: "); 24 va_start(args, fmt); 25 vfprintf(stderr, fmt, args); 26 va_end(args); 27 exit(1); 28} 29 30 31// Heap allocation. 32 33void* g_malloc(size_t size) { 34 if (size == 0) 35 return NULL; 36 37 void* ptr = malloc(size); 38 if (ptr == NULL) 39 g_panic("Can't allocate %zu bytes!\n", size); 40 41 return ptr; 42} 43 44 45void* g_malloc0(size_t size) { 46 void* ptr = g_malloc(size); 47 if (ptr == NULL) 48 return NULL; 49 50 memset(ptr, 0, size); 51 return ptr; 52} 53 54 55void* g_realloc(void* ptr, size_t size) { 56 if (size == 0) { 57 g_free(ptr); 58 return NULL; 59 } 60 void* new_ptr = realloc(ptr, size); 61 if (new_ptr == NULL) 62 g_panic("Can't reallocate pointer %p to %zu bytes!\n", ptr, size); 63 64 return new_ptr; 65} 66 67 68void g_free(void* ptr) { 69 if (ptr) 70 free(ptr); 71} 72 73// Strings. 74 75char* g_strdup(const char* str) { 76 if (str == NULL) 77 return NULL; 78 79 size_t len = strlen(str); 80 char* copy = g_malloc(len + 1); 81 memcpy(copy, str, len + 1); 82 return copy; 83} 84 85 86char* g_strndup(const char* str, size_t size) { 87 const char *end = memchr(str, 0, size); 88 char *copy; 89 90 if (end) 91 size = end - str; 92 93 copy = g_malloc(size + 1); 94 memcpy(copy, str, size); 95 copy[size] = 0; 96 return copy; 97} 98 99 100char* g_strdup_printf(const char* fmt, ...) { 101 char* result; 102 va_list args; 103 va_start(args, fmt); 104 g_vasprintf(&result, fmt, args); 105 va_end(args); 106 return result; 107} 108 109 110char* g_strdup_vprintf(const char* fmt, va_list args) { 111 char* result; 112 g_vasprintf(&result, fmt, args); 113 return result; 114} 115 116 117int g_vasprintf(char** str, const char* fmt, va_list args) { 118#ifdef _WIN32 119 // On Win32, vsnprintf() is broken and always returns -1 in case of truncation, 120 // so make an educated guess, and try again if that fails with a larger pool. 121 size_t capacity = 128; 122 char* buffer = g_malloc(capacity); 123 for (;;) { 124 va_list args2; 125 va_copy(args2, args); 126 int len = vsnprintf(buffer, capacity, fmt, args2); 127 if (len >= 0) { 128 *str = buffer; 129 return len; 130 } 131 va_end(args2); 132 133 capacity *= 2; 134 if (capacity > INT_MAX) 135 g_panic("Formatted string is too long!\n"); 136 137 buffer = g_realloc(buffer, capacity); 138 } 139#else 140 // On other systems, vsnprintf() works properly and returns the size of the 141 // formatted string without truncation. 142 va_list args2; 143 va_copy(args2, args); 144 int len = vsnprintf(NULL, 0, fmt, args2); 145 va_end(args2); 146 if (len < 0) 147 g_panic("Can't format string!\n"); 148 149 char* result = g_malloc(len + 1); 150 va_copy(args2, args); 151 vsnprintf(result, (size_t)len, fmt, args2); 152 va_end(args2); 153 154 *str = result; 155 return len; 156#endif 157} 158 159 160// Single-linked list 161 162static GSList* _g_slist_alloc(void) { 163 return (GSList*) g_malloc(sizeof(GSList)); 164} 165 166void g_slist_free(GSList* list) { 167 while (list) { 168 GSList* next = list->next; 169 g_free(list); 170 list = next; 171 } 172} 173 174GSList* g_slist_last(GSList* list) { 175 while (list && list->next) 176 list = list->next; 177 return list; 178} 179 180GSList* g_slist_find(GSList* list, const void* data) { 181 while (list) { 182 if (list->data == data) 183 break; 184 list = list->next; 185 } 186 return list; 187} 188 189GSList* g_slist_append(GSList* list, void* data) { 190 GSList* new_list = _g_slist_alloc(); 191 new_list->data = data; 192 new_list->next = NULL; 193 194 if (!list) 195 return new_list; 196 197 GSList* last = g_slist_last(list); 198 last->next = new_list; 199 return list; 200} 201 202GSList* g_slist_prepend(GSList* list, void* data) { 203 GSList* new_list = _g_slist_alloc(); 204 new_list->data = data; 205 new_list->next = list; 206 return new_list; 207} 208 209GSList* g_slist_remove(GSList* list, const void* data) { 210 GSList** pnode = &list; 211 for (;;) { 212 GSList* node = *pnode; 213 if (!node) 214 break; 215 if (node->data == data) { 216 *pnode = node->next; 217 g_slist_free(node); 218 break; 219 } 220 pnode = &node->next; 221 } 222 return list; 223} 224 225void g_slist_foreach(GSList* list, GFunc func, void* user_data) { 226 while (list) { 227 GSList* next = list->next; 228 (*func)(list->data, user_data); 229 list = next; 230 } 231} 232 233// 234static GSList* g_slist_sort_merge(GSList* l1, 235 GSList* l2, 236 GFunc compare_func, 237 void* user_data) { 238 GSList* list = NULL; 239 GSList** tail = &list; 240 241 while (l1 && l2) { 242 int cmp = ((GCompareDataFunc) compare_func)(l1->data, l2->data, user_data); 243 if (cmp <= 0) { 244 *tail = l1; 245 tail = &l1->next; 246 l1 = l1->next; 247 } else { 248 *tail = l2; 249 tail = &l2->next; 250 l2 = l2->next; 251 } 252 } 253 *tail = l1 ? l1 : l2; 254 255 return list; 256} 257 258static GSList* g_slist_sort_real(GSList* list, 259 GFunc compare_func, 260 void* user_data) { 261 262 if (!list) 263 return NULL; 264 if (!list->next) 265 return list; 266 267 // Split list into two halves. 268 GSList* l1 = list; 269 GSList* l2 = list->next; 270 271 while (l2->next && l2->next->next) { 272 l2 = l2->next->next; 273 l1 = l1->next; 274 } 275 l2 = l1->next; 276 l1->next = NULL; 277 278 return g_slist_sort_merge( 279 g_slist_sort_real(list, compare_func, user_data), 280 g_slist_sort_real(l2, compare_func, user_data), 281 compare_func, 282 user_data); 283} 284 285GSList* g_slist_sort(GSList* list, GCompareFunc compare_func) { 286 return g_slist_sort_real(list, (GFunc) compare_func, NULL); 287} 288 289// Atomic operations 290 291#if !_WIN32 292// Note: Windows implementation in glib-mini-win32.c 293 294void g_atomic_int_inc(int volatile* atomic) { 295 __sync_fetch_and_add(atomic, 1); 296} 297 298gboolean g_atomic_int_dec_and_test(int volatile* atomic) { 299 return __sync_fetch_and_add(atomic, -1) == 1; 300} 301#endif // !_WIN32 302 303// Hash Tables 304 305// This is a rather vanilla implementation, slightly simpler 306// than the GLib one, since QEMU doesn't require the full features: 307// 308// - Uses a single dynamic array of (key,value,hash) tuples. 309// - Array capacity is always 2^N 310// - No use of modulo primes for simplicity, we don't expect 311// QEMU/QAPI to degenerate here. 312// - Dumb container only: doesn't own and free keys and values. 313// - No optimization for sets (i.e. when key == value for each entry). 314// - No iterators. 315// 316typedef struct { 317 gpointer key; 318 gpointer value; 319 guint hash; 320} GHashEntry; 321 322#define HASH_UNUSED 0 // Must be 0, see _remove_all() below. 323#define HASH_TOMBSTONE 1 324#define HASH_IS_REAL(h) ((h) >= 2) 325 326#define HASH_MIN_SHIFT 3 327#define HASH_MIN_CAPACITY (1 << HASH_MIN_SHIFT) 328 329struct _GHashTable { 330 int ref_count; 331 int num_items; 332 int num_used; // count of items + tombstones 333 int shift; 334 int capacity; 335 GHashEntry* entries; 336 GHashFunc hash_func; 337 GEqualFunc key_equal_func; 338}; 339 340// Compute the hash value of a given key. 341static inline size_t 342_g_hash_table_hash(GHashTable* table, gconstpointer key) { 343 size_t hash = table->hash_func(key); 344 return HASH_IS_REAL(hash) ? hash : 2; 345} 346 347 348GHashTable* g_hash_table_new(GHashFunc hash_func, 349 GEqualFunc key_equal_func) { 350 GHashTable* hash_table = g_new0(GHashTable, 1); 351 352 hash_table->ref_count = 1; 353 hash_table->num_items = 0; 354 hash_table->capacity = HASH_MIN_CAPACITY; 355 hash_table->entries = g_new0(GHashEntry, hash_table->capacity); 356 hash_table->hash_func = hash_func; 357 hash_table->key_equal_func = key_equal_func; 358 359 return hash_table; 360} 361 362 363static void _g_hash_table_remove_all(GHashTable* hash_table) { 364 // NOTE: This uses the fact that HASH_UNUSED is 0! 365 hash_table->num_items = 0; 366 memset(hash_table->entries, 367 0, 368 sizeof(hash_table->entries[0]) * hash_table->capacity); 369} 370 371 372GHashTable* g_hash_table_ref(GHashTable* hash_table) { 373 if (!hash_table) 374 return NULL; 375 376 g_atomic_int_inc(&hash_table->ref_count); 377 return hash_table; 378} 379 380 381void g_hash_table_unref(GHashTable* hash_table) { 382 if (!hash_table) 383 return; 384 385 if (!g_atomic_int_dec_and_test(&hash_table->ref_count)) 386 return; 387 388 _g_hash_table_remove_all(hash_table); 389 390 g_free(hash_table->entries); 391 hash_table->capacity = 0; 392 hash_table->entries = NULL; 393 394 g_free(hash_table); 395} 396 397 398void g_hash_table_destroy(GHashTable* hash_table) { 399 if (!hash_table) 400 return; 401 402 _g_hash_table_remove_all(hash_table); 403 g_hash_table_unref(hash_table); 404} 405 406 407// Probe the hash table for |key|. If it is in the table, return the index 408// to the corresponding entry. Otherwise, return the index of an unused 409// or tombstone entry. Also sets |*key_hash| to the key hash value on 410// return. 411static guint _g_hash_table_lookup_index(GHashTable* hash_table, 412 gconstpointer key, 413 guint* key_hash) { 414 guint hash = _g_hash_table_hash(hash_table, key); 415 *key_hash = hash; 416 417 guint probe_mask = (hash_table->capacity - 1); 418 gint tombstone = -1; 419 guint probe_index = hash & probe_mask; 420 guint step = 0; 421 422 GHashEntry* probe = &hash_table->entries[probe_index]; 423 while (probe->hash != HASH_UNUSED) { 424 if (probe->hash == hash) { 425 if (hash_table->key_equal_func) { 426 if (hash_table->key_equal_func(probe->key, key)) 427 return probe_index; 428 } else if (probe->key == key) { 429 return probe_index; 430 } 431 } else if (probe->hash == HASH_TOMBSTONE && tombstone < 0) { 432 tombstone = (int)probe_index; 433 } 434 435 step++; 436 probe_index = (probe_index + step) & probe_mask; 437 probe = &hash_table->entries[probe_index]; 438 } 439 440 if (tombstone >= 0) 441 return (guint)tombstone; 442 443 return probe_index; 444} 445 446 447void* g_hash_table_lookup(GHashTable* hash_table, 448 const void* key) { 449 guint key_hash = HASH_UNUSED; 450 guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash); 451 GHashEntry* entry = &hash_table->entries[probe_index]; 452 453 return HASH_IS_REAL(entry->hash) ? entry->value : NULL; 454} 455 456 457// Remove key/value pair at index position |i|. 458static void _g_hash_table_remove_index(GHashTable* hash_table, 459 int i) { 460 GHashEntry* entry = &hash_table->entries[i]; 461 entry->hash = HASH_TOMBSTONE; 462 entry->key = NULL; 463 entry->value = NULL; 464} 465 466 467gboolean g_hash_table_remove(GHashTable* hash_table, 468 const void* key) { 469 guint key_hash = HASH_UNUSED; 470 guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash); 471 GHashEntry* entry = &hash_table->entries[probe_index]; 472 if (!HASH_IS_REAL(entry->hash)) 473 return 0; 474 475 _g_hash_table_remove_index(hash_table, probe_index); 476 hash_table->num_items--; 477 return 1; 478} 479 480// Resize the hash table, this also gets rid of all tombstones. 481static void _g_hash_table_resize(GHashTable* hash_table) { 482 guint old_capacity = hash_table->capacity; 483 484 // Compute new shift from new size 485 guint new_size = hash_table->num_items * 2; 486 guint new_capacity = HASH_MIN_CAPACITY; 487 while (new_capacity < new_size) 488 new_capacity <<= 1; 489 490 GHashEntry* new_entries = g_new0(GHashEntry, new_capacity); 491 guint n; 492 for (n = 0; n < old_capacity; ++n) { 493 GHashEntry* old_entry = &hash_table->entries[n]; 494 guint old_hash = old_entry->hash; 495 496 if (!HASH_IS_REAL(old_hash)) 497 continue; 498 499 guint probe_mask = (new_capacity - 1); 500 guint probe_n = old_hash & probe_mask; 501 GHashEntry* probe = &new_entries[probe_n]; 502 guint step = 0; 503 while (probe->hash != HASH_UNUSED) { 504 step++; 505 probe_n = (probe_n + step) & probe_mask; 506 probe = &new_entries[probe_n]; 507 } 508 probe[0] = old_entry[0]; 509 } 510 511 g_free(hash_table->entries); 512 hash_table->entries = new_entries; 513 hash_table->capacity = new_capacity; 514 hash_table->num_used = hash_table->num_items; 515} 516 517// Resize the hash table if needed. 518static void _g_hash_table_maybe_resize(GHashTable* hash_table) { 519 guint used = hash_table->num_used; 520 guint count = hash_table->num_items; 521 guint capacity = hash_table->capacity; 522 if ((capacity > count * 4 && capacity > HASH_MIN_CAPACITY) || 523 capacity < used + (used / 16)) { 524 _g_hash_table_resize(hash_table); 525 } 526} 527 528static void _g_hash_table_insert_index(GHashTable* hash_table, 529 guint key_index, 530 guint new_key_hash, 531 gpointer new_key, 532 gpointer new_value) { 533 GHashEntry* entry = &hash_table->entries[key_index]; 534 guint old_hash = entry->hash; 535 536 entry->key = new_key; 537 entry->value = new_value; 538 entry->hash = new_key_hash; 539 540 if (HASH_IS_REAL(old_hash)) { 541 // Simple replacement, exit immediately. 542 return; 543 } 544 545 hash_table->num_items++; 546 if (old_hash == HASH_TOMBSTONE) { 547 // No need to resize when replacing a tombstone. 548 return; 549 } 550 551 hash_table->num_used++; 552 _g_hash_table_maybe_resize(hash_table); 553} 554 555void g_hash_table_insert(GHashTable* hash_table, 556 void* key, 557 void* value) { 558 guint key_hash; 559 guint key_index = 560 _g_hash_table_lookup_index(hash_table, key, &key_hash); 561 562 _g_hash_table_insert_index(hash_table, key_index, key_hash, key, value); 563} 564 565 566void g_hash_table_foreach(GHashTable* hash_table, 567 GHFunc func, 568 gpointer user_data) { 569 guint n; 570 for (n = 0; n < hash_table->capacity; ++n) { 571 GHashEntry* entry = &hash_table->entries[n]; 572 if (HASH_IS_REAL(entry->hash)) 573 (*func)(entry->key, entry->value, user_data); 574 } 575} 576 577 578gpointer g_hash_table_find(GHashTable* hash_table, 579 GHRFunc predicate, 580 gpointer user_data) { 581 guint n; 582 for (n = 0; n < hash_table->capacity; ++n) { 583 GHashEntry* entry = &hash_table->entries[n]; 584 if (HASH_IS_REAL(entry->hash) && 585 (*predicate)(entry->key, entry->value, user_data)) { 586 return entry->value; 587 } 588 } 589 return NULL; 590} 591 592 593guint g_hash_table_size(GHashTable* hash_table) { 594 return hash_table->num_items; 595} 596