Container Data Structures

Data Structures
struct	_drvector_t
struct	_hashtable_config_t

Macros
#define	DRTABLE_INVALID_INDEX   ((ptr_uint_t)-1)

Typedefs
typedef struct _drvector_t	drvector_t
typedef struct _hashtable_config_t	hashtable_config_t

Enumerations
enum	drtable_flags_t {   DRTABLE_MEM_REACHABLE = 0x1,   DRTABLE_MEM_32BIT = 0x2,   DRTABLE_ALLOC_COMPACT = 0x4 }
enum	hash_type_t {   HASH_INTPTR,   HASH_STRING,   HASH_STRING_NOCASE,   HASH_CUSTOM }
enum	hasthable_persist_flags_t {   DR_HASHPERS_PAYLOAD_IS_POINTER = 0x0001,   DR_HASHPERS_CLONE_PAYLOAD = 0x0002,   DR_HASHPERS_REBASE_KEY = 0x0004,   DR_HASHPERS_ONLY_IN_RANGE = 0x0008,   DR_HASHPERS_ONLY_PERSISTED = 0x0010 }

Functions
void *	drtable_create (ptr_uint_t capacity, size_t entry_size, uint flags, bool synch, void(*free_entry_func)(ptr_uint_t idx, void *entry, void *user_data))
void *	drtable_alloc (void *tab, ptr_uint_t num_entries, ptr_uint_t *idx_ptr)
void	drtable_destroy (void *tab, void *user_data)
void	drtable_iterate (void *tab, void *iter_data, bool(*iter_func)(ptr_uint_t id, void *, void *))
void *	drtable_get_entry (void *tab, ptr_uint_t idx)
ptr_uint_t	drtable_get_index (void *tab, void *ptr)
void	drtable_lock (void *tab)
void	drtable_unlock (void *tab)
ptr_uint_t	drtable_num_entries (void *tab)
ptr_uint_t	drtable_dump_entries (void *tab, file_t log)
bool	drvector_init (drvector_t *vec, uint initial_capacity, bool synch, void(*free_data_func)(void *))
void *	drvector_get_entry (drvector_t *vec, uint idx)
bool	drvector_set_entry (drvector_t *vec, uint idx, void *data)
bool	drvector_append (drvector_t *vec, void *data)
bool	drvector_delete (drvector_t *vec)
void	drvector_lock (drvector_t *vec)
void	drvector_unlock (drvector_t *vec)
bool	stri_eq (const char *s1, const char *s2)
void	hashtable_global_config (void *(*alloc_func)(size_t), void(*free_func)(void *, size_t), void(*assert_fail_func)(const char *))
void	hashtable_init (hashtable_t *table, uint num_bits, hash_type_t hashtype, bool str_dup)
void	hashtable_init_ex (hashtable_t *table, uint num_bits, hash_type_t hashtype, bool str_dup, bool synch, void(*free_payload_func)(void *), uint(*hash_key_func)(void *), bool(*cmp_key_func)(void *, void *))
void	hashtable_configure (hashtable_t *table, hashtable_config_t *config)
void *	hashtable_lookup (hashtable_t *table, void *key)
bool	hashtable_add (hashtable_t *table, void *key, void *payload)
void *	hashtable_add_replace (hashtable_t *table, void *key, void *payload)
bool	hashtable_remove (hashtable_t *table, void *key)
bool	hashtable_remove_range (hashtable_t *table, void *start, void *end)
void	hashtable_apply_to_all_payloads (hashtable_t *table, void(*apply_func)(void *payload))
void	hashtable_apply_to_all_payloads_user_data (hashtable_t *table, void(*apply_func)(void *payload, void *user_data), void *user_data)
void	hashtable_clear (hashtable_t *table)
void	hashtable_delete (hashtable_t *table)
void	hashtable_lock (hashtable_t *table)
void	hashtable_unlock (hashtable_t *table)
bool	hashtable_lock_self_owns (hashtable_t *table)
size_t	hashtable_persist_size (void *drcontext, hashtable_t *table, size_t entry_size, void *perscxt, hasthable_persist_flags_t flags)
bool	hashtable_persist (void *drcontext, hashtable_t *table, size_t entry_size, file_t fd, void *perscxt, hasthable_persist_flags_t flags)
bool	hashtable_resurrect (void *drcontext, byte **map, hashtable_t *table, size_t entry_size, void *perscxt, hasthable_persist_flags_t flags, bool(*process_payload)(void *key, void *payload, ptr_int_t shift))

Detailed Description

Macro Definition Documentation

DRTABLE_INVALID_INDEX

#define DRTABLE_INVALID_INDEX   ((ptr_uint_t)-1)

Invalid index of drtable

Typedef Documentation

drvector_t

typedef struct _drvector_t drvector_t

The storage for a vector.

hashtable_config_t

typedef struct _hashtable_config_t hashtable_config_t

Configuration parameters for a hashtable.

Enumeration Type Documentation

drtable_flags_t

enum drtable_flags_t

Flags used for drtable_create

Enumerator
DRTABLE_MEM_REACHABLE	allocated table entries must be reachable from code cache
DRTABLE_MEM_32BIT	Allocates table entries from the addresss space that can be converted to a 32-bit int.
DRTABLE_ALLOC_COMPACT	Allocates table entries as compactly as possible, which may return indics in a random order.

hash_type_t

enum hash_type_t

The type of hash key

Enumerator
HASH_INTPTR	A pointer-sized integer or pointer
HASH_STRING	A case-sensitive string
HASH_STRING_NOCASE	A case-insensitive string
HASH_CUSTOM	A custom key. Hash and compare operations must be provided in hashtable_init_ex(). The hash operation can return a full uint, as its result will be truncated via a mod of the hash key bit size. This allows for resizing the table without changing the hash operation.

hasthable_persist_flags_t

enum hasthable_persist_flags_t

Flags to control hashtable persistence

Enumerator
DR_HASHPERS_PAYLOAD_IS_POINTER	Valid for hashtable_persist() and hashtable_resurrect() and the same value must be passed to both. Treats payloads as pointers to allocated memory. By default payloads are treated as inlined values if this flag is not set.
DR_HASHPERS_CLONE_PAYLOAD	Valid for hashtable_resurrect(). Only applies if DR_HASHPERS_KEY_IS_POINTER. Performs a shallow clone of the payload upon resurrection. If this flag is not set, the payloads will remain pointing into the mapped file.
DR_HASHPERS_REBASE_KEY	Valid for hashtable_persist_size(), hashtable_persist(), and hashtable_resurrect(), and the same value must be passed to all. Only applies if keys are of type HASH_INTPTR. Adjusts each key by the difference in the persist-time start address of the persisted code region and the resurrected start address. The value of this flag must match across all three calls hashtable_persist_size(), hashtable_persist(), and hashtable_resurrect().
DR_HASHPERS_ONLY_IN_RANGE	Valid for hashtable_persist_size() and hashtable_persist() and the same value must be passed to both. Only applies if keys are of type HASH_INTPTR. Only persists entries whose key is in the address range being persisted.
DR_HASHPERS_ONLY_PERSISTED	Valid for hashtable_persist_size() and hashtable_persist() and the same value must be passed to both. Only applies if keys are of type HASH_INTPTR. Only persists entries for which dr_fragment_persistable() returns true.

Function Documentation

drtable_alloc()

void* drtable_alloc	(	void *	tab,
		ptr_uint_t	num_entries,
		ptr_uint_t *	idx_ptr
	)

Allocates memory for an array of num_entries table entries, and returns a pointer to the allocated memory. Returns NULL if fails. If idx_ptr is not NULL, the index for the first entry is returned in idx_ptr, and all the entries from the same allocation can be referred to as index + n.

drtable_create()

void* drtable_create	(	ptr_uint_t	capacity,
		size_t	entry_size,
		uint	flags,
		bool	synch,
		void(*)(ptr_uint_t idx, void *entry, void *user_data)	free_entry_func
	)

Creates a drtable with the given parameters.

Parameters

[in]	capacity	The approximate number of entries for the table. The capacity is only a suggestion for better memory usage.
[in]	entry_size	The size of each table entry, which should be greater than 0 and smaller than USHRT_MAX (65535).
[in]	flags	The flags to specify the features of the table.
[in]	synch	Whether to synchronize each operation. Even when synch is false, the table's lock is initialized and can be used via drtable_lock() and drtable_unlock(), allowing the caller to extend synchronization beyond just the operation in question.
[in]	free_entry_func	The callback for freeing each table entry. Leave it NULL if no callback is needed.

drtable_destroy()

void drtable_destroy	(	void *	tab,
		void *	user_data
	)

Destroys all storage for the table. The user_data is passed to each free_entry_func if specified.

drtable_dump_entries()

ptr_uint_t drtable_dump_entries	(	void *	tab,
		file_t	log
	)

Dumps all the table entries as an array into a file in binary format. There is no header add, so the user should add one if so desired. Returns the number of entries dumped.

drtable_get_entry()

void* drtable_get_entry	(	void *	tab,
		ptr_uint_t	idx
	)

Returns a pointer to the entry at index idx. Returns NULL if the entry for idx is not allocated.

drtable_get_index()

ptr_uint_t drtable_get_index	(	void *	tab,
		void *	ptr
	)

Returns an index to the entry pointed at by ptr. Returns DRTABLE_INVALID_INDEX if ptr does not point to any allocated entries.

drtable_iterate()

void drtable_iterate	(	void *	tab,
		void *	iter_data,
		bool(*)(ptr_uint_t id, void *, void *)	iter_func
	)

Iterates over entries in the table and call the callback function.

Parameters

[in]	tab	The drtable to be operated on.
[in]	iter_data	Iteration data passed to iter_func.
[in]	iter_func	The callback for iterating each table entry. Returns false to stop iterating.

drtable_lock()

void drtable_lock

(

void *

tab

)

Acquires the table lock.

drtable_num_entries()

ptr_uint_t drtable_num_entries

(

void *

tab

)

Returns the number of entries in the table.

drtable_unlock()

void drtable_unlock

(

void *

tab

)

Releases the table lock.

drvector_append()

bool drvector_append	(	drvector_t *	vec,
		void *	data
	)

Adds a new entry to the end of the vector, resizing it if necessary. If drvector_set_entry() has been called, this will add to the index beyond the last index passed to drvector_set_entry().

drvector_delete()

bool drvector_delete

(

drvector_t *

vec

)

Destroys all storage for the vector. If free_payload_func was specified calls it for each payload.

drvector_get_entry()

void* drvector_get_entry	(	drvector_t *	vec,
		uint	idx
	)

Returns the entry at index idx. For an unsychronized table, the caller is free to directly access the array field of vec.

drvector_init()

bool drvector_init	(	drvector_t *	vec,
		uint	initial_capacity,
		bool	synch,
		void(*)(void *)	free_data_func
	)

Initializes a drvector with the given parameters

Parameters

[out]	vec	The vector to be initialized.
[in]	initial_capacity	The initial number of entries allocated for the vector.
[in]	synch	Whether to synchronize each operation. Even when synch is false, the vector's lock is initialized and can be used via vector_lock() and vector_unlock(), allowing the caller to extend synchronization beyond just the operation in question, to include accessing a looked-up payload, e.g.
[in]	free_data_func	A callback for freeing each data item. Leave it NULL if no callback is needed.

drvector_lock()

void drvector_lock

(

drvector_t *

vec

)

Acquires the vector lock.

drvector_set_entry()

bool drvector_set_entry	(	drvector_t *	vec,
		uint	idx,
		void *	data
	)

Sets the entry at index idx to data. For an unsychronized table, the caller is free to directly set the array field of vec. Entries in between the last set index and idx are left uninitialized. Returns whether successful.

drvector_unlock()

void drvector_unlock

(

drvector_t *

vec

)

Releases the vector lock.

hashtable_add()

bool hashtable_add	(	hashtable_t *	table,
		void *	key,
		void *	payload
	)

Adds a new entry. Returns false if an entry for key already exists.

Note

Never use NULL as a payload as that is used for a lookup failure.

hashtable_add_replace()

void* hashtable_add_replace	(	hashtable_t *	table,
		void *	key,
		void *	payload
	)

Adds a new entry, replacing an existing entry if any. Returns the old payload, or NULL if there was no existing entry.

Note

Never use NULL as a payload as that is used for a lookup failure.

hashtable_apply_to_all_payloads()

void hashtable_apply_to_all_payloads	(	hashtable_t *	table,
		void(*)(void *payload)	apply_func
	)

Calls the apply_func for each payload.

Parameters

table	The hashtable to apply the function.
apply_func	A pointer to a function that is called for all payloads stored in the map.

hashtable_apply_to_all_payloads_user_data()

void hashtable_apply_to_all_payloads_user_data	(	hashtable_t *	table,
		void(*)(void *payload, void *user_data)	apply_func,
		void *	user_data
	)

Calls the apply_func for each payload with user data. Similar to hashtable_apply_to_all_payloads().

Parameters

table	The hashtable to apply the function.
apply_func	A pointer to a function that is called for all payloads stored in the map. It also takes user data as a parameter.
user_data	User data that is available when iterating through payloads.

hashtable_clear()

void hashtable_clear

(

hashtable_t *

table

)

Removes all entries from the table. If free_payload_func was specified calls it for each payload.

hashtable_configure()

void hashtable_configure	(	hashtable_t *	table,
		hashtable_config_t *	config
	)

Configures optional parameters of hashtable operation.

hashtable_delete()

void hashtable_delete

(

hashtable_t *

table

)

Destroys all storage for the table, including all entries and the table itself. If free_payload_func was specified calls it for each payload.

hashtable_global_config()

void hashtable_global_config	(	void *(*)(size_t)	alloc_func,
		void(*)(void *, size_t)	free_func,
		void(*)(const char *)	assert_fail_func
	)

The hashtable has parametrized heap and assert routines for flexibility. This routine must be called BEFORE any other hashtable_ routine; else, the defaults will be used.

hashtable_init()

void hashtable_init	(	hashtable_t *	table,
		uint	num_bits,
		hash_type_t	hashtype,
		bool	str_dup
	)

Initializes a hashtable with the given size, hash type, and whether to duplicate string keys. All operations are synchronized by default.

hashtable_init_ex()

void hashtable_init_ex	(	hashtable_t *	table,
		uint	num_bits,
		hash_type_t	hashtype,
		bool	str_dup,
		bool	synch,
		void(*)(void *)	free_payload_func,
		uint(*)(void *)	hash_key_func,
		bool(*)(void *, void *)	cmp_key_func
	)

Initializes a hashtable with the given parameters.

Parameters

[out]	table	The hashtable to be initialized.
[in]	num_bits	The initial number of bits to use for the hash key which determines the initial size of the table itself. The result of the hash function will be truncated to this size. This size will be increased when the table is resized (resizing always doubles the size).
[in]	hashtype	The type of hash to perform.
[in]	str_dup	Whether to duplicate string keys.
[in]	synch	Whether to synchronize each operation. Even when synch is false, the hashtable's lock is initialized and can be used via hashtable_lock() and hashtable_unlock(), allowing the caller to extend synchronization beyond just the operation in question, to include accessing a looked-up payload, e.g.
[in]	free_payload_func	A callback for freeing each payload. Leave it NULL if no callback is needed.
[in]	hash_key_func	A callback for hashing a key. Leave it NULL if no callback is needed and the default is to be used. For HASH_CUSTOM, a callback must be provided. The hash operation can return a full uint, as its result will be truncated via a mod of the hash key bit size. This allows for resizing the table without changing the hash operation.
[in]	cmp_key_func	A callback for comparing two keys. Leave it NULL if no callback is needed and the default is to be used. For HASH_CUSTOM, a callback must be provided.

This hashtable uses closed addressing. For an open-address hashtable, consider dr_hashtable_create().

hashtable_lock()

void hashtable_lock

(

hashtable_t *

table

)

Acquires the hashtable lock.

hashtable_lock_self_owns()

bool hashtable_lock_self_owns

(

hashtable_t *

table

)

Returns true iff the hashtable lock is owned by the calling thread. This routine is only available in debug builds. In release builds it always returns true.

hashtable_lookup()

void* hashtable_lookup	(	hashtable_t *	table,
		void *	key
	)

Returns the payload for the given key, or NULL if the key is not found

hashtable_persist()

bool hashtable_persist	(	void *	drcontext,
		hashtable_t *	table,
		size_t	entry_size,
		file_t	fd,
		void *	perscxt,
		hasthable_persist_flags_t	flags
	)

For use persisting a table of single-alloc entries (i.e., via a shallow copy) for loading into a live table later.

These routines assume that the caller is synchronizing across the call to hashtable_persist_size() and hashtable_persist(). If these are called using DR's persistence interface, DR guarantees synchronization.

hashtable_persist_size() must be called immediately prior to calling hashtable_persist().

Parameters

[in]	drcontext	The opaque DR context
[in]	table	The table to persist
[in]	entry_size	The size of each table entry payload
[in]	fd	The target persisted file handle
[in]	perscxt	The opaque persistence context from DR's persist events
[in]	flags	Controls various aspects of the persistence

hashtable_persist_size()

size_t hashtable_persist_size	(	void *	drcontext,
		hashtable_t *	table,
		size_t	entry_size,
		void *	perscxt,
		hasthable_persist_flags_t	flags
	)

For use persisting a table of single-alloc entries (i.e., via a shallow copy) for loading into a live table later.

These routines assume that the caller is synchronizing across the call to hashtable_persist_size() and hashtable_persist(). If these are called using DR's persistence interface, DR guarantees synchronization.

Parameters

[in]	drcontext	The opaque DR context
[in]	table	The table to persist
[in]	entry_size	The size of each table entry payload
[in]	perscxt	The opaque persistence context from DR's persist events
[in]	flags	Controls various aspects of the persistence

hashtable_remove()

bool hashtable_remove	(	hashtable_t *	table,
		void *	key
	)

Removes the entry for key. If free_payload_func was specified calls it for the payload being removed. Returns false if no such entry exists.

hashtable_remove_range()

bool hashtable_remove_range	(	hashtable_t *	table,
		void *	start,
		void *	end
	)

Removes all entries with key in [start..end). If free_payload_func was specified calls it for each payload being removed. Returns false if no such entry exists.

hashtable_resurrect()

bool hashtable_resurrect	(	void *	drcontext,
		byte **	map,
		hashtable_t *	table,
		size_t	entry_size,
		void *	perscxt,
		hasthable_persist_flags_t	flags,
		bool(*)(void *key, void *payload, ptr_int_t shift)	process_payload
	)

For use persisting a table of single-alloc entries (i.e., via a shallow copy) for loading into a live table later.

Reads in entries from disk and adds them to the live table.

Parameters

[in]	drcontext	The opaque DR context
[in]	map	The mapped-in persisted file, pointing at the data written by hashtable_persist()
[in]	table	The live table to add to
[in]	entry_size	The size of each table entry payload
[in]	perscxt	The opaque persistence context from DR's persist events
[in]	flags	Controls various aspects of the persistence
[in]	process_payload	If non-NULL, calls process_payload instead of hashtable_add. process_payload can then adjust the paylod and if it wishes invoke hashtable_add.

hashtable_unlock()

void hashtable_unlock

(

hashtable_t *

table

)

Releases the hashtable lock.

stri_eq()

bool stri_eq	(	const char *	s1,
		const char *	s2
	)

Caseless string compare