glib-mini.c revision e33e5e9dee88459eb11456a773bdb64e1cce53eb
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_critical(const char* fmt, ...) { 22 va_list args; 23 fprintf(stderr, "CRITICAL: "); 24 va_start(args, fmt); 25 vfprintf(stderr, fmt, args); 26 va_end(args); 27} 28 29void g_panic(const char* fmt, ...) { 30 va_list args; 31 fprintf(stderr, "PANIC: "); 32 va_start(args, fmt); 33 vfprintf(stderr, fmt, args); 34 va_end(args); 35 exit(1); 36} 37 38// Heap allocation. 39 40void* g_malloc(size_t size) { 41 if (size == 0) 42 return NULL; 43 44 void* ptr = malloc(size); 45 if (ptr == NULL) 46 g_panic("Can't allocate %zu bytes!\n", size); 47 48 return ptr; 49} 50 51 52void* g_malloc0(size_t size) { 53 void* ptr = g_malloc(size); 54 if (ptr == NULL) 55 return NULL; 56 57 memset(ptr, 0, size); 58 return ptr; 59} 60 61 62void* g_realloc(void* ptr, size_t size) { 63 if (size == 0) { 64 g_free(ptr); 65 return NULL; 66 } 67 void* new_ptr = realloc(ptr, size); 68 if (new_ptr == NULL) 69 g_panic("Can't reallocate pointer %p to %zu bytes!\n", ptr, size); 70 71 return new_ptr; 72} 73 74 75void g_free(void* ptr) { 76 if (ptr) 77 free(ptr); 78} 79 80// Strings. 81 82char* g_strdup(const char* str) { 83 if (str == NULL) 84 return NULL; 85 86 size_t len = strlen(str); 87 char* copy = g_malloc(len + 1); 88 memcpy(copy, str, len + 1); 89 return copy; 90} 91 92 93char* g_strndup(const char* str, size_t size) { 94 const char *end = memchr(str, 0, size); 95 char *copy; 96 97 if (end) 98 size = end - str; 99 100 copy = g_malloc(size + 1); 101 memcpy(copy, str, size); 102 copy[size] = 0; 103 return copy; 104} 105 106 107char* g_strdup_printf(const char* fmt, ...) { 108 char* result; 109 va_list args; 110 va_start(args, fmt); 111 g_vasprintf(&result, fmt, args); 112 va_end(args); 113 return result; 114} 115 116 117char* g_strdup_vprintf(const char* fmt, va_list args) { 118 char* result; 119 g_vasprintf(&result, fmt, args); 120 return result; 121} 122 123 124int g_vasprintf(char** str, const char* fmt, va_list args) { 125#ifdef _WIN32 126 // On Win32, vsnprintf() is broken and always returns -1 in case of truncation, 127 // so make an educated guess, and try again if that fails with a larger pool. 128 size_t capacity = 128; 129 char* buffer = g_malloc(capacity); 130 for (;;) { 131 va_list args2; 132 va_copy(args2, args); 133 int len = vsnprintf(buffer, capacity, fmt, args2); 134 if (len >= 0) { 135 *str = buffer; 136 return len; 137 } 138 va_end(args2); 139 140 capacity *= 2; 141 if (capacity > INT_MAX) 142 g_panic("Formatted string is too long!\n"); 143 144 buffer = g_realloc(buffer, capacity); 145 } 146#else 147 // On other systems, vsnprintf() works properly and returns the size of the 148 // formatted string without truncation. 149 va_list args2; 150 va_copy(args2, args); 151 int len = vsnprintf(NULL, 0, fmt, args2); 152 va_end(args2); 153 if (len < 0) 154 g_panic("Can't format string!\n"); 155 156 char* result = g_malloc(len + 1); 157 va_copy(args2, args); 158 vsnprintf(result, (size_t)len, fmt, args2); 159 va_end(args2); 160 161 *str = result; 162 return len; 163#endif 164} 165 166char** g_strsplit(const char* string, const char* delim, int max_tokens) { 167 // Sanity checks. 168 if (!string || !delim || !*delim) 169 return NULL; 170 171 if (max_tokens < 1) 172 max_tokens = INT_MAX; 173 174 // Create empty list of results. 175 GSList* string_list = NULL; 176 guint n = 0; 177 178 if (*string) { 179 // Input list is not empty, so try to split it. 180 const char* remainder = string; 181 const char* s = strstr(remainder, delim); 182 if (s) { 183 size_t delim_len = strlen(delim); 184 while (--max_tokens && s) { 185 size_t len = s - remainder; 186 string_list = g_slist_prepend(string_list, g_strndup(remainder, len)); 187 n++; 188 remainder = s + delim_len; 189 s = strstr(remainder, delim); 190 } 191 } 192 n++; 193 string_list = g_slist_prepend(string_list, g_strdup(remainder)); 194 } 195 196 // Convert list into NULL-terminated vector. 197 char** result = g_new(char*, n + 1); 198 result[n--] = NULL; 199 GSList* slist = string_list; 200 while (slist) { 201 result[n--] = slist->data; 202 slist = slist->next; 203 } 204 g_slist_free(string_list); 205 206 return result; 207} 208 209void g_strfreev(char** strings) { 210 guint n; 211 for (n = 0; strings[n]; ++n) { 212 g_free(strings[n]); 213 } 214 g_free(strings); 215} 216 217gboolean g_str_equal(const void* v1, const void* v2) { 218 return !strcmp((const char*)v1, (const char*)v2); 219} 220 221guint g_str_hash(const void* str) { 222 const signed char* p = str; 223 guint hash = 5381U; 224 225 for (; *p; ++p) 226 hash = (hash << 5) + hash + (guint)*p; 227 228 return hash; 229} 230 231// Single-linked list 232 233static GSList* _g_slist_alloc(void) { 234 return (GSList*) g_malloc(sizeof(GSList)); 235} 236 237void g_slist_free(GSList* list) { 238 while (list) { 239 GSList* next = list->next; 240 g_free(list); 241 list = next; 242 } 243} 244 245GSList* g_slist_last(GSList* list) { 246 while (list && list->next) 247 list = list->next; 248 return list; 249} 250 251GSList* g_slist_find(GSList* list, const void* data) { 252 while (list) { 253 if (list->data == data) 254 break; 255 list = list->next; 256 } 257 return list; 258} 259 260GSList* g_slist_append(GSList* list, void* data) { 261 GSList* new_list = _g_slist_alloc(); 262 new_list->data = data; 263 new_list->next = NULL; 264 265 if (!list) 266 return new_list; 267 268 GSList* last = g_slist_last(list); 269 last->next = new_list; 270 return list; 271} 272 273GSList* g_slist_prepend(GSList* list, void* data) { 274 GSList* new_list = _g_slist_alloc(); 275 new_list->data = data; 276 new_list->next = list; 277 return new_list; 278} 279 280GSList* g_slist_remove(GSList* list, const void* data) { 281 GSList** pnode = &list; 282 for (;;) { 283 GSList* node = *pnode; 284 if (!node) 285 break; 286 if (node->data == data) { 287 *pnode = node->next; 288 g_slist_free(node); 289 break; 290 } 291 pnode = &node->next; 292 } 293 return list; 294} 295 296void g_slist_foreach(GSList* list, GFunc func, void* user_data) { 297 while (list) { 298 GSList* next = list->next; 299 (*func)(list->data, user_data); 300 list = next; 301 } 302} 303 304// 305static GSList* g_slist_sort_merge(GSList* l1, 306 GSList* l2, 307 GFunc compare_func, 308 void* user_data) { 309 GSList* list = NULL; 310 GSList** tail = &list; 311 312 while (l1 && l2) { 313 int cmp = ((GCompareDataFunc) compare_func)(l1->data, l2->data, user_data); 314 if (cmp <= 0) { 315 *tail = l1; 316 tail = &l1->next; 317 l1 = l1->next; 318 } else { 319 *tail = l2; 320 tail = &l2->next; 321 l2 = l2->next; 322 } 323 } 324 *tail = l1 ? l1 : l2; 325 326 return list; 327} 328 329static GSList* g_slist_sort_real(GSList* list, 330 GFunc compare_func, 331 void* user_data) { 332 333 if (!list) 334 return NULL; 335 if (!list->next) 336 return list; 337 338 // Split list into two halves. 339 GSList* l1 = list; 340 GSList* l2 = list->next; 341 342 while (l2->next && l2->next->next) { 343 l2 = l2->next->next; 344 l1 = l1->next; 345 } 346 l2 = l1->next; 347 l1->next = NULL; 348 349 return g_slist_sort_merge( 350 g_slist_sort_real(list, compare_func, user_data), 351 g_slist_sort_real(l2, compare_func, user_data), 352 compare_func, 353 user_data); 354} 355 356GSList* g_slist_sort(GSList* list, GCompareFunc compare_func) { 357 return g_slist_sort_real(list, (GFunc) compare_func, NULL); 358} 359 360// Atomic operations 361 362#if !_WIN32 363// Note: Windows implementation in glib-mini-win32.c 364 365void g_atomic_int_inc(int volatile* atomic) { 366 __sync_fetch_and_add(atomic, 1); 367} 368 369gboolean g_atomic_int_dec_and_test(int volatile* atomic) { 370 return __sync_fetch_and_add(atomic, -1) == 1; 371} 372#endif // !_WIN32 373 374// Hash Tables 375 376// This is a rather vanilla implementation, slightly simpler 377// than the GLib one, since QEMU doesn't require the full features: 378// 379// - Uses a single dynamic array of (key,value,hash) tuples. 380// - Array capacity is always 2^N 381// - No use of modulo primes for simplicity, we don't expect 382// QEMU/QAPI to degenerate here. 383// - Dumb container only: doesn't own and free keys and values. 384// - No optimization for sets (i.e. when key == value for each entry). 385// - No iterators. 386// 387typedef struct { 388 gpointer key; 389 gpointer value; 390 guint hash; 391} GHashEntry; 392 393#define HASH_UNUSED 0 // Must be 0, see _remove_all() below. 394#define HASH_TOMBSTONE 1 395#define HASH_IS_REAL(h) ((h) >= 2) 396 397#define HASH_MIN_SHIFT 3 398#define HASH_MIN_CAPACITY (1 << HASH_MIN_SHIFT) 399 400struct _GHashTable { 401 int ref_count; 402 int num_items; 403 int num_used; // count of items + tombstones 404 int shift; 405 int capacity; 406 GHashEntry* entries; 407 GHashFunc hash_func; 408 GEqualFunc key_equal_func; 409}; 410 411// Compute the hash value of a given key. 412static inline size_t 413_g_hash_table_hash(GHashTable* table, gconstpointer key) { 414 size_t hash = table->hash_func(key); 415 return HASH_IS_REAL(hash) ? hash : 2; 416} 417 418 419GHashTable* g_hash_table_new(GHashFunc hash_func, 420 GEqualFunc key_equal_func) { 421 GHashTable* hash_table = g_new0(GHashTable, 1); 422 423 hash_table->ref_count = 1; 424 hash_table->num_items = 0; 425 hash_table->capacity = HASH_MIN_CAPACITY; 426 hash_table->entries = g_new0(GHashEntry, hash_table->capacity); 427 hash_table->hash_func = hash_func; 428 hash_table->key_equal_func = key_equal_func; 429 430 return hash_table; 431} 432 433 434static void _g_hash_table_remove_all(GHashTable* hash_table) { 435 // NOTE: This uses the fact that HASH_UNUSED is 0! 436 hash_table->num_items = 0; 437 memset(hash_table->entries, 438 0, 439 sizeof(hash_table->entries[0]) * hash_table->capacity); 440} 441 442 443GHashTable* g_hash_table_ref(GHashTable* hash_table) { 444 if (!hash_table) 445 return NULL; 446 447 g_atomic_int_inc(&hash_table->ref_count); 448 return hash_table; 449} 450 451 452void g_hash_table_unref(GHashTable* hash_table) { 453 if (!hash_table) 454 return; 455 456 if (!g_atomic_int_dec_and_test(&hash_table->ref_count)) 457 return; 458 459 _g_hash_table_remove_all(hash_table); 460 461 g_free(hash_table->entries); 462 hash_table->capacity = 0; 463 hash_table->entries = NULL; 464 465 g_free(hash_table); 466} 467 468 469void g_hash_table_destroy(GHashTable* hash_table) { 470 if (!hash_table) 471 return; 472 473 _g_hash_table_remove_all(hash_table); 474 g_hash_table_unref(hash_table); 475} 476 477 478// Probe the hash table for |key|. If it is in the table, return the index 479// to the corresponding entry. Otherwise, return the index of an unused 480// or tombstone entry. Also sets |*key_hash| to the key hash value on 481// return. 482static guint _g_hash_table_lookup_index(GHashTable* hash_table, 483 gconstpointer key, 484 guint* key_hash) { 485 guint hash = _g_hash_table_hash(hash_table, key); 486 *key_hash = hash; 487 488 guint probe_mask = (hash_table->capacity - 1); 489 gint tombstone = -1; 490 guint probe_index = hash & probe_mask; 491 guint step = 0; 492 493 GHashEntry* probe = &hash_table->entries[probe_index]; 494 while (probe->hash != HASH_UNUSED) { 495 if (probe->hash == hash) { 496 if (hash_table->key_equal_func) { 497 if (hash_table->key_equal_func(probe->key, key)) 498 return probe_index; 499 } else if (probe->key == key) { 500 return probe_index; 501 } 502 } else if (probe->hash == HASH_TOMBSTONE && tombstone < 0) { 503 tombstone = (int)probe_index; 504 } 505 506 step++; 507 probe_index = (probe_index + step) & probe_mask; 508 probe = &hash_table->entries[probe_index]; 509 } 510 511 if (tombstone >= 0) 512 return (guint)tombstone; 513 514 return probe_index; 515} 516 517 518void* g_hash_table_lookup(GHashTable* hash_table, 519 const void* key) { 520 guint key_hash = HASH_UNUSED; 521 guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash); 522 GHashEntry* entry = &hash_table->entries[probe_index]; 523 524 return HASH_IS_REAL(entry->hash) ? entry->value : NULL; 525} 526 527 528// Remove key/value pair at index position |i|. 529static void _g_hash_table_remove_index(GHashTable* hash_table, 530 int i) { 531 GHashEntry* entry = &hash_table->entries[i]; 532 entry->hash = HASH_TOMBSTONE; 533 entry->key = NULL; 534 entry->value = NULL; 535} 536 537 538gboolean g_hash_table_remove(GHashTable* hash_table, 539 const void* key) { 540 guint key_hash = HASH_UNUSED; 541 guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash); 542 GHashEntry* entry = &hash_table->entries[probe_index]; 543 if (!HASH_IS_REAL(entry->hash)) 544 return 0; 545 546 _g_hash_table_remove_index(hash_table, probe_index); 547 hash_table->num_items--; 548 return 1; 549} 550 551// Resize the hash table, this also gets rid of all tombstones. 552static void _g_hash_table_resize(GHashTable* hash_table) { 553 guint old_capacity = hash_table->capacity; 554 555 // Compute new shift from new size 556 guint new_size = hash_table->num_items * 2; 557 guint new_capacity = HASH_MIN_CAPACITY; 558 while (new_capacity < new_size) 559 new_capacity <<= 1; 560 561 GHashEntry* new_entries = g_new0(GHashEntry, new_capacity); 562 guint n; 563 for (n = 0; n < old_capacity; ++n) { 564 GHashEntry* old_entry = &hash_table->entries[n]; 565 guint old_hash = old_entry->hash; 566 567 if (!HASH_IS_REAL(old_hash)) 568 continue; 569 570 guint probe_mask = (new_capacity - 1); 571 guint probe_n = old_hash & probe_mask; 572 GHashEntry* probe = &new_entries[probe_n]; 573 guint step = 0; 574 while (probe->hash != HASH_UNUSED) { 575 step++; 576 probe_n = (probe_n + step) & probe_mask; 577 probe = &new_entries[probe_n]; 578 } 579 probe[0] = old_entry[0]; 580 } 581 582 g_free(hash_table->entries); 583 hash_table->entries = new_entries; 584 hash_table->capacity = new_capacity; 585 hash_table->num_used = hash_table->num_items; 586} 587 588// Resize the hash table if needed. 589static void _g_hash_table_maybe_resize(GHashTable* hash_table) { 590 guint used = hash_table->num_used; 591 guint count = hash_table->num_items; 592 guint capacity = hash_table->capacity; 593 if ((capacity > count * 4 && capacity > HASH_MIN_CAPACITY) || 594 capacity < used + (used / 16)) { 595 _g_hash_table_resize(hash_table); 596 } 597} 598 599static void _g_hash_table_insert_index(GHashTable* hash_table, 600 guint key_index, 601 guint new_key_hash, 602 gpointer new_key, 603 gpointer new_value) { 604 GHashEntry* entry = &hash_table->entries[key_index]; 605 guint old_hash = entry->hash; 606 607 entry->key = new_key; 608 entry->value = new_value; 609 entry->hash = new_key_hash; 610 611 if (HASH_IS_REAL(old_hash)) { 612 // Simple replacement, exit immediately. 613 return; 614 } 615 616 hash_table->num_items++; 617 if (old_hash == HASH_TOMBSTONE) { 618 // No need to resize when replacing a tombstone. 619 return; 620 } 621 622 hash_table->num_used++; 623 _g_hash_table_maybe_resize(hash_table); 624} 625 626void g_hash_table_insert(GHashTable* hash_table, 627 void* key, 628 void* value) { 629 guint key_hash; 630 guint key_index = 631 _g_hash_table_lookup_index(hash_table, key, &key_hash); 632 633 _g_hash_table_insert_index(hash_table, key_index, key_hash, key, value); 634} 635 636 637void g_hash_table_foreach(GHashTable* hash_table, 638 GHFunc func, 639 gpointer user_data) { 640 guint n; 641 for (n = 0; n < hash_table->capacity; ++n) { 642 GHashEntry* entry = &hash_table->entries[n]; 643 if (HASH_IS_REAL(entry->hash)) 644 (*func)(entry->key, entry->value, user_data); 645 } 646} 647 648 649gpointer g_hash_table_find(GHashTable* hash_table, 650 GHRFunc predicate, 651 gpointer user_data) { 652 guint n; 653 for (n = 0; n < hash_table->capacity; ++n) { 654 GHashEntry* entry = &hash_table->entries[n]; 655 if (HASH_IS_REAL(entry->hash) && 656 (*predicate)(entry->key, entry->value, user_data)) { 657 return entry->value; 658 } 659 } 660 return NULL; 661} 662 663 664guint g_hash_table_size(GHashTable* hash_table) { 665 return hash_table->num_items; 666} 667 668// Queues 669 670struct _GQueueNode { 671 void* data; 672 GQueueNode* next; 673 GQueueNode* prev; 674}; 675 676static inline GQueueNode* _g_queue_node_alloc(void) { 677 return g_new0(GQueueNode, 1); 678} 679 680static void inline _g_queue_node_free(GQueueNode* node) { 681 g_free(node); 682} 683 684GQueue* g_queue_new(void) { 685 GQueue* queue = g_new0(GQueue, 1); 686 return queue; 687} 688 689void g_queue_free(GQueue* queue) { 690 GQueueNode* node = queue->head; 691 while (node) { 692 GQueueNode* next = node->next; 693 _g_queue_node_free(node); 694 node = next; 695 } 696 queue->head = queue->tail = NULL; 697 queue->length = 0; 698 g_free(queue); 699} 700 701gboolean g_queue_is_empty(GQueue* queue) { 702 return queue->head == NULL; 703} 704 705void g_queue_push_tail(GQueue* queue, void* data) { 706 GQueueNode* node = _g_queue_node_alloc(); 707 node->data = data; 708 node->next = NULL; 709 node->prev = queue->tail; 710 queue->tail = node; 711 queue->length++; 712} 713 714void* g_queue_peek_head(GQueue* queue) { 715 return (queue->head) ? queue->head->data : NULL; 716} 717 718void* g_queue_peek_tail(GQueue* queue) { 719 return (queue->tail) ? queue->tail->data : NULL; 720} 721 722void* g_queue_pop_head(GQueue* queue) { 723 GQueueNode* head = queue->head; 724 if (!head) 725 return NULL; 726 727 void* result = head->data; 728 729 if (head->next) { 730 queue->head = head->next; 731 head->next->prev = NULL; 732 } else { 733 queue->head = NULL; 734 queue->tail = NULL; 735 } 736 queue->length--; 737 738 return result; 739} 740