commit 358436592befbdeb3249c5301f3e2b802de61aca Author: Nick Mathewson nickm@torproject.org Date: Mon Oct 14 15:05:47 2019 -0400

Edit 01b-collections.md a bit for md and missing content --- doc/HACKING/design/01b-collections.md | 24 +++++++++++++----------- 1 file changed, 13 insertions(+), 11 deletions(-)

diff --git a/doc/HACKING/design/01b-collections.md b/doc/HACKING/design/01b-collections.md index def60b0f1..ed6fdc907 100644 --- a/doc/HACKING/design/01b-collections.md +++ b/doc/HACKING/design/01b-collections.md @@ -4,27 +4,27 @@ ### 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. +`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 +All smartlists hold an array of `void *`. Whenever you expose a smartlist in an API you *must* document which types its pointers actually hold.

<!-- It would be neat to fix that, wouldn't it? -NM -->

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

+<!-- TODO: WRITE more about what you can do with smartlists. -->

### 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 +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" @@ -32,12 +32,14 @@ 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 +Unfortunately, the `sys/queue.h` macros vary significantly between the platforms that have them, so we provide our own variants in -src/ext/tor_queue.h . +`src/ext/tor_queue.h`.

-We also provide an intrusive hashtable implementation in src/ext/ht.h -. When you're using it, you'll need to define your own hash +We also provide an intrusive hashtable implementation in `src/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.

+<!-- TODO: WRITE about bloom filters, namemaps, bit-arrays, order functions. +-->