wmem/wmem_list.c
wmem/wmem_miscutl.c
wmem/wmem_scopes.c
- wmem/wmem_splay.c
wmem/wmem_stack.c
wmem/wmem_strbuf.c
wmem/wmem_strutl.c
wmem_list.c \
wmem_miscutl.c \
wmem_scopes.c \
- wmem_splay.c \
wmem_stack.c \
wmem_strbuf.c \
wmem_strutl.c \
wmem_miscutl.h \
wmem_queue.h \
wmem_scopes.h \
- wmem_splay.h \
wmem_stack.h \
wmem_strbuf.h \
wmem_strutl.h \
#include "wmem_miscutl.h"
#include "wmem_queue.h"
#include "wmem_scopes.h"
-#include "wmem_splay.h"
#include "wmem_stack.h"
#include "wmem_strbuf.h"
#include "wmem_strutl.h"
+++ /dev/null
-/* wmem_splay.c
- * Wireshark Memory Manager Splay Tree
- * Copyright 2014, Evan Huus <eapache@gmail.com>
- *
- * Wireshark - Network traffic analyzer
- * By Gerald Combs <gerald@wireshark.org>
- * Copyright 1998 Gerald Combs
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along
- * with this program; if not, write to the Free Software Foundation, Inc.,
- * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
- */
-
-/* Splay trees provide (sort of) balanced binary search trees that bubble
- * recently accessed keys to the top, and as such have a number of very nice
- * properties: https://en.wikipedia.org/wiki/Splay_tree
- *
- * This implementation is of a variant known as "independent semi-splaying",
- * as described in the 2008 paper by Brinkmann, Degraer and De Loof:
- * http://onlinelibrary.wiley.com/doi/10.1002/spe.886/abstract
- * Unfortunately I have not found a link to a public copy of this paper...
- *
- * Independent semi-splaying is a variant on Sleator and Tarjan's original splay
- * tree structure with better practical performance. It should do about as well
- * as a red-black tree for random insertions and accesses, but somewhat better
- * for patterned accesses (such as accessing each key in order, or accessing
- * certain keys very frequently).
- *
- * I took the opportunity of writing new code to make a few other changes
- * relative to the old red-black tree implementation:
- * - Instead of requiring complex keys to be split into guint32 chunks and
- * doing this weird radix-like trick with sub-trees, I let the keys be
- * arbitrary pointers and allowed the user to specify an arbitrary comparison
- * function. If the function is NULL then the pointers are compared directly
- * for the simple integer-key case.
- * - Splay trees do not need to store a red-black colour flag for each node.
- * It is also much easier to do without the parent pointer in each node. And
- * due to the simpler system for complex keys, I was able to remove the
- * "is_subtree" boolean. As such, splay nodes are 12 bytes smaller on 32-bit
- * platforms, and 16 bytes smaller on a 64-bit platform.
- */
-
-#include "config.h"
-
-#include <glib.h>
-
-#include "wmem_core.h"
-#include "wmem_splay.h"
-#include "wmem_user_cb.h"
-
-struct _wmem_splay_node_t {
- void *key, *value;
- struct _wmem_splay_node_t *left, *right;
-};
-
-typedef struct _wmem_splay_node_t wmem_splay_node_t;
-
-struct _wmem_splay_t {
- wmem_allocator_t *master;
- wmem_allocator_t *allocator;
- guint master_cb_id;
- guint slave_cb_id;
-
- wmem_compare_func cmp;
-
- wmem_splay_node_t *root;
-};
-
-static gboolean
-wmem_splay_reset_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event,
- void *user_data)
-{
- wmem_splay_t *tree = (wmem_splay_t *)user_data;
-
- tree->root = NULL;
-
- if (event == WMEM_CB_DESTROY_EVENT) {
- wmem_unregister_callback(tree->master, tree->master_cb_id);
- wmem_free(tree->master, tree);
- }
-
- return TRUE;
-}
-
-static gboolean
-wmem_splay_destroy_cb(wmem_allocator_t *allocator _U_, wmem_cb_event_t event _U_,
- void *user_data)
-{
- wmem_splay_t *tree = (wmem_splay_t *)user_data;
-
- wmem_unregister_callback(tree->allocator, tree->slave_cb_id);
-
- return FALSE;
-}
-
-wmem_splay_t *
-wmem_splay_new(wmem_allocator_t *allocator, wmem_compare_func cmp)
-{
- wmem_splay_t *tree;
-
- tree = wmem_new(allocator, wmem_splay_t);
- tree->master = allocator;
- tree->allocator = allocator;
- tree->root = NULL;
- tree->cmp = cmp;
-
- return tree;
-}
-
-wmem_splay_t *
-wmem_splay_new_autoreset(wmem_allocator_t *master, wmem_allocator_t *slave,
- wmem_compare_func cmp)
-{
- wmem_splay_t *tree;
-
- tree = wmem_new(master, wmem_splay_t);
- tree->master = master;
- tree->allocator = slave;
- tree->root = NULL;
- tree->cmp = cmp;
-
- tree->master_cb_id = wmem_register_callback(master, wmem_splay_destroy_cb,
- tree);
- tree->slave_cb_id = wmem_register_callback(slave, wmem_splay_reset_cb,
- tree);
-
- return tree;
-}
-
-gboolean
-wmem_splay_is_empty(const wmem_splay_t *tree)
-{
- return tree->root == NULL;
-}
-
-#define COMPARE(a, b) \
- (tree->cmp == NULL ? \
- GPOINTER_TO_INT(a)-GPOINTER_TO_INT(b) : \
- tree->cmp(a, b))
-
-static void
-wmem_splay_pred_succ(wmem_splay_t *tree, const void *key,
- wmem_splay_node_t **pred, wmem_splay_node_t **succ)
-{
- wmem_splay_node_t *cur = tree->root;
- int cmp;
-
- if (pred != NULL) {
- *pred = NULL;
- }
- if (succ != NULL) {
- *succ = NULL;
- }
-
- while (cur != NULL) {
- cmp = COMPARE(key, cur->key);
- if (cmp == 0) {
- return;
- }
- else if (cmp < 0) {
- if (succ != NULL) {
- *succ = cur;
- }
- cur = cur->left;
- }
- else {
- if (pred != NULL) {
- *pred = cur;
- }
- cur = cur->right;
- }
- }
-}
-
-#define TRAVERSE(CUR, NXT, KEY) \
-do { \
- if ((*CUR) == NULL) { \
- return (CUR); \
- } \
- cmp = COMPARE((KEY), (*CUR)->key); \
- if (cmp == 0) { \
- return (CUR); \
- } \
- else if (cmp < 0) { \
- (NXT) = &((*CUR)->left); \
- } \
- else { \
- (NXT) = &((*CUR)->right); \
- } \
-} while (0)
-
-#define ZIGZIG(CHILD, KEY) \
-do { \
- tmp = *p; \
- *p = tmp->CHILD; \
- tmp->CHILD = *gp; \
- *gp = tmp; \
- cmp = COMPARE((KEY), (*cur)->key); \
- if (cmp == 0) { \
- return cur; \
- } \
- else if (cmp < 0) { \
- gp = &((*cur)->left); \
- } \
- else { \
- gp = &((*cur)->right); \
- } \
-} while (0)
-
-#define ZIGZAG(LEFT, RIGHT, KEY) \
-do { \
- tmp = *cur; \
- *cur = tmp->LEFT; \
- tmp->LEFT = *p; \
- *p = tmp->RIGHT; \
- tmp->RIGHT = *gp; \
- *gp = tmp; \
- cmp = COMPARE((KEY), tmp->key); \
- if (cmp == 0) { \
- return gp; \
- } \
- else if (cmp < 0) { \
- gp = &(tmp->left->right); \
- } \
- else { \
- gp = &(tmp->right->left); \
- } \
-} while (0)
-
-static wmem_splay_node_t **
-wmem_splay_splay(wmem_splay_t *tree, const void *key)
-{
- wmem_splay_node_t **gp, **p, **cur, *tmp;
- int cmp;
-
- gp = &(tree->root);
-
- while (TRUE) {
- TRAVERSE(gp, p, key);
- TRAVERSE(p, cur, key);
-
- if ((*cur) == NULL) {
- return cur;
- }
-
- if (p == &((*gp)->left)) {
- if (cur == &((*p)->left)) {
- ZIGZIG(right, key);
- }
- else {
- ZIGZAG(left, right, key);
- }
- }
- else {
- if (cur == &((*p)->right)) {
- ZIGZIG(left, key);
- }
- else {
- ZIGZAG(right, left, key);
- }
- }
- }
-}
-
-void *
-wmem_splay_lookup(wmem_splay_t *tree, const void *key)
-{
- wmem_splay_node_t **target;
- target = wmem_splay_splay(tree, key);
-
- if ((*target) == NULL) {
- return NULL;
- }
-
- return (*target)->value;
-}
-
-void *
-wmem_splay_lookup_le(wmem_splay_t *tree, const void *key)
-{
- wmem_splay_node_t *target;
- target = *(wmem_splay_splay(tree, key));
-
- if (target == NULL) {
- wmem_splay_pred_succ(tree, key, &target, NULL);
- }
-
- if (target == NULL) {
- return NULL;
- }
-
- return target->value;
-}
-
-void
-wmem_splay_insert(wmem_splay_t *tree, void *key, void *value)
-{
- wmem_splay_node_t **target;
- target = wmem_splay_splay(tree, key);
-
- if ((*target) == NULL) {
- *target = wmem_new(tree->allocator, wmem_splay_node_t);
- (*target)->key = key;
- (*target)->value = value;
- (*target)->left = NULL;
- (*target)->right = NULL;
- }
- else {
- (*target)->value = value;
- }
-}
-
-static gboolean
-wmem_splay_foreach_node(wmem_splay_node_t* node, wmem_foreach_func callback,
- void *user_data)
-{
- if (!node) {
- return FALSE;
- }
-
- if (node->left) {
- if (wmem_splay_foreach_node(node->left, callback, user_data)) {
- return TRUE;
- }
- }
-
- if (callback(node->value, user_data)) {
- return TRUE;
- }
-
- if(node->right) {
- if (wmem_splay_foreach_node(node->right, callback, user_data)) {
- return TRUE;
- }
- }
-
- return FALSE;
-}
-
-gboolean
-wmem_splay_foreach(wmem_splay_t* tree, wmem_foreach_func callback,
- void *user_data)
-{
- return wmem_splay_foreach_node(tree->root, callback, user_data);
-}
-
-/*
- * Editor modelines - http://www.wireshark.org/tools/modelines.html
- *
- * Local variables:
- * c-basic-offset: 4
- * tab-width: 8
- * indent-tabs-mode: nil
- * End:
- *
- * vi: set shiftwidth=4 tabstop=8 expandtab:
- * :indentSize=4:tabSize=8:noTabs=true:
- */
+++ /dev/null
-/* wmem_splay.h
- * Definitions for the Wireshark Memory Manager Splay Tree
- * Copyright 2014, Evan Huus <eapache@gmail.com>
- *
- * Wireshark - Network traffic analyzer
- * By Gerald Combs <gerald@wireshark.org>
- * Copyright 1998 Gerald Combs
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License along
- * with this program; if not, write to the Free Software Foundation, Inc.,
- * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
- */
-
-#ifndef __WMEM_SPLAY_H__
-#define __WMEM_SPLAY_H__
-
-#include "wmem_core.h"
-#include "wmem_tree.h"
-
-#ifdef __cplusplus
-extern "C" {
-#endif /* __cplusplus */
-
-/** @addtogroup wmem
- * @{
- * @defgroup wmem-splay Splay Tree
- *
- * Binary trees are a well-known and popular device in computer science to
- * handle storage of objects based on a search key or identity. The
- * particular binary tree style implemented here is the splay tree, which
- * has a large number of nice properties. It guarantees O(log(n)) amortized
- * time per operation, and O(1) per operation for certain special access
- * patterns. See https://en.wikipedia.org/wiki/Splay_tree
- *
- * The version implemented here is known as "independent semi-splaying",
- * which is a variant with the same properties but slightly better practical
- * performance.
- *
- * @{
- */
-
-struct _wmem_splay_t;
-typedef struct _wmem_splay_t wmem_splay_t;
-
-/** A wmem_compare_func compares two keys in a tree, and must return:
- * 0 if a==b
- * >0 if a>b
- * <0 if a<b
- * It must be able to compare any two keys, and must form a total order on the
- * space of keys (https://en.wikipedia.org/wiki/Total_order). For example, the
- * builtin strcmp() function satisfies these requirements.
- */
-typedef int (*wmem_compare_func)(const void *a, const void *b);
-
-/** Creates a tree with the given allocator scope. When the scope is emptied,
- * the tree is fully destroyed. The given comparison function is used to compare
- * keys. It is permitted to pass NULL for the comparison function, in which case
- * the key pointer values will be compared directly (cast to signed integers).
- */
-WS_DLL_PUBLIC
-wmem_splay_t *
-wmem_splay_new(wmem_allocator_t *allocator, wmem_compare_func cmp)
-G_GNUC_MALLOC;
-
-/** Creates a tree with two allocator scopes. The base structure lives in the
- * master scope, however the data lives in the slave scope. Every time free_all
- * occurs in the slave scope the tree is transparently emptied without affecting
- * the location of the master structure.
- *
- * WARNING: None of the tree (even the part in the master scope) can be used
- * after the slave scope has been *destroyed*.
- *
- * The primary use for this function is to create trees that reset for each new
- * capture file that is loaded. This can be done by specifying wmem_epan_scope()
- * as the master and wmem_file_scope() as the slave.
- */
-WS_DLL_PUBLIC
-wmem_splay_t *
-wmem_splay_new_autoreset(wmem_allocator_t *master, wmem_allocator_t *slave,
- wmem_compare_func cmp)
-G_GNUC_MALLOC;
-
-/** Returns true if the tree is empty (has no nodes). */
-WS_DLL_PUBLIC
-gboolean
-wmem_splay_is_empty(const wmem_splay_t *tree);
-
-/** Look up a node in the tree indexed by the given key. If no node is found
- * the function will return NULL.
- */
-WS_DLL_PUBLIC
-void *
-wmem_splay_lookup(wmem_splay_t *tree, const void *key);
-
-/** Look up a node in the tree indexed by the given key. Returns the node that
- * has the largest key that is less than or equal to the search key, or NULL if
- * no such node exists.
- */
-WS_DLL_PUBLIC
-void *
-wmem_splay_lookup_le(wmem_splay_t *tree, const void *key);
-
-/** Insert a node indexed by the given key.
- *
- * Value is a pointer to the structure you want to be able to retrieve by
- * searching for the same key later.
- *
- * Unlike the old wmem_tree/emem_tree, inserting does *not* take a copy of
- * whatever key is pointed to, it simply stores a pointer. As such, inserted
- * keys cannot be on the stack and must instead last as long as the tree itself
- * (keys used during lookups are not stored, and can be on the stack).
- *
- * NOTE: If you insert a node to a key that already exists in the tree this
- * function will simply overwrite the old value. If the structures you are
- * storing are allocated in a wmem pool this is not a problem as they will still
- * be freed with the pool. If you are managing them manually however, you must
- * either ensure each key is unique, or do a lookup before each insert.
- */
-WS_DLL_PUBLIC
-void
-wmem_splay_insert(wmem_splay_t *tree, void *key, void *value);
-
-/** Traverse the tree and call callback(value, userdata) for each value found.
- * Returns TRUE if the traversal was ended prematurely by the callback.
- */
-WS_DLL_PUBLIC
-gboolean
-wmem_splay_foreach(wmem_splay_t* tree, wmem_foreach_func callback,
- void *user_data);
-
-/** @}
- * @} */
-
-#ifdef __cplusplus
-}
-#endif /* __cplusplus */
-
-#endif /* __WMEM_SPLAY_H__ */
-
-/*
- * Editor modelines - http://www.wireshark.org/tools/modelines.html
- *
- * Local variables:
- * c-basic-offset: 4
- * tab-width: 8
- * indent-tabs-mode: nil
- * End:
- *
- * vi: set shiftwidth=4 tabstop=8 expandtab:
- * :indentSize=4:tabSize=8:noTabs=true:
- */
wmem_destroy_allocator(allocator);
}
-static void
-wmem_test_splay(void)
-{
- wmem_allocator_t *allocator, *extra_allocator;
- wmem_splay_t *tree;
- guint32 i;
- int seen_values = 0;
-
- allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
- extra_allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
-
- tree = wmem_splay_new(allocator, NULL);
- g_assert(tree);
- g_assert(wmem_splay_is_empty(tree));
-
- /* test basic integer key operations */
- for (i=0; i<CONTAINER_ITERS; i++) {
- void *tmp = GINT_TO_POINTER(i);
- g_assert(wmem_splay_lookup(tree, tmp) == NULL);
- if (i > 0) {
- g_assert(wmem_splay_lookup_le(tree, tmp) == GINT_TO_POINTER(i-1));
- }
- wmem_splay_insert(tree, tmp, tmp);
- g_assert(wmem_splay_lookup(tree, tmp) == tmp);
- g_assert(!wmem_splay_is_empty(tree));
- }
- wmem_free_all(allocator);
-
- tree = wmem_splay_new(allocator, NULL);
- for (i=0; i<CONTAINER_ITERS; i++) {
- guint32 rand_int = g_test_rand_int();
- wmem_splay_insert(tree, GINT_TO_POINTER(rand_int), GINT_TO_POINTER(i));
- g_assert(wmem_splay_lookup(tree, GINT_TO_POINTER(rand_int)) == GINT_TO_POINTER(i));
- }
- wmem_free_all(allocator);
-
- /* test auto-reset functionality */
- tree = wmem_splay_new_autoreset(allocator, extra_allocator, NULL);
- for (i=0; i<CONTAINER_ITERS; i++) {
- void *tmp = GINT_TO_POINTER(i);
- g_assert(wmem_splay_lookup(tree, tmp) == NULL);
- wmem_splay_insert(tree, tmp, tmp);
- g_assert(wmem_splay_lookup(tree, tmp) == tmp);
- }
- wmem_free_all(extra_allocator);
- for (i=0; i<CONTAINER_ITERS; i++) {
- g_assert(wmem_splay_lookup(tree, GINT_TO_POINTER(i)) == NULL);
- g_assert(wmem_splay_lookup_le(tree, GINT_TO_POINTER(i)) == NULL);
- }
- wmem_free_all(allocator);
-
- /* test complex key functionality */
- tree = wmem_splay_new(allocator, (wmem_compare_func)(&strcmp));
- for (i=0; i<CONTAINER_ITERS; i++) {
- char *str_key = wmem_test_rand_string(allocator, 1, 64);
- wmem_splay_insert(tree, str_key, GINT_TO_POINTER(i));
- g_assert(wmem_splay_lookup(tree, str_key) == GINT_TO_POINTER(i));
- /* lookup some other arbitrary string to stir the tree; there's nothing
- * we can assert about the result, but it shouldn't crash */
- str_key = wmem_test_rand_string(allocator, 1, 64);
- wmem_splay_lookup_le(tree, str_key);
- }
- wmem_free_all(allocator);
-
- /* test for-each functionality */
- tree = wmem_splay_new(allocator, NULL);
- expected_user_data = GINT_TO_POINTER(g_test_rand_int());
- for (i=0; i<CONTAINER_ITERS; i++) {
- gint tmp;
- do {
- tmp = g_test_rand_int();
- } while (wmem_splay_lookup(tree, GINT_TO_POINTER(tmp)));
- value_seen[i] = FALSE;
- wmem_splay_insert(tree, GINT_TO_POINTER(tmp), GINT_TO_POINTER(i));
- }
-
- cb_called_count = 0;
- cb_continue_count = CONTAINER_ITERS;
- wmem_splay_foreach(tree, wmem_test_foreach_cb, expected_user_data);
- g_assert(cb_called_count == CONTAINER_ITERS);
- g_assert(cb_continue_count == 0);
-
- for (i=0; i<CONTAINER_ITERS; i++) {
- g_assert(value_seen[i]);
- value_seen[i] = FALSE;
- }
-
- cb_called_count = 0;
- cb_continue_count = 10;
- wmem_splay_foreach(tree, wmem_test_foreach_cb, expected_user_data);
- g_assert(cb_called_count == 10);
- g_assert(cb_continue_count == 0);
-
- for (i=0; i<CONTAINER_ITERS; i++) {
- if (value_seen[i]) {
- seen_values++;
- }
- }
- g_assert(seen_values == 10);
-
- wmem_destroy_allocator(extra_allocator);
- wmem_destroy_allocator(allocator);
-}
-
static void
wmem_test_stack(void)
{
wmem_destroy_allocator(allocator);
}
-static void
-wmem_time_trees(void)
-{
- int i;
- char *str_key;
- wmem_allocator_t *allocator;
-
- double rb_time, rb_string_time;
- wmem_tree_t *tree;
-
- double splay_time, splay_string_time;
- wmem_splay_t *splay;
-
- /* red-black tree with integer keys */
- allocator = wmem_allocator_new(WMEM_ALLOCATOR_BLOCK);
- g_test_timer_start();
- tree = wmem_tree_new(allocator);
- for (i=0; i<CONTAINER_ITERS; i++) {
- wmem_tree_insert32(tree, g_test_rand_int(), GINT_TO_POINTER(i));
- }
- for (i=0; i<MANY_ITERS; i++) {
- wmem_tree_lookup32(tree, g_test_rand_int());
- }
- rb_time = g_test_timer_elapsed();
- wmem_destroy_allocator(allocator);
-
- /* splay tree with integer keys */
- allocator = wmem_allocator_new(WMEM_ALLOCATOR_BLOCK);
- g_test_timer_start();
- splay = wmem_splay_new(allocator, NULL);
- for (i=0; i<CONTAINER_ITERS; i++) {
- wmem_splay_insert(splay, GINT_TO_POINTER(g_test_rand_int()), GINT_TO_POINTER(i));
- }
- for (i=0; i<MANY_ITERS; i++) {
- wmem_splay_lookup(splay, GINT_TO_POINTER(g_test_rand_int()));
- }
- splay_time = g_test_timer_elapsed();
- wmem_destroy_allocator(allocator);
-
- /* red-black tree with string keys */
- allocator = wmem_allocator_new(WMEM_ALLOCATOR_BLOCK);
- g_test_timer_start();
- tree = wmem_tree_new(allocator);
- for (i=0; i<CONTAINER_ITERS; i++) {
- str_key = wmem_test_rand_string(allocator, 1, 64);
- wmem_tree_insert_string(tree, str_key, GINT_TO_POINTER(i), 0);
- }
- for (i=0; i<MANY_ITERS; i++) {
- str_key = wmem_test_rand_string(allocator, 1, 64);
- wmem_tree_lookup_string(tree, str_key, 0);
- wmem_free(allocator, str_key);
- }
- rb_string_time = g_test_timer_elapsed();
- wmem_destroy_allocator(allocator);
-
- /* splay tree with string keys */
- allocator = wmem_allocator_new(WMEM_ALLOCATOR_BLOCK);
- g_test_timer_start();
- splay = wmem_splay_new(allocator, (wmem_compare_func)(&strcmp));
- for (i=0; i<CONTAINER_ITERS; i++) {
- str_key = wmem_test_rand_string(allocator, 1, 64);
- wmem_splay_insert(splay, str_key, GINT_TO_POINTER(i));
- }
- for (i=0; i<MANY_ITERS; i++) {
- str_key = wmem_test_rand_string(allocator, 1, 64);
- wmem_splay_lookup(splay, str_key);
- wmem_free(allocator, str_key);
- }
- splay_string_time = g_test_timer_elapsed();
- wmem_destroy_allocator(allocator);
-
- printf("(red-black: %lf+%lf; splay: %lf+%lf) ", rb_time, rb_string_time,
- splay_time, splay_string_time);
-
- /* Performance is close enough that about 10% of the time (in my tests) the
- * red-black tree will work out to be faster just due to random variation.
- * So we add a 0.1 fudge factor. */
- g_assert((rb_time + rb_string_time) * 1.1 > splay_time + splay_string_time);
-}
-
int
main(int argc, char **argv)
{
g_test_add_func("/wmem/datastruct/array", wmem_test_array);
g_test_add_func("/wmem/datastruct/list", wmem_test_list);
g_test_add_func("/wmem/datastruct/queue", wmem_test_queue);
- g_test_add_func("/wmem/datastruct/splay", wmem_test_splay);
g_test_add_func("/wmem/datastruct/stack", wmem_test_stack);
g_test_add_func("/wmem/datastruct/strbuf", wmem_test_strbuf);
g_test_add_func("/wmem/datastruct/tree", wmem_test_tree);
- g_test_add_func("/wmem/timing/trees", wmem_time_trees);
g_test_add_func("/wmem/timing/allocators", wmem_time_allocators);
return g_test_run();
git.samba.org / metze / wireshark / wip.git / commitdiff