diff options
Diffstat (limited to 'mesalib/src/util')
| -rw-r--r-- | mesalib/src/util/.gitignore | 1 | ||||
| -rw-r--r-- | mesalib/src/util/Makefile.am | 41 | ||||
| -rw-r--r-- | mesalib/src/util/Makefile.sources | 6 | ||||
| -rw-r--r-- | mesalib/src/util/SConscript | 35 | ||||
| -rw-r--r-- | mesalib/src/util/format_srgb.h | 149 | ||||
| -rw-r--r-- | mesalib/src/util/format_srgb.py | 155 | ||||
| -rw-r--r-- | mesalib/src/util/hash_table.c | 440 | ||||
| -rw-r--r-- | mesalib/src/util/hash_table.h | 107 | ||||
| -rw-r--r-- | mesalib/src/util/macros.h | 128 | ||||
| -rw-r--r-- | mesalib/src/util/ralloc.c | 492 | ||||
| -rw-r--r-- | mesalib/src/util/ralloc.h | 445 |
11 files changed, 1999 insertions, 0 deletions
diff --git a/mesalib/src/util/.gitignore b/mesalib/src/util/.gitignore new file mode 100644 index 000000000..e945ecbb5 --- /dev/null +++ b/mesalib/src/util/.gitignore @@ -0,0 +1 @@ +format_srgb.c diff --git a/mesalib/src/util/Makefile.am b/mesalib/src/util/Makefile.am new file mode 100644 index 000000000..4733a1a74 --- /dev/null +++ b/mesalib/src/util/Makefile.am @@ -0,0 +1,41 @@ +# Copyright © 2014 Intel Corporation +# +# Permission is hereby granted, free of charge, to any person obtaining a +# copy of this software and associated documentation files (the "Software"), +# to deal in the Software without restriction, including without limitation +# the rights to use, copy, modify, merge, publish, distribute, sublicense, +# and/or sell copies of the Software, and to permit persons to whom the +# Software is furnished to do so, subject to the following conditions: +# +# The above copyright notice and this permission notice (including the next +# paragraph) shall be included in all copies or substantial portions of the +# Software. +# +# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL +# THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING +# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS +# IN THE SOFTWARE. + +SUBDIRS = . tests/hash_table + +include Makefile.sources + +noinst_LTLIBRARIES = libmesautil.la + +libmesautil_la_CPPFLAGS = \ + $(DEFINES) \ + -I$(top_srcdir)/include \ + $(VISIBILITY_CFLAGS) + +libmesautil_la_SOURCES = \ + $(MESA_UTIL_FILES) \ + $(MESA_UTIL_GENERATED_FILES) + +BUILT_SOURCES = $(MESA_UTIL_GENERATED_FILES) +CLEANFILES = $(BUILT_SOURCES) + +format_srgb.c: $(srcdir)/format_srgb.py + $(AM_V_GEN) $(PYTHON2) $< > $@ diff --git a/mesalib/src/util/Makefile.sources b/mesalib/src/util/Makefile.sources new file mode 100644 index 000000000..b99aa25e8 --- /dev/null +++ b/mesalib/src/util/Makefile.sources @@ -0,0 +1,6 @@ +MESA_UTIL_FILES := \ + hash_table.c \ + ralloc.c + +MESA_UTIL_GENERATED_FILES = \ + format_srgb.c diff --git a/mesalib/src/util/SConscript b/mesalib/src/util/SConscript new file mode 100644 index 000000000..84803c016 --- /dev/null +++ b/mesalib/src/util/SConscript @@ -0,0 +1,35 @@ +import common + +Import('*') + +from sys import executable as python_cmd + +env = env.Clone() + +env.Prepend(CPPPATH = [ + '#include', + '#src/util', +]) + +env.CodeGenerate( + target = 'format_srgb.c', + script = 'format_srgb.py', + source = [], + command = python_cmd + ' $SCRIPT > $TARGET' +) + +# parse Makefile.sources +source_lists = env.ParseSourceList('Makefile.sources') + +mesautil_sources = ( + source_lists['MESA_UTIL_FILES'] + + source_lists['MESA_UTIL_GENERATED_FILES'] +) + +mesautil = env.ConvenienceLibrary( + target = 'mesautil', + source = mesautil_sources, +) + +env.Alias('mesautil', mesautil) +Export('mesautil') diff --git a/mesalib/src/util/format_srgb.h b/mesalib/src/util/format_srgb.h new file mode 100644 index 000000000..4a8d73f12 --- /dev/null +++ b/mesalib/src/util/format_srgb.h @@ -0,0 +1,149 @@ +/************************************************************************** + * + * Copyright 2010 VMware, Inc. + * All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sub license, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL + * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + * + * The above copyright notice and this permission notice (including the + * next paragraph) shall be included in all copies or substantial portions + * of the Software. + * + **************************************************************************/ + +/** + * @file + * SRGB translation. + * + * @author Brian Paul <brianp@vmware.com> + * @author Michal Krol <michal@vmware.com> + * @author Jose Fonseca <jfonseca@vmware.com> + */ + +#ifndef U_FORMAT_SRGB_H_ +#define U_FORMAT_SRGB_H_ + +#include <stdint.h> +#include <math.h> +#include "c99_compat.h" + +extern const float +util_format_srgb_8unorm_to_linear_float_table[256]; + +extern const uint8_t +util_format_srgb_to_linear_8unorm_table[256]; + +extern const uint8_t +util_format_linear_to_srgb_8unorm_table[256]; + +extern const unsigned +util_format_linear_to_srgb_helper_table[104]; + + +static inline float +util_format_linear_to_srgb_float(float cl) +{ + if (cl < 0.0f) + return 0.0f; + else if (cl < 0.0031308f) + return 12.92f * cl; + else if (cl < 1.0f) + return 1.055f * powf(cl, 0.41666f) - 0.055f; + else + return 1.0f; +} + + +/** + * Convert a unclamped linear float to srgb value in the [0,255]. + */ +static inline uint8_t +util_format_linear_float_to_srgb_8unorm(float x) +{ + /* + * This is taken from https://gist.github.com/rygorous/2203834 + * Use LUT and do linear interpolation. + */ + union { + uint32_t ui; + float f; + } almostone, minval, f; + unsigned tab, bias, scale, t; + + almostone.ui = 0x3f7fffff; + minval.ui = (127-13) << 23; + + /* + * Clamp to [2^(-13), 1-eps]; these two values map to 0 and 1, respectively. + * The tests are carefully written so that NaNs map to 0, same as in the + * reference implementation. + */ + if (!(x > minval.f)) + x = minval.f; + if (x > almostone.f) + x = almostone.f; + + /* Do the table lookup and unpack bias, scale */ + f.f = x; + tab = util_format_linear_to_srgb_helper_table[(f.ui - minval.ui) >> 20]; + bias = (tab >> 16) << 9; + scale = tab & 0xffff; + + /* Grab next-highest mantissa bits and perform linear interpolation */ + t = (f.ui >> 12) & 0xff; + return (uint8_t) ((bias + scale*t) >> 16); +} + + +/** + * Convert an 8-bit sRGB value from non-linear space to a + * linear RGB value in [0, 1]. + * Implemented with a 256-entry lookup table. + */ +static inline float +util_format_srgb_8unorm_to_linear_float(uint8_t x) +{ + return util_format_srgb_8unorm_to_linear_float_table[x]; +} + + +/* + * XXX These 2 functions probably don't make a lot of sense (but lots + * of potential callers which most likely all don't make sense neither) + */ + +/** + * Convert a 8bit normalized value from linear to srgb. + */ +static inline uint8_t +util_format_linear_to_srgb_8unorm(uint8_t x) +{ + return util_format_linear_to_srgb_8unorm_table[x]; +} + + +/** + * Convert a 8bit normalized value from srgb to linear. + */ +static inline uint8_t +util_format_srgb_to_linear_8unorm(uint8_t x) +{ + return util_format_srgb_to_linear_8unorm_table[x]; +} + + +#endif /* U_FORMAT_SRGB_H_ */ diff --git a/mesalib/src/util/format_srgb.py b/mesalib/src/util/format_srgb.py new file mode 100644 index 000000000..d5cbcf764 --- /dev/null +++ b/mesalib/src/util/format_srgb.py @@ -0,0 +1,155 @@ +#!/usr/bin/env python + +CopyRight = ''' +/************************************************************************** + * + * Copyright 2010 VMware, Inc. + * All Rights Reserved. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sub license, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice (including the + * next paragraph) shall be included in all copies or substantial portions + * of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. + * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR + * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, + * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE + * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + * + **************************************************************************/ + +/** + * @file + * SRGB translation. + * + * @author Brian Paul <brianp@vmware.com> + * @author Michal Krol <michal@vmware.com> + * @author Jose Fonseca <jfonseca@vmware.com> + */ +''' + + +import math +import struct + + +def srgb_to_linear(x): + if x <= 0.04045: + return x / 12.92 + else: + return math.pow((x + 0.055) / 1.055, 2.4) + + +def linear_to_srgb(x): + if x >= 0.0031308: + return 1.055 * math.pow(x, 0.41666666) - 0.055 + else: + return 12.92 * x + + +def generate_srgb_tables(): + print 'const float' + print 'util_format_srgb_8unorm_to_linear_float_table[256] = {' + for j in range(0, 256, 4): + print ' ', + for i in range(j, j + 4): + print '%.7e,' % (srgb_to_linear(i / 255.0),), + print + print '};' + print + print 'const uint8_t' + print 'util_format_srgb_to_linear_8unorm_table[256] = {' + for j in range(0, 256, 16): + print ' ', + for i in range(j, j + 16): + print '%3u,' % (int(srgb_to_linear(i / 255.0) * 255.0 + 0.5),), + print + print '};' + print + print 'const uint8_t' + print 'util_format_linear_to_srgb_8unorm_table[256] = {' + for j in range(0, 256, 16): + print ' ', + for i in range(j, j + 16): + print '%3u,' % (int(linear_to_srgb(i / 255.0) * 255.0 + 0.5),), + print + print '};' + print + +# calculate the table interpolation values used in float linear to unorm8 srgb + numexp = 13 + mantissa_msb = 3 +# stepshift is just used to only use every x-th float to make things faster, +# 5 is largest value which still gives exact same table as 0 + stepshift = 5 + nbuckets = numexp << mantissa_msb + bucketsize = (1 << (23 - mantissa_msb)) >> stepshift + mantshift = 12 + valtable = [] + sum_aa = float(bucketsize) + sum_ab = 0.0 + sum_bb = 0.0 + for i in range(0, bucketsize): + j = (i << stepshift) >> mantshift + sum_ab += j + sum_bb += j*j + inv_det = 1.0 / (sum_aa * sum_bb - sum_ab * sum_ab) + + for bucket in range(0, nbuckets): + start = ((127 - numexp) << 23) + bucket*(bucketsize << stepshift) + sum_a = 0.0 + sum_b = 0.0 + + for i in range(0, bucketsize): + j = (i << stepshift) >> mantshift + fint = start + (i << stepshift) + ffloat = struct.unpack('f', struct.pack('I', fint))[0] + val = linear_to_srgb(ffloat) * 255.0 + 0.5 + sum_a += val + sum_b += j*val + + solved_a = inv_det * (sum_bb*sum_a - sum_ab*sum_b) + solved_b = inv_det * (sum_aa*sum_b - sum_ab*sum_a) + + scaled_a = solved_a * 65536.0 / 512.0 + scaled_b = solved_b * 65536.0 + + int_a = int(scaled_a + 0.5) + int_b = int(scaled_b + 0.5) + + valtable.append((int_a << 16) + int_b) + + print 'const unsigned' + print 'util_format_linear_to_srgb_helper_table[104] = {' + + for j in range(0, nbuckets, 4): + print ' ', + for i in range(j, j + 4): + print '0x%08x,' % (valtable[i],), + print + print '};' + print + +def main(): + print '/* This file is autogenerated by u_format_srgb.py. Do not edit directly. */' + print + # This will print the copyright message on the top of this file + print CopyRight.strip() + print + print '#include "format_srgb.h"' + print + generate_srgb_tables() + + +if __name__ == '__main__': + main() diff --git a/mesalib/src/util/hash_table.c b/mesalib/src/util/hash_table.c new file mode 100644 index 000000000..1b6726c79 --- /dev/null +++ b/mesalib/src/util/hash_table.c @@ -0,0 +1,440 @@ +/* + * Copyright © 2009,2012 Intel Corporation + * Copyright © 1988-2004 Keith Packard and Bart Massey. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Except as contained in this notice, the names of the authors + * or their institutions shall not be used in advertising or + * otherwise to promote the sale, use or other dealings in this + * Software without prior written authorization from the + * authors. + * + * Authors: + * Eric Anholt <eric@anholt.net> + * Keith Packard <keithp@keithp.com> + */ + +/** + * Implements an open-addressing, linear-reprobing hash table. + * + * For more information, see: + * + * http://cgit.freedesktop.org/~anholt/hash_table/tree/README + */ + +#include <stdlib.h> +#include <string.h> + +#include "hash_table.h" +#include "ralloc.h" +#include "macros.h" + +static const uint32_t deleted_key_value; + +/** + * From Knuth -- a good choice for hash/rehash values is p, p-2 where + * p and p-2 are both prime. These tables are sized to have an extra 10% + * free to avoid exponential performance degradation as the hash table fills + */ +static const struct { + uint32_t max_entries, size, rehash; +} hash_sizes[] = { + { 2, 5, 3 }, + { 4, 7, 5 }, + { 8, 13, 11 }, + { 16, 19, 17 }, + { 32, 43, 41 }, + { 64, 73, 71 }, + { 128, 151, 149 }, + { 256, 283, 281 }, + { 512, 571, 569 }, + { 1024, 1153, 1151 }, + { 2048, 2269, 2267 }, + { 4096, 4519, 4517 }, + { 8192, 9013, 9011 }, + { 16384, 18043, 18041 }, + { 32768, 36109, 36107 }, + { 65536, 72091, 72089 }, + { 131072, 144409, 144407 }, + { 262144, 288361, 288359 }, + { 524288, 576883, 576881 }, + { 1048576, 1153459, 1153457 }, + { 2097152, 2307163, 2307161 }, + { 4194304, 4613893, 4613891 }, + { 8388608, 9227641, 9227639 }, + { 16777216, 18455029, 18455027 }, + { 33554432, 36911011, 36911009 }, + { 67108864, 73819861, 73819859 }, + { 134217728, 147639589, 147639587 }, + { 268435456, 295279081, 295279079 }, + { 536870912, 590559793, 590559791 }, + { 1073741824, 1181116273, 1181116271}, + { 2147483648ul, 2362232233ul, 2362232231ul} +}; + +static int +entry_is_free(const struct hash_entry *entry) +{ + return entry->key == NULL; +} + +static int +entry_is_deleted(const struct hash_table *ht, struct hash_entry *entry) +{ + return entry->key == ht->deleted_key; +} + +static int +entry_is_present(const struct hash_table *ht, struct hash_entry *entry) +{ + return entry->key != NULL && entry->key != ht->deleted_key; +} + +struct hash_table * +_mesa_hash_table_create(void *mem_ctx, + bool (*key_equals_function)(const void *a, + const void *b)) +{ + struct hash_table *ht; + + ht = ralloc(mem_ctx, struct hash_table); + if (ht == NULL) + return NULL; + + ht->size_index = 0; + ht->size = hash_sizes[ht->size_index].size; + ht->rehash = hash_sizes[ht->size_index].rehash; + ht->max_entries = hash_sizes[ht->size_index].max_entries; + ht->key_equals_function = key_equals_function; + ht->table = rzalloc_array(ht, struct hash_entry, ht->size); + ht->entries = 0; + ht->deleted_entries = 0; + ht->deleted_key = &deleted_key_value; + + if (ht->table == NULL) { + ralloc_free(ht); + return NULL; + } + + return ht; +} + +/** + * Frees the given hash table. + * + * If delete_function is passed, it gets called on each entry present before + * freeing. + */ +void +_mesa_hash_table_destroy(struct hash_table *ht, + void (*delete_function)(struct hash_entry *entry)) +{ + if (!ht) + return; + + if (delete_function) { + struct hash_entry *entry; + + hash_table_foreach(ht, entry) { + delete_function(entry); + } + } + ralloc_free(ht); +} + +/** Sets the value of the key pointer used for deleted entries in the table. + * + * The assumption is that usually keys are actual pointers, so we use a + * default value of a pointer to an arbitrary piece of storage in the library. + * But in some cases a consumer wants to store some other sort of value in the + * table, like a uint32_t, in which case that pointer may conflict with one of + * their valid keys. This lets that user select a safe value. + * + * This must be called before any keys are actually deleted from the table. + */ +void +_mesa_hash_table_set_deleted_key(struct hash_table *ht, const void *deleted_key) +{ + ht->deleted_key = deleted_key; +} + +/** + * Finds a hash table entry with the given key and hash of that key. + * + * Returns NULL if no entry is found. Note that the data pointer may be + * modified by the user. + */ +struct hash_entry * +_mesa_hash_table_search(struct hash_table *ht, uint32_t hash, + const void *key) +{ + uint32_t start_hash_address = hash % ht->size; + uint32_t hash_address = start_hash_address; + + do { + uint32_t double_hash; + + struct hash_entry *entry = ht->table + hash_address; + + if (entry_is_free(entry)) { + return NULL; + } else if (entry_is_present(ht, entry) && entry->hash == hash) { + if (ht->key_equals_function(key, entry->key)) { + return entry; + } + } + + double_hash = 1 + hash % ht->rehash; + + hash_address = (hash_address + double_hash) % ht->size; + } while (hash_address != start_hash_address); + + return NULL; +} + +static void +_mesa_hash_table_rehash(struct hash_table *ht, int new_size_index) +{ + struct hash_table old_ht; + struct hash_entry *table, *entry; + + if (new_size_index >= ARRAY_SIZE(hash_sizes)) + return; + + table = rzalloc_array(ht, struct hash_entry, + hash_sizes[new_size_index].size); + if (table == NULL) + return; + + old_ht = *ht; + + ht->table = table; + ht->size_index = new_size_index; + ht->size = hash_sizes[ht->size_index].size; + ht->rehash = hash_sizes[ht->size_index].rehash; + ht->max_entries = hash_sizes[ht->size_index].max_entries; + ht->entries = 0; + ht->deleted_entries = 0; + + hash_table_foreach(&old_ht, entry) { + _mesa_hash_table_insert(ht, entry->hash, + entry->key, entry->data); + } + + ralloc_free(old_ht.table); +} + +/** + * Inserts the key with the given hash into the table. + * + * Note that insertion may rearrange the table on a resize or rehash, + * so previously found hash_entries are no longer valid after this function. + */ +struct hash_entry * +_mesa_hash_table_insert(struct hash_table *ht, uint32_t hash, + const void *key, void *data) +{ + uint32_t start_hash_address, hash_address; + + if (ht->entries >= ht->max_entries) { + _mesa_hash_table_rehash(ht, ht->size_index + 1); + } else if (ht->deleted_entries + ht->entries >= ht->max_entries) { + _mesa_hash_table_rehash(ht, ht->size_index); + } + + start_hash_address = hash % ht->size; + hash_address = start_hash_address; + do { + struct hash_entry *entry = ht->table + hash_address; + uint32_t double_hash; + + if (!entry_is_present(ht, entry)) { + if (entry_is_deleted(ht, entry)) + ht->deleted_entries--; + entry->hash = hash; + entry->key = key; + entry->data = data; + ht->entries++; + return entry; + } + + /* Implement replacement when another insert happens + * with a matching key. This is a relatively common + * feature of hash tables, with the alternative + * generally being "insert the new value as well, and + * return it first when the key is searched for". + * + * Note that the hash table doesn't have a delete + * callback. If freeing of old data pointers is + * required to avoid memory leaks, perform a search + * before inserting. + */ + if (entry->hash == hash && + ht->key_equals_function(key, entry->key)) { + entry->key = key; + entry->data = data; + return entry; + } + + + double_hash = 1 + hash % ht->rehash; + + hash_address = (hash_address + double_hash) % ht->size; + } while (hash_address != start_hash_address); + + /* We could hit here if a required resize failed. An unchecked-malloc + * application could ignore this result. + */ + return NULL; +} + +/** + * This function deletes the given hash table entry. + * + * Note that deletion doesn't otherwise modify the table, so an iteration over + * the table deleting entries is safe. + */ +void +_mesa_hash_table_remove(struct hash_table *ht, + struct hash_entry *entry) +{ + if (!entry) + return; + + entry->key = ht->deleted_key; + ht->entries--; + ht->deleted_entries++; +} + +/** + * This function is an iterator over the hash table. + * + * Pass in NULL for the first entry, as in the start of a for loop. Note that + * an iteration over the table is O(table_size) not O(entries). + */ +struct hash_entry * +_mesa_hash_table_next_entry(struct hash_table *ht, + struct hash_entry *entry) +{ + if (entry == NULL) + entry = ht->table; + else + entry = entry + 1; + + for (; entry != ht->table + ht->size; entry++) { + if (entry_is_present(ht, entry)) { + return entry; + } + } + + return NULL; +} + +/** + * Returns a random entry from the hash table. + * + * This may be useful in implementing random replacement (as opposed + * to just removing everything) in caches based on this hash table + * implementation. @predicate may be used to filter entries, or may + * be set to NULL for no filtering. + */ +struct hash_entry * +_mesa_hash_table_random_entry(struct hash_table *ht, + bool (*predicate)(struct hash_entry *entry)) +{ + struct hash_entry *entry; + uint32_t i = rand() % ht->size; + + if (ht->entries == 0) + return NULL; + + for (entry = ht->table + i; entry != ht->table + ht->size; entry++) { + if (entry_is_present(ht, entry) && + (!predicate || predicate(entry))) { + return entry; + } + } + + for (entry = ht->table; entry != ht->table + i; entry++) { + if (entry_is_present(ht, entry) && + (!predicate || predicate(entry))) { + return entry; + } + } + + return NULL; +} + + +/** + * Quick FNV-1 hash implementation based on: + * http://www.isthe.com/chongo/tech/comp/fnv/ + * + * FNV-1 is not be the best hash out there -- Jenkins's lookup3 is supposed to + * be quite good, and it probably beats FNV. But FNV has the advantage that + * it involves almost no code. For an improvement on both, see Paul + * Hsieh's http://www.azillionmonkeys.com/qed/hash.html + */ +uint32_t +_mesa_hash_data(const void *data, size_t size) +{ + uint32_t hash = 2166136261ul; + const uint8_t *bytes = data; + + while (size-- != 0) { + hash ^= *bytes; + hash = hash * 0x01000193; + bytes++; + } + + return hash; +} + +/** FNV-1 string hash implementation */ +uint32_t +_mesa_hash_string(const char *key) +{ + uint32_t hash = 2166136261ul; + + while (*key != 0) { + hash ^= *key; + hash = hash * 0x01000193; + key++; + } + + return hash; +} + +/** + * String compare function for use as the comparison callback in + * _mesa_hash_table_create(). + */ +bool +_mesa_key_string_equal(const void *a, const void *b) +{ + return strcmp(a, b) == 0; +} + +bool +_mesa_key_pointer_equal(const void *a, const void *b) +{ + return a == b; +} diff --git a/mesalib/src/util/hash_table.h b/mesalib/src/util/hash_table.h new file mode 100644 index 000000000..d6b6ebf40 --- /dev/null +++ b/mesalib/src/util/hash_table.h @@ -0,0 +1,107 @@ +/* + * Copyright © 2009,2012 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + * + * Authors: + * Eric Anholt <eric@anholt.net> + * + */ + +#ifndef _HASH_TABLE_H +#define _HASH_TABLE_H + +#include <stdlib.h> +#include <inttypes.h> +#include <stdbool.h> +#include "c99_compat.h" +#include "macros.h" + +#ifdef __cplusplus +extern "C" { +#endif + +struct hash_entry { + uint32_t hash; + const void *key; + void *data; +}; + +struct hash_table { + struct hash_entry *table; + bool (*key_equals_function)(const void *a, const void *b); + const void *deleted_key; + uint32_t size; + uint32_t rehash; + uint32_t max_entries; + uint32_t size_index; + uint32_t entries; + uint32_t deleted_entries; +}; + +struct hash_table * +_mesa_hash_table_create(void *mem_ctx, + bool (*key_equals_function)(const void *a, + const void *b)); +void _mesa_hash_table_destroy(struct hash_table *ht, + void (*delete_function)(struct hash_entry *entry)); +void _mesa_hash_table_set_deleted_key(struct hash_table *ht, + const void *deleted_key); + +struct hash_entry * +_mesa_hash_table_insert(struct hash_table *ht, uint32_t hash, + const void *key, void *data); +struct hash_entry * +_mesa_hash_table_search(struct hash_table *ht, uint32_t hash, + const void *key); +void _mesa_hash_table_remove(struct hash_table *ht, + struct hash_entry *entry); + +struct hash_entry *_mesa_hash_table_next_entry(struct hash_table *ht, + struct hash_entry *entry); +struct hash_entry * +_mesa_hash_table_random_entry(struct hash_table *ht, + bool (*predicate)(struct hash_entry *entry)); + +uint32_t _mesa_hash_data(const void *data, size_t size); +uint32_t _mesa_hash_string(const char *key); +bool _mesa_key_string_equal(const void *a, const void *b); +bool _mesa_key_pointer_equal(const void *a, const void *b); + +static inline uint32_t _mesa_hash_pointer(const void *pointer) +{ + return _mesa_hash_data(&pointer, sizeof(pointer)); +} + +/** + * This foreach function is safe against deletion (which just replaces + * an entry's data with the deleted marker), but not against insertion + * (which may rehash the table, making entry a dangling pointer). + */ +#define hash_table_foreach(ht, entry) \ + for (entry = _mesa_hash_table_next_entry(ht, NULL); \ + entry != NULL; \ + entry = _mesa_hash_table_next_entry(ht, entry)) + +#ifdef __cplusplus +} /* extern C */ +#endif + +#endif /* _HASH_TABLE_H */ diff --git a/mesalib/src/util/macros.h b/mesalib/src/util/macros.h new file mode 100644 index 000000000..ee05e05a4 --- /dev/null +++ b/mesalib/src/util/macros.h @@ -0,0 +1,128 @@ +/* + * Copyright © 2014 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#ifndef UTIL_MACROS_H +#define UTIL_MACROS_H + +/* Compute the size of an array */ +#ifndef ARRAY_SIZE +# define ARRAY_SIZE(x) (sizeof(x) / sizeof(*(x))) +#endif + + +/** + * __builtin_expect macros + */ +#if !defined(__GNUC__) +# define __builtin_expect(x, y) (x) +#endif + +#ifndef likely +# ifdef __GNUC__ +# define likely(x) __builtin_expect(!!(x), 1) +# define unlikely(x) __builtin_expect(!!(x), 0) +# else +# define likely(x) (x) +# define unlikely(x) (x) +# endif +#endif + + +/** + * Static (compile-time) assertion. + * Basically, use COND to dimension an array. If COND is false/zero the + * array size will be -1 and we'll get a compilation error. + */ +#define STATIC_ASSERT(COND) \ + do { \ + (void) sizeof(char [1 - 2*!(COND)]); \ + } while (0) + + +/** + * Unreachable macro. Useful for suppressing "control reaches end of non-void + * function" warnings. + */ +#if __GNUC__ >= 4 && __GNUC_MINOR__ >= 5 +#define unreachable(str) \ +do { \ + assert(!str); \ + __builtin_unreachable(); \ +} while (0) +#elif (defined(__clang__) && defined(__has_builtin)) +# if __has_builtin(__builtin_unreachable) +# define unreachable(str) \ +do { \ + assert(!str); \ + __builtin_unreachable(); \ +} while (0) +# endif +#endif + +#ifndef unreachable +#define unreachable(str) +#endif + + +#if (__GNUC__ >= 3) +#define PRINTFLIKE(f, a) __attribute__ ((format(__printf__, f, a))) +#else +#define PRINTFLIKE(f, a) +#endif + + +/* Used to optionally mark structures with misaligned elements or size as + * packed, to trade off performance for space. + */ +#if (__GNUC__ >= 3) +#define PACKED __attribute__((__packed__)) +#else +#define PACKED +#endif + + +#ifdef __cplusplus +/** + * Macro function that evaluates to true if T is a trivially + * destructible type -- that is, if its (non-virtual) destructor + * performs no action and all member variables and base classes are + * trivially destructible themselves. + */ +# if defined(__GNUC__) +# if ((__GNUC__ > 4) || ((__GNUC__ == 4) && (__GNUC_MINOR__ >= 3))) +# define HAS_TRIVIAL_DESTRUCTOR(T) __has_trivial_destructor(T) +# endif +# elif (defined(__clang__) && defined(__has_feature)) +# if __has_feature(has_trivial_destructor) +# define HAS_TRIVIAL_DESTRUCTOR(T) __has_trivial_destructor(T) +# endif +# endif +# ifndef HAS_TRIVIAL_DESTRUCTOR + /* It's always safe (if inefficient) to assume that a + * destructor is non-trivial. + */ +# define HAS_TRIVIAL_DESTRUCTOR(T) (false) +# endif +#endif + +#endif /* UTIL_MACROS_H */ diff --git a/mesalib/src/util/ralloc.c b/mesalib/src/util/ralloc.c new file mode 100644 index 000000000..36bc61fd0 --- /dev/null +++ b/mesalib/src/util/ralloc.c @@ -0,0 +1,492 @@ +/* + * Copyright © 2010 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#include <assert.h> +#include <stdlib.h> +#include <stdarg.h> +#include <stdio.h> +#include <string.h> +#include <stdint.h> + +/* Android defines SIZE_MAX in limits.h, instead of the standard stdint.h */ +#ifdef ANDROID +#include <limits.h> +#endif + +/* Some versions of MinGW are missing _vscprintf's declaration, although they + * still provide the symbol in the import library. */ +#ifdef __MINGW32__ +_CRTIMP int _vscprintf(const char *format, va_list argptr); +#endif + +#include "ralloc.h" + +#ifndef va_copy +#ifdef __va_copy +#define va_copy(dest, src) __va_copy((dest), (src)) +#else +#define va_copy(dest, src) (dest) = (src) +#endif +#endif + +#define CANARY 0x5A1106 + +struct ralloc_header +{ +#ifdef DEBUG + /* A canary value used to determine whether a pointer is ralloc'd. */ + unsigned canary; +#endif + + struct ralloc_header *parent; + + /* The first child (head of a linked list) */ + struct ralloc_header *child; + + /* Linked list of siblings */ + struct ralloc_header *prev; + struct ralloc_header *next; + + void (*destructor)(void *); +}; + +typedef struct ralloc_header ralloc_header; + +static void unlink_block(ralloc_header *info); +static void unsafe_free(ralloc_header *info); + +static ralloc_header * +get_header(const void *ptr) +{ + ralloc_header *info = (ralloc_header *) (((char *) ptr) - + sizeof(ralloc_header)); +#ifdef DEBUG + assert(info->canary == CANARY); +#endif + return info; +} + +#define PTR_FROM_HEADER(info) (((char *) info) + sizeof(ralloc_header)) + +static void +add_child(ralloc_header *parent, ralloc_header *info) +{ + if (parent != NULL) { + info->parent = parent; + info->next = parent->child; + parent->child = info; + + if (info->next != NULL) + info->next->prev = info; + } +} + +void * +ralloc_context(const void *ctx) +{ + return ralloc_size(ctx, 0); +} + +void * +ralloc_size(const void *ctx, size_t size) +{ + void *block = calloc(1, size + sizeof(ralloc_header)); + ralloc_header *info; + ralloc_header *parent; + + if (unlikely(block == NULL)) + return NULL; + info = (ralloc_header *) block; + parent = ctx != NULL ? get_header(ctx) : NULL; + + add_child(parent, info); + +#ifdef DEBUG + info->canary = CANARY; +#endif + + return PTR_FROM_HEADER(info); +} + +void * +rzalloc_size(const void *ctx, size_t size) +{ + void *ptr = ralloc_size(ctx, size); + if (likely(ptr != NULL)) + memset(ptr, 0, size); + return ptr; +} + +/* helper function - assumes ptr != NULL */ +static void * +resize(void *ptr, size_t size) +{ + ralloc_header *child, *old, *info; + + old = get_header(ptr); + info = realloc(old, size + sizeof(ralloc_header)); + + if (info == NULL) + return NULL; + + /* Update parent and sibling's links to the reallocated node. */ + if (info != old && info->parent != NULL) { + if (info->parent->child == old) + info->parent->child = info; + + if (info->prev != NULL) + info->prev->next = info; + + if (info->next != NULL) + info->next->prev = info; + } + + /* Update child->parent links for all children */ + for (child = info->child; child != NULL; child = child->next) + child->parent = info; + + return PTR_FROM_HEADER(info); +} + +void * +reralloc_size(const void *ctx, void *ptr, size_t size) +{ + if (unlikely(ptr == NULL)) + return ralloc_size(ctx, size); + + assert(ralloc_parent(ptr) == ctx); + return resize(ptr, size); +} + +void * +ralloc_array_size(const void *ctx, size_t size, unsigned count) +{ + if (count > SIZE_MAX/size) + return NULL; + + return ralloc_size(ctx, size * count); +} + +void * +rzalloc_array_size(const void *ctx, size_t size, unsigned count) +{ + if (count > SIZE_MAX/size) + return NULL; + + return rzalloc_size(ctx, size * count); +} + +void * +reralloc_array_size(const void *ctx, void *ptr, size_t size, unsigned count) +{ + if (count > SIZE_MAX/size) + return NULL; + + return reralloc_size(ctx, ptr, size * count); +} + +void +ralloc_free(void *ptr) +{ + ralloc_header *info; + + if (ptr == NULL) + return; + + info = get_header(ptr); + unlink_block(info); + unsafe_free(info); +} + +static void +unlink_block(ralloc_header *info) +{ + /* Unlink from parent & siblings */ + if (info->parent != NULL) { + if (info->parent->child == info) + info->parent->child = info->next; + + if (info->prev != NULL) + info->prev->next = info->next; + + if (info->next != NULL) + info->next->prev = info->prev; + } + info->parent = NULL; + info->prev = NULL; + info->next = NULL; +} + +static void +unsafe_free(ralloc_header *info) +{ + /* Recursively free any children...don't waste time unlinking them. */ + ralloc_header *temp; + while (info->child != NULL) { + temp = info->child; + info->child = temp->next; + unsafe_free(temp); + } + + /* Free the block itself. Call the destructor first, if any. */ + if (info->destructor != NULL) + info->destructor(PTR_FROM_HEADER(info)); + + free(info); +} + +void +ralloc_steal(const void *new_ctx, void *ptr) +{ + ralloc_header *info, *parent; + + if (unlikely(ptr == NULL)) + return; + + info = get_header(ptr); + parent = get_header(new_ctx); + + unlink_block(info); + + add_child(parent, info); +} + +void * +ralloc_parent(const void *ptr) +{ + ralloc_header *info; + + if (unlikely(ptr == NULL)) + return NULL; + + info = get_header(ptr); + return info->parent ? PTR_FROM_HEADER(info->parent) : NULL; +} + +static void *autofree_context = NULL; + +static void +autofree(void) +{ + ralloc_free(autofree_context); +} + +void * +ralloc_autofree_context(void) +{ + if (unlikely(autofree_context == NULL)) { + autofree_context = ralloc_context(NULL); + atexit(autofree); + } + return autofree_context; +} + +void +ralloc_set_destructor(const void *ptr, void(*destructor)(void *)) +{ + ralloc_header *info = get_header(ptr); + info->destructor = destructor; +} + +char * +ralloc_strdup(const void *ctx, const char *str) +{ + size_t n; + char *ptr; + + if (unlikely(str == NULL)) + return NULL; + + n = strlen(str); + ptr = ralloc_array(ctx, char, n + 1); + memcpy(ptr, str, n); + ptr[n] = '\0'; + return ptr; +} + +char * +ralloc_strndup(const void *ctx, const char *str, size_t max) +{ + size_t n; + char *ptr; + + if (unlikely(str == NULL)) + return NULL; + + n = strlen(str); + if (n > max) + n = max; + + ptr = ralloc_array(ctx, char, n + 1); + memcpy(ptr, str, n); + ptr[n] = '\0'; + return ptr; +} + +/* helper routine for strcat/strncat - n is the exact amount to copy */ +static bool +cat(char **dest, const char *str, size_t n) +{ + char *both; + size_t existing_length; + assert(dest != NULL && *dest != NULL); + + existing_length = strlen(*dest); + both = resize(*dest, existing_length + n + 1); + if (unlikely(both == NULL)) + return false; + + memcpy(both + existing_length, str, n); + both[existing_length + n] = '\0'; + + *dest = both; + return true; +} + + +bool +ralloc_strcat(char **dest, const char *str) +{ + return cat(dest, str, strlen(str)); +} + +bool +ralloc_strncat(char **dest, const char *str, size_t n) +{ + /* Clamp n to the string length */ + size_t str_length = strlen(str); + if (str_length < n) + n = str_length; + + return cat(dest, str, n); +} + +char * +ralloc_asprintf(const void *ctx, const char *fmt, ...) +{ + char *ptr; + va_list args; + va_start(args, fmt); + ptr = ralloc_vasprintf(ctx, fmt, args); + va_end(args); + return ptr; +} + +/* Return the length of the string that would be generated by a printf-style + * format and argument list, not including the \0 byte. + */ +static size_t +printf_length(const char *fmt, va_list untouched_args) +{ + int size; + char junk; + + /* Make a copy of the va_list so the original caller can still use it */ + va_list args; + va_copy(args, untouched_args); + +#ifdef _WIN32 + /* We need to use _vcsprintf to calculate the size as vsnprintf returns -1 + * if the number of characters to write is greater than count. + */ + size = _vscprintf(fmt, args); + (void)junk; +#else + size = vsnprintf(&junk, 1, fmt, args); +#endif + assert(size >= 0); + + va_end(args); + + return size; +} + +char * +ralloc_vasprintf(const void *ctx, const char *fmt, va_list args) +{ + size_t size = printf_length(fmt, args) + 1; + + char *ptr = ralloc_size(ctx, size); + if (ptr != NULL) + vsnprintf(ptr, size, fmt, args); + + return ptr; +} + +bool +ralloc_asprintf_append(char **str, const char *fmt, ...) +{ + bool success; + va_list args; + va_start(args, fmt); + success = ralloc_vasprintf_append(str, fmt, args); + va_end(args); + return success; +} + +bool +ralloc_vasprintf_append(char **str, const char *fmt, va_list args) +{ + size_t existing_length; + assert(str != NULL); + existing_length = *str ? strlen(*str) : 0; + return ralloc_vasprintf_rewrite_tail(str, &existing_length, fmt, args); +} + +bool +ralloc_asprintf_rewrite_tail(char **str, size_t *start, const char *fmt, ...) +{ + bool success; + va_list args; + va_start(args, fmt); + success = ralloc_vasprintf_rewrite_tail(str, start, fmt, args); + va_end(args); + return success; +} + +bool +ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt, + va_list args) +{ + size_t new_length; + char *ptr; + + assert(str != NULL); + + if (unlikely(*str == NULL)) { + // Assuming a NULL context is probably bad, but it's expected behavior. + *str = ralloc_vasprintf(NULL, fmt, args); + return true; + } + + new_length = printf_length(fmt, args); + + ptr = resize(*str, *start + new_length + 1); + if (unlikely(ptr == NULL)) + return false; + + vsnprintf(ptr + *start, new_length + 1, fmt, args); + *str = ptr; + *start += new_length; + return true; +} diff --git a/mesalib/src/util/ralloc.h b/mesalib/src/util/ralloc.h new file mode 100644 index 000000000..4b88f3286 --- /dev/null +++ b/mesalib/src/util/ralloc.h @@ -0,0 +1,445 @@ +/* + * Copyright © 2010 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +/** + * \file ralloc.h + * + * ralloc: a recursive memory allocator + * + * The ralloc memory allocator creates a hierarchy of allocated + * objects. Every allocation is in reference to some parent, and + * every allocated object can in turn be used as the parent of a + * subsequent allocation. This allows for extremely convenient + * discarding of an entire tree/sub-tree of allocations by calling + * ralloc_free on any particular object to free it and all of its + * children. + * + * The conceptual working of ralloc was directly inspired by Andrew + * Tridgell's talloc, but ralloc is an independent implementation + * released under the MIT license and tuned for Mesa. + * + * talloc is more sophisticated than ralloc in that it includes reference + * counting and useful debugging features. However, it is released under + * a non-permissive open source license. + */ + +#ifndef RALLOC_H +#define RALLOC_H + +#ifdef __cplusplus +extern "C" { +#endif + +#include <stddef.h> +#include <stdarg.h> +#include <stdbool.h> + +#include "macros.h" + +/** + * \def ralloc(ctx, type) + * Allocate a new object chained off of the given context. + * + * This is equivalent to: + * \code + * ((type *) ralloc_size(ctx, sizeof(type)) + * \endcode + */ +#define ralloc(ctx, type) ((type *) ralloc_size(ctx, sizeof(type))) + +/** + * \def rzalloc(ctx, type) + * Allocate a new object out of the given context and initialize it to zero. + * + * This is equivalent to: + * \code + * ((type *) rzalloc_size(ctx, sizeof(type)) + * \endcode + */ +#define rzalloc(ctx, type) ((type *) rzalloc_size(ctx, sizeof(type))) + +/** + * Allocate a new ralloc context. + * + * While any ralloc'd pointer can be used as a context, sometimes it is useful + * to simply allocate a context with no associated memory. + * + * It is equivalent to: + * \code + * ((type *) ralloc_size(ctx, 0) + * \endcode + */ +void *ralloc_context(const void *ctx); + +/** + * Allocate memory chained off of the given context. + * + * This is the core allocation routine which is used by all others. It + * simply allocates storage for \p size bytes and returns the pointer, + * similar to \c malloc. + */ +void *ralloc_size(const void *ctx, size_t size); + +/** + * Allocate zero-initialized memory chained off of the given context. + * + * This is similar to \c calloc with a size of 1. + */ +void *rzalloc_size(const void *ctx, size_t size); + +/** + * Resize a piece of ralloc-managed memory, preserving data. + * + * Similar to \c realloc. Unlike C89, passing 0 for \p size does not free the + * memory. Instead, it resizes it to a 0-byte ralloc context, just like + * calling ralloc_size(ctx, 0). This is different from talloc. + * + * \param ctx The context to use for new allocation. If \p ptr != NULL, + * it must be the same as ralloc_parent(\p ptr). + * \param ptr Pointer to the memory to be resized. May be NULL. + * \param size The amount of memory to allocate, in bytes. + */ +void *reralloc_size(const void *ctx, void *ptr, size_t size); + +/// \defgroup array Array Allocators @{ + +/** + * \def ralloc_array(ctx, type, count) + * Allocate an array of objects chained off the given context. + * + * Similar to \c calloc, but does not initialize the memory to zero. + * + * More than a convenience function, this also checks for integer overflow when + * multiplying \c sizeof(type) and \p count. This is necessary for security. + * + * This is equivalent to: + * \code + * ((type *) ralloc_array_size(ctx, sizeof(type), count) + * \endcode + */ +#define ralloc_array(ctx, type, count) \ + ((type *) ralloc_array_size(ctx, sizeof(type), count)) + +/** + * \def rzalloc_array(ctx, type, count) + * Allocate a zero-initialized array chained off the given context. + * + * Similar to \c calloc. + * + * More than a convenience function, this also checks for integer overflow when + * multiplying \c sizeof(type) and \p count. This is necessary for security. + * + * This is equivalent to: + * \code + * ((type *) rzalloc_array_size(ctx, sizeof(type), count) + * \endcode + */ +#define rzalloc_array(ctx, type, count) \ + ((type *) rzalloc_array_size(ctx, sizeof(type), count)) + +/** + * \def reralloc(ctx, ptr, type, count) + * Resize a ralloc-managed array, preserving data. + * + * Similar to \c realloc. Unlike C89, passing 0 for \p size does not free the + * memory. Instead, it resizes it to a 0-byte ralloc context, just like + * calling ralloc_size(ctx, 0). This is different from talloc. + * + * More than a convenience function, this also checks for integer overflow when + * multiplying \c sizeof(type) and \p count. This is necessary for security. + * + * \param ctx The context to use for new allocation. If \p ptr != NULL, + * it must be the same as ralloc_parent(\p ptr). + * \param ptr Pointer to the array to be resized. May be NULL. + * \param type The element type. + * \param count The number of elements to allocate. + */ +#define reralloc(ctx, ptr, type, count) \ + ((type *) reralloc_array_size(ctx, ptr, sizeof(type), count)) + +/** + * Allocate memory for an array chained off the given context. + * + * Similar to \c calloc, but does not initialize the memory to zero. + * + * More than a convenience function, this also checks for integer overflow when + * multiplying \p size and \p count. This is necessary for security. + */ +void *ralloc_array_size(const void *ctx, size_t size, unsigned count); + +/** + * Allocate a zero-initialized array chained off the given context. + * + * Similar to \c calloc. + * + * More than a convenience function, this also checks for integer overflow when + * multiplying \p size and \p count. This is necessary for security. + */ +void *rzalloc_array_size(const void *ctx, size_t size, unsigned count); + +/** + * Resize a ralloc-managed array, preserving data. + * + * Similar to \c realloc. Unlike C89, passing 0 for \p size does not free the + * memory. Instead, it resizes it to a 0-byte ralloc context, just like + * calling ralloc_size(ctx, 0). This is different from talloc. + * + * More than a convenience function, this also checks for integer overflow when + * multiplying \c sizeof(type) and \p count. This is necessary for security. + * + * \param ctx The context to use for new allocation. If \p ptr != NULL, + * it must be the same as ralloc_parent(\p ptr). + * \param ptr Pointer to the array to be resized. May be NULL. + * \param size The size of an individual element. + * \param count The number of elements to allocate. + * + * \return True unless allocation failed. + */ +void *reralloc_array_size(const void *ctx, void *ptr, size_t size, + unsigned count); +/// @} + +/** + * Free a piece of ralloc-managed memory. + * + * This will also free the memory of any children allocated this context. + */ +void ralloc_free(void *ptr); + +/** + * "Steal" memory from one context, changing it to another. + * + * This changes \p ptr's context to \p new_ctx. This is quite useful if + * memory is allocated out of a temporary context. + */ +void ralloc_steal(const void *new_ctx, void *ptr); + +/** + * Return the given pointer's ralloc context. + */ +void *ralloc_parent(const void *ptr); + +/** + * Return a context whose memory will be automatically freed at program exit. + * + * The first call to this function creates a context and registers a handler + * to free it using \c atexit. This may cause trouble if used in a library + * loaded with \c dlopen. + */ +void *ralloc_autofree_context(void); + +/** + * Set a callback to occur just before an object is freed. + */ +void ralloc_set_destructor(const void *ptr, void(*destructor)(void *)); + +/// \defgroup array String Functions @{ +/** + * Duplicate a string, allocating the memory from the given context. + */ +char *ralloc_strdup(const void *ctx, const char *str); + +/** + * Duplicate a string, allocating the memory from the given context. + * + * Like \c strndup, at most \p n characters are copied. If \p str is longer + * than \p n characters, \p n are copied, and a termining \c '\0' byte is added. + */ +char *ralloc_strndup(const void *ctx, const char *str, size_t n); + +/** + * Concatenate two strings, allocating the necessary space. + * + * This appends \p str to \p *dest, similar to \c strcat, using ralloc_resize + * to expand \p *dest to the appropriate size. \p dest will be updated to the + * new pointer unless allocation fails. + * + * The result will always be null-terminated. + * + * \return True unless allocation failed. + */ +bool ralloc_strcat(char **dest, const char *str); + +/** + * Concatenate two strings, allocating the necessary space. + * + * This appends at most \p n bytes of \p str to \p *dest, using ralloc_resize + * to expand \p *dest to the appropriate size. \p dest will be updated to the + * new pointer unless allocation fails. + * + * The result will always be null-terminated; \p str does not need to be null + * terminated if it is longer than \p n. + * + * \return True unless allocation failed. + */ +bool ralloc_strncat(char **dest, const char *str, size_t n); + +/** + * Print to a string. + * + * This is analogous to \c sprintf, but allocates enough space (using \p ctx + * as the context) for the resulting string. + * + * \return The newly allocated string. + */ +char *ralloc_asprintf (const void *ctx, const char *fmt, ...) PRINTFLIKE(2, 3); + +/** + * Print to a string, given a va_list. + * + * This is analogous to \c vsprintf, but allocates enough space (using \p ctx + * as the context) for the resulting string. + * + * \return The newly allocated string. + */ +char *ralloc_vasprintf(const void *ctx, const char *fmt, va_list args); + +/** + * Rewrite the tail of an existing string, starting at a given index. + * + * Overwrites the contents of *str starting at \p start with newly formatted + * text, including a new null-terminator. Allocates more memory as necessary. + * + * This can be used to append formatted text when the length of the existing + * string is already known, saving a strlen() call. + * + * \sa ralloc_asprintf_append + * + * \param str The string to be updated. + * \param start The index to start appending new data at. + * \param fmt A printf-style formatting string + * + * \p str will be updated to the new pointer unless allocation fails. + * \p start will be increased by the length of the newly formatted text. + * + * \return True unless allocation failed. + */ +bool ralloc_asprintf_rewrite_tail(char **str, size_t *start, + const char *fmt, ...) + PRINTFLIKE(3, 4); + +/** + * Rewrite the tail of an existing string, starting at a given index. + * + * Overwrites the contents of *str starting at \p start with newly formatted + * text, including a new null-terminator. Allocates more memory as necessary. + * + * This can be used to append formatted text when the length of the existing + * string is already known, saving a strlen() call. + * + * \sa ralloc_vasprintf_append + * + * \param str The string to be updated. + * \param start The index to start appending new data at. + * \param fmt A printf-style formatting string + * \param args A va_list containing the data to be formatted + * + * \p str will be updated to the new pointer unless allocation fails. + * \p start will be increased by the length of the newly formatted text. + * + * \return True unless allocation failed. + */ +bool ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt, + va_list args); + +/** + * Append formatted text to the supplied string. + * + * This is equivalent to + * \code + * ralloc_asprintf_rewrite_tail(str, strlen(*str), fmt, ...) + * \endcode + * + * \sa ralloc_asprintf + * \sa ralloc_asprintf_rewrite_tail + * \sa ralloc_strcat + * + * \p str will be updated to the new pointer unless allocation fails. + * + * \return True unless allocation failed. + */ +bool ralloc_asprintf_append (char **str, const char *fmt, ...) + PRINTFLIKE(2, 3); + +/** + * Append formatted text to the supplied string, given a va_list. + * + * This is equivalent to + * \code + * ralloc_vasprintf_rewrite_tail(str, strlen(*str), fmt, args) + * \endcode + * + * \sa ralloc_vasprintf + * \sa ralloc_vasprintf_rewrite_tail + * \sa ralloc_strcat + * + * \p str will be updated to the new pointer unless allocation fails. + * + * \return True unless allocation failed. + */ +bool ralloc_vasprintf_append(char **str, const char *fmt, va_list args); +/// @} + +#ifdef __cplusplus +} /* end of extern "C" */ +#endif + +/** + * Declare C++ new and delete operators which use ralloc. + * + * Placing this macro in the body of a class makes it possible to do: + * + * TYPE *var = new(mem_ctx) TYPE(...); + * delete var; + * + * which is more idiomatic in C++ than calling ralloc. + */ +#define DECLARE_RALLOC_CXX_OPERATORS(TYPE) \ +private: \ + static void _ralloc_destructor(void *p) \ + { \ + reinterpret_cast<TYPE *>(p)->~TYPE(); \ + } \ +public: \ + static void* operator new(size_t size, void *mem_ctx) \ + { \ + void *p = ralloc_size(mem_ctx, size); \ + assert(p != NULL); \ + if (!HAS_TRIVIAL_DESTRUCTOR(TYPE)) \ + ralloc_set_destructor(p, _ralloc_destructor); \ + return p; \ + } \ + \ + static void operator delete(void *p) \ + { \ + /* The object's destructor is guaranteed to have already been \ + * called by the delete operator at this point -- Make sure it's \ + * not called again. \ + */ \ + if (!HAS_TRIVIAL_DESTRUCTOR(TYPE)) \ + ralloc_set_destructor(p, NULL); \ + ralloc_free(p); \ + } + + +#endif |