container Directory Reference

lib/container: Hash tables, dynamic arrays, bit arrays, etc.

More...

Files
file	bitarray.h [code]
	Implements a variable-sized (but non-resizeable) bit-array.
file	bloomfilt.c [code]
	Uses bitarray_t to implement a bloom filter.
file	bloomfilt.h [code]
	Header for bloomfilt.c.
file	handles.h [code]
	Macros for C weak-handle implementation.
file	map.c [code]
	Hash-table implementations of a string-to-void* map, and of a digest-to-void* map.
file	map.h [code]
	Headers for map.c.
file	namemap.c [code]
	Mappings between identifiers and 16-bit ints.
file	namemap.h [code]
	Header for namemap.c.
file	namemap_st.h [code]
	Internal declarations for namemap structure.
file	order.c [code]
	Functions for finding the n'th element of an array.
file	order.h [code]
	Header for order.c.
file	smartlist.c [code]
	Higher-level functions for the "smartlist" resizeable array abstraction.
file	smartlist.h [code]
	Header for smartlist.c.

Detailed Description

lib/container: Hash tables, dynamic arrays, bit arrays, etc.

Smartlists: Neither lists, nor especially smart.

For historical reasons, we call our dynamic-allocated array type smartlist_t. It can grow or shrink as elements are added and removed.

All smartlists hold an array of void *. Whenever you expose a smartlist in an API you must document which types its pointers actually hold.

Smartlists are created empty with smartlist_new() and freed with smartlist_free(). See the containers.h header documentation for more information; there are many convenience functions for commonly needed operations.

For low-level operations on smartlists, see also lib/smartlist_core.

Digest maps, string maps, and more.

Tor makes frequent use of maps from 160-bit digests, 256-bit digests, or nul-terminated strings to void *. These types are digestmap_t, digest256map_t, and strmap_t respectively. See the containers.h module documentation for more information.

Intrusive lists and hashtables

For performance-sensitive cases, we sometimes want to use "intrusive" collections: ones where the bookkeeping pointers are stuck inside the structures that belong to the collection. If you've used the BSD-style sys/queue.h macros, you'll be familiar with these.

Unfortunately, the sys/queue.h macros vary significantly between the platforms that have them, so we provide our own variants in ext/tor_queue.h.

We also provide an intrusive hashtable implementation in ext/ht.h. When you're using it, you'll need to define your own hash functions. If attacker-induced collisions are a worry here, use the cryptographic siphash24g function to extract hashes.