11d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// Copyright 2014 The Android Open Source Project 21d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// 31d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// This software is licensed under the terms of the GNU General Public 41d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// License version 2, as published by the Free Software Foundation, and 51d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// may be copied, distributed, and modified under those terms. 61d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// 71d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// This program is distributed in the hope that it will be useful, 81d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// but WITHOUT ANY WARRANTY; without even the implied warranty of 91d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 101d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// GNU General Public License for more details. 111d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 121d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner#include <glib.h> 131d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 141d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner#include <limits.h> 151d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner#include <stdarg.h> 161d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner#include <stdio.h> 171d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner#include <stdlib.h> 189f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner#include <stdint.h> 191d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner#include <string.h> 201d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 211d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// Print a panic message then exit the program immediately. 22e33e5e9dee88459eb11456a773bdb64e1cce53ebDavid 'Digit' Turnervoid g_critical(const char* fmt, ...) { 23e33e5e9dee88459eb11456a773bdb64e1cce53ebDavid 'Digit' Turner va_list args; 24e33e5e9dee88459eb11456a773bdb64e1cce53ebDavid 'Digit' Turner fprintf(stderr, "CRITICAL: "); 25e33e5e9dee88459eb11456a773bdb64e1cce53ebDavid 'Digit' Turner va_start(args, fmt); 26e33e5e9dee88459eb11456a773bdb64e1cce53ebDavid 'Digit' Turner vfprintf(stderr, fmt, args); 27e33e5e9dee88459eb11456a773bdb64e1cce53ebDavid 'Digit' Turner va_end(args); 28e33e5e9dee88459eb11456a773bdb64e1cce53ebDavid 'Digit' Turner} 29e33e5e9dee88459eb11456a773bdb64e1cce53ebDavid 'Digit' Turner 30f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnervoid g_panic(const char* fmt, ...) { 311d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_list args; 32e33e5e9dee88459eb11456a773bdb64e1cce53ebDavid 'Digit' Turner fprintf(stderr, "PANIC: "); 331d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_start(args, fmt); 341d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner vfprintf(stderr, fmt, args); 351d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_end(args); 361d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner exit(1); 371d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 381d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 391d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// Heap allocation. 401d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 411d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turnervoid* g_malloc(size_t size) { 421d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (size == 0) 431d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return NULL; 441d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 451d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner void* ptr = malloc(size); 461d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (ptr == NULL) 471d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner g_panic("Can't allocate %zu bytes!\n", size); 481d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 491d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return ptr; 501d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 511d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 521d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 531d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turnervoid* g_malloc0(size_t size) { 541d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner void* ptr = g_malloc(size); 551d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (ptr == NULL) 561d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return NULL; 571d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 581d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner memset(ptr, 0, size); 591d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return ptr; 601d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 611d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 621d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 631d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turnervoid* g_realloc(void* ptr, size_t size) { 641d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (size == 0) { 651d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner g_free(ptr); 661d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return NULL; 671d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner } 681d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner void* new_ptr = realloc(ptr, size); 691d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (new_ptr == NULL) 701d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner g_panic("Can't reallocate pointer %p to %zu bytes!\n", ptr, size); 711d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 721d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return new_ptr; 731d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 741d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 751d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 761d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turnervoid g_free(void* ptr) { 771d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (ptr) 781d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner free(ptr); 791d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 801d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 811d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner// Strings. 821d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 831d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turnerchar* g_strdup(const char* str) { 841d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (str == NULL) 851d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return NULL; 861d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 871d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner size_t len = strlen(str); 881d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner char* copy = g_malloc(len + 1); 891d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner memcpy(copy, str, len + 1); 901d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return copy; 911d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 921d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 931d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 941d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turnerchar* g_strndup(const char* str, size_t size) { 951d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner const char *end = memchr(str, 0, size); 961d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner char *copy; 971d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 981d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (end) 991d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner size = end - str; 1001d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1011d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner copy = g_malloc(size + 1); 1021d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner memcpy(copy, str, size); 1031d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner copy[size] = 0; 1041d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return copy; 1051d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 1061d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1071d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1081d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turnerchar* g_strdup_printf(const char* fmt, ...) { 1091d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner char* result; 1101d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_list args; 1111d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_start(args, fmt); 1121d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner g_vasprintf(&result, fmt, args); 1131d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_end(args); 1141d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return result; 1151d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 1161d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1171d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1181d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turnerchar* g_strdup_vprintf(const char* fmt, va_list args) { 1191d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner char* result; 1201d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner g_vasprintf(&result, fmt, args); 1211d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return result; 1221d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 1231d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1241d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1251d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turnerint g_vasprintf(char** str, const char* fmt, va_list args) { 1261d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner#ifdef _WIN32 1271d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner // On Win32, vsnprintf() is broken and always returns -1 in case of truncation, 1281d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner // so make an educated guess, and try again if that fails with a larger pool. 1291d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner size_t capacity = 128; 1301d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner char* buffer = g_malloc(capacity); 1311d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner for (;;) { 1321d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_list args2; 1331d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_copy(args2, args); 1341d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner int len = vsnprintf(buffer, capacity, fmt, args2); 1351d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (len >= 0) { 1361d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner *str = buffer; 1371d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return len; 1381d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner } 1391d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_end(args2); 1401d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1411d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner capacity *= 2; 1421d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (capacity > INT_MAX) 1431d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner g_panic("Formatted string is too long!\n"); 1441d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1451d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner buffer = g_realloc(buffer, capacity); 1461d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner } 1471d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner#else 1481d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner // On other systems, vsnprintf() works properly and returns the size of the 1491d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner // formatted string without truncation. 1501d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_list args2; 1511d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_copy(args2, args); 1521d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner int len = vsnprintf(NULL, 0, fmt, args2); 1531d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_end(args2); 1541d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner if (len < 0) 1551d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner g_panic("Can't format string!\n"); 1561d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1571d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner char* result = g_malloc(len + 1); 1581d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_copy(args2, args); 1591d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner vsnprintf(result, (size_t)len, fmt, args2); 1601d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner va_end(args2); 1611d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner 1621d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner *str = result; 1631d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner return len; 1641d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner#endif 1651d1a2af599bfd91357cbc44b3cf20b1ab104f4abDavid 'Digit' Turner} 166aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 16745df61baff91503dd922964044345de5da230314David 'Digit' Turnerchar** g_strsplit(const char* string, const char* delim, int max_tokens) { 16845df61baff91503dd922964044345de5da230314David 'Digit' Turner // Sanity checks. 16945df61baff91503dd922964044345de5da230314David 'Digit' Turner if (!string || !delim || !*delim) 17045df61baff91503dd922964044345de5da230314David 'Digit' Turner return NULL; 17145df61baff91503dd922964044345de5da230314David 'Digit' Turner 17245df61baff91503dd922964044345de5da230314David 'Digit' Turner if (max_tokens < 1) 17345df61baff91503dd922964044345de5da230314David 'Digit' Turner max_tokens = INT_MAX; 17445df61baff91503dd922964044345de5da230314David 'Digit' Turner 17545df61baff91503dd922964044345de5da230314David 'Digit' Turner // Create empty list of results. 17645df61baff91503dd922964044345de5da230314David 'Digit' Turner GSList* string_list = NULL; 17745df61baff91503dd922964044345de5da230314David 'Digit' Turner guint n = 0; 17845df61baff91503dd922964044345de5da230314David 'Digit' Turner 17945df61baff91503dd922964044345de5da230314David 'Digit' Turner if (*string) { 18045df61baff91503dd922964044345de5da230314David 'Digit' Turner // Input list is not empty, so try to split it. 18145df61baff91503dd922964044345de5da230314David 'Digit' Turner const char* remainder = string; 18245df61baff91503dd922964044345de5da230314David 'Digit' Turner const char* s = strstr(remainder, delim); 18345df61baff91503dd922964044345de5da230314David 'Digit' Turner if (s) { 18445df61baff91503dd922964044345de5da230314David 'Digit' Turner size_t delim_len = strlen(delim); 18545df61baff91503dd922964044345de5da230314David 'Digit' Turner while (--max_tokens && s) { 18645df61baff91503dd922964044345de5da230314David 'Digit' Turner size_t len = s - remainder; 18745df61baff91503dd922964044345de5da230314David 'Digit' Turner string_list = g_slist_prepend(string_list, g_strndup(remainder, len)); 18845df61baff91503dd922964044345de5da230314David 'Digit' Turner n++; 18945df61baff91503dd922964044345de5da230314David 'Digit' Turner remainder = s + delim_len; 19045df61baff91503dd922964044345de5da230314David 'Digit' Turner s = strstr(remainder, delim); 19145df61baff91503dd922964044345de5da230314David 'Digit' Turner } 19245df61baff91503dd922964044345de5da230314David 'Digit' Turner } 19345df61baff91503dd922964044345de5da230314David 'Digit' Turner n++; 19445df61baff91503dd922964044345de5da230314David 'Digit' Turner string_list = g_slist_prepend(string_list, g_strdup(remainder)); 19545df61baff91503dd922964044345de5da230314David 'Digit' Turner } 19645df61baff91503dd922964044345de5da230314David 'Digit' Turner 19745df61baff91503dd922964044345de5da230314David 'Digit' Turner // Convert list into NULL-terminated vector. 19845df61baff91503dd922964044345de5da230314David 'Digit' Turner char** result = g_new(char*, n + 1); 19945df61baff91503dd922964044345de5da230314David 'Digit' Turner result[n--] = NULL; 20045df61baff91503dd922964044345de5da230314David 'Digit' Turner GSList* slist = string_list; 20145df61baff91503dd922964044345de5da230314David 'Digit' Turner while (slist) { 20245df61baff91503dd922964044345de5da230314David 'Digit' Turner result[n--] = slist->data; 20345df61baff91503dd922964044345de5da230314David 'Digit' Turner slist = slist->next; 20445df61baff91503dd922964044345de5da230314David 'Digit' Turner } 20545df61baff91503dd922964044345de5da230314David 'Digit' Turner g_slist_free(string_list); 20645df61baff91503dd922964044345de5da230314David 'Digit' Turner 20745df61baff91503dd922964044345de5da230314David 'Digit' Turner return result; 20845df61baff91503dd922964044345de5da230314David 'Digit' Turner} 20945df61baff91503dd922964044345de5da230314David 'Digit' Turner 21045df61baff91503dd922964044345de5da230314David 'Digit' Turnervoid g_strfreev(char** strings) { 21145df61baff91503dd922964044345de5da230314David 'Digit' Turner guint n; 21245df61baff91503dd922964044345de5da230314David 'Digit' Turner for (n = 0; strings[n]; ++n) { 21345df61baff91503dd922964044345de5da230314David 'Digit' Turner g_free(strings[n]); 21445df61baff91503dd922964044345de5da230314David 'Digit' Turner } 21545df61baff91503dd922964044345de5da230314David 'Digit' Turner g_free(strings); 21645df61baff91503dd922964044345de5da230314David 'Digit' Turner} 21745df61baff91503dd922964044345de5da230314David 'Digit' Turner 218ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turnergboolean g_str_equal(const void* v1, const void* v2) { 219ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner return !strcmp((const char*)v1, (const char*)v2); 220ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner} 221ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner 222ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turnerguint g_str_hash(const void* str) { 223ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner const signed char* p = str; 224ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner guint hash = 5381U; 225ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner 226ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner for (; *p; ++p) 227ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner hash = (hash << 5) + hash + (guint)*p; 228ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner 229ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner return hash; 230ad5a0ac8a11793472af654411a522270a4f1e5a1David 'Digit' Turner} 231aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 232aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner// Single-linked list 233aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 234aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turnerstatic GSList* _g_slist_alloc(void) { 235aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return (GSList*) g_malloc(sizeof(GSList)); 236aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 237aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 238aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turnervoid g_slist_free(GSList* list) { 239aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner while (list) { 240aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* next = list->next; 241aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner g_free(list); 242aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner list = next; 243aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner } 244aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 245aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 246aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' TurnerGSList* g_slist_last(GSList* list) { 247aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner while (list && list->next) 248aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner list = list->next; 249aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return list; 250aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 251aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 252aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' TurnerGSList* g_slist_find(GSList* list, const void* data) { 253aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner while (list) { 254aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner if (list->data == data) 255aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner break; 256aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner list = list->next; 257aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner } 258aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return list; 259aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 260aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 261aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' TurnerGSList* g_slist_append(GSList* list, void* data) { 262aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* new_list = _g_slist_alloc(); 263aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner new_list->data = data; 264aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner new_list->next = NULL; 265aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 266aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner if (!list) 267aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return new_list; 268aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 269aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* last = g_slist_last(list); 270aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner last->next = new_list; 271aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return list; 272aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 273aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 274aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' TurnerGSList* g_slist_prepend(GSList* list, void* data) { 275aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* new_list = _g_slist_alloc(); 276aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner new_list->data = data; 277aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner new_list->next = list; 278aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return new_list; 279aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 280aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 281aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' TurnerGSList* g_slist_remove(GSList* list, const void* data) { 282aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList** pnode = &list; 283aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner for (;;) { 284aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* node = *pnode; 285aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner if (!node) 286aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner break; 287aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner if (node->data == data) { 288aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner *pnode = node->next; 289aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner g_slist_free(node); 290aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner break; 291aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner } 292aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner pnode = &node->next; 293aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner } 294aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return list; 295aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 296aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 297aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turnervoid g_slist_foreach(GSList* list, GFunc func, void* user_data) { 298aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner while (list) { 299aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* next = list->next; 300aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner (*func)(list->data, user_data); 301aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner list = next; 302aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner } 303aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 304aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 305aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner// 306aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turnerstatic GSList* g_slist_sort_merge(GSList* l1, 307aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* l2, 308aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GFunc compare_func, 309aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner void* user_data) { 310aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* list = NULL; 311aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList** tail = &list; 312aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 313aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner while (l1 && l2) { 314aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner int cmp = ((GCompareDataFunc) compare_func)(l1->data, l2->data, user_data); 315aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner if (cmp <= 0) { 316aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner *tail = l1; 317aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner tail = &l1->next; 318aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner l1 = l1->next; 319aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner } else { 320aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner *tail = l2; 321aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner tail = &l2->next; 322aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner l2 = l2->next; 323aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner } 324aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner } 325aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner *tail = l1 ? l1 : l2; 326aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 327aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return list; 328aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 329aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 330aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turnerstatic GSList* g_slist_sort_real(GSList* list, 331aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GFunc compare_func, 332aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner void* user_data) { 333aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 334aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner if (!list) 335aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return NULL; 336aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner if (!list->next) 337aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return list; 338aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 339aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner // Split list into two halves. 340aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* l1 = list; 341aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner GSList* l2 = list->next; 342aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 343aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner while (l2->next && l2->next->next) { 344aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner l2 = l2->next->next; 345aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner l1 = l1->next; 346aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner } 347aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner l2 = l1->next; 348aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner l1->next = NULL; 349aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 350aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return g_slist_sort_merge( 351aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner g_slist_sort_real(list, compare_func, user_data), 352aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner g_slist_sort_real(l2, compare_func, user_data), 353aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner compare_func, 354aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner user_data); 355aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 356aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner 357aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' TurnerGSList* g_slist_sort(GSList* list, GCompareFunc compare_func) { 358aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner return g_slist_sort_real(list, (GFunc) compare_func, NULL); 359aadb3b585bfe9f7ddd00d8c4276db4828665a81eDavid 'Digit' Turner} 360f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 361f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// Atomic operations 362f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 363f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner#if !_WIN32 364f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// Note: Windows implementation in glib-mini-win32.c 365f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 366f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnervoid g_atomic_int_inc(int volatile* atomic) { 367f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner __sync_fetch_and_add(atomic, 1); 368f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 369f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 370f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnergboolean g_atomic_int_dec_and_test(int volatile* atomic) { 371f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return __sync_fetch_and_add(atomic, -1) == 1; 372f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 373f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner#endif // !_WIN32 374f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 375f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// Hash Tables 376f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 377f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// This is a rather vanilla implementation, slightly simpler 378f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// than the GLib one, since QEMU doesn't require the full features: 379f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// 380f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// - Uses a single dynamic array of (key,value,hash) tuples. 381f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// - Array capacity is always 2^N 382f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// - No use of modulo primes for simplicity, we don't expect 383f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// QEMU/QAPI to degenerate here. 384f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// - Dumb container only: doesn't own and free keys and values. 385f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// - No optimization for sets (i.e. when key == value for each entry). 386f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// - No iterators. 387f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// 388f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnertypedef struct { 389f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner gpointer key; 390f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner gpointer value; 391f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint hash; 392f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} GHashEntry; 393f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 394f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner#define HASH_UNUSED 0 // Must be 0, see _remove_all() below. 395f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner#define HASH_TOMBSTONE 1 396f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner#define HASH_IS_REAL(h) ((h) >= 2) 397f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 398f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner#define HASH_MIN_SHIFT 3 399f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner#define HASH_MIN_CAPACITY (1 << HASH_MIN_SHIFT) 400f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 4019f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner#define HASH_LOAD_SCALE 1024 4029f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner#define HASH_MIN_LOAD 256 4039f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner#define HASH_MAX_LOAD 768 4049f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner 405f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnerstruct _GHashTable { 406f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner int ref_count; 407f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner int num_items; 408f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner int num_used; // count of items + tombstones 409f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner int capacity; 410f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* entries; 411f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashFunc hash_func; 412f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GEqualFunc key_equal_func; 413f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner}; 414f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 4159f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner// Default hash function for pointers. 4169f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turnerstatic guint _gpointer_hash(gconstpointer key) { 4179f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner return (guint)(uintptr_t)key; 4189f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner} 4199f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner 420f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// Compute the hash value of a given key. 421f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnerstatic inline size_t 422f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner_g_hash_table_hash(GHashTable* table, gconstpointer key) { 423f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner size_t hash = table->hash_func(key); 424f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return HASH_IS_REAL(hash) ? hash : 2; 425f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 426f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 427f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 428f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' TurnerGHashTable* g_hash_table_new(GHashFunc hash_func, 429f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GEqualFunc key_equal_func) { 430f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashTable* hash_table = g_new0(GHashTable, 1); 431f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 432f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->ref_count = 1; 433f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->num_items = 0; 434f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->capacity = HASH_MIN_CAPACITY; 435f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->entries = g_new0(GHashEntry, hash_table->capacity); 4369f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner hash_table->hash_func = hash_func ? hash_func : &_gpointer_hash; 437f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->key_equal_func = key_equal_func; 438f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 439f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return hash_table; 440f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 441f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 442f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 443f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnerstatic void _g_hash_table_remove_all(GHashTable* hash_table) { 444f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner // NOTE: This uses the fact that HASH_UNUSED is 0! 445f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->num_items = 0; 446f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner memset(hash_table->entries, 447f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 0, 448f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner sizeof(hash_table->entries[0]) * hash_table->capacity); 449f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 450f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 451f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 452f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' TurnerGHashTable* g_hash_table_ref(GHashTable* hash_table) { 453f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (!hash_table) 454f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return NULL; 455f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 456f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner g_atomic_int_inc(&hash_table->ref_count); 457f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return hash_table; 458f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 459f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 460f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 461f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnervoid g_hash_table_unref(GHashTable* hash_table) { 462f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (!hash_table) 463f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return; 464f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 465f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (!g_atomic_int_dec_and_test(&hash_table->ref_count)) 466f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return; 467f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 468f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner _g_hash_table_remove_all(hash_table); 469f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 470f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner g_free(hash_table->entries); 471f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->capacity = 0; 472f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->entries = NULL; 473f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 474f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner g_free(hash_table); 475f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 476f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 477f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 478f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnervoid g_hash_table_destroy(GHashTable* hash_table) { 479f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (!hash_table) 480f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return; 481f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 482f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner _g_hash_table_remove_all(hash_table); 483f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner g_hash_table_unref(hash_table); 484f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 485f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 486f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 487f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// Probe the hash table for |key|. If it is in the table, return the index 488f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// to the corresponding entry. Otherwise, return the index of an unused 489f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// or tombstone entry. Also sets |*key_hash| to the key hash value on 490f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// return. 491f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnerstatic guint _g_hash_table_lookup_index(GHashTable* hash_table, 492f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner gconstpointer key, 493f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint* key_hash) { 494f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint hash = _g_hash_table_hash(hash_table, key); 495f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner *key_hash = hash; 496f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 497f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint probe_mask = (hash_table->capacity - 1); 498f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner gint tombstone = -1; 499f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint probe_index = hash & probe_mask; 500f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint step = 0; 501f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 502f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* probe = &hash_table->entries[probe_index]; 503f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner while (probe->hash != HASH_UNUSED) { 504f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (probe->hash == hash) { 505f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (hash_table->key_equal_func) { 506f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (hash_table->key_equal_func(probe->key, key)) 507f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return probe_index; 508f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } else if (probe->key == key) { 509f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return probe_index; 510f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 511f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } else if (probe->hash == HASH_TOMBSTONE && tombstone < 0) { 512f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner tombstone = (int)probe_index; 513f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 514f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 515f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner step++; 516f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner probe_index = (probe_index + step) & probe_mask; 517f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner probe = &hash_table->entries[probe_index]; 518f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 519f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 520f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (tombstone >= 0) 521f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return (guint)tombstone; 522f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 523f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return probe_index; 524f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 525f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 526f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 527f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnervoid* g_hash_table_lookup(GHashTable* hash_table, 528f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner const void* key) { 529f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint key_hash = HASH_UNUSED; 530f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash); 531f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* entry = &hash_table->entries[probe_index]; 532f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 533f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return HASH_IS_REAL(entry->hash) ? entry->value : NULL; 534f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 535f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 536f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 537f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// Remove key/value pair at index position |i|. 538f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnerstatic void _g_hash_table_remove_index(GHashTable* hash_table, 539f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner int i) { 540f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* entry = &hash_table->entries[i]; 541f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner entry->hash = HASH_TOMBSTONE; 542f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner entry->key = NULL; 543f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner entry->value = NULL; 544f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 545f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 546f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 547f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnergboolean g_hash_table_remove(GHashTable* hash_table, 548f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner const void* key) { 549f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint key_hash = HASH_UNUSED; 550f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint probe_index = _g_hash_table_lookup_index(hash_table, key, &key_hash); 551f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* entry = &hash_table->entries[probe_index]; 552f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (!HASH_IS_REAL(entry->hash)) 553f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return 0; 554f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 555f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner _g_hash_table_remove_index(hash_table, probe_index); 556f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->num_items--; 557f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return 1; 558f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 559f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 560f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// Resize the hash table, this also gets rid of all tombstones. 561f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnerstatic void _g_hash_table_resize(GHashTable* hash_table) { 562f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint old_capacity = hash_table->capacity; 563f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 5649f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // Compute new capacity from new size 565f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint new_size = hash_table->num_items * 2; 566f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint new_capacity = HASH_MIN_CAPACITY; 567f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner while (new_capacity < new_size) 568f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner new_capacity <<= 1; 569f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 570f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* new_entries = g_new0(GHashEntry, new_capacity); 571f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint n; 572f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner for (n = 0; n < old_capacity; ++n) { 573f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* old_entry = &hash_table->entries[n]; 574f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint old_hash = old_entry->hash; 575f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 576f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (!HASH_IS_REAL(old_hash)) 577f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner continue; 578f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 579f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint probe_mask = (new_capacity - 1); 580f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint probe_n = old_hash & probe_mask; 581f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* probe = &new_entries[probe_n]; 582f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint step = 0; 583f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner while (probe->hash != HASH_UNUSED) { 584f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner step++; 585f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner probe_n = (probe_n + step) & probe_mask; 586f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner probe = &new_entries[probe_n]; 587f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 588f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner probe[0] = old_entry[0]; 589f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 590f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 591f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner g_free(hash_table->entries); 592f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->entries = new_entries; 593f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->capacity = new_capacity; 594f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->num_used = hash_table->num_items; 595f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 596f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 597f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner// Resize the hash table if needed. 598f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnerstatic void _g_hash_table_maybe_resize(GHashTable* hash_table) { 599f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint count = hash_table->num_items; 600f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint capacity = hash_table->capacity; 6019f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // Computations explained. 6029f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // 6039f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // load < min_load i.e. 6049f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // => used / capacity < min_load 6059f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // => used < min_load * capacity 6069f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // => used * HASH_SCALE < HASH_MIN_LOAD * capacity 6079f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // 6089f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // load > max_load 6099f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // => used / capacity > max_load 6109f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner // => used * HASH_SCALER > HASH_MAX_LOAD * capacity 6119f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner uint64_t load = (uint64_t)count * HASH_LOAD_SCALE; 6129f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner uint64_t min_load = (uint64_t)capacity * HASH_MIN_LOAD; 6139f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner uint64_t max_load = (uint64_t)capacity * HASH_MAX_LOAD; 6149f10420e1f874a07556f0fe0b57edfff704ecae3David 'Digit' Turner if (load < min_load || load > max_load) { 615f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner _g_hash_table_resize(hash_table); 616f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 617f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 618f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 619f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnerstatic void _g_hash_table_insert_index(GHashTable* hash_table, 620f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint key_index, 621f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint new_key_hash, 622f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner gpointer new_key, 623f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner gpointer new_value) { 624f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* entry = &hash_table->entries[key_index]; 625f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint old_hash = entry->hash; 626f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 627f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner entry->key = new_key; 628f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner entry->value = new_value; 629f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner entry->hash = new_key_hash; 630f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 631f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (HASH_IS_REAL(old_hash)) { 632f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner // Simple replacement, exit immediately. 633f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return; 634f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 635f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 636f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->num_items++; 637f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (old_hash == HASH_TOMBSTONE) { 638f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner // No need to resize when replacing a tombstone. 639f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return; 640f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 641f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 642f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner hash_table->num_used++; 643f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner _g_hash_table_maybe_resize(hash_table); 644f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 645f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 646f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnervoid g_hash_table_insert(GHashTable* hash_table, 647f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner void* key, 648f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner void* value) { 649f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint key_hash; 650f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint key_index = 651f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner _g_hash_table_lookup_index(hash_table, key, &key_hash); 652f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 653f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner _g_hash_table_insert_index(hash_table, key_index, key_hash, key, value); 654f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 655f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 656f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 657f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnervoid g_hash_table_foreach(GHashTable* hash_table, 658f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHFunc func, 659f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner gpointer user_data) { 660f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint n; 661f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner for (n = 0; n < hash_table->capacity; ++n) { 662f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* entry = &hash_table->entries[n]; 663f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (HASH_IS_REAL(entry->hash)) 664f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner (*func)(entry->key, entry->value, user_data); 665f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 666f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 667f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 668f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 669f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnergpointer g_hash_table_find(GHashTable* hash_table, 670f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHRFunc predicate, 671f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner gpointer user_data) { 672f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner guint n; 673f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner for (n = 0; n < hash_table->capacity; ++n) { 674f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner GHashEntry* entry = &hash_table->entries[n]; 675f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner if (HASH_IS_REAL(entry->hash) && 676f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner (*predicate)(entry->key, entry->value, user_data)) { 677f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return entry->value; 678f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 679f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner } 680f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return NULL; 681f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 682f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 683f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner 684f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turnerguint g_hash_table_size(GHashTable* hash_table) { 685f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner return hash_table->num_items; 686f3f3c9b864a902e10cefb0e666f2354672352fcaDavid 'Digit' Turner} 6879069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 6889069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner// Queues 6899069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 6909069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turnerstruct _GQueueNode { 6919069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner void* data; 6929069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner GQueueNode* next; 6939069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner GQueueNode* prev; 6949069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner}; 6959069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 6969069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turnerstatic inline GQueueNode* _g_queue_node_alloc(void) { 6979069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner return g_new0(GQueueNode, 1); 6989069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner} 6999069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7009069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turnerstatic void inline _g_queue_node_free(GQueueNode* node) { 7019069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner g_free(node); 7029069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner} 7039069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7049069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' TurnerGQueue* g_queue_new(void) { 7059069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner GQueue* queue = g_new0(GQueue, 1); 7069069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner return queue; 7079069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner} 7089069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7099069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turnervoid g_queue_free(GQueue* queue) { 7109069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner GQueueNode* node = queue->head; 7119069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner while (node) { 7129069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner GQueueNode* next = node->next; 7139069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner _g_queue_node_free(node); 7149069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner node = next; 7159069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner } 7169069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner queue->head = queue->tail = NULL; 7179069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner queue->length = 0; 7189069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner g_free(queue); 7199069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner} 7209069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7219069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turnergboolean g_queue_is_empty(GQueue* queue) { 7229069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner return queue->head == NULL; 7239069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner} 7249069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7259069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turnervoid g_queue_push_tail(GQueue* queue, void* data) { 7269069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner GQueueNode* node = _g_queue_node_alloc(); 7279069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner node->data = data; 7289069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner node->next = NULL; 7299069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner node->prev = queue->tail; 7309069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner queue->tail = node; 7319069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner queue->length++; 7329069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner} 7339069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7349069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turnervoid* g_queue_peek_head(GQueue* queue) { 7359069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner return (queue->head) ? queue->head->data : NULL; 7369069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner} 7379069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7389069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turnervoid* g_queue_peek_tail(GQueue* queue) { 7399069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner return (queue->tail) ? queue->tail->data : NULL; 7409069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner} 7419069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7429069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turnervoid* g_queue_pop_head(GQueue* queue) { 7439069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner GQueueNode* head = queue->head; 7449069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner if (!head) 7459069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner return NULL; 7469069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7479069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner void* result = head->data; 7489069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7499069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner if (head->next) { 7509069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner queue->head = head->next; 7519069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner head->next->prev = NULL; 7529069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner } else { 7539069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner queue->head = NULL; 7549069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner queue->tail = NULL; 7559069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner } 7569069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner queue->length--; 7579069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner 7589069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner return result; 7599069fab3c26d972318fe75192f8194294451ccbcDavid 'Digit' Turner} 760