Rewrite dict module to be more in line with vect
It's now a bit more strongly typed, can grow and shrink on demand, and has
a more complete interface.
It uses open addressing scheme to store hashes.
diff --git a/breakpoints.c b/breakpoints.c
index 88ada7f..7ec05c3 100644
--- a/breakpoints.c
+++ b/breakpoints.c
@@ -88,13 +88,18 @@
/*****************************************************************************/
struct breakpoint *
-address2bpstruct(struct process *proc, void *addr)
+address2bpstruct(struct process *proc, arch_addr_t addr)
{
assert(proc != NULL);
assert(proc->breakpoints != NULL);
assert(proc->leader == proc);
debug(DEBUG_FUNCTION, "address2bpstruct(pid=%d, addr=%p)", proc->pid, addr);
- return dict_find_entry(proc->breakpoints, addr);
+
+ struct breakpoint **found
+ = DICT_FIND(proc->breakpoints, &addr, struct breakpoint *);
+ if (found == NULL)
+ return NULL;
+ return *found;
}
#ifndef ARCH_HAVE_BREAKPOINT_DATA
@@ -196,7 +201,7 @@
}
struct breakpoint *
-insert_breakpoint(struct process *proc, void *addr,
+insert_breakpoint(struct process *proc, arch_addr_t addr,
struct library_symbol *libsym)
{
struct process *leader = proc->leader;
@@ -218,39 +223,46 @@
* will suffice, about the only realistic case where we need
* to have more than one breakpoint per address is return from
* a recursive library call. */
- struct breakpoint *sbp = dict_find_entry(leader->breakpoints, addr);
- if (sbp == NULL) {
- sbp = malloc(sizeof(*sbp));
- if (sbp == NULL
- || breakpoint_init(sbp, proc, addr, libsym) < 0) {
- free(sbp);
+ struct breakpoint **found
+ = DICT_FIND(leader->breakpoints, &addr, struct breakpoint *);
+ struct breakpoint *bp;
+ if (found == NULL) {
+ bp = malloc(sizeof(*bp));
+ if (bp == NULL
+ || breakpoint_init(bp, proc, addr, libsym) < 0) {
+ free(bp);
return NULL;
}
- if (proc_add_breakpoint(leader, sbp) < 0) {
+ if (proc_add_breakpoint(leader, bp) < 0) {
fail:
- breakpoint_destroy(sbp);
- free(sbp);
+ breakpoint_destroy(bp);
+ free(bp);
return NULL;
}
+ } else {
+ bp = *found;
}
- if (breakpoint_turn_on(sbp, proc) < 0) {
- proc_remove_breakpoint(leader, sbp);
+ if (breakpoint_turn_on(bp, proc) < 0) {
+ proc_remove_breakpoint(leader, bp);
goto fail;
}
- return sbp;
+ return bp;
}
void
-delete_breakpoint(struct process *proc, void *addr)
+delete_breakpoint(struct process *proc, arch_addr_t addr)
{
debug(DEBUG_FUNCTION, "delete_breakpoint(pid=%d, addr=%p)", proc->pid, addr);
struct process *leader = proc->leader;
assert(leader != NULL);
- struct breakpoint *sbp = dict_find_entry(leader->breakpoints, addr);
+ struct breakpoint **found
+ = DICT_FIND(leader->breakpoints, &addr, struct breakpoint *);
+ assert(found != NULL);
+ struct breakpoint *sbp = *found;
assert(sbp != NULL);
/* This should only happen on out-of-memory conditions. */
if (sbp == NULL)
@@ -282,13 +294,14 @@
return bp->libsym != NULL ? bp->libsym->lib : NULL;
}
-static void
-enable_bp_cb(void *addr, void *sbp, void *proc)
+static enum callback_status
+enable_bp_cb(arch_addr_t *addr, struct breakpoint **bpp, void *data)
{
- debug(DEBUG_FUNCTION, "enable_bp_cb(pid=%d)",
- ((struct process *)proc)->pid);
- if (((struct breakpoint *)sbp)->enabled)
- enable_breakpoint(proc, sbp);
+ struct process *proc = data;
+ debug(DEBUG_FUNCTION, "enable_bp_cb(pid=%d)", proc->pid);
+ if ((*bpp)->enabled)
+ enable_breakpoint(proc, *bpp);
+ return CBS_CONT;
}
void
@@ -297,19 +310,19 @@
debug(DEBUG_FUNCTION, "enable_all_breakpoints(pid=%d)", proc->pid);
debug(1, "Enabling breakpoints for pid %u...", proc->pid);
- if (proc->breakpoints) {
- dict_apply_to_all(proc->breakpoints, enable_bp_cb,
- proc);
- }
+ if (proc->breakpoints != NULL)
+ DICT_EACH(proc->breakpoints, arch_addr_t, struct breakpoint *,
+ NULL, enable_bp_cb, proc);
}
-static void
-disable_bp_cb(void *addr, void *sbp, void *proc)
+static enum callback_status
+disable_bp_cb(arch_addr_t *addr, struct breakpoint **bpp, void *data)
{
- debug(DEBUG_FUNCTION, "disable_bp_cb(pid=%d)",
- ((struct process *)proc)->pid);
- if (((struct breakpoint *)sbp)->enabled)
- disable_breakpoint(proc, sbp);
+ struct process *proc = data;
+ debug(DEBUG_FUNCTION, "disable_bp_cb(pid=%d)", proc->pid);
+ if ((*bpp)->enabled)
+ disable_breakpoint(proc, *bpp);
+ return CBS_CONT;
}
void
@@ -317,7 +330,8 @@
{
debug(DEBUG_FUNCTION, "disable_all_breakpoints(pid=%d)", proc->pid);
assert(proc->leader == proc);
- dict_apply_to_all(proc->breakpoints, disable_bp_cb, proc);
+ DICT_EACH(proc->breakpoints, arch_addr_t, struct breakpoint *,
+ NULL, disable_bp_cb, proc);
}
/* XXX This is not currently properly supported. On clone, this is
diff --git a/common.h b/common.h
index f333f3f..5fbe861 100644
--- a/common.h
+++ b/common.h
@@ -74,7 +74,7 @@
#include "demangle.h"
#endif
-extern Dict * dict_opt_c;
+extern struct dict *dict_opt_c;
/* Events */
extern Event * next_event(void);
diff --git a/demangle.c b/demangle.c
index 5147367..2216a32 100644
--- a/demangle.c
+++ b/demangle.c
@@ -1,5 +1,6 @@
/*
* This file is part of ltrace.
+ * Copyright (C) 2012 Petr Machata, Red Hat Inc.
* Copyright (C) 1998,1999,2003,2004,2008,2009 Juan Cespedes
* Copyright (C) 2006 Ian Wienand
*
@@ -31,34 +32,53 @@
/*****************************************************************************/
-static Dict *d = NULL;
+static struct dict *name_cache = NULL;
const char *
my_demangle(const char *function_name) {
- const char *tmp, *fn_copy;
#ifdef USE_CXA_DEMANGLE
extern char *__cxa_demangle(const char *, char *, size_t *, int *);
#endif
debug(DEBUG_FUNCTION, "my_demangle(name=%s)", function_name);
- if (!d)
- d = dict_init(dict_key2hash_string, dict_key_cmp_string);
-
- tmp = dict_find_entry(d, (void *)function_name);
- if (!tmp) {
- fn_copy = strdup(function_name);
-#ifdef HAVE_LIBIBERTY
- tmp = cplus_demangle(function_name, DMGL_ANSI | DMGL_PARAMS);
-#elif defined USE_CXA_DEMANGLE
- int status = 0;
- tmp = __cxa_demangle(function_name, NULL, NULL, &status);
-#endif
- if (!tmp)
- tmp = fn_copy;
- if (tmp)
- dict_enter(d, (void *)fn_copy, (void *)tmp);
+ if (name_cache == NULL) {
+ name_cache = malloc(sizeof(*name_cache));
+ if (name_cache != NULL)
+ DICT_INIT(name_cache, const char *, const char *,
+ dict_hash_string, dict_eq_string, NULL);
}
+
+ const char **found = NULL;
+ if (name_cache != NULL)
+ found = DICT_FIND(name_cache, &function_name, const char *);
+
+ if (found != NULL)
+ return *found;
+
+#ifdef HAVE_LIBIBERTY
+ const char *tmp = cplus_demangle(function_name,
+ DMGL_ANSI | DMGL_PARAMS);
+#elif defined USE_CXA_DEMANGLE
+ int status = 0;
+ const char *tmp = __cxa_demangle(function_name, NULL, NULL, &status);
+#endif
+ if (name_cache == NULL || tmp == NULL) {
+ fail:
+ if (tmp == NULL)
+ return function_name;
+ return tmp;
+ }
+
+ const char *fn_copy = strdup(function_name);
+ if (fn_copy == NULL)
+ goto fail;
+
+ if (DICT_INSERT(name_cache, &fn_copy, &tmp) < 0) {
+ free((char *)fn_copy);
+ goto fail;
+ }
+
return tmp;
}
diff --git a/dict.c b/dict.c
index aad50fd..38e3daa 100644
--- a/dict.c
+++ b/dict.c
@@ -1,8 +1,6 @@
/*
* This file is part of ltrace.
- * Copyright (C) 2011,2012 Petr Machata
- * Copyright (C) 2003,2004,2008,2009 Juan Cespedes
- * Copyright (C) 2006 Ian Wienand
+ * Copyright (C) 2012 Petr Machata, Red Hat Inc.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
@@ -20,298 +18,581 @@
* 02110-1301 USA
*/
-#include <stdio.h>
-#include <stdlib.h>
#include <string.h>
-#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include "dict.h"
-#include "common.h"
-
-/*
- * Dictionary based on code by Morten Eriksen <mortene@sim.no>.
- */
-
-struct dict_entry {
- unsigned int hash;
- void *key;
- void *value;
- struct dict_entry *next;
+struct status_bits {
+ unsigned char taken : 1;
+ unsigned char erased : 1;
};
-/* #define DICTTABLESIZE 97 */
-#define DICTTABLESIZE 997 /* Semi-randomly selected prime number. */
-/* #define DICTTABLESIZE 9973 */
-/* #define DICTTABLESIZE 99991 */
-/* #define DICTTABLESIZE 999983 */
-
-struct dict {
- struct dict_entry *buckets[DICTTABLESIZE];
- unsigned int (*key2hash) (const void *);
- int (*key_cmp) (const void *, const void *);
-};
-
-Dict *
-dict_init(unsigned int (*key2hash) (const void *),
- int (*key_cmp) (const void *, const void *))
+static struct status_bits *
+bitp(struct dict *dict, size_t n)
{
- Dict *d;
- int i;
-
- debug(DEBUG_FUNCTION, "dict_init()");
-
- d = malloc(sizeof(Dict));
- if (!d) {
- perror("malloc()");
- exit(1);
- }
- for (i = 0; i < DICTTABLESIZE; i++) { /* better use memset()? */
- d->buckets[i] = NULL;
- }
- d->key2hash = key2hash;
- d->key_cmp = key_cmp;
- return d;
+ return VECT_ELEMENT(&dict->status, struct status_bits, n);
}
void
-dict_clear(Dict *d) {
- int i;
- struct dict_entry *entry, *nextentry;
+dict_init(struct dict *dict,
+ size_t key_size, size_t value_size,
+ size_t (*hash1)(const void *),
+ int (*eq)(const void *, const void *),
+ size_t (*hash2)(size_t))
+{
+ assert(hash1 != NULL);
+ assert(eq != NULL);
- debug(DEBUG_FUNCTION, "dict_clear()");
- assert(d);
- for (i = 0; i < DICTTABLESIZE; i++) {
- for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
- nextentry = entry->next;
- free(entry);
- }
- d->buckets[i] = NULL;
+ vect_init(&dict->keys, key_size);
+ vect_init(&dict->values, value_size);
+ VECT_INIT(&dict->status, struct status_bits);
+ dict->size = 0;
+
+ dict->hash1 = hash1;
+ dict->hash2 = hash2;
+ dict->eq = eq;
+}
+
+struct clone_data {
+ struct dict *target;
+ int (*clone_key)(void *tgt, const void *src, void *data);
+ int (*clone_value)(void *tgt, const void *src, void *data);
+ void (*dtor_key)(void *tgt, void *data);
+ void (*dtor_value)(void *tgt, void *data);
+ void *data;
+};
+
+enum callback_status
+clone_cb(void *key, void *value, void *data)
+{
+ struct clone_data *clone_data = data;
+
+ char nkey[clone_data->target->keys.elt_size];
+ if (clone_data->clone_key == NULL)
+ memmove(nkey, key, sizeof(nkey));
+ else if (clone_data->clone_key(&nkey, key, clone_data->data) < 0)
+ return CBS_STOP;
+
+ char nvalue[clone_data->target->values.elt_size];
+ if (clone_data->clone_value == NULL) {
+ memmove(nvalue, value, sizeof(nvalue));
+ } else if (clone_data->clone_value(&nvalue, value,
+ clone_data->data) < 0) {
+ fail:
+ if (clone_data->clone_key != NULL)
+ clone_data->dtor_key(&nkey, clone_data->data);
+ return CBS_STOP;
}
- free(d);
+
+ if (dict_insert(clone_data->target, nkey, nvalue) < 0) {
+ if (clone_data->clone_value != NULL)
+ clone_data->dtor_value(&nvalue, clone_data->data);
+ goto fail;
+ }
+
+ return CBS_CONT;
}
int
-dict_enter(Dict *d, void *key, void *value) {
- struct dict_entry *entry, *newentry;
- unsigned int hash;
- unsigned int bucketpos;
+dict_clone(struct dict *target, const struct dict *source,
+ int (*clone_key)(void *tgt, const void *src, void *data),
+ void (*dtor_key)(void *tgt, void *data),
+ int (*clone_value)(void *tgt, const void *src, void *data),
+ void (*dtor_value)(void *tgt, void *data),
+ void *data)
+{
+ assert((clone_key != NULL) == (dtor_key != NULL));
+ assert((clone_value != NULL) == (dtor_value != NULL));
- debug(DEBUG_FUNCTION, "dict_enter()");
+ dict_init(target, source->keys.elt_size, source->values.elt_size,
+ source->hash1, source->eq, source->hash2);
+ struct clone_data clone_data = {
+ target, clone_key, clone_value, dtor_key, dtor_value, data
+ };
+ if (dict_each((struct dict *)source, NULL,
+ clone_cb, &clone_data) != NULL) {
+ dict_destroy(target, dtor_key, dtor_value, data);
+ return -1;
+ }
+ return 0;
+}
- hash = d->key2hash(key);
- bucketpos = hash % DICTTABLESIZE;
+size_t
+dict_size(const struct dict *dict)
+{
+ return dict->size;
+}
- assert(d);
- newentry = malloc(sizeof(struct dict_entry));
- if (!newentry) {
- perror("malloc");
- exit(1);
+int
+dict_empty(const struct dict *dict)
+{
+ return dict->size == 0;
+}
+
+struct destroy_data {
+ void (*dtor_key)(void *tgt, void *data);
+ void (*dtor_value)(void *tgt, void *data);
+ void *data;
+};
+
+enum callback_status
+destroy_cb(void *key, void *value, void *data)
+{
+ struct destroy_data *destroy_data = data;
+ if (destroy_data->dtor_key)
+ destroy_data->dtor_key(key, destroy_data->data);
+ if (destroy_data->dtor_value)
+ destroy_data->dtor_value(value, destroy_data->data);
+ return CBS_CONT;
+}
+
+void
+dict_destroy(struct dict *dict,
+ void (*dtor_key)(void *tgt, void *data),
+ void (*dtor_value)(void *tgt, void *data),
+ void *data)
+{
+ /* Some keys and values are not initialized, so we can't call
+ * dtors for them. Iterate DICT instead. */
+ if (dtor_key != NULL || dtor_value != NULL) {
+ struct destroy_data destroy_data = {
+ dtor_key, dtor_value, data
+ };
+ dict_each(dict, NULL, destroy_cb, &destroy_data);
}
- newentry->hash = hash;
- newentry->key = key;
- newentry->value = value;
- newentry->next = NULL;
+ vect_destroy(&dict->keys, NULL, NULL);
+ vect_destroy(&dict->values, NULL, NULL);
+ vect_destroy(&dict->status, NULL, NULL);
+}
- entry = d->buckets[bucketpos];
- while (entry && entry->next)
- entry = entry->next;
+static size_t
+default_secondary_hash(size_t pos)
+{
+ return pos % 97 + 1;
+}
- if (entry)
- entry->next = newentry;
+static inline size_t
+n(struct dict *dict)
+{
+ return vect_size(&dict->keys);
+}
+
+static inline size_t (*
+hash2(struct dict *dict))(size_t)
+{
+ if (dict->hash2 != NULL)
+ return dict->hash2;
else
- d->buckets[bucketpos] = newentry;
+ return default_secondary_hash;
+}
- debug(3, "new dict entry at %p[%d]: (%p,%p)", d, bucketpos, key, value);
+static void *
+getkey(struct dict *dict, size_t pos)
+{
+ return ((unsigned char *)dict->keys.data)
+ + dict->keys.elt_size * pos;
+}
+
+static void *
+getvalue(struct dict *dict, size_t pos)
+{
+ return ((unsigned char *)dict->values.data)
+ + dict->values.elt_size * pos;
+}
+
+static size_t
+find_slot(struct dict *dict, const void *key,
+ int *foundp, int *should_rehash, size_t *pi)
+{
+ size_t pos = dict->hash1(key) % n(dict);
+ size_t pos0 = -1;
+ size_t d = hash2(dict)(pos);
+ size_t i = 0;
+ *foundp = 0;
+
+ /* We skip over any taken or erased slots. But we remember
+ * the first erased that we find, and if we don't find the key
+ * later, we return that position. */
+ for (; bitp(dict, pos)->taken || bitp(dict, pos)->erased;
+ pos = (pos + d) % n(dict)) {
+
+ if (pos0 == (size_t)-1 && bitp(dict, pos)->erased)
+ pos0 = pos;
+
+ if (++i > dict->size)
+ break;
+
+ if (bitp(dict, pos)->taken
+ && dict->eq(getkey(dict, pos), key)) {
+ *foundp = 1;
+ break;
+ }
+ }
+
+ if (!*foundp && pos0 != (size_t)-1)
+ pos = pos0;
+
+ /* If the hash table degraded into a linked list, request a
+ * rehash. */
+ if (should_rehash != NULL)
+ *should_rehash = i > 10 && i > n(dict) / 10;
+
+ if (pi != NULL)
+ *pi = i;
+ return pos;
+}
+
+enum callback_status
+rehash_move(void *key, void *value, void *data)
+{
+ if (dict_insert(data, key, value) < 0)
+ return CBS_STOP;
+ else
+ return CBS_CONT;
+}
+
+int
+rehash(struct dict *dict, size_t nn)
+{
+ int ret = -1;
+
+ struct dict tmp;
+ dict_init(&tmp, dict->keys.elt_size, dict->values.elt_size,
+ dict->hash1, dict->eq, dict->hash2);
+
+ /* To honor all invariants (so that we can safely call
+ * dict_destroy), we first make a request to _reserve_ enough
+ * room in all vectors. This has no observable effect on
+ * contents of vectors. */
+ if (vect_reserve(&tmp.keys, nn) < 0
+ || vect_reserve(&tmp.values, nn) < 0
+ || vect_reserve(&tmp.status, nn) < 0)
+ goto done;
+
+ /* Now that we know that there is enough size in vectors, we
+ * simply bump the size. */
+ tmp.keys.size = nn;
+ tmp.values.size = nn;
+ size_t old_size = tmp.status.size;
+ tmp.status.size = nn;
+ memset(VECT_ELEMENT(&tmp.status, struct status_bits, old_size),
+ 0, (tmp.status.size - old_size) * tmp.status.elt_size);
+
+ /* At this point, TMP is once more an empty dictionary with NN
+ * slots. Now move stuff from DICT to TMP. */
+ if (dict_each(dict, NULL, rehash_move, &tmp) != NULL)
+ goto done;
+
+ /* And now swap contents of DICT and TMP, and we are done. */
+ {
+ struct dict tmp2 = *dict;
+ *dict = tmp;
+ tmp = tmp2;
+ }
+
+ ret = 0;
+
+done:
+ /* We only want to release the containers, not the actual data
+ * that they hold, so it's fine if we don't pass any dtor. */
+ dict_destroy(&tmp, NULL, NULL, NULL);
+ return ret;
+
+}
+
+static const size_t primes[] = {
+ 13, 31, 61, 127, 251, 509, 1021, 2039, 4093,
+ 8191, 16381, 32749, 65521, 130981, 0
+};
+
+static size_t
+larger_size(size_t current)
+{
+ if (current == 0)
+ return primes[0];
+
+ if (current < primes[sizeof(primes)/sizeof(*primes) - 2]) {
+ size_t i;
+ for (i = 0; primes[i] != 0; ++i)
+ if (primes[i] > current)
+ return primes[i];
+ abort();
+ }
+
+ /* We ran out of primes, so invent a new one. The following
+ * gives primes until about 17M elements (and then some more
+ * later). */
+ return 2 * current + 6585;
+}
+
+static size_t
+smaller_size(size_t current)
+{
+ if (current <= primes[0])
+ return primes[0];
+
+ if (current <= primes[sizeof(primes)/sizeof(*primes) - 2]) {
+ size_t i;
+ size_t prev = 0;
+ for (i = 0; primes[i] != 0; ++i) {
+ if (primes[i] >= current)
+ return prev;
+ prev = primes[i];
+ }
+ abort();
+ }
+
+ return (current - 6585) / 2;
+}
+
+int
+dict_insert(struct dict *dict, void *key, void *value)
+{
+ if (n(dict) == 0 || dict->size > 0.7 * n(dict))
+ rehash:
+ if (rehash(dict, larger_size(n(dict))) < 0)
+ return -1;
+
+ int found;
+ int should_rehash;
+ size_t slot_n = find_slot(dict, key, &found, &should_rehash, NULL);
+
+ if (found)
+ return 1;
+
+ /* If rehash was requested, do that, and retry. But just live
+ * with it for apparently sparse tables. No resizing can fix
+ * a rubbish hash. */
+ if (should_rehash && dict->size > 0.3 * n(dict))
+ goto rehash;
+
+ memmove(getkey(dict, slot_n), key, dict->keys.elt_size);
+ memmove(getvalue(dict, slot_n), value, dict->values.elt_size);
+
+ bitp(dict, slot_n)->taken = 1;
+ bitp(dict, slot_n)->erased = 0;
+ ++dict->size;
+
return 0;
}
void *
-dict_remove(Dict *d, void *key)
+dict_find(struct dict *dict, const void *key)
{
- assert(d != NULL);
- debug(DEBUG_FUNCTION, "dict_remove(%p)", key);
+ if (dict->size == 0)
+ return NULL;
- unsigned int hash = d->key2hash(key);
- unsigned int bucketpos = hash % DICTTABLESIZE;
+ int found;
+ size_t slot_n = find_slot(dict, key, &found, NULL, NULL);
+ if (found)
+ return getvalue(dict, slot_n);
+ else
+ return NULL;
+}
- struct dict_entry **entryp;
- for (entryp = &d->buckets[bucketpos]; (*entryp) != NULL;
- entryp = &(*entryp)->next) {
- struct dict_entry *entry = *entryp;
- if (hash != entry->hash)
- continue;
- if (d->key_cmp(key, entry->key) == 0) {
- *entryp = entry->next;
- void *value = entry->value;
- free(entry);
- return value;
- }
+int
+dict_erase(struct dict *dict, const void *key,
+ void (*dtor_key)(void *tgt, void *data),
+ void (*dtor_value)(void *tgt, void *data),
+ void *data)
+{
+ int found;
+ size_t i;
+ size_t slot_n = find_slot(dict, key, &found, NULL, &i);
+ if (!found)
+ return -1;
+
+ if (dtor_key != NULL)
+ dtor_key(getkey(dict, slot_n), data);
+ if (dtor_value != NULL)
+ dtor_value(getvalue(dict, slot_n), data);
+
+ bitp(dict, slot_n)->taken = 0;
+ bitp(dict, slot_n)->erased = 1;
+ --dict->size;
+
+ if (dict->size < 0.3 * n(dict)) {
+ /* Don't mind if it fails when shrinking. */
+ rehash(dict, smaller_size(n(dict)));
}
- return NULL;
+
+ return 0;
}
void *
-dict_find_entry(Dict *d, const void *key)
+dict_each(struct dict *dict, void *start_after,
+ enum callback_status (*cb)(void *, void *, void *), void *data)
{
- unsigned int hash;
- unsigned int bucketpos;
- struct dict_entry *entry;
+ size_t i;
+ if (start_after != NULL)
+ i = ((start_after - dict->keys.data) / dict->keys.elt_size) + 1;
+ else
+ i = 0;
- debug(DEBUG_FUNCTION, "dict_find_entry()");
-
- hash = d->key2hash(key);
- bucketpos = hash % DICTTABLESIZE;
-
- assert(d);
- for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
- if (hash != entry->hash) {
- continue;
+ for (; i < dict->keys.size; ++i)
+ if (bitp(dict, i)->taken && !bitp(dict, i)->erased) {
+ void *key = getkey(dict, i);
+ if (cb(key, getvalue(dict, i), data) != CBS_CONT)
+ return key;
}
- if (!d->key_cmp(key, entry->key)) {
- break;
- }
- }
- return entry ? entry->value : NULL;
+
+ return NULL;
}
-void
-dict_apply_to_all(Dict *d,
- void (*func) (void *key, void *value, void *data), void *data) {
- int i;
-
- debug(DEBUG_FUNCTION, "dict_apply_to_all()");
-
- if (!d) {
- return;
- }
- for (i = 0; i < DICTTABLESIZE; i++) {
- struct dict_entry *entry = d->buckets[i];
- while (entry) {
- func(entry->key, entry->value, data);
- entry = entry->next;
- }
- }
-}
-
-/*****************************************************************************/
-
-unsigned int
-dict_key2hash_string(const void *key)
+size_t
+dict_hash_int(const int *key)
{
- const char *s = (const char *)key;
- unsigned int total = 0, shift = 0;
-
- assert(key);
- while (*s) {
- total = total ^ ((*s) << shift);
- shift += 5;
- if (shift > 24)
- shift -= 24;
- s++;
- }
- return total;
+ return (size_t)(*key * 2654435761);
}
int
-dict_key_cmp_string(const void *key1, const void *key2)
+dict_eq_int(const int *key1, const int *key2)
{
- assert(key1);
- assert(key2);
- return strcmp((const char *)key1, (const char *)key2);
+ return *key1 == *key2;
}
-unsigned int
-dict_key2hash_int(const void *key)
+size_t
+dict_hash_string(const char **key)
{
- return (unsigned long)key;
+ size_t h = 5381;
+ const char *str = *key;
+ while (*str != 0)
+ h = h * 33 ^ *str++;
+ return h;
}
int
-dict_key_cmp_int(const void *key1, const void *key2)
+dict_eq_string(const char **key1, const char **key2)
{
- return key1 - key2;
+ return strcmp(*key1, *key2) == 0;
}
-Dict *
-dict_clone2(Dict * old, void * (*key_clone)(void *, void *),
- void * (*value_clone)(void *, void *), void * data)
+#ifdef TEST
+static enum callback_status
+dump(int *key, int *value, void *data)
{
- Dict *d;
+ char *seen = data;
+ assert(seen[*key] == 0);
+ seen[*key] = 1;
+ assert(*value == *key * 2 + 1);
+ return CBS_STOP;
+}
+
+static size_t
+dict_hash_int_silly(const int *key)
+{
+ return *key % 10;
+}
+
+static void
+verify(struct dict *di, size_t len, char *seen)
+{
+ size_t ct = 0;
+ int *it;
+ for (it = NULL; (it = DICT_EACH(di, int, int, it, dump, seen)) != NULL;)
+ ct++;
+ assert(ct == len);
+ memset(seen, 0, len);
+}
+
+static enum callback_status
+fill_keys(int *key, int *value, void *data)
+{
+ int *array = data;
+ array[++array[0]] = *key;
+ return CBS_CONT;
+}
+
+static void
+test1(void)
+{
+ struct dict di;
+ DICT_INIT(&di, int, int, dict_hash_int, dict_eq_int, NULL);
+
+ char seen[100000] = {};
+ size_t i;
+ for (i = 0; i < sizeof(seen); ++i) {
+ int key = i;
+ int value = 2 * i + 1;
+ DICT_INSERT(&di, &key, &value);
+ int *valp = DICT_FIND(&di, &key, int);
+ assert(valp != NULL);
+ assert(*valp == value);
+ assert(dict_size(&di) == i + 1);
+ }
+
+ verify(&di, sizeof(seen), seen);
+
+ struct dict d2;
+ DICT_CLONE(&d2, &di, int, int, NULL, NULL, NULL, NULL, NULL);
+ DICT_DESTROY(&di, int, int, NULL, NULL, NULL);
+ verify(&d2, sizeof(seen), seen);
+
+ /* Now we try to gradually erase all elements. We can't erase
+ * inside a DICT_EACH call, so copy first keys to a separate
+ * memory area first. */
+ int keys[d2.size + 1];
+ size_t ct = 0;
+ keys[0] = 0;
+ DICT_EACH(&d2, int, int, NULL, fill_keys, keys);
+ for (i = 0; i < (size_t)keys[0]; ++i) {
+ assert(DICT_ERASE(&d2, &keys[i + 1], int,
+ NULL, NULL, NULL) == 0);
+ ++ct;
+ }
+ assert(ct == sizeof(seen));
+ DICT_DESTROY(&d2, int, int, NULL, NULL, NULL);
+}
+
+static void
+test_erase(void)
+{
int i;
- debug(DEBUG_FUNCTION, "dict_clone()");
-
- d = malloc(sizeof(Dict));
- if (!d) {
- perror("malloc()");
- exit(1);
+ /* To test erase, we need a relatively bad hash function, so
+ * that there are some overlapping chains in the table. */
+ struct dict d2;
+ DICT_INIT(&d2, int, int, dict_hash_int_silly, dict_eq_int, NULL);
+ const int limit = 500;
+ for (i = 0; i < limit; ++i) {
+ int key = 2 * i + 1;
+ int value = 2 * key + 1;
+ DICT_INSERT(&d2, &key, &value);
}
- memcpy(d, old, sizeof(Dict));
- for (i = 0; i < DICTTABLESIZE; i++) { /* better use memset()? */
- struct dict_entry *de_old;
- struct dict_entry **de_new;
- de_old = old->buckets[i];
- de_new = &d->buckets[i];
- while (de_old) {
- void * nkey, * nval;
- *de_new = malloc(sizeof(struct dict_entry));
- if (!*de_new) {
- perror("malloc()");
- exit(1);
+ /* Now we try to delete each of the keys, and verify that none
+ * of the chains was broken. */
+ for (i = 0; i < limit; ++i) {
+ struct dict copy;
+ DICT_CLONE(©, &d2, int, int, NULL, NULL, NULL, NULL, NULL);
+ int key = 2 * i + 1;
+ DICT_ERASE(©, &key, int, NULL, NULL, NULL);
+ assert(dict_size(©) == dict_size(&d2) - 1);
+
+ int j;
+ for (j = 0; j < limit; ++j) {
+ key = 2 * j + 1;
+ int *valp = DICT_FIND(©, &key, int);
+ if (i != j) {
+ assert(valp != NULL);
+ assert(*valp == 2 * key + 1);
+ } else {
+ assert(valp == NULL);
}
- memcpy(*de_new, de_old, sizeof(struct dict_entry));
-
- /* The error detection is rather weak :-/ */
- nkey = key_clone(de_old->key, data);
- if (nkey == NULL && de_old->key != NULL) {
- perror("key_clone");
- err:
- /* XXX Will this actually work? We
- * simply memcpy the old dictionary
- * over up there. */
- dict_clear(d);
- free(de_new);
- return NULL;
- }
-
- nval = value_clone(de_old->value, data);
- if (nval == NULL && de_old->value != NULL) {
- perror("value_clone");
- goto err;
- }
-
- (*de_new)->key = nkey;
- (*de_new)->value = nval;
- de_new = &(*de_new)->next;
- de_old = de_old->next;
}
+
+ DICT_DESTROY(©, int, int, NULL, NULL, NULL);
}
- return d;
+ DICT_DESTROY(&d2, int, int, NULL, NULL, NULL);
}
-struct wrap_clone_cb
+int main(int argc, char *argv[])
{
- void * (*key_clone)(void *);
- void * (*value_clone)(void *);
-};
-
-static void *
-value_clone_1(void * arg, void * data)
-{
- return ((struct wrap_clone_cb *)data)->value_clone(arg);
+ test1();
+ test_erase();
+ return 0;
}
-static void *
-key_clone_1(void * arg, void * data)
-{
- return ((struct wrap_clone_cb *)data)->key_clone(arg);
-}
-
-Dict *
-dict_clone(Dict * old, void * (*key_clone)(void *),
- void * (*value_clone)(void *))
-{
- struct wrap_clone_cb cb = { key_clone, value_clone };
- return dict_clone2(old, &key_clone_1, &value_clone_1, &cb);
-}
+#endif
diff --git a/dict.h b/dict.h
index fcc1acb..d84ea80 100644
--- a/dict.h
+++ b/dict.h
@@ -1,9 +1,6 @@
/*
* This file is part of ltrace.
- * Copyright (C) 2011,2012 Petr Machata
- * Copyright (C) 2003,2004,2008,2009 Juan Cespedes
- * Copyright (C) 2006 Ian Wienand
- * Copyright (C) ???? Morten Eriksen <mortene@sim.no>
+ * Copyright (C) 2012 Petr Machata, Red Hat Inc.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
@@ -24,32 +21,201 @@
#ifndef _DICT_H_
#define _DICT_H_
-/*
- * Dictionary based on code by Morten Eriksen <mortene@sim.no>.
- */
+#include <stddef.h>
+#include <assert.h>
+#include "vect.h"
-typedef struct dict Dict;
+struct dict {
+ /* The invariant is that KEYS, VALUES and STATUS are of the
+ * same size. */
+ struct vect keys;
+ struct vect values;
+ struct vect status;
+ size_t size;
-extern Dict *dict_init(unsigned int (*key2hash) (const void *),
- int (*key_cmp) (const void *, const void *));
-extern void dict_clear(Dict *d);
-extern int dict_enter(Dict *d, void *key, void *value);
-extern void *dict_remove(Dict *d, void *key);
-extern void *dict_find_entry(Dict *d, const void *key);
-extern void dict_apply_to_all(Dict *d,
- void (*func) (void *key, void *value, void *data),
- void *data);
+ size_t (*hash1)(const void *);
+ int (*eq)(const void *, const void *);
+ size_t (*hash2)(size_t);
+};
-extern unsigned int dict_key2hash_string(const void *key);
-extern int dict_key_cmp_string(const void *key1, const void *key2);
+/* Initialize a dictionary DICT. The dictionary will hold keys of the
+ * size KEY_SIZE and values of the size VALUE_SIZE. HASH1 and HASH2
+ * are, respectively, primary and secondary hashing functions. The
+ * latter may be NULL, in which case a default internal hash is used.
+ * EQ is a callback for comparing two keys. */
+void dict_init(struct dict *dict,
+ size_t key_size, size_t value_size,
+ size_t (*hash1)(const void *),
+ int (*eq)(const void *, const void *),
+ size_t (*hash2)(size_t));
-extern unsigned int dict_key2hash_int(const void *key);
-extern int dict_key_cmp_int(const void *key1, const void *key2);
+/* Wrapper around dict_init. Initializes a dictionary DITCP which
+ * will hold keys of type KEY_TYPE and values of type VALUE_TYPE.
+ * Other arguments as above. */
+#define DICT_INIT(DICTP, KEY_TYPE, VALUE_TYPE, HASH1, EQ, HASH2) \
+ ({ \
+ /* Check that callbacks are typed properly. */ \
+ size_t (*_hash1_callback)(const KEY_TYPE *) = HASH1; \
+ int (*_eq_callback)(const KEY_TYPE *, const KEY_TYPE *) = EQ; \
+ dict_init(DICTP, sizeof(KEY_TYPE), sizeof(VALUE_TYPE), \
+ (size_t (*)(const void *))_hash1_callback, \
+ (int (*)(const void *, const void *))_eq_callback, \
+ HASH2); \
+ })
-extern Dict * dict_clone(Dict *old, void * (*key_clone)(void*), void * (*value_clone)(void*));
-extern Dict * dict_clone2(Dict * old,
- void * (* key_clone)(void * key, void * data),
- void * (* value_clone)(void * value, void * data),
- void * data);
+/* Clone SOURCE to TARGET. For cloning slots, CLONE_KEY and
+ * CLONE_VALUE are called. These callbacks return 0 on success or a
+ * negative value on failure. If any of the callbacks is NULL, the
+ * default action is simple memmove. Returns 0 on success. If the
+ * cloning fails for any reason, already-cloned keys and values are
+ * destroyed again by DTOR_KEY and DTOR_VALUE callbacks (if non-NULL),
+ * and the function returns a negative value. DATA is passed to all
+ * callbacks verbatim. */
+int dict_clone(struct dict *target, const struct dict *source,
+ int (*clone_key)(void *tgt, const void *src, void *data),
+ void (*dtor_key)(void *tgt, void *data),
+ int (*clone_value)(void *tgt, const void *src, void *data),
+ void (*dtor_value)(void *tgt, void *data),
+ void *data);
+
+/* Clone SRC_DICTP, which holds KEY_TYPE-VALUE_TYPE pairs, into
+ * TGT_DICTP. Other arguments and return codes as above. */
+#define DICT_CLONE(TGT_DICTP, SRC_DICTP, KEY_TYPE, VALUE_TYPE, \
+ CLONE_KEY, DTOR_KEY, CLONE_VALUE, DTOR_VALUE, DATA) \
+ /* xxx GCC-ism necessary to get in the safety latches. */ \
+ ({ \
+ const struct dict *_source_d = (SRC_DICTP); \
+ assert(_source_d->keys.elt_size == sizeof(KEY_TYPE)); \
+ assert(_source_d->values.elt_size == sizeof(VALUE_TYPE)); \
+ /* Check that callbacks are typed properly. */ \
+ void (*_key_dtor_cb)(KEY_TYPE *, void *) = DTOR_KEY; \
+ int (*_key_clone_cb)(KEY_TYPE *, const KEY_TYPE *, \
+ void *) = CLONE_KEY; \
+ void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
+ int (*_value_clone_cb)(VALUE_TYPE *, const VALUE_TYPE *, \
+ void *) = CLONE_VALUE; \
+ dict_clone((TGT_DICTP), _source_d, \
+ (int (*)(void *, const void *, \
+ void *))_key_clone_cb, \
+ (void (*)(void *, void *))_key_dtor_cb, \
+ (int (*)(void *, const void *, \
+ void *))_value_clone_cb, \
+ (void (*)(void *, void *))_value_dtor_cb, \
+ (DATA)); \
+ })
+
+/* Return number of key-value pairs stored in DICT. */
+size_t dict_size(const struct dict *dict);
+
+/* Emptiness predicate. */
+int dict_empty(const struct dict *dict);
+
+/* Insert into DICT a pair of KEY and VALUE. Returns 0 if insertion
+ * was successful, a negative value on error, or a positive value if
+ * this key is already present in the table. */
+int dict_insert(struct dict *dict, void *key, void *value);
+
+/* Insert into DICT a pair of KEY and VALUE. See dict_insert for
+ * details. In addition, make a check whether DICTP holds elements of
+ * the right size. */
+#define DICT_INSERT(DICTP, KEYP, VALUEP) \
+ (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
+ assert((DICTP)->values.elt_size == sizeof(*(VALUEP))), \
+ dict_insert((DICTP), (KEYP), (VALUEP)))
+
+/* Find in DICT a value corresponding to KEY and return a pointer to
+ * it. Returns NULL if the key was not found. */
+void *dict_find(struct dict *dict, const void *key);
+
+/* Find in DICTP a value of type VALUE_TYPE corresponding to KEYP and
+ * return a pointer (VALUE_TYPE *) to it. Returns NULL if the key was
+ * not found. */
+#define DICT_FIND(DICTP, KEYP, VALUE_TYPE) \
+ (assert((DICTP)->keys.elt_size == sizeof(*(KEYP))), \
+ (VALUE_TYPE *)dict_find((DICTP), (KEYP)))
+
+/* Erase from DICT the entry corresponding to KEY. Returns a negative
+ * value if the key was not found, or 0 on success. DTOR_KEY and
+ * DTOR_VALUE, if non-NULL, are called to destroy the erased
+ * value. */
+int dict_erase(struct dict *dict, const void *key,
+ void (*dtor_key)(void *tgt, void *data),
+ void (*dtor_value)(void *tgt, void *data),
+ void *data);
+
+/* Erase from DICTP a value of type VALUE_TYPE corresponding to
+ * KEYP. */
+#define DICT_ERASE(DICTP, KEYP, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \
+ ({ \
+ struct dict *_d = (DICTP); \
+ assert(_d->keys.elt_size == sizeof(*KEYP)); \
+ assert(_d->values.elt_size == sizeof(VALUE_TYPE)); \
+ /* Check that callbacks are typed properly. */ \
+ void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
+ dict_erase(_d, (KEYP), (DTOR_KEY), \
+ (void (*)(void *, void *))_value_dtor_cb, \
+ (DATA)); \
+ })
+
+/* Destroy DICT. If KEY_DTOR is non-NULL, then it's called on each
+ * key stored in DICT. Similarly for VALUE_DTOR. DATA is passed to
+ * DTOR's verbatim. The memory pointed-to by DICT is not freed. */
+void dict_destroy(struct dict *dict,
+ void (*dtor_key)(void *tgt, void *data),
+ void (*dtor_value)(void *tgt, void *data),
+ void *data);
+
+/* Destroy DICTP, which holds keys of type KEY_TYPE and values of type
+ * VALUE_TYPE, using DTOR. */
+#define DICT_DESTROY(DICTP, KEY_TYPE, VALUE_TYPE, DTOR_KEY, DTOR_VALUE, DATA) \
+ do { \
+ struct dict *_d = (DICTP); \
+ assert(_d->keys.elt_size == sizeof(KEY_TYPE)); \
+ assert(_d->values.elt_size == sizeof(VALUE_TYPE)); \
+ /* Check that callbacks are typed properly. */ \
+ void (*_key_dtor_cb)(KEY_TYPE *, void *) = DTOR_KEY; \
+ void (*_value_dtor_cb)(VALUE_TYPE *, void *) = DTOR_VALUE; \
+ dict_destroy(_d, (void (*)(void *, void *))_key_dtor_cb, \
+ (void (*)(void *, void *))_value_dtor_cb, \
+ (DATA)); \
+ } while (0)
+
+/* Iterate through DICT. See callback.h for notes on iteration
+ * interfaces. Callback arguments are key, value, DATA. Note that
+ * the iteration over DICT is more expensive than in other containers:
+ * while CB is only called for items present in the table, and is
+ * therefore O(number of elements), the iterator needs to go through
+ * all the table, which is proportional to O(size of table).
+ * START_AFTER and the returned iterator are key where the iteration
+ * stopped. */
+void *dict_each(struct dict *dict, void *start_after,
+ enum callback_status (*cb)(void *, void *, void *), void *data);
+
+#define DICT_EACH(DICTP, KEY_TYPE, VALUE_TYPE, START_AFTER, CB, DATA) \
+ /* xxx GCC-ism necessary to get in the safety latches. */ \
+ ({ \
+ assert((DICTP)->keys.elt_size == sizeof(KEY_TYPE)); \
+ assert((DICTP)->values.elt_size == sizeof(VALUE_TYPE)); \
+ /* Check that CB is typed properly. */ \
+ enum callback_status (*_cb)(KEY_TYPE *, VALUE_TYPE *, \
+ void *) = CB; \
+ KEY_TYPE *start_after = (START_AFTER); \
+ (KEY_TYPE *)dict_each((DICTP), start_after, \
+ (enum callback_status \
+ (*)(void *, void *, void *))_cb, \
+ (DATA)); \
+ })
+
+/* A callback for hashing integers. */
+size_t dict_hash_int(const int *key);
+
+/* An equality predicate callback for integers. */
+int dict_eq_int(const int *key1, const int *key2);
+
+/* A callback for hashing NULL-terminated strings. */
+size_t dict_hash_string(const char **key);
+
+/* An equality predicate callback for strings. */
+int dict_eq_string(const char **key1, const char **key2);
#endif /* _DICT_H_ */
diff --git a/library.c b/library.c
index b5f6386..3d27917 100644
--- a/library.c
+++ b/library.c
@@ -68,31 +68,26 @@
}
#endif
-unsigned int
-target_address_hash(const void *key)
+size_t
+arch_addr_hash(const arch_addr_t *addr)
{
- /* XXX this assumes that key is passed by value. */
union {
arch_addr_t addr;
- unsigned int ints[sizeof(arch_addr_t)
- / sizeof(unsigned int)];
- } u = { .addr = (arch_addr_t)key };
+ int ints[sizeof(arch_addr_t)
+ / sizeof(unsigned int)];
+ } u = { .addr = *addr };
size_t i;
- unsigned int h = 0;
+ size_t h = 0;
for (i = 0; i < sizeof(u.ints) / sizeof(*u.ints); ++i)
- h ^= dict_key2hash_int((void *)(uintptr_t)u.ints[i]);
+ h ^= dict_hash_int(&u.ints[i]);
return h;
}
int
-target_address_cmp(const void *key1, const void *key2)
+arch_addr_eq(const arch_addr_t *addr1, const arch_addr_t *addr2)
{
- /* XXX this assumes that key is passed by value. */
- arch_addr_t addr1 = (arch_addr_t)key1;
- arch_addr_t addr2 = (arch_addr_t)key2;
- return addr1 < addr2 ? 1
- : addr1 > addr2 ? -1 : 0;
+ return *addr1 == *addr2;
}
/* If the other symbol owns the name, we need to make the copy, so
diff --git a/library.h b/library.h
index 74e1df2..206d6d7 100644
--- a/library.h
+++ b/library.h
@@ -34,8 +34,8 @@
};
/* Dict interface. */
-unsigned int target_address_hash(const void *key);
-int target_address_cmp(const void *key1, const void *key2);
+size_t arch_addr_hash(const arch_addr_t *addr);
+int arch_addr_eq(const arch_addr_t *addr1, const arch_addr_t *addr2);
/* For handling -l. */
struct library_exported_name {
diff --git a/output.c b/output.c
index 04a0138..22eda77 100644
--- a/output.c
+++ b/output.c
@@ -48,7 +48,7 @@
/* TODO FIXME XXX: include in common.h: */
extern struct timeval current_time_spent;
-Dict *dict_opt_c = NULL;
+struct dict *dict_opt_c = NULL;
static struct process *current_proc = 0;
static size_t current_depth = 0;
@@ -501,6 +501,12 @@
stel->out.need_delim = need_delim;
}
+static void
+free_stringp_cb(const char **stringp, void *data)
+{
+ free((char *)*stringp);
+}
+
void
output_right(enum tof type, struct process *proc, struct library_symbol *libsym)
{
@@ -509,26 +515,41 @@
if (func == NULL)
return;
+again:
if (options.summary) {
- struct opt_c_struct *st;
- if (!dict_opt_c) {
- dict_opt_c =
- dict_init(dict_key2hash_string,
- dict_key_cmp_string);
- }
- st = dict_find_entry(dict_opt_c, function_name);
- if (!st) {
- char *na;
- st = malloc(sizeof(struct opt_c_struct));
- na = strdup(function_name);
- if (!st || !na) {
- perror("malloc()");
- exit(1);
+ if (dict_opt_c == NULL) {
+ dict_opt_c = malloc(sizeof(*dict_opt_c));
+ if (dict_opt_c == NULL) {
+ oom:
+ fprintf(stderr,
+ "Can't allocate memory for "
+ "keeping track of -c.\n");
+ free(dict_opt_c);
+ options.summary = 0;
+ goto again;
}
- st->count = 0;
- st->tv.tv_sec = st->tv.tv_usec = 0;
- dict_enter(dict_opt_c, na, st);
+ DICT_INIT(dict_opt_c, const char *, struct opt_c_struct,
+ dict_hash_string, dict_eq_string, NULL);
}
+
+ struct opt_c_struct *st = DICT_FIND(dict_opt_c, &function_name,
+ struct opt_c_struct);
+ if (st == NULL) {
+ const char *na = strdup(function_name);
+ struct opt_c_struct new_st = {.count = 0, .tv = {0, 0}};
+ if (na == NULL
+ || DICT_INSERT(dict_opt_c, &na, &new_st) < 0) {
+ free((char *)na);
+ DICT_DESTROY(dict_opt_c, const char *,
+ struct opt_c_struct,
+ free_stringp_cb, NULL, NULL);
+ goto oom;
+ }
+ st = DICT_FIND(dict_opt_c, &function_name,
+ struct opt_c_struct);
+ assert(st != NULL);
+ }
+
if (st->tv.tv_usec + current_time_spent.tv_usec > 1000000) {
st->tv.tv_usec += current_time_spent.tv_usec - 1000000;
st->tv.tv_sec++;
@@ -537,11 +558,9 @@
}
st->count++;
st->tv.tv_sec += current_time_spent.tv_sec;
-
-// fprintf(options.output, "%s <%lu.%06d>\n", function_name,
-// current_time_spent.tv_sec, (int)current_time_spent.tv_usec);
return;
}
+
if (current_proc && (current_proc != proc ||
current_depth != proc->callstack_depth)) {
fprintf(options.output, " <unfinished ...>\n");
diff --git a/proc.c b/proc.c
index db3f645..ea44e29 100644
--- a/proc.c
+++ b/proc.c
@@ -121,8 +121,12 @@
if (proc->filename == NULL) {
fail:
free(proc->filename);
- if (proc->breakpoints != NULL)
- dict_clear(proc->breakpoints);
+ if (proc->breakpoints != NULL) {
+ dict_destroy(proc->breakpoints,
+ NULL, NULL, NULL);
+ free(proc->breakpoints);
+ proc->breakpoints = NULL;
+ }
return -1;
}
}
@@ -134,10 +138,12 @@
goto fail;
if (proc->leader == proc) {
- proc->breakpoints = dict_init(target_address_hash,
- target_address_cmp);
+ proc->breakpoints = malloc(sizeof(*proc->breakpoints));
if (proc->breakpoints == NULL)
goto fail;
+ DICT_INIT(proc->breakpoints,
+ arch_addr_t, struct breakpoint *,
+ arch_addr_hash, arch_addr_eq, NULL);
} else {
proc->breakpoints = NULL;
}
@@ -153,7 +159,8 @@
static void
process_bare_destroy(struct process *proc, int was_exec)
{
- dict_clear(proc->breakpoints);
+ dict_destroy(proc->breakpoints, NULL, NULL, NULL);
+ free(proc->breakpoints);
if (!was_exec) {
free(proc->filename);
unlist_process(proc);
@@ -249,7 +256,8 @@
/* Breakpoints. */
if (proc->breakpoints != NULL) {
proc_each_breakpoint(proc, NULL, destroy_breakpoint_cb, NULL);
- dict_clear(proc->breakpoints);
+ dict_destroy(proc->breakpoints, NULL, NULL, NULL);
+ free(proc->breakpoints);
proc->breakpoints = NULL;
}
@@ -299,31 +307,27 @@
struct clone_single_bp_data {
struct process *old_proc;
struct process *new_proc;
- int error;
};
-static void
-clone_single_bp(void *key, void *value, void *u)
+static enum callback_status
+clone_single_bp(arch_addr_t *key, struct breakpoint **bpp, void *u)
{
- struct breakpoint *bp = value;
+ struct breakpoint *bp = *bpp;
struct clone_single_bp_data *data = u;
- /* Don't bother if there were errors anyway. */
- if (data->error != 0)
- return;
-
struct breakpoint *clone = malloc(sizeof(*clone));
if (clone == NULL
|| breakpoint_clone(clone, data->new_proc,
bp, data->old_proc) < 0) {
fail:
free(clone);
- data->error = -1;
+ return CBS_STOP;
}
if (proc_add_breakpoint(data->new_proc->leader, clone) < 0) {
breakpoint_destroy(clone);
goto fail;
}
+ return CBS_CONT;
}
int
@@ -373,10 +377,10 @@
struct clone_single_bp_data data = {
.old_proc = proc,
.new_proc = retp,
- .error = 0,
};
- dict_apply_to_all(proc->leader->breakpoints, &clone_single_bp, &data);
- if (data.error < 0)
+ if (DICT_EACH(proc->leader->breakpoints,
+ arch_addr_t, struct breakpoint *, NULL,
+ clone_single_bp, &data) != NULL)
goto fail2;
/* And finally the call stack. */
@@ -747,9 +751,9 @@
* be also custom-allocated, and we would really need to swap
* the two: delete the one now in the dictionary, swap values
* around, and put the new breakpoint back in. */
- struct breakpoint *bp = dict_find_entry(proc->breakpoints,
- bp_addr);
- if (bp != NULL) {
+ struct breakpoint **found = DICT_FIND(proc->breakpoints,
+ &bp_addr, struct breakpoint *);
+ if (found != NULL) {
/* MIPS backend makes duplicate requests. This is
* likely a bug in the backend. Currently there's no
* point assigning more than one symbol to a
@@ -763,13 +767,13 @@
* http://lists.alioth.debian.org/pipermail/ltrace-devel/2012-November/000770.html
*/
#ifndef __mips__
- assert(bp->libsym == NULL);
- bp->libsym = libsym;
+ assert((*found)->libsym == NULL);
+ (*found)->libsym = libsym;
#endif
return 0;
}
- bp = malloc(sizeof(*bp));
+ struct breakpoint *bp = malloc(sizeof(*bp));
if (bp == NULL
|| breakpoint_init(bp, proc, bp_addr, libsym) < 0) {
fail:
@@ -920,9 +924,9 @@
/* XXX We might merge bp->libsym instead of the following
* assert, but that's not necessary right now. Read the
* comment in breakpoint_for_symbol. */
- assert(dict_find_entry(proc->breakpoints, bp->addr) == NULL);
+ assert(dict_find(proc->breakpoints, &bp->addr) == NULL);
- if (dict_enter(proc->breakpoints, bp->addr, bp) < 0) {
+ if (DICT_INSERT(proc->breakpoints, &bp->addr, &bp) < 0) {
fprintf(stderr,
"couldn't enter breakpoint %s@%p to dictionary: %s\n",
breakpoint_name(bp), bp->addr, strerror(errno));
@@ -938,16 +942,13 @@
debug(DEBUG_FUNCTION, "proc_remove_breakpoint(pid=%d, %s@%p)",
proc->pid, breakpoint_name(bp), bp->addr);
check_leader(proc);
- struct breakpoint *removed = dict_remove(proc->breakpoints, bp->addr);
- assert(removed == bp);
+ int rc = DICT_ERASE(proc->breakpoints, &bp->addr, struct breakpoint *,
+ NULL, NULL, NULL);
+ assert(rc == 0);
}
-/* Dict doesn't support iteration restarts, so here's this contraption
- * for now. XXX add restarts to dict. */
struct each_breakpoint_data
{
- void *start;
- void *end;
struct process *proc;
enum callback_status (*cb)(struct process *proc,
struct breakpoint *bp,
@@ -955,25 +956,11 @@
void *cb_data;
};
-static void
-each_breakpoint_cb(void *key, void *value, void *d)
+static enum callback_status
+each_breakpoint_cb(arch_addr_t *key, struct breakpoint **bpp, void *d)
{
struct each_breakpoint_data *data = d;
- if (data->end != NULL)
- return;
- if (data->start == key)
- data->start = NULL;
-
- if (data->start == NULL) {
- switch (data->cb(data->proc, value, data->cb_data)) {
- case CBS_FAIL:
- /* XXX handle me */
- case CBS_STOP:
- data->end = key;
- case CBS_CONT:
- return;
- }
- }
+ return data->cb(data->proc, *bpp, data->cb_data);
}
void *
@@ -983,13 +970,13 @@
void *data), void *data)
{
struct each_breakpoint_data dd = {
- .start = start,
.proc = proc,
.cb = cb,
.cb_data = data,
};
- dict_apply_to_all(proc->breakpoints, &each_breakpoint_cb, &dd);
- return dd.end;
+ return DICT_EACH(proc->breakpoints,
+ arch_addr_t, struct breakpoint *, start,
+ &each_breakpoint_cb, &dd);
}
int
diff --git a/proc.h b/proc.h
index 04c0ef7..2e35319 100644
--- a/proc.h
+++ b/proc.h
@@ -87,10 +87,8 @@
/* Dictionary of breakpoints (which is a mapping
* address->breakpoint). This is NULL for non-leader
- * processes. XXX note that we store addresses (keys) by
- * value. That assumes that arch_addr_t fits in host
- * pointer. */
- Dict * breakpoints;
+ * processes. */
+ struct dict *breakpoints;
int mask_32bit; /* 1 if 64-bit ltrace is tracing 32-bit process */
unsigned int personality;
diff --git a/summary.c b/summary.c
index 937da1a..e9203e3 100644
--- a/summary.c
+++ b/summary.c
@@ -1,5 +1,6 @@
/*
* This file is part of ltrace.
+ * Copyright (C) 2012 Petr Machata, Red Hat Inc.
* Copyright (C) 2003,2008,2009 Juan Cespedes
* Copyright (C) 2006 Ian Wienand
*
@@ -37,16 +38,15 @@
static int tot_count = 0;
static unsigned long int tot_usecs = 0;
-static void fill_struct(void *key, void *value, void *data)
+static enum callback_status
+fill_struct(const char **namep, struct opt_c_struct *st, void *data)
{
- struct opt_c_struct *st = (struct opt_c_struct *)value;
-
entries = realloc(entries, (num_entries + 1) * sizeof(struct entry_st));
if (!entries) {
perror("realloc()");
exit(1);
}
- entries[num_entries].name = (char *)key;
+ entries[num_entries].name = (char *)*namep;
entries[num_entries].count = st->count;
entries[num_entries].tv = st->tv;
@@ -55,6 +55,7 @@
tot_usecs += st->tv.tv_usec;
num_entries++;
+ return CBS_CONT;
}
static int compar(const void *a, const void *b)
@@ -78,7 +79,8 @@
num_entries = 0;
entries = NULL;
- dict_apply_to_all(dict_opt_c, fill_struct, NULL);
+ DICT_EACH(dict_opt_c, const char *, struct opt_c_struct, NULL,
+ fill_struct, NULL);
qsort(entries, num_entries, sizeof(*entries), compar);
diff --git a/sysdeps/linux-gnu/mips/trace.c b/sysdeps/linux-gnu/mips/trace.c
index f420424..73b42c9 100644
--- a/sysdeps/linux-gnu/mips/trace.c
+++ b/sysdeps/linux-gnu/mips/trace.c
@@ -278,7 +278,7 @@
while (nr-- > 0) {
arch_addr_t baddr = (arch_addr_t) newpcs[nr];
/* Not sure what to do here. We've already got a bp? */
- if (dict_find_entry(proc->leader->breakpoints, baddr) != NULL) {
+ if (dict_find(proc->leader->breakpoints, &baddr) != NULL) {
fprintf(stderr, "skip %p %p\n", baddr, add_cb_data);
continue;
}
diff --git a/sysdeps/linux-gnu/trace.c b/sysdeps/linux-gnu/trace.c
index d10e665..2d9ade3 100644
--- a/sysdeps/linux-gnu/trace.c
+++ b/sysdeps/linux-gnu/trace.c
@@ -323,10 +323,11 @@
static void
ugly_workaround(struct process *proc)
{
- void *ip = get_instruction_pointer(proc);
- struct breakpoint *sbp = dict_find_entry(proc->leader->breakpoints, ip);
- if (sbp != NULL)
- enable_breakpoint(proc, sbp);
+ arch_addr_t ip = get_instruction_pointer(proc);
+ struct breakpoint **found = DICT_FIND(proc->leader->breakpoints, &ip,
+ struct breakpoint *);
+ if (found != NULL)
+ enable_breakpoint(proc, *found);
else
insert_breakpoint(proc, ip, NULL);
ptrace(PTRACE_CONT, proc->pid, 0, 0);
@@ -1031,7 +1032,7 @@
struct process_vfork_handler
{
struct event_handler super;
- void *bp_addr;
+ arch_addr_t bp_addr;
};
static Event *
@@ -1042,7 +1043,6 @@
event->proc->pid, event->type);
struct process_vfork_handler *self = (void *)super;
- struct breakpoint *sbp;
assert(self != NULL);
switch (event->type) {
@@ -1058,10 +1058,12 @@
/* Smuggle back in the vfork return breakpoint, so
* that our parent can trip over it once again. */
if (self->bp_addr != 0) {
- sbp = dict_find_entry(event->proc->leader->breakpoints,
- self->bp_addr);
- if (sbp != NULL)
- assert(sbp->libsym == NULL);
+ struct breakpoint **found
+ = DICT_FIND(event->proc->leader->breakpoints,
+ &self->bp_addr,
+ struct breakpoint *);
+ if (found != NULL)
+ assert((*found)->libsym == NULL);
/* We don't mind failing that, it's not a big
* deal to not display one extra vfork return. */
insert_breakpoint(event->proc->parent,