1 2008-09-19 Hans Petter Jansson <hpj@novell.com>
3 Rewrite most of GHashTable to use open addressing with quadratic
4 probing instead of chaining. This has the potential to reduce memory
5 fragmentation significantly, while being slightly faster due to
6 better locality and no need to call alloc/free functions for nodes.
7 Benchmarks suggest it also uses less memory overall.
9 * glib/ghash.c (prime_mod): Table of suitable primes for
10 initial-probe distribution.
11 (g_hash_table_set_shift): New function.
12 (g_hash_table_find_closest_shift): New function.
13 (g_hash_table_set_shift_from_size): New function.
14 (g_hash_table_lookup_node_for_insertion): New function.
15 (g_hash_table_lookup_node): Rewritten to return node index instead of
16 pointer, use quadratic probe on flat table, and not return insertion
17 data. The latter saves some computation for read-only lookups.
18 (g_hash_table_remove_node): Rewrite to take a pointer directly to the
19 node structure to remove, and clear that. Remove unlinking code.
20 (g_hash_table_remove_all_nodes): Rewrite to not clear nodes
21 individually, but en masse using memset () after potentially calling
23 (iter_remove_or_steal): Use new data structure and algorithm. Vastly
24 simplified - now just a call to g_hash_table_remove_node ().
25 (g_hash_table_resize): New resize code, re-indexing with new prime
26 and cleaning up tombstones.
27 (g_hash_table_maybe_resize): Table may hold 8 buckets minimum, no less
28 than 1/4 load excluding tombstones, and no more than 15/16 load
29 including tombstones. These numbers are the results of a lot of
30 benchmarking with multiple complex applications, and should not be
32 (g_hash_table_iter_next)
34 (g_hash_table_lookup_extended)
35 (g_hash_table_insert_internal)
36 (g_hash_table_remove_internal)
37 (g_hash_table_foreach_remove_or_steal)
38 (g_hash_table_foreach)
40 (g_hash_table_get_keys)
41 (g_hash_table_get_values): Use new data structure and algorithm,
42 fairly trivial changes.
44 2008-09-19 Tor Lillqvist <tml@novell.com>
46 * glib-zip.in: Look for man pages in share/man.
48 * glib/gutils.c (_glib_get_dll_directory)
49 * glib/gspawn-win32.c (do_spawn_with_pipes): Be a bit less
50 restrictive, look for the helper programs in the same folder where
51 the GLib DLL is, not necessarily in a "bin" subfolder of the top
52 GLib installation folder.
54 2008-09-18 Matthias Clasen <mclasen@redhat.com>
56 * configure.in: Bump version to 2.19.0
58 * ChangeLog.pre-2-18: rotate ChangeLog
60 * === branch for 2.18 ===