glib-mini.c revision 45df61baff91503dd922964044345de5da230314
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 159char** g_strsplit(const char* string, const char* delim, int max_tokens) { 160 // Sanity checks. 161 if (!string || !delim || !*delim) 162 return NULL; 163 164 if (max_tokens < 1) 165 max_tokens = INT_MAX; 166 167 // Create empty list of results. 168 GSList* string_list = NULL; 169 guint n = 0; 170 171 if (*string) { 172 // Input list is not empty, so try to split it. 173 const char* remainder = string; 174 const char* s = strstr(remainder, delim); 175 if (s) { 176 size_t delim_len = strlen(delim); 177 while (--max_tokens && s) { 178 size_t len = s - remainder; 179 string_list = g_slist_prepend(string_list, g_strndup(remainder, len)); 180 n++; 181 remainder = s + delim_len; 182 s = strstr(remainder, delim); 183 } 184 } 185 n++; 186 string_list = g_slist_prepend(string_list, g_strdup(remainder)); 187 } 188 189 // Convert list into NULL-terminated vector. 190 char** result = g_new(char*, n + 1); 191 result[n--] = NULL; 192 GSList* slist = string_list; 193 while (slist) { 194 result[n--] = slist->data; 195 slist = slist->next; 196 } 197 g_slist_free(string_list); 198 199 return result; 200} 201 202void g_strfreev(char** strings) { 203 guint n; 204 for (n = 0; strings[n]; ++n) { 205 g_free(strings[n]); 206 } 207 g_free(strings); 208} 209 210gboolean g_str_equal(const void* v1, const void* v2) { 211 return !strcmp((const char*)v1, (const char*)v2); 212} 213 214guint g_str_hash(const void* str) { 215 const signed char* p = str; 216 guint hash = 5381U; 217 218 for (; *p; ++p) 219 hash = (hash << 5) + hash + (guint)*p; 220 221 return hash; 222} 223 224// Single-linked list 225 226static GSList* _g_slist_alloc(void) { 227 return (GSList*) g_malloc(sizeof(GSList)); 228} 229 230void g_slist_free(GSList* list) { 231 while (list) { 232 GSList* next = list->next; 233 g_free(list); 234 list = next; 235 } 236} 237 238GSList* g_slist_last(GSList* list) { 239 while (list && list->next) 240 list = list->next; 241 return list; 242} 243 244GSList* g_slist_find(GSList* list, const void* data) { 245 while (list) { 246 if (list->data == data) 247 break; 248 list = list->next; 249 } 250 return list; 251} 252 253GSList* g_slist_append(GSList* list, void* data) { 254 GSList* new_list = _g_slist_alloc(); 255 new_list->data = data; 256 new_list->next = NULL; 257 258 if (!list) 259 return new_list; 260 261 GSList* last = g_slist_last(list); 262 last->next = new_list; 263 return list; 264} 265 266GSList* g_slist_prepend(GSList* list, void* data) { 267 GSList* new_list = _g_slist_alloc(); 268 new_list->data = data; 269 new_list->next = list; 270 return new_list; 271} 272 273GSList* g_slist_remove(GSList* list, const void* data) { 274 GSList** pnode = &list; 275 for (;;) { 276 GSList* node = *pnode; 277 if (!node) 278 break; 279 if (node->data == data) { 280 *pnode = node->next; 281 g_slist_free(node); 282 break; 283 } 284 pnode = &node->next; 285 } 286 return list; 287} 288 289void g_slist_foreach(GSList* list, GFunc func, void* user_data) { 290 while (list) { 291 GSList* next = list->next; 292 (*func)(list->data, user_data); 293 list = next; 294 } 295} 296 297// 298static GSList* g_slist_sort_merge(GSList* l1, 299 GSList* l2, 300 GFunc compare_func, 301 void* user_data) { 302 GSList* list = NULL; 303 GSList** tail = &list; 304 305 while (l1 && l2) { 306 int cmp = ((GCompareDataFunc) compare_func)(l1->data, l2->data, user_data); 307 if (cmp <= 0) { 308 *tail = l1; 309 tail = &l1->next; 310 l1 = l1->next; 311 } else { 312 *tail = l2; 313 tail = &l2->next; 314 l2 = l2->next; 315 } 316 } 317 *tail = l1 ? l1 : l2; 318 319 return list; 320} 321 322static GSList* g_slist_sort_real(GSList* list, 323 GFunc compare_func, 324 void* user_data) { 325 326 if (!list) 327 return NULL; 328 if (!list->next) 329 return list; 330 331 // Split list into two halves. 332 GSList* l1 = list; 333 GSList* l2 = list->next; 334 335 while (l2->next && l2->next->next) { 336 l2 = l2->next->next; 337 l1 = l1->next; 338 } 339 l2 = l1->next; 340 l1->next = NULL; 341 342 return g_slist_sort_merge( 343 g_slist_sort_real(list, compare_func, user_data), 344 g_slist_sort_real(l2, compare_func, user_data), 345 compare_func, 346 user_data); 347} 348 349GSList* g_slist_sort(GSList* list, GCompareFunc compare_func) { 350 return g_slist_sort_real(list, (GFunc) compare_func, NULL); 351} 352 353// Atomic operations 354 355#if !_WIN32 356// Note: Windows implementation in glib-mini-win32.c 357 358void g_atomic_int_inc(int volatile* atomic) { 359 __sync_fetch_and_add(atomic, 1); 360} 361 362gboolean g_atomic_int_dec_and_test(int volatile* atomic) { 363 return __sync_fetch_and_add(atomic, -1) == 1; 364} 365#endif // !_WIN32 366 367// Hash Tables 368 369// This is a rather vanilla implementation, slightly simpler 370// than the GLib one, since QEMU doesn't require the full features: 371// 372// - Uses a single dynamic array of (key,value,hash) tuples. 373// - Array capacity is always 2^N 374// - No use of modulo primes for simplicity, we don't expect 375// QEMU/QAPI to degenerate here. 376// - Dumb container only: doesn't own and free keys and values. 377// - No optimization for sets (i.e. when key == value for each entry). 378// - No iterators. 379// 380typedef struct { 381 gpointer key; 382 gpointer value; 383 guint hash; 384} GHashEntry; 385 386#define HASH_UNUSED 0 // Must be 0, see _remove_all() below. 387#define HASH_TOMBSTONE 1 388#define HASH_IS_REAL(h) ((h) >= 2) 389 390#define HASH_MIN_SHIFT 3 391#define HASH_MIN_CAPACITY (1 << HASH_MIN_SHIFT) 392 393struct _GHashTable { 394 int ref_count; 395 int num_items; 396 int num_used; // count of items + tombstones 397 int shift; 398 int capacity; 399 GHashEntry* entries; 400 GHashFunc hash_func; 401 GEqualFunc key_equal_func; 402}; 403 404// Compute the hash value of a given key. 405static inline size_t 406_g_hash_table_hash(GHashTable* table, gconstpointer key) { 407 size_t hash = table->hash_func(key); 408 return HASH_IS_REAL(hash) ? hash : 2; 409} 410 411 412GHashTable* g_hash_table_new(GHashFunc hash_func, 413 GEqualFunc key_equal_func) { 414 GHashTable* hash_table = g_new0(GHashTable, 1); 415 416 hash_table->ref_count = 1; 417 hash_table->num_items = 0; 418 hash_table->capacity = HASH_MIN_CAPACITY; 419 hash_table->entries = g_new0(GHashEntry, hash_table->capacity); 420 hash_table->hash_func = hash_func; 421 hash_table->key_equal_func = key_equal_func; 422 423 return hash_table; 424} 425 426 427static void _g_hash_table_remove_all(GHashTable* hash_table) { 428 // NOTE: This uses the fact that HASH_UNUSED is 0! 429 hash_table->num_items = 0; 430 memset(hash_table->entries, 431 0, 432 sizeof(hash_table->entries[0]) * hash_table->capacity); 433} 434 435 436GHashTable* g_hash_table_ref(GHashTable* hash_table) { 437 if (!hash_table) 438 return NULL; 439 440 g_atomic_int_inc(&hash_table->ref_count); 441 return hash_table; 442} 443 444 445void g_hash_table_unref(GHashTable* hash_table) { 446 if (!hash_table) 447 return; 448 449 if (!g_atomic_int_dec_and_test(&hash_table->ref_count)) 450 return; 451 452 _g_hash_table_remove_all(hash_table); 453 454 g_free(hash_table->entries); 455 hash_table->capacity = 0; 456 hash_table->entries = NULL; 457 458 g_free(hash_table); 459} 460 461 462void g_hash_table_destroy(GHashTable* hash_table) { 463 if (!hash_table) 464 return; 465 466 _g_hash_table_remove_all(hash_table); 467 g_hash_table_unref(hash_table); 468} 469 470 471// Probe the hash table for |key|. If it is in the table, return the index 472// to the corresponding entry. Otherwise, return the index of an unused 473// or tombstone entry. Also sets |*key_hash| to the key hash value on 474// return. 475static guint _g_hash_table_lookup_index(GHashTable* hash_table, 476 gconstpointer key, 477 guint* key_hash) { 478 guint hash = _g_hash_table_hash(hash_table, key); 479 *key_hash = hash; 480 481 guint probe_mask = (hash_table->capacity - 1); 482 gint tombstone = -1; 483 guint probe_index = hash & probe_mask; 484 guint step = 0; 485 486 GHashEntry* probe = &hash_table->entries[probe_index]; 487 while (probe->hash != HASH_UNUSED) { 488 if (probe->hash == hash) { 489 if (hash_table->key_equal_func) { 490 if (hash_table->key_equal_func(probe->key, key)) 491 return probe_index; 492 } else if (probe->key == key) { 493 return probe_index; 494 } 495 } else if (probe->hash == HASH_TOMBSTONE && tombstone < 0) { 496 tombstone = (int)probe_index; 497 } 498 499 step++; 500 probe_index = (probe_index + step) & probe_mask; 501 probe = &hash_table->entries[probe_index]; 502 } 503 504 if (tombstone >= 0) 505 return (guint)tombstone; 506 507 return probe_index; 508} 509 510 511void* g_hash_table_lookup(GHashTable* hash_table, 512 const void* key) { 513 guint key_hash = HASH_UNUSED; 514 guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash); 515 GHashEntry* entry = &hash_table->entries[probe_index]; 516 517 return HASH_IS_REAL(entry->hash) ? entry->value : NULL; 518} 519 520 521// Remove key/value pair at index position |i|. 522static void _g_hash_table_remove_index(GHashTable* hash_table, 523 int i) { 524 GHashEntry* entry = &hash_table->entries[i]; 525 entry->hash = HASH_TOMBSTONE; 526 entry->key = NULL; 527 entry->value = NULL; 528} 529 530 531gboolean g_hash_table_remove(GHashTable* hash_table, 532 const void* key) { 533 guint key_hash = HASH_UNUSED; 534 guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash); 535 GHashEntry* entry = &hash_table->entries[probe_index]; 536 if (!HASH_IS_REAL(entry->hash)) 537 return 0; 538 539 _g_hash_table_remove_index(hash_table, probe_index); 540 hash_table->num_items--; 541 return 1; 542} 543 544// Resize the hash table, this also gets rid of all tombstones. 545static void _g_hash_table_resize(GHashTable* hash_table) { 546 guint old_capacity = hash_table->capacity; 547 548 // Compute new shift from new size 549 guint new_size = hash_table->num_items * 2; 550 guint new_capacity = HASH_MIN_CAPACITY; 551 while (new_capacity < new_size) 552 new_capacity <<= 1; 553 554 GHashEntry* new_entries = g_new0(GHashEntry, new_capacity); 555 guint n; 556 for (n = 0; n < old_capacity; ++n) { 557 GHashEntry* old_entry = &hash_table->entries[n]; 558 guint old_hash = old_entry->hash; 559 560 if (!HASH_IS_REAL(old_hash)) 561 continue; 562 563 guint probe_mask = (new_capacity - 1); 564 guint probe_n = old_hash & probe_mask; 565 GHashEntry* probe = &new_entries[probe_n]; 566 guint step = 0; 567 while (probe->hash != HASH_UNUSED) { 568 step++; 569 probe_n = (probe_n + step) & probe_mask; 570 probe = &new_entries[probe_n]; 571 } 572 probe[0] = old_entry[0]; 573 } 574 575 g_free(hash_table->entries); 576 hash_table->entries = new_entries; 577 hash_table->capacity = new_capacity; 578 hash_table->num_used = hash_table->num_items; 579} 580 581// Resize the hash table if needed. 582static void _g_hash_table_maybe_resize(GHashTable* hash_table) { 583 guint used = hash_table->num_used; 584 guint count = hash_table->num_items; 585 guint capacity = hash_table->capacity; 586 if ((capacity > count * 4 && capacity > HASH_MIN_CAPACITY) || 587 capacity < used + (used / 16)) { 588 _g_hash_table_resize(hash_table); 589 } 590} 591 592static void _g_hash_table_insert_index(GHashTable* hash_table, 593 guint key_index, 594 guint new_key_hash, 595 gpointer new_key, 596 gpointer new_value) { 597 GHashEntry* entry = &hash_table->entries[key_index]; 598 guint old_hash = entry->hash; 599 600 entry->key = new_key; 601 entry->value = new_value; 602 entry->hash = new_key_hash; 603 604 if (HASH_IS_REAL(old_hash)) { 605 // Simple replacement, exit immediately. 606 return; 607 } 608 609 hash_table->num_items++; 610 if (old_hash == HASH_TOMBSTONE) { 611 // No need to resize when replacing a tombstone. 612 return; 613 } 614 615 hash_table->num_used++; 616 _g_hash_table_maybe_resize(hash_table); 617} 618 619void g_hash_table_insert(GHashTable* hash_table, 620 void* key, 621 void* value) { 622 guint key_hash; 623 guint key_index = 624 _g_hash_table_lookup_index(hash_table, key, &key_hash); 625 626 _g_hash_table_insert_index(hash_table, key_index, key_hash, key, value); 627} 628 629 630void g_hash_table_foreach(GHashTable* hash_table, 631 GHFunc func, 632 gpointer user_data) { 633 guint n; 634 for (n = 0; n < hash_table->capacity; ++n) { 635 GHashEntry* entry = &hash_table->entries[n]; 636 if (HASH_IS_REAL(entry->hash)) 637 (*func)(entry->key, entry->value, user_data); 638 } 639} 640 641 642gpointer g_hash_table_find(GHashTable* hash_table, 643 GHRFunc predicate, 644 gpointer user_data) { 645 guint n; 646 for (n = 0; n < hash_table->capacity; ++n) { 647 GHashEntry* entry = &hash_table->entries[n]; 648 if (HASH_IS_REAL(entry->hash) && 649 (*predicate)(entry->key, entry->value, user_data)) { 650 return entry->value; 651 } 652 } 653 return NULL; 654} 655 656 657guint g_hash_table_size(GHashTable* hash_table) { 658 return hash_table->num_items; 659} 660