aboutsummaryrefslogtreecommitdiff
path: root/src/lib/container
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/container')
-rw-r--r--src/lib/container/.may_include9
-rw-r--r--src/lib/container/bitarray.h4
-rw-r--r--src/lib/container/bloomfilt.c4
-rw-r--r--src/lib/container/bloomfilt.h2
-rw-r--r--src/lib/container/buffers.c934
-rw-r--r--src/lib/container/buffers.h122
-rw-r--r--src/lib/container/handles.h25
-rw-r--r--src/lib/container/include.am7
-rw-r--r--src/lib/container/lib_container.md49
-rw-r--r--src/lib/container/map.c16
-rw-r--r--src/lib/container/map.h133
-rw-r--r--src/lib/container/namemap.c189
-rw-r--r--src/lib/container/namemap.h35
-rw-r--r--src/lib/container/namemap_st.h41
-rw-r--r--src/lib/container/order.c2
-rw-r--r--src/lib/container/order.h4
-rw-r--r--src/lib/container/smartlist.c14
-rw-r--r--src/lib/container/smartlist.h15
18 files changed, 434 insertions, 1171 deletions
diff --git a/src/lib/container/.may_include b/src/lib/container/.may_include
index 90de5eda40..81507527d3 100644
--- a/src/lib/container/.may_include
+++ b/src/lib/container/.may_include
@@ -7,12 +7,9 @@ lib/malloc/*.h
lib/err/*.h
lib/smartlist_core/*.h
lib/string/*.h
-lib/testsupport/testsupport.h
+lib/testsupport/*.h
lib/intmath/*.h
lib/log/*.h
-# XXXX I am unsure about this one. It's only here for buffers.c
-lib/time/*.h
-
-ht.h
-siphash.h
+ext/ht.h
+ext/siphash.h
diff --git a/src/lib/container/bitarray.h b/src/lib/container/bitarray.h
index 910d5fea65..41409e350a 100644
--- a/src/lib/container/bitarray.h
+++ b/src/lib/container/bitarray.h
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
#ifndef TOR_BITARRAY_H
@@ -83,4 +83,4 @@ bitarray_is_set(bitarray_t *b, int bit)
return b[bit >> BITARRAY_SHIFT] & (1u << (bit & BITARRAY_MASK));
}
-#endif /* !defined(TOR_CONTAINER_H) */
+#endif /* !defined(TOR_BITARRAY_H) */
diff --git a/src/lib/container/bloomfilt.c b/src/lib/container/bloomfilt.c
index 9aa9b1ee56..34b1265d81 100644
--- a/src/lib/container/bloomfilt.c
+++ b/src/lib/container/bloomfilt.c
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/**
@@ -14,7 +14,7 @@
#include "lib/container/bloomfilt.h"
#include "lib/intmath/bits.h"
#include "lib/log/util_bug.h"
-#include "siphash.h"
+#include "ext/siphash.h"
/** How many bloom-filter bits we set per address. This is twice the
* BLOOMFILT_N_HASHES value, since we split the siphash output into two 32-bit
diff --git a/src/lib/container/bloomfilt.h b/src/lib/container/bloomfilt.h
index 0ce18bd3ec..6d36056b5a 100644
--- a/src/lib/container/bloomfilt.h
+++ b/src/lib/container/bloomfilt.h
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
#ifndef TOR_BLOOMFILT_H
diff --git a/src/lib/container/buffers.c b/src/lib/container/buffers.c
deleted file mode 100644
index fe4cf7c385..0000000000
--- a/src/lib/container/buffers.c
+++ /dev/null
@@ -1,934 +0,0 @@
-/* Copyright (c) 2001 Matej Pfajfar.
- * Copyright (c) 2001-2004, Roger Dingledine.
- * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
-/* See LICENSE for licensing information */
-
-/**
- * \file buffers.c
- * \brief Implements a generic buffer interface.
- *
- * A buf_t is a (fairly) opaque byte-oriented FIFO that can read to or flush
- * from memory, sockets, file descriptors, TLS connections, or another buf_t.
- * Buffers are implemented as linked lists of memory chunks.
- *
- * All socket-backed and TLS-based connection_t objects have a pair of
- * buffers: one for incoming data, and one for outcoming data. These are fed
- * and drained from functions in connection.c, trigged by events that are
- * monitored in main.c.
- *
- * This module only handles the buffer implementation itself. To use a buffer
- * with the network, a compressor, or a TLS connection, see the other buffer_*
- * modules.
- **/
-
-#define BUFFERS_PRIVATE
-#include "orconfig.h"
-#include <stddef.h>
-#include "lib/container/buffers.h"
-#include "lib/cc/torint.h"
-#include "lib/log/log.h"
-#include "lib/log/util_bug.h"
-#include "lib/ctime/di_ops.h"
-#include "lib/malloc/malloc.h"
-#include "lib/string/printf.h"
-#include "lib/time/compat_time.h"
-
-#ifdef HAVE_UNISTD_H
-#include <unistd.h>
-#endif
-
-#include <stdlib.h>
-#include <string.h>
-
-//#define PARANOIA
-
-#ifdef PARANOIA
-/** Helper: If PARANOIA is defined, assert that the buffer in local variable
- * <b>buf</b> is well-formed. */
-#define check() STMT_BEGIN buf_assert_ok(buf); STMT_END
-#else
-#define check() STMT_NIL
-#endif /* defined(PARANOIA) */
-
-/* Implementation notes:
- *
- * After flirting with memmove, and dallying with ring-buffers, we're finally
- * getting up to speed with the 1970s and implementing buffers as a linked
- * list of small chunks. Each buffer has such a list; data is removed from
- * the head of the list, and added at the tail. The list is singly linked,
- * and the buffer keeps a pointer to the head and the tail.
- *
- * Every chunk, except the tail, contains at least one byte of data. Data in
- * each chunk is contiguous.
- *
- * When you need to treat the first N characters on a buffer as a contiguous
- * string, use the buf_pullup function to make them so. Don't do this more
- * than necessary.
- *
- * The major free Unix kernels have handled buffers like this since, like,
- * forever.
- */
-
-/* Chunk manipulation functions */
-
-#define CHUNK_HEADER_LEN offsetof(chunk_t, mem[0])
-
-/* We leave this many NUL bytes at the end of the buffer. */
-#ifdef DISABLE_MEMORY_SENTINELS
-#define SENTINEL_LEN 0
-#else
-#define SENTINEL_LEN 4
-#endif
-
-/* Header size plus NUL bytes at the end */
-#define CHUNK_OVERHEAD (CHUNK_HEADER_LEN + SENTINEL_LEN)
-
-/** Return the number of bytes needed to allocate a chunk to hold
- * <b>memlen</b> bytes. */
-#define CHUNK_ALLOC_SIZE(memlen) (CHUNK_OVERHEAD + (memlen))
-/** Return the number of usable bytes in a chunk allocated with
- * malloc(<b>memlen</b>). */
-#define CHUNK_SIZE_WITH_ALLOC(memlen) ((memlen) - CHUNK_OVERHEAD)
-
-#define DEBUG_SENTINEL
-
-#if defined(DEBUG_SENTINEL) && !defined(DISABLE_MEMORY_SENTINELS)
-#define DBG_S(s) s
-#else
-#define DBG_S(s) (void)0
-#endif
-
-#ifdef DISABLE_MEMORY_SENTINELS
-#define CHUNK_SET_SENTINEL(chunk, alloclen) STMT_NIL
-#else
-#define CHUNK_SET_SENTINEL(chunk, alloclen) do { \
- uint8_t *a = (uint8_t*) &(chunk)->mem[(chunk)->memlen]; \
- DBG_S(uint8_t *b = &((uint8_t*)(chunk))[(alloclen)-SENTINEL_LEN]); \
- DBG_S(tor_assert(a == b)); \
- memset(a,0,SENTINEL_LEN); \
- } while (0)
-#endif /* defined(DISABLE_MEMORY_SENTINELS) */
-
-/** Move all bytes stored in <b>chunk</b> to the front of <b>chunk</b>->mem,
- * to free up space at the end. */
-static inline void
-chunk_repack(chunk_t *chunk)
-{
- if (chunk->datalen && chunk->data != &chunk->mem[0]) {
- memmove(chunk->mem, chunk->data, chunk->datalen);
- }
- chunk->data = &chunk->mem[0];
-}
-
-/** Keep track of total size of allocated chunks for consistency asserts */
-static size_t total_bytes_allocated_in_chunks = 0;
-static void
-buf_chunk_free_unchecked(chunk_t *chunk)
-{
- if (!chunk)
- return;
-#ifdef DEBUG_CHUNK_ALLOC
- tor_assert(CHUNK_ALLOC_SIZE(chunk->memlen) == chunk->DBG_alloc);
-#endif
- tor_assert(total_bytes_allocated_in_chunks >=
- CHUNK_ALLOC_SIZE(chunk->memlen));
- total_bytes_allocated_in_chunks -= CHUNK_ALLOC_SIZE(chunk->memlen);
- tor_free(chunk);
-}
-static inline chunk_t *
-chunk_new_with_alloc_size(size_t alloc)
-{
- chunk_t *ch;
- ch = tor_malloc(alloc);
- ch->next = NULL;
- ch->datalen = 0;
-#ifdef DEBUG_CHUNK_ALLOC
- ch->DBG_alloc = alloc;
-#endif
- ch->memlen = CHUNK_SIZE_WITH_ALLOC(alloc);
- total_bytes_allocated_in_chunks += alloc;
- ch->data = &ch->mem[0];
- CHUNK_SET_SENTINEL(ch, alloc);
- return ch;
-}
-
-/** Expand <b>chunk</b> until it can hold <b>sz</b> bytes, and return a
- * new pointer to <b>chunk</b>. Old pointers are no longer valid. */
-static inline chunk_t *
-chunk_grow(chunk_t *chunk, size_t sz)
-{
- off_t offset;
- const size_t memlen_orig = chunk->memlen;
- const size_t orig_alloc = CHUNK_ALLOC_SIZE(memlen_orig);
- const size_t new_alloc = CHUNK_ALLOC_SIZE(sz);
- tor_assert(sz > chunk->memlen);
- offset = chunk->data - chunk->mem;
- chunk = tor_realloc(chunk, new_alloc);
- chunk->memlen = sz;
- chunk->data = chunk->mem + offset;
-#ifdef DEBUG_CHUNK_ALLOC
- tor_assert(chunk->DBG_alloc == orig_alloc);
- chunk->DBG_alloc = new_alloc;
-#endif
- total_bytes_allocated_in_chunks += new_alloc - orig_alloc;
- CHUNK_SET_SENTINEL(chunk, new_alloc);
- return chunk;
-}
-
-/** Every chunk should take up at least this many bytes. */
-#define MIN_CHUNK_ALLOC 256
-/** No chunk should take up more than this many bytes. */
-#define MAX_CHUNK_ALLOC 65536
-
-/** Return the allocation size we'd like to use to hold <b>target</b>
- * bytes. */
-size_t
-buf_preferred_chunk_size(size_t target)
-{
- tor_assert(target <= SIZE_T_CEILING - CHUNK_OVERHEAD);
- if (CHUNK_ALLOC_SIZE(target) >= MAX_CHUNK_ALLOC)
- return CHUNK_ALLOC_SIZE(target);
- size_t sz = MIN_CHUNK_ALLOC;
- while (CHUNK_SIZE_WITH_ALLOC(sz) < target) {
- sz <<= 1;
- }
- return sz;
-}
-
-/** Collapse data from the first N chunks from <b>buf</b> into buf->head,
- * growing it as necessary, until buf->head has the first <b>bytes</b> bytes
- * of data from the buffer, or until buf->head has all the data in <b>buf</b>.
- *
- * Set *<b>head_out</b> to point to the first byte of available data, and
- * *<b>len_out</b> to the number of bytes of data available at
- * *<b>head_out</b>. Note that *<b>len_out</b> may be more or less than
- * <b>bytes</b>, depending on the number of bytes available.
- */
-void
-buf_pullup(buf_t *buf, size_t bytes, const char **head_out, size_t *len_out)
-{
- chunk_t *dest, *src;
- size_t capacity;
- if (!buf->head) {
- *head_out = NULL;
- *len_out = 0;
- return;
- }
-
- check();
- if (buf->datalen < bytes)
- bytes = buf->datalen;
-
- capacity = bytes;
- if (buf->head->datalen >= bytes) {
- *head_out = buf->head->data;
- *len_out = buf->head->datalen;
- return;
- }
-
- if (buf->head->memlen >= capacity) {
- /* We don't need to grow the first chunk, but we might need to repack it.*/
- size_t needed = capacity - buf->head->datalen;
- if (CHUNK_REMAINING_CAPACITY(buf->head) < needed)
- chunk_repack(buf->head);
- tor_assert(CHUNK_REMAINING_CAPACITY(buf->head) >= needed);
- } else {
- chunk_t *newhead;
- size_t newsize;
- /* We need to grow the chunk. */
- chunk_repack(buf->head);
- newsize = CHUNK_SIZE_WITH_ALLOC(buf_preferred_chunk_size(capacity));
- newhead = chunk_grow(buf->head, newsize);
- tor_assert(newhead->memlen >= capacity);
- if (newhead != buf->head) {
- if (buf->tail == buf->head)
- buf->tail = newhead;
- buf->head = newhead;
- }
- }
-
- dest = buf->head;
- while (dest->datalen < bytes) {
- size_t n = bytes - dest->datalen;
- src = dest->next;
- tor_assert(src);
- if (n >= src->datalen) {
- memcpy(CHUNK_WRITE_PTR(dest), src->data, src->datalen);
- dest->datalen += src->datalen;
- dest->next = src->next;
- if (buf->tail == src)
- buf->tail = dest;
- buf_chunk_free_unchecked(src);
- } else {
- memcpy(CHUNK_WRITE_PTR(dest), src->data, n);
- dest->datalen += n;
- src->data += n;
- src->datalen -= n;
- tor_assert(dest->datalen == bytes);
- }
- }
-
- check();
- *head_out = buf->head->data;
- *len_out = buf->head->datalen;
-}
-
-#ifdef TOR_UNIT_TESTS
-/* Write sz bytes from cp into a newly allocated buffer buf.
- * Returns NULL when passed a NULL cp or zero sz.
- * Asserts on failure: only for use in unit tests.
- * buf must be freed using buf_free(). */
-buf_t *
-buf_new_with_data(const char *cp, size_t sz)
-{
- /* Validate arguments */
- if (!cp || sz <= 0 || sz >= INT_MAX) {
- return NULL;
- }
-
- tor_assert(sz < SSIZE_T_CEILING);
-
- /* Allocate a buffer */
- buf_t *buf = buf_new_with_capacity(sz);
- tor_assert(buf);
- buf_assert_ok(buf);
- tor_assert(!buf->head);
-
- /* Allocate a chunk that is sz bytes long */
- buf->head = chunk_new_with_alloc_size(CHUNK_ALLOC_SIZE(sz));
- buf->tail = buf->head;
- tor_assert(buf->head);
- buf_assert_ok(buf);
- tor_assert(buf_allocation(buf) >= sz);
-
- /* Copy the data and size the buffers */
- tor_assert(sz <= buf_slack(buf));
- tor_assert(sz <= CHUNK_REMAINING_CAPACITY(buf->head));
- memcpy(&buf->head->mem[0], cp, sz);
- buf->datalen = sz;
- buf->head->datalen = sz;
- buf->head->data = &buf->head->mem[0];
- buf_assert_ok(buf);
-
- /* Make sure everything is large enough */
- tor_assert(buf_allocation(buf) >= sz);
- tor_assert(buf_allocation(buf) >= buf_datalen(buf) + buf_slack(buf));
- /* Does the buffer implementation allocate more than the requested size?
- * (for example, by rounding up). If so, these checks will fail. */
- tor_assert(buf_datalen(buf) == sz);
- tor_assert(buf_slack(buf) == 0);
-
- return buf;
-}
-#endif /* defined(TOR_UNIT_TESTS) */
-
-/** Remove the first <b>n</b> bytes from buf. */
-void
-buf_drain(buf_t *buf, size_t n)
-{
- tor_assert(buf->datalen >= n);
- while (n) {
- tor_assert(buf->head);
- if (buf->head->datalen > n) {
- buf->head->datalen -= n;
- buf->head->data += n;
- buf->datalen -= n;
- return;
- } else {
- chunk_t *victim = buf->head;
- n -= victim->datalen;
- buf->datalen -= victim->datalen;
- buf->head = victim->next;
- if (buf->tail == victim)
- buf->tail = NULL;
- buf_chunk_free_unchecked(victim);
- }
- }
- check();
-}
-
-/** Create and return a new buf with default chunk capacity <b>size</b>.
- */
-buf_t *
-buf_new_with_capacity(size_t size)
-{
- buf_t *b = buf_new();
- b->default_chunk_size = buf_preferred_chunk_size(size);
- return b;
-}
-
-/** Allocate and return a new buffer with default capacity. */
-buf_t *
-buf_new(void)
-{
- buf_t *buf = tor_malloc_zero(sizeof(buf_t));
- buf->magic = BUFFER_MAGIC;
- buf->default_chunk_size = 4096;
- return buf;
-}
-
-size_t
-buf_get_default_chunk_size(const buf_t *buf)
-{
- return buf->default_chunk_size;
-}
-
-/** Remove all data from <b>buf</b>. */
-void
-buf_clear(buf_t *buf)
-{
- chunk_t *chunk, *next;
- buf->datalen = 0;
- for (chunk = buf->head; chunk; chunk = next) {
- next = chunk->next;
- buf_chunk_free_unchecked(chunk);
- }
- buf->head = buf->tail = NULL;
-}
-
-/** Return the number of bytes stored in <b>buf</b> */
-MOCK_IMPL(size_t,
-buf_datalen, (const buf_t *buf))
-{
- return buf->datalen;
-}
-
-/** Return the total length of all chunks used in <b>buf</b>. */
-size_t
-buf_allocation(const buf_t *buf)
-{
- size_t total = 0;
- const chunk_t *chunk;
- for (chunk = buf->head; chunk; chunk = chunk->next) {
- total += CHUNK_ALLOC_SIZE(chunk->memlen);
- }
- return total;
-}
-
-/** Return the number of bytes that can be added to <b>buf</b> without
- * performing any additional allocation. */
-size_t
-buf_slack(const buf_t *buf)
-{
- if (!buf->tail)
- return 0;
- else
- return CHUNK_REMAINING_CAPACITY(buf->tail);
-}
-
-/** Release storage held by <b>buf</b>. */
-void
-buf_free_(buf_t *buf)
-{
- if (!buf)
- return;
-
- buf_clear(buf);
- buf->magic = 0xdeadbeef;
- tor_free(buf);
-}
-
-/** Return a new copy of <b>in_chunk</b> */
-static chunk_t *
-chunk_copy(const chunk_t *in_chunk)
-{
- chunk_t *newch = tor_memdup(in_chunk, CHUNK_ALLOC_SIZE(in_chunk->memlen));
- total_bytes_allocated_in_chunks += CHUNK_ALLOC_SIZE(in_chunk->memlen);
-#ifdef DEBUG_CHUNK_ALLOC
- newch->DBG_alloc = CHUNK_ALLOC_SIZE(in_chunk->memlen);
-#endif
- newch->next = NULL;
- if (in_chunk->data) {
- off_t offset = in_chunk->data - in_chunk->mem;
- newch->data = newch->mem + offset;
- }
- return newch;
-}
-
-/** Return a new copy of <b>buf</b> */
-buf_t *
-buf_copy(const buf_t *buf)
-{
- chunk_t *ch;
- buf_t *out = buf_new();
- out->default_chunk_size = buf->default_chunk_size;
- for (ch = buf->head; ch; ch = ch->next) {
- chunk_t *newch = chunk_copy(ch);
- if (out->tail) {
- out->tail->next = newch;
- out->tail = newch;
- } else {
- out->head = out->tail = newch;
- }
- }
- out->datalen = buf->datalen;
- return out;
-}
-
-/** Append a new chunk with enough capacity to hold <b>capacity</b> bytes to
- * the tail of <b>buf</b>. If <b>capped</b>, don't allocate a chunk bigger
- * than MAX_CHUNK_ALLOC. */
-chunk_t *
-buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped)
-{
- chunk_t *chunk;
-
- if (CHUNK_ALLOC_SIZE(capacity) < buf->default_chunk_size) {
- chunk = chunk_new_with_alloc_size(buf->default_chunk_size);
- } else if (capped && CHUNK_ALLOC_SIZE(capacity) > MAX_CHUNK_ALLOC) {
- chunk = chunk_new_with_alloc_size(MAX_CHUNK_ALLOC);
- } else {
- chunk = chunk_new_with_alloc_size(buf_preferred_chunk_size(capacity));
- }
-
- chunk->inserted_time = monotime_coarse_get_stamp();
-
- if (buf->tail) {
- tor_assert(buf->head);
- buf->tail->next = chunk;
- buf->tail = chunk;
- } else {
- tor_assert(!buf->head);
- buf->head = buf->tail = chunk;
- }
- check();
- return chunk;
-}
-
-/** Return the age of the oldest chunk in the buffer <b>buf</b>, in
- * timestamp units. Requires the current monotonic timestamp as its
- * input <b>now</b>.
- */
-uint32_t
-buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now)
-{
- if (buf->head) {
- return now - buf->head->inserted_time;
- } else {
- return 0;
- }
-}
-
-size_t
-buf_get_total_allocation(void)
-{
- return total_bytes_allocated_in_chunks;
-}
-
-/** Append <b>string_len</b> bytes from <b>string</b> to the end of
- * <b>buf</b>.
- *
- * Return the new length of the buffer on success, -1 on failure.
- */
-int
-buf_add(buf_t *buf, const char *string, size_t string_len)
-{
- if (!string_len)
- return (int)buf->datalen;
- check();
-
- if (BUG(buf->datalen >= INT_MAX))
- return -1;
- if (BUG(buf->datalen >= INT_MAX - string_len))
- return -1;
-
- while (string_len) {
- size_t copy;
- if (!buf->tail || !CHUNK_REMAINING_CAPACITY(buf->tail))
- buf_add_chunk_with_capacity(buf, string_len, 1);
-
- copy = CHUNK_REMAINING_CAPACITY(buf->tail);
- if (copy > string_len)
- copy = string_len;
- memcpy(CHUNK_WRITE_PTR(buf->tail), string, copy);
- string_len -= copy;
- string += copy;
- buf->datalen += copy;
- buf->tail->datalen += copy;
- }
-
- check();
- tor_assert(buf->datalen < INT_MAX);
- return (int)buf->datalen;
-}
-
-/** Add a nul-terminated <b>string</b> to <b>buf</b>, not including the
- * terminating NUL. */
-void
-buf_add_string(buf_t *buf, const char *string)
-{
- buf_add(buf, string, strlen(string));
-}
-
-/** As tor_snprintf, but write the results into a buf_t */
-void
-buf_add_printf(buf_t *buf, const char *format, ...)
-{
- va_list ap;
- va_start(ap,format);
- buf_add_vprintf(buf, format, ap);
- va_end(ap);
-}
-
-/** As tor_vsnprintf, but write the results into a buf_t. */
-void
-buf_add_vprintf(buf_t *buf, const char *format, va_list args)
-{
- /* XXXX Faster implementations are easy enough, but let's optimize later */
- char *tmp;
- tor_vasprintf(&tmp, format, args);
- buf_add(buf, tmp, strlen(tmp));
- tor_free(tmp);
-}
-
-/** Return a heap-allocated string containing the contents of <b>buf</b>, plus
- * a NUL byte. If <b>sz_out</b> is provided, set *<b>sz_out</b> to the length
- * of the returned string, not including the terminating NUL. */
-char *
-buf_extract(buf_t *buf, size_t *sz_out)
-{
- tor_assert(buf);
-
- size_t sz = buf_datalen(buf);
- char *result;
- result = tor_malloc(sz+1);
- buf_peek(buf, result, sz);
- result[sz] = 0;
- if (sz_out)
- *sz_out = sz;
- return result;
-}
-
-/** Helper: copy the first <b>string_len</b> bytes from <b>buf</b>
- * onto <b>string</b>.
- */
-void
-buf_peek(const buf_t *buf, char *string, size_t string_len)
-{
- chunk_t *chunk;
-
- tor_assert(string);
- /* make sure we don't ask for too much */
- tor_assert(string_len <= buf->datalen);
- /* buf_assert_ok(buf); */
-
- chunk = buf->head;
- while (string_len) {
- size_t copy = string_len;
- tor_assert(chunk);
- if (chunk->datalen < copy)
- copy = chunk->datalen;
- memcpy(string, chunk->data, copy);
- string_len -= copy;
- string += copy;
- chunk = chunk->next;
- }
-}
-
-/** Remove <b>string_len</b> bytes from the front of <b>buf</b>, and store
- * them into <b>string</b>. Return the new buffer size. <b>string_len</b>
- * must be \<= the number of bytes on the buffer.
- */
-int
-buf_get_bytes(buf_t *buf, char *string, size_t string_len)
-{
- /* There must be string_len bytes in buf; write them onto string,
- * then memmove buf back (that is, remove them from buf).
- *
- * Return the number of bytes still on the buffer. */
-
- check();
- buf_peek(buf, string, string_len);
- buf_drain(buf, string_len);
- check();
- tor_assert(buf->datalen < INT_MAX);
- return (int)buf->datalen;
-}
-
-/** Move up to *<b>buf_flushlen</b> bytes from <b>buf_in</b> to
- * <b>buf_out</b>, and modify *<b>buf_flushlen</b> appropriately.
- * Return the number of bytes actually copied.
- */
-int
-buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen)
-{
- /* We can do way better here, but this doesn't turn up in any profiles. */
- char b[4096];
- size_t cp, len;
-
- if (BUG(buf_out->datalen >= INT_MAX || *buf_flushlen >= INT_MAX))
- return -1;
- if (BUG(buf_out->datalen >= INT_MAX - *buf_flushlen))
- return -1;
-
- len = *buf_flushlen;
- if (len > buf_in->datalen)
- len = buf_in->datalen;
-
- cp = len; /* Remember the number of bytes we intend to copy. */
- tor_assert(cp < INT_MAX);
- while (len) {
- /* This isn't the most efficient implementation one could imagine, since
- * it does two copies instead of 1, but I kinda doubt that this will be
- * critical path. */
- size_t n = len > sizeof(b) ? sizeof(b) : len;
- buf_get_bytes(buf_in, b, n);
- buf_add(buf_out, b, n);
- len -= n;
- }
- *buf_flushlen -= cp;
- return (int)cp;
-}
-
-/** Moves all data from <b>buf_in</b> to <b>buf_out</b>, without copying.
- */
-void
-buf_move_all(buf_t *buf_out, buf_t *buf_in)
-{
- tor_assert(buf_out);
- if (!buf_in)
- return;
- if (buf_datalen(buf_in) == 0)
- return;
- if (BUG(buf_out->datalen >= INT_MAX || buf_in->datalen >= INT_MAX))
- return;
- if (BUG(buf_out->datalen >= INT_MAX - buf_in->datalen))
- return;
-
- if (buf_out->head == NULL) {
- buf_out->head = buf_in->head;
- buf_out->tail = buf_in->tail;
- } else {
- buf_out->tail->next = buf_in->head;
- buf_out->tail = buf_in->tail;
- }
-
- buf_out->datalen += buf_in->datalen;
- buf_in->head = buf_in->tail = NULL;
- buf_in->datalen = 0;
-}
-
-/** Internal structure: represents a position in a buffer. */
-typedef struct buf_pos_t {
- const chunk_t *chunk; /**< Which chunk are we pointing to? */
- int pos;/**< Which character inside the chunk's data are we pointing to? */
- size_t chunk_pos; /**< Total length of all previous chunks. */
-} buf_pos_t;
-
-/** Initialize <b>out</b> to point to the first character of <b>buf</b>.*/
-static void
-buf_pos_init(const buf_t *buf, buf_pos_t *out)
-{
- out->chunk = buf->head;
- out->pos = 0;
- out->chunk_pos = 0;
-}
-
-/** Advance <b>out</b> to the first appearance of <b>ch</b> at the current
- * position of <b>out</b>, or later. Return -1 if no instances are found;
- * otherwise returns the absolute position of the character. */
-static off_t
-buf_find_pos_of_char(char ch, buf_pos_t *out)
-{
- const chunk_t *chunk;
- int pos;
- tor_assert(out);
- if (out->chunk) {
- if (out->chunk->datalen) {
- tor_assert(out->pos < (off_t)out->chunk->datalen);
- } else {
- tor_assert(out->pos == 0);
- }
- }
- pos = out->pos;
- for (chunk = out->chunk; chunk; chunk = chunk->next) {
- char *cp = memchr(chunk->data+pos, ch, chunk->datalen - pos);
- if (cp) {
- out->chunk = chunk;
- tor_assert(cp - chunk->data < INT_MAX);
- out->pos = (int)(cp - chunk->data);
- return out->chunk_pos + out->pos;
- } else {
- out->chunk_pos += chunk->datalen;
- pos = 0;
- }
- }
- return -1;
-}
-
-/** Advance <b>pos</b> by a single character, if there are any more characters
- * in the buffer. Returns 0 on success, -1 on failure. */
-static inline int
-buf_pos_inc(buf_pos_t *pos)
-{
- tor_assert(pos->pos < INT_MAX - 1);
- ++pos->pos;
- if (pos->pos == (off_t)pos->chunk->datalen) {
- if (!pos->chunk->next)
- return -1;
- pos->chunk_pos += pos->chunk->datalen;
- pos->chunk = pos->chunk->next;
- pos->pos = 0;
- }
- return 0;
-}
-
-/** Return true iff the <b>n</b>-character string in <b>s</b> appears
- * (verbatim) at <b>pos</b>. */
-static int
-buf_matches_at_pos(const buf_pos_t *pos, const char *s, size_t n)
-{
- buf_pos_t p;
- if (!n)
- return 1;
-
- memcpy(&p, pos, sizeof(p));
-
- while (1) {
- char ch = p.chunk->data[p.pos];
- if (ch != *s)
- return 0;
- ++s;
- /* If we're out of characters that don't match, we match. Check this
- * _before_ we test incrementing pos, in case we're at the end of the
- * string. */
- if (--n == 0)
- return 1;
- if (buf_pos_inc(&p)<0)
- return 0;
- }
-}
-
-/** Return the first position in <b>buf</b> at which the <b>n</b>-character
- * string <b>s</b> occurs, or -1 if it does not occur. */
-int
-buf_find_string_offset(const buf_t *buf, const char *s, size_t n)
-{
- buf_pos_t pos;
- buf_pos_init(buf, &pos);
- while (buf_find_pos_of_char(*s, &pos) >= 0) {
- if (buf_matches_at_pos(&pos, s, n)) {
- tor_assert(pos.chunk_pos + pos.pos < INT_MAX);
- return (int)(pos.chunk_pos + pos.pos);
- } else {
- if (buf_pos_inc(&pos)<0)
- return -1;
- }
- }
- return -1;
-}
-
-/** Return 1 iff <b>buf</b> starts with <b>cmd</b>. <b>cmd</b> must be a null
- * terminated string, of no more than PEEK_BUF_STARTSWITH_MAX bytes. */
-int
-buf_peek_startswith(const buf_t *buf, const char *cmd)
-{
- char tmp[PEEK_BUF_STARTSWITH_MAX];
- size_t clen = strlen(cmd);
- if (clen == 0)
- return 1;
- if (BUG(clen > sizeof(tmp)))
- return 0;
- if (buf->datalen < clen)
- return 0;
- buf_peek(buf, tmp, clen);
- return fast_memeq(tmp, cmd, clen);
-}
-
-/** Return the index within <b>buf</b> at which <b>ch</b> first appears,
- * or -1 if <b>ch</b> does not appear on buf. */
-static off_t
-buf_find_offset_of_char(buf_t *buf, char ch)
-{
- chunk_t *chunk;
- off_t offset = 0;
- tor_assert(buf->datalen < INT_MAX);
- for (chunk = buf->head; chunk; chunk = chunk->next) {
- char *cp = memchr(chunk->data, ch, chunk->datalen);
- if (cp)
- return offset + (cp - chunk->data);
- else
- offset += chunk->datalen;
- }
- return -1;
-}
-
-/** Try to read a single LF-terminated line from <b>buf</b>, and write it
- * (including the LF), NUL-terminated, into the *<b>data_len</b> byte buffer
- * at <b>data_out</b>. Set *<b>data_len</b> to the number of bytes in the
- * line, not counting the terminating NUL. Return 1 if we read a whole line,
- * return 0 if we don't have a whole line yet, and return -1 if the line
- * length exceeds *<b>data_len</b>.
- */
-int
-buf_get_line(buf_t *buf, char *data_out, size_t *data_len)
-{
- size_t sz;
- off_t offset;
-
- if (!buf->head)
- return 0;
-
- offset = buf_find_offset_of_char(buf, '\n');
- if (offset < 0)
- return 0;
- sz = (size_t) offset;
- if (sz+2 > *data_len) {
- *data_len = sz + 2;
- return -1;
- }
- buf_get_bytes(buf, data_out, sz+1);
- data_out[sz+1] = '\0';
- *data_len = sz+1;
- return 1;
-}
-
-/** Set *<b>output</b> to contain a copy of the data in *<b>input</b> */
-int
-buf_set_to_copy(buf_t **output,
- const buf_t *input)
-{
- if (*output)
- buf_free(*output);
- *output = buf_copy(input);
- return 0;
-}
-
-/** Log an error and exit if <b>buf</b> is corrupted.
- */
-void
-buf_assert_ok(buf_t *buf)
-{
- tor_assert(buf);
- tor_assert(buf->magic == BUFFER_MAGIC);
-
- if (! buf->head) {
- tor_assert(!buf->tail);
- tor_assert(buf->datalen == 0);
- } else {
- chunk_t *ch;
- size_t total = 0;
- tor_assert(buf->tail);
- for (ch = buf->head; ch; ch = ch->next) {
- total += ch->datalen;
- tor_assert(ch->datalen <= ch->memlen);
- tor_assert(ch->datalen < INT_MAX);
- tor_assert(ch->data >= &ch->mem[0]);
- tor_assert(ch->data <= &ch->mem[0]+ch->memlen);
- if (ch->data == &ch->mem[0]+ch->memlen) {
- /* LCOV_EXCL_START */
- static int warned = 0;
- if (! warned) {
- log_warn(LD_BUG, "Invariant violation in buf.c related to #15083");
- warned = 1;
- }
- /* LCOV_EXCL_STOP */
- }
- tor_assert(ch->data+ch->datalen <= &ch->mem[0] + ch->memlen);
- if (!ch->next)
- tor_assert(ch == buf->tail);
- }
- tor_assert(buf->datalen == total);
- }
-}
diff --git a/src/lib/container/buffers.h b/src/lib/container/buffers.h
deleted file mode 100644
index c103b93a82..0000000000
--- a/src/lib/container/buffers.h
+++ /dev/null
@@ -1,122 +0,0 @@
-/* Copyright (c) 2001 Matej Pfajfar.
- * Copyright (c) 2001-2004, Roger Dingledine.
- * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
-/* See LICENSE for licensing information */
-
-/**
- * \file buffers.h
- *
- * \brief Header file for buffers.c.
- **/
-
-#ifndef TOR_BUFFERS_H
-#define TOR_BUFFERS_H
-
-#include "lib/cc/compat_compiler.h"
-#include "lib/cc/torint.h"
-#include "lib/testsupport/testsupport.h"
-
-#include <stdarg.h>
-
-typedef struct buf_t buf_t;
-
-buf_t *buf_new(void);
-buf_t *buf_new_with_capacity(size_t size);
-size_t buf_get_default_chunk_size(const buf_t *buf);
-void buf_free_(buf_t *buf);
-#define buf_free(b) FREE_AND_NULL(buf_t, buf_free_, (b))
-void buf_clear(buf_t *buf);
-buf_t *buf_copy(const buf_t *buf);
-
-MOCK_DECL(size_t, buf_datalen, (const buf_t *buf));
-size_t buf_allocation(const buf_t *buf);
-size_t buf_slack(const buf_t *buf);
-
-uint32_t buf_get_oldest_chunk_timestamp(const buf_t *buf, uint32_t now);
-size_t buf_get_total_allocation(void);
-
-int buf_add(buf_t *buf, const char *string, size_t string_len);
-void buf_add_string(buf_t *buf, const char *string);
-void buf_add_printf(buf_t *buf, const char *format, ...)
- CHECK_PRINTF(2, 3);
-void buf_add_vprintf(buf_t *buf, const char *format, va_list args)
- CHECK_PRINTF(2, 0);
-int buf_move_to_buf(buf_t *buf_out, buf_t *buf_in, size_t *buf_flushlen);
-void buf_move_all(buf_t *buf_out, buf_t *buf_in);
-void buf_peek(const buf_t *buf, char *string, size_t string_len);
-void buf_drain(buf_t *buf, size_t n);
-int buf_get_bytes(buf_t *buf, char *string, size_t string_len);
-int buf_get_line(buf_t *buf, char *data_out, size_t *data_len);
-
-#define PEEK_BUF_STARTSWITH_MAX 16
-int buf_peek_startswith(const buf_t *buf, const char *cmd);
-
-int buf_set_to_copy(buf_t **output,
- const buf_t *input);
-
-void buf_assert_ok(buf_t *buf);
-
-int buf_find_string_offset(const buf_t *buf, const char *s, size_t n);
-void buf_pullup(buf_t *buf, size_t bytes,
- const char **head_out, size_t *len_out);
-char *buf_extract(buf_t *buf, size_t *sz_out);
-
-#ifdef BUFFERS_PRIVATE
-#ifdef TOR_UNIT_TESTS
-buf_t *buf_new_with_data(const char *cp, size_t sz);
-#endif
-size_t buf_preferred_chunk_size(size_t target);
-
-#define DEBUG_CHUNK_ALLOC
-/** A single chunk on a buffer. */
-typedef struct chunk_t {
- struct chunk_t *next; /**< The next chunk on the buffer. */
- size_t datalen; /**< The number of bytes stored in this chunk */
- size_t memlen; /**< The number of usable bytes of storage in <b>mem</b>. */
-#ifdef DEBUG_CHUNK_ALLOC
- size_t DBG_alloc;
-#endif
- char *data; /**< A pointer to the first byte of data stored in <b>mem</b>. */
- uint32_t inserted_time; /**< Timestamp when this chunk was inserted. */
- char mem[FLEXIBLE_ARRAY_MEMBER]; /**< The actual memory used for storage in
- * this chunk. */
-} chunk_t;
-
-/** Magic value for buf_t.magic, to catch pointer errors. */
-#define BUFFER_MAGIC 0xB0FFF312u
-/** A resizeable buffer, optimized for reading and writing. */
-struct buf_t {
- uint32_t magic; /**< Magic cookie for debugging: Must be set to
- * BUFFER_MAGIC. */
- size_t datalen; /**< How many bytes is this buffer holding right now? */
- size_t default_chunk_size; /**< Don't allocate any chunks smaller than
- * this for this buffer. */
- chunk_t *head; /**< First chunk in the list, or NULL for none. */
- chunk_t *tail; /**< Last chunk in the list, or NULL for none. */
-};
-
-chunk_t *buf_add_chunk_with_capacity(buf_t *buf, size_t capacity, int capped);
-/** If a read onto the end of a chunk would be smaller than this number, then
- * just start a new chunk. */
-#define MIN_READ_LEN 8
-
-/** Return the number of bytes that can be written onto <b>chunk</b> without
- * running out of space. */
-static inline size_t
-CHUNK_REMAINING_CAPACITY(const chunk_t *chunk)
-{
- return (chunk->mem + chunk->memlen) - (chunk->data + chunk->datalen);
-}
-
-/** Return the next character in <b>chunk</b> onto which data can be appended.
- * If the chunk is full, this might be off the end of chunk->mem. */
-static inline char *
-CHUNK_WRITE_PTR(chunk_t *chunk)
-{
- return chunk->data + chunk->datalen;
-}
-
-#endif /* defined(BUFFERS_PRIVATE) */
-
-#endif /* !defined(TOR_BUFFERS_H) */
diff --git a/src/lib/container/handles.h b/src/lib/container/handles.h
index ca7c94559e..6b1bbd5167 100644
--- a/src/lib/container/handles.h
+++ b/src/lib/container/handles.h
@@ -1,4 +1,4 @@
-/* Copyright (c) 2016-2019, The Tor Project, Inc. */
+/* Copyright (c) 2016-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/**
@@ -16,33 +16,33 @@
* To enable a type to have handles, add a HANDLE_ENTRY() field in its
* definition, as in:
*
- * struct walrus {
- * HANDLE_ENTRY(wlr, walrus);
+ * struct walrus_t {
+ * HANDLE_ENTRY(wlr, walrus_t);
* // ...
* };
*
- * And invoke HANDLE_DECL(wlr, walrus, [static]) to declare the handle
+ * And invoke HANDLE_DECL(wlr, walrus_t, [static]) to declare the handle
* manipulation functions (typically in a header):
*
* // opaque handle to walrus.
* typedef struct wlr_handle_t wlr_handle_t;
*
* // make a new handle
- * struct wlr_handle_t *wlr_handle_new(struct walrus *);
+ * struct wlr_handle_t *wlr_handle_new(struct walrus_t *);
*
* // release a handle
* void wlr_handle_free(wlr_handle_t *);
*
* // return the pointed-to walrus, or NULL.
- * struct walrus *wlr_handle_get(wlr_handle_t *).
+ * struct walrus_t *wlr_handle_get(wlr_handle_t *).
*
* // call this function when you're about to free the walrus;
* // it invalidates all handles. (IF YOU DON'T, YOU WILL HAVE
* // DANGLING REFERENCES)
- * void wlr_handles_clear(struct walrus *);
+ * void wlr_handles_clear(struct walrus_t *);
*
* Finally, use HANDLE_IMPL() to define the above functions in some
- * appropriate C file: HANDLE_IMPL(wlr, walrus, [static])
+ * appropriate C file: HANDLE_IMPL(wlr, walrus_t, [static])
*
**/
@@ -57,12 +57,13 @@
#define HANDLE_ENTRY(name, structname) \
struct name ## _handle_head_t *handle_head
-#define HANDLE_DECL(name, structname, linkage) \
+#define HANDLE_DECL(name, structname_t, linkage) \
typedef struct name ## _handle_t name ## _handle_t; \
- linkage name ## _handle_t *name ## _handle_new(struct structname *object); \
+ linkage name ## _handle_t *name ## _handle_new( \
+ struct structname_t *object); \
linkage void name ## _handle_free_(name ## _handle_t *); \
- linkage struct structname *name ## _handle_get(name ## _handle_t *); \
- linkage void name ## _handles_clear(struct structname *object);
+ linkage struct structname_t *name ## _handle_get(name ## _handle_t *); \
+ linkage void name ## _handles_clear(struct structname_t *object);
/*
* Implementation notes: there are lots of possible implementations here. We
diff --git a/src/lib/container/include.am b/src/lib/container/include.am
index e6492098b5..00d7b8e587 100644
--- a/src/lib/container/include.am
+++ b/src/lib/container/include.am
@@ -5,10 +5,11 @@ if UNITTESTS_ENABLED
noinst_LIBRARIES += src/lib/libtor-container-testing.a
endif
+# ADD_C_FILE: INSERT SOURCES HERE.
src_lib_libtor_container_a_SOURCES = \
src/lib/container/bloomfilt.c \
- src/lib/container/buffers.c \
src/lib/container/map.c \
+ src/lib/container/namemap.c \
src/lib/container/order.c \
src/lib/container/smartlist.c
@@ -17,11 +18,13 @@ src_lib_libtor_container_testing_a_SOURCES = \
src_lib_libtor_container_testing_a_CPPFLAGS = $(AM_CPPFLAGS) $(TEST_CPPFLAGS)
src_lib_libtor_container_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS)
+# ADD_C_FILE: INSERT HEADERS HERE.
noinst_HEADERS += \
src/lib/container/bitarray.h \
src/lib/container/bloomfilt.h \
- src/lib/container/buffers.h \
src/lib/container/handles.h \
src/lib/container/map.h \
+ src/lib/container/namemap.h \
+ src/lib/container/namemap_st.h \
src/lib/container/order.h \
src/lib/container/smartlist.h
diff --git a/src/lib/container/lib_container.md b/src/lib/container/lib_container.md
new file mode 100644
index 0000000000..f4902ca44a
--- /dev/null
+++ b/src/lib/container/lib_container.md
@@ -0,0 +1,49 @@
+@dir /lib/container
+@brief 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.
+
+<!-- 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` header documentation for more
+information; there are many convenience functions for commonly needed
+operations.
+
+For low-level operations on smartlists, see also
+\refdir{lib/smartlist_core}.
+
+<!-- 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
+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.
+
+<!-- TODO: WRITE about bloom filters, namemaps, bit-arrays, order functions.
+-->
+
diff --git a/src/lib/container/map.c b/src/lib/container/map.c
index d213ad50bf..7db84313ea 100644
--- a/src/lib/container/map.c
+++ b/src/lib/container/map.c
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/**
@@ -21,7 +21,7 @@
#include <stdlib.h>
#include <string.h>
-#include "ht.h"
+#include "ext/ht.h"
/** Helper: Declare an entry type and a map type to implement a mapping using
* ht.h. The map type will be called <b>maptype</b>. The key part of each
@@ -85,21 +85,21 @@ digest256map_entry_hash(const digest256map_entry_t *a)
}
HT_PROTOTYPE(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
- strmap_entries_eq)
+ strmap_entries_eq);
HT_GENERATE2(strmap_impl, strmap_entry_t, node, strmap_entry_hash,
- strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)
+ strmap_entries_eq, 0.6, tor_reallocarray_, tor_free_);
HT_PROTOTYPE(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
- digestmap_entries_eq)
+ digestmap_entries_eq);
HT_GENERATE2(digestmap_impl, digestmap_entry_t, node, digestmap_entry_hash,
- digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_)
+ digestmap_entries_eq, 0.6, tor_reallocarray_, tor_free_);
HT_PROTOTYPE(digest256map_impl, digest256map_entry_t, node,
digest256map_entry_hash,
- digest256map_entries_eq)
+ digest256map_entries_eq);
HT_GENERATE2(digest256map_impl, digest256map_entry_t, node,
digest256map_entry_hash,
- digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_)
+ digest256map_entries_eq, 0.6, tor_reallocarray_, tor_free_);
#define strmap_entry_free(ent) \
FREE_AND_NULL(strmap_entry_t, strmap_entry_free_, (ent))
diff --git a/src/lib/container/map.h b/src/lib/container/map.h
index a2d1b01d12..dbc1967247 100644
--- a/src/lib/container/map.h
+++ b/src/lib/container/map.h
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
#ifndef TOR_MAP_H
@@ -15,36 +15,37 @@
#include "lib/testsupport/testsupport.h"
#include "lib/cc/torint.h"
-#include "siphash.h"
+#include "ext/siphash.h"
-#define DECLARE_MAP_FNS(maptype, keytype, prefix) \
- typedef struct maptype maptype; \
- typedef struct prefix##entry_t *prefix##iter_t; \
- MOCK_DECL(maptype*, prefix##new, (void)); \
- void* prefix##set(maptype *map, keytype key, void *val); \
- void* prefix##get(const maptype *map, keytype key); \
- void* prefix##remove(maptype *map, keytype key); \
- MOCK_DECL(void, prefix##free_, (maptype *map, void (*free_val)(void*))); \
- int prefix##isempty(const maptype *map); \
- int prefix##size(const maptype *map); \
- prefix##iter_t *prefix##iter_init(maptype *map); \
- prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter); \
- prefix##iter_t *prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter); \
- void prefix##iter_get(prefix##iter_t *iter, keytype *keyp, void **valp); \
- int prefix##iter_done(prefix##iter_t *iter); \
- void prefix##assert_ok(const maptype *map)
+#define DECLARE_MAP_FNS(mapname_t, keytype, prefix) \
+ typedef struct mapname_t mapname_t; \
+ typedef struct prefix##_entry_t *prefix##_iter_t; \
+ MOCK_DECL(mapname_t*, prefix##_new, (void)); \
+ void* prefix##_set(mapname_t *map, keytype key, void *val); \
+ void* prefix##_get(const mapname_t *map, keytype key); \
+ void* prefix##_remove(mapname_t *map, keytype key); \
+ MOCK_DECL(void, prefix##_free_, (mapname_t *map, void (*free_val)(void*))); \
+ int prefix##_isempty(const mapname_t *map); \
+ int prefix##_size(const mapname_t *map); \
+ prefix##_iter_t *prefix##_iter_init(mapname_t *map); \
+ prefix##_iter_t *prefix##_iter_next(mapname_t *map, prefix##_iter_t *iter); \
+ prefix##_iter_t *prefix##_iter_next_rmv(mapname_t *map, \
+ prefix##_iter_t *iter); \
+ void prefix##_iter_get(prefix##_iter_t *iter, keytype *keyp, void **valp); \
+ int prefix##_iter_done(prefix##_iter_t *iter); \
+ void prefix##_assert_ok(const mapname_t *map)
/* Map from const char * to void *. Implemented with a hash table. */
-DECLARE_MAP_FNS(strmap_t, const char *, strmap_);
+DECLARE_MAP_FNS(strmap_t, const char *, strmap);
/* Map from const char[DIGEST_LEN] to void *. Implemented with a hash table. */
-DECLARE_MAP_FNS(digestmap_t, const char *, digestmap_);
+DECLARE_MAP_FNS(digestmap_t, const char *, digestmap);
/* Map from const uint8_t[DIGEST256_LEN] to void *. Implemented with a hash
* table. */
-DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_);
+DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map);
-#define MAP_FREE_AND_NULL(maptype, map, fn) \
+#define MAP_FREE_AND_NULL(mapname_t, map, fn) \
do { \
- maptype ## _free_((map), (fn)); \
+ mapname_t ## _free_((map), (fn)); \
(map) = NULL; \
} while (0)
@@ -55,12 +56,12 @@ DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_);
#undef DECLARE_MAP_FNS
/** Iterates over the key-value pairs in a map <b>map</b> in order.
- * <b>prefix</b> is as for DECLARE_MAP_FNS (i.e., strmap_ or digestmap_).
+ * <b>prefix</b> is as for DECLARE_MAP_FNS (i.e., strmap or digestmap).
* The map's keys and values are of type keytype and valtype respectively;
* each iteration assigns them to keyvar and valvar.
*
* Example use:
- * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) {
+ * MAP_FOREACH(digestmap, m, const char *, k, routerinfo_t *, r) {
* // use k and r
* } MAP_FOREACH_END.
*/
@@ -80,21 +81,21 @@ DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_);
*/
#define MAP_FOREACH(prefix, map, keytype, keyvar, valtype, valvar) \
STMT_BEGIN \
- prefix##iter_t *keyvar##_iter; \
- for (keyvar##_iter = prefix##iter_init(map); \
- !prefix##iter_done(keyvar##_iter); \
- keyvar##_iter = prefix##iter_next(map, keyvar##_iter)) { \
+ prefix##_iter_t *keyvar##_iter; \
+ for (keyvar##_iter = prefix##_iter_init(map); \
+ !prefix##_iter_done(keyvar##_iter); \
+ keyvar##_iter = prefix##_iter_next(map, keyvar##_iter)) { \
keytype keyvar; \
void *valvar##_voidp; \
valtype valvar; \
- prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \
+ prefix##_iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \
valvar = valvar##_voidp;
/** As MAP_FOREACH, except allows members to be removed from the map
* during the iteration via MAP_DEL_CURRENT. Example use:
*
* Example use:
- * MAP_FOREACH(digestmap_, m, const char *, k, routerinfo_t *, r) {
+ * MAP_FOREACH(digestmap, m, const char *, k, routerinfo_t *, r) {
* if (is_very_old(r))
* MAP_DEL_CURRENT(k);
* } MAP_FOREACH_END.
@@ -120,18 +121,18 @@ DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_);
*/
#define MAP_FOREACH_MODIFY(prefix, map, keytype, keyvar, valtype, valvar) \
STMT_BEGIN \
- prefix##iter_t *keyvar##_iter; \
+ prefix##_iter_t *keyvar##_iter; \
int keyvar##_del=0; \
- for (keyvar##_iter = prefix##iter_init(map); \
- !prefix##iter_done(keyvar##_iter); \
+ for (keyvar##_iter = prefix##_iter_init(map); \
+ !prefix##_iter_done(keyvar##_iter); \
keyvar##_iter = keyvar##_del ? \
- prefix##iter_next_rmv(map, keyvar##_iter) : \
- prefix##iter_next(map, keyvar##_iter)) { \
+ prefix##_iter_next_rmv(map, keyvar##_iter) : \
+ prefix##_iter_next(map, keyvar##_iter)) { \
keytype keyvar; \
void *valvar##_voidp; \
valtype valvar; \
keyvar##_del=0; \
- prefix##iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \
+ prefix##_iter_get(keyvar##_iter, &keyvar, &valvar##_voidp); \
valvar = valvar##_voidp;
/** Used with MAP_FOREACH_MODIFY to remove the currently-iterated-upon
@@ -151,7 +152,7 @@ DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_);
* } DIGESTMAP_FOREACH_END.
*/
#define DIGESTMAP_FOREACH(map, keyvar, valtype, valvar) \
- MAP_FOREACH(digestmap_, map, const char *, keyvar, valtype, valvar)
+ MAP_FOREACH(digestmap, map, const char *, keyvar, valtype, valvar)
/** As MAP_FOREACH_MODIFY, but does not require declaration of prefix or
* keytype.
@@ -162,89 +163,89 @@ DECLARE_MAP_FNS(digest256map_t, const uint8_t *, digest256map_);
* } DIGESTMAP_FOREACH_END.
*/
#define DIGESTMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \
- MAP_FOREACH_MODIFY(digestmap_, map, const char *, keyvar, valtype, valvar)
+ MAP_FOREACH_MODIFY(digestmap, map, const char *, keyvar, valtype, valvar)
/** Used to end a DIGESTMAP_FOREACH() block. */
#define DIGESTMAP_FOREACH_END MAP_FOREACH_END
#define DIGEST256MAP_FOREACH(map, keyvar, valtype, valvar) \
- MAP_FOREACH(digest256map_, map, const uint8_t *, keyvar, valtype, valvar)
+ MAP_FOREACH(digest256map, map, const uint8_t *, keyvar, valtype, valvar)
#define DIGEST256MAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \
- MAP_FOREACH_MODIFY(digest256map_, map, const uint8_t *, \
+ MAP_FOREACH_MODIFY(digest256map, map, const uint8_t *, \
keyvar, valtype, valvar)
#define DIGEST256MAP_FOREACH_END MAP_FOREACH_END
#define STRMAP_FOREACH(map, keyvar, valtype, valvar) \
- MAP_FOREACH(strmap_, map, const char *, keyvar, valtype, valvar)
+ MAP_FOREACH(strmap, map, const char *, keyvar, valtype, valvar)
#define STRMAP_FOREACH_MODIFY(map, keyvar, valtype, valvar) \
- MAP_FOREACH_MODIFY(strmap_, map, const char *, keyvar, valtype, valvar)
+ MAP_FOREACH_MODIFY(strmap, map, const char *, keyvar, valtype, valvar)
#define STRMAP_FOREACH_END MAP_FOREACH_END
void* strmap_set_lc(strmap_t *map, const char *key, void *val);
void* strmap_get_lc(const strmap_t *map, const char *key);
void* strmap_remove_lc(strmap_t *map, const char *key);
-#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, maptype, valtype) \
- typedef struct maptype maptype; \
- typedef struct prefix##iter_t *prefix##iter_t; \
- ATTR_UNUSED static inline maptype* \
- prefix##new(void) \
+#define DECLARE_TYPED_DIGESTMAP_FNS(prefix, mapname_t, valtype) \
+ typedef struct mapname_t mapname_t; \
+ typedef struct prefix##_iter_t *prefix##_iter_t; \
+ ATTR_UNUSED static inline mapname_t* \
+ prefix##_new(void) \
{ \
- return (maptype*)digestmap_new(); \
+ return (mapname_t*)digestmap_new(); \
} \
ATTR_UNUSED static inline digestmap_t* \
- prefix##to_digestmap(maptype *map) \
+ prefix##_to_digestmap(mapname_t *map) \
{ \
return (digestmap_t*)map; \
} \
ATTR_UNUSED static inline valtype* \
- prefix##get(maptype *map, const char *key) \
+ prefix##_get(mapname_t *map, const char *key) \
{ \
return (valtype*)digestmap_get((digestmap_t*)map, key); \
} \
ATTR_UNUSED static inline valtype* \
- prefix##set(maptype *map, const char *key, valtype *val) \
+ prefix##_set(mapname_t *map, const char *key, valtype *val) \
{ \
return (valtype*)digestmap_set((digestmap_t*)map, key, val); \
} \
ATTR_UNUSED static inline valtype* \
- prefix##remove(maptype *map, const char *key) \
+ prefix##_remove(mapname_t *map, const char *key) \
{ \
return (valtype*)digestmap_remove((digestmap_t*)map, key); \
} \
ATTR_UNUSED static inline void \
- prefix##f##ree_(maptype *map, void (*free_val)(void*)) \
+ prefix##_f##ree_(mapname_t *map, void (*free_val)(void*)) \
{ \
digestmap_free_((digestmap_t*)map, free_val); \
} \
ATTR_UNUSED static inline int \
- prefix##isempty(maptype *map) \
+ prefix##_isempty(mapname_t *map) \
{ \
return digestmap_isempty((digestmap_t*)map); \
} \
ATTR_UNUSED static inline int \
- prefix##size(maptype *map) \
+ prefix##_size(mapname_t *map) \
{ \
return digestmap_size((digestmap_t*)map); \
} \
ATTR_UNUSED static inline \
- prefix##iter_t *prefix##iter_init(maptype *map) \
+ prefix##_iter_t *prefix##_iter_init(mapname_t *map) \
{ \
- return (prefix##iter_t*) digestmap_iter_init((digestmap_t*)map); \
+ return (prefix##_iter_t*) digestmap_iter_init((digestmap_t*)map); \
} \
ATTR_UNUSED static inline \
- prefix##iter_t *prefix##iter_next(maptype *map, prefix##iter_t *iter) \
+ prefix##_iter_t *prefix##_iter_next(mapname_t *map, prefix##_iter_t *iter) \
{ \
- return (prefix##iter_t*) digestmap_iter_next( \
+ return (prefix##_iter_t*) digestmap_iter_next( \
(digestmap_t*)map, (digestmap_iter_t*)iter); \
} \
- ATTR_UNUSED static inline prefix##iter_t* \
- prefix##iter_next_rmv(maptype *map, prefix##iter_t *iter) \
+ ATTR_UNUSED static inline prefix##_iter_t* \
+ prefix##_iter_next_rmv(mapname_t *map, prefix##_iter_t *iter) \
{ \
- return (prefix##iter_t*) digestmap_iter_next_rmv( \
+ return (prefix##_iter_t*) digestmap_iter_next_rmv( \
(digestmap_t*)map, (digestmap_iter_t*)iter); \
} \
ATTR_UNUSED static inline void \
- prefix##iter_get(prefix##iter_t *iter, \
+ prefix##_iter_get(prefix##_iter_t *iter, \
const char **keyp, \
valtype **valp) \
{ \
@@ -253,9 +254,9 @@ void* strmap_remove_lc(strmap_t *map, const char *key);
*valp = v; \
} \
ATTR_UNUSED static inline int \
- prefix##iter_done(prefix##iter_t *iter) \
+ prefix##_iter_done(prefix##_iter_t *iter) \
{ \
return digestmap_iter_done((digestmap_iter_t*)iter); \
}
-#endif /* !defined(TOR_CONTAINER_H) */
+#endif /* !defined(TOR_MAP_H) */
diff --git a/src/lib/container/namemap.c b/src/lib/container/namemap.c
new file mode 100644
index 0000000000..e286cad947
--- /dev/null
+++ b/src/lib/container/namemap.c
@@ -0,0 +1,189 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * @file namemap.c
+ * @brief Mappings between identifiers and 16-bit ints.
+ **/
+
+#include "orconfig.h"
+#include "lib/container/smartlist.h"
+#include "lib/container/namemap.h"
+#include "lib/container/namemap_st.h"
+#include "lib/log/util_bug.h"
+#include "lib/malloc/malloc.h"
+#include "lib/string/printf.h"
+
+#include "ext/siphash.h"
+
+#include <string.h>
+
+/** Helper for namemap hashtable implementation: compare two entries. */
+static inline int
+mapped_name_eq(const mapped_name_t *a, const mapped_name_t *b)
+{
+ return !strcmp(a->name, b->name);
+}
+
+/** Helper for namemap hashtable implementation: hash an entry. */
+static inline unsigned
+mapped_name_hash(const mapped_name_t *a)
+{
+ return (unsigned) siphash24g(a->name, strlen(a->name));
+}
+
+HT_PROTOTYPE(namemap_ht, mapped_name_t, node, mapped_name_hash,
+ mapped_name_eq);
+HT_GENERATE2(namemap_ht, mapped_name_t, node, mapped_name_hash,
+ mapped_name_eq, 0.6, tor_reallocarray_, tor_free_);
+
+/** Set up an uninitialized <b>map</b>. */
+void
+namemap_init(namemap_t *map)
+{
+ memset(map, 0, sizeof(*map));
+ HT_INIT(namemap_ht, &map->ht);
+ map->names = smartlist_new();
+}
+
+/** Return the name that <b>map</b> associates with a given <b>id</b>, or
+ * NULL if there is no such name. */
+const char *
+namemap_get_name(const namemap_t *map, unsigned id)
+{
+ if (map->names && id < (unsigned)smartlist_len(map->names)) {
+ mapped_name_t *name = smartlist_get(map->names, (int)id);
+ return name->name;
+ } else {
+ return NULL;
+ }
+}
+
+/**
+ * Return the name that <b>map</b> associates with a given <b>id</b>, or a
+ * pointer to a statically allocated string describing the value of <b>id</b>
+ * if no such name exists.
+ **/
+const char *
+namemap_fmt_name(const namemap_t *map, unsigned id)
+{
+ static char buf[32];
+
+ const char *name = namemap_get_name(map, id);
+ if (name)
+ return name;
+
+ tor_snprintf(buf, sizeof(buf), "{%u}", id);
+
+ return buf;
+}
+
+/**
+ * Helper: As namemap_get_id(), but requires that <b>name</b> is
+ * <b>namelen</b> charaters long, and that <b>namelen</b> is no more than
+ * MAX_NAMEMAP_NAME_LEN.
+ */
+static unsigned
+namemap_get_id_unchecked(const namemap_t *map,
+ const char *name,
+ size_t namelen)
+{
+ union {
+ mapped_name_t n;
+ char storage[MAX_NAMEMAP_NAME_LEN + sizeof(mapped_name_t) + 1];
+ } u;
+ memcpy(u.n.name, name, namelen);
+ u.n.name[namelen] = 0;
+ const mapped_name_t *found = HT_FIND(namemap_ht, &map->ht, &u.n);
+ if (found) {
+ tor_assert(map->names);
+ tor_assert(smartlist_get(map->names, found->intval) == found);
+ return found->intval;
+ }
+
+ return NAMEMAP_ERR;
+}
+
+/**
+ * Return the identifier currently associated by <b>map</b> with the name
+ * <b>name</b>, or NAMEMAP_ERR if no such identifier exists.
+ **/
+unsigned
+namemap_get_id(const namemap_t *map,
+ const char *name)
+{
+ size_t namelen = strlen(name);
+ if (namelen > MAX_NAMEMAP_NAME_LEN) {
+ return NAMEMAP_ERR;
+ }
+
+ return namemap_get_id_unchecked(map, name, namelen);
+}
+
+/**
+ * Return the identifier associated by <b>map</b> with the name
+ * <b>name</b>, allocating a new identifier in <b>map</b> if none exists.
+ *
+ * Return NAMEMAP_ERR if <b>name</b> is too long, or if there are no more
+ * identifiers we can allocate.
+ **/
+unsigned
+namemap_get_or_create_id(namemap_t *map,
+ const char *name)
+{
+ size_t namelen = strlen(name);
+ if (namelen > MAX_NAMEMAP_NAME_LEN) {
+ return NAMEMAP_ERR;
+ }
+
+ if (PREDICT_UNLIKELY(map->names == NULL))
+ map->names = smartlist_new();
+
+ unsigned found = namemap_get_id_unchecked(map, name, namelen);
+ if (found != NAMEMAP_ERR)
+ return found;
+
+ unsigned new_id = (unsigned)smartlist_len(map->names);
+ if (new_id == NAMEMAP_ERR)
+ return NAMEMAP_ERR; /* Can't allocate any more. */
+
+ mapped_name_t *insert = tor_malloc_zero(
+ offsetof(mapped_name_t, name) + namelen + 1);
+ memcpy(insert->name, name, namelen+1);
+ insert->intval = new_id;
+
+ HT_INSERT(namemap_ht, &map->ht, insert);
+ smartlist_add(map->names, insert);
+
+ return new_id;
+}
+
+/** Return the number of entries in 'names' */
+size_t
+namemap_get_size(const namemap_t *map)
+{
+ if (PREDICT_UNLIKELY(map->names == NULL))
+ return 0;
+
+ return smartlist_len(map->names);
+}
+
+/**
+ * Release all storage held in <b>map</b>.
+ */
+void
+namemap_clear(namemap_t *map)
+{
+ if (!map)
+ return;
+
+ HT_CLEAR(namemap_ht, &map->ht);
+ if (map->names) {
+ SMARTLIST_FOREACH(map->names, mapped_name_t *, n,
+ tor_free(n));
+ smartlist_free(map->names);
+ }
+ memset(map, 0, sizeof(*map));
+}
diff --git a/src/lib/container/namemap.h b/src/lib/container/namemap.h
new file mode 100644
index 0000000000..b451c18c68
--- /dev/null
+++ b/src/lib/container/namemap.h
@@ -0,0 +1,35 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_NAMEMAP_H
+#define TOR_NAMEMAP_H
+
+/**
+ * \file namemap.h
+ *
+ * \brief Header for namemap.c
+ **/
+
+#include "lib/cc/compat_compiler.h"
+#include "ext/ht.h"
+
+#include <stddef.h>
+
+typedef struct namemap_t namemap_t;
+
+/** Returned in place of an identifier when an error occurs. */
+#define NAMEMAP_ERR UINT_MAX
+
+void namemap_init(namemap_t *map);
+const char *namemap_get_name(const namemap_t *map, unsigned id);
+const char *namemap_fmt_name(const namemap_t *map, unsigned id);
+unsigned namemap_get_id(const namemap_t *map,
+ const char *name);
+unsigned namemap_get_or_create_id(namemap_t *map,
+ const char *name);
+size_t namemap_get_size(const namemap_t *map);
+void namemap_clear(namemap_t *map);
+
+#endif /* !defined(TOR_NAMEMAP_H) */
diff --git a/src/lib/container/namemap_st.h b/src/lib/container/namemap_st.h
new file mode 100644
index 0000000000..39aa85cc09
--- /dev/null
+++ b/src/lib/container/namemap_st.h
@@ -0,0 +1,41 @@
+/* Copyright (c) 2003-2004, Roger Dingledine
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef NAMEMAP_ST_H
+#define NAMEMAP_ST_H
+
+/**
+ * @file namemap_st.h
+ * @brief Internal declarations for namemap structure.
+ **/
+
+#include "lib/cc/compat_compiler.h"
+#include "ext/ht.h"
+
+struct smartlist_t;
+
+/** Longest allowed name that's allowed in a namemap_t. */
+#define MAX_NAMEMAP_NAME_LEN 128
+
+/** An entry inside a namemap_t. Maps a string to a numeric identifier. */
+typedef struct mapped_name_t {
+ HT_ENTRY(mapped_name_t) node;
+ unsigned intval;
+ char name[FLEXIBLE_ARRAY_MEMBER];
+} mapped_name_t;
+
+/** A structure that allocates small numeric identifiers for names and maps
+ * back and forth between them. */
+struct namemap_t {
+ HT_HEAD(namemap_ht, mapped_name_t) ht;
+ struct smartlist_t *names;
+};
+
+#ifndef COCCI
+/** Macro to initialize a namemap. */
+#define NAMEMAP_INIT() { HT_INITIALIZER(), NULL }
+#endif
+
+#endif /* !defined(NAMEMAP_ST_H) */
diff --git a/src/lib/container/order.c b/src/lib/container/order.c
index f6503a124e..cac241f027 100644
--- a/src/lib/container/order.c
+++ b/src/lib/container/order.c
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/**
diff --git a/src/lib/container/order.h b/src/lib/container/order.h
index a176d6d8a6..5bca095f35 100644
--- a/src/lib/container/order.h
+++ b/src/lib/container/order.h
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
#ifndef TOR_ORDER_H
@@ -57,4 +57,4 @@ third_quartile_uint32(uint32_t *array, int n_elements)
return find_nth_uint32(array, n_elements, (n_elements*3)/4);
}
-#endif /* !defined(TOR_CONTAINER_H) */
+#endif /* !defined(TOR_ORDER_H) */
diff --git a/src/lib/container/smartlist.c b/src/lib/container/smartlist.c
index 3ab2797d68..7784f83957 100644
--- a/src/lib/container/smartlist.c
+++ b/src/lib/container/smartlist.c
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
/**
@@ -652,7 +652,7 @@ smartlist_sort_pointers(smartlist_t *sl)
#define LEFT_CHILD(i) ( 2*(i) + 1 )
#define RIGHT_CHILD(i) ( 2*(i) + 2 )
#define PARENT(i) ( ((i)-1) / 2 )
-/** }@ */
+/** @} */
/** @{ */
/** Helper macros for heaps: Given a local variable <b>idx_field_offset</b>
@@ -678,7 +678,7 @@ smartlist_sort_pointers(smartlist_t *sl)
static inline void
smartlist_heapify(smartlist_t *sl,
int (*compare)(const void *a, const void *b),
- int idx_field_offset,
+ ptrdiff_t idx_field_offset,
int idx)
{
while (1) {
@@ -725,7 +725,7 @@ smartlist_heapify(smartlist_t *sl,
void
smartlist_pqueue_add(smartlist_t *sl,
int (*compare)(const void *a, const void *b),
- int idx_field_offset,
+ ptrdiff_t idx_field_offset,
void *item)
{
int idx;
@@ -754,7 +754,7 @@ smartlist_pqueue_add(smartlist_t *sl,
void *
smartlist_pqueue_pop(smartlist_t *sl,
int (*compare)(const void *a, const void *b),
- int idx_field_offset)
+ ptrdiff_t idx_field_offset)
{
void *top;
tor_assert(sl->num_used);
@@ -778,7 +778,7 @@ smartlist_pqueue_pop(smartlist_t *sl,
void
smartlist_pqueue_remove(smartlist_t *sl,
int (*compare)(const void *a, const void *b),
- int idx_field_offset,
+ ptrdiff_t idx_field_offset,
void *item)
{
int idx = IDX_OF_ITEM(item);
@@ -802,7 +802,7 @@ smartlist_pqueue_remove(smartlist_t *sl,
void
smartlist_pqueue_assert_ok(smartlist_t *sl,
int (*compare)(const void *a, const void *b),
- int idx_field_offset)
+ ptrdiff_t idx_field_offset)
{
int i;
for (i = sl->num_used - 1; i >= 0; --i) {
diff --git a/src/lib/container/smartlist.h b/src/lib/container/smartlist.h
index 77682db03e..458d564cd5 100644
--- a/src/lib/container/smartlist.h
+++ b/src/lib/container/smartlist.h
@@ -1,6 +1,6 @@
/* Copyright (c) 2003-2004, Roger Dingledine
* Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
- * Copyright (c) 2007-2019, The Tor Project, Inc. */
+ * Copyright (c) 2007-2020, The Tor Project, Inc. */
/* See LICENSE for licensing information */
#ifndef TOR_SMARTLIST_H
@@ -13,6 +13,7 @@
**/
#include <stdarg.h>
+#include <stddef.h>
#include "lib/smartlist_core/smartlist_core.h"
#include "lib/smartlist_core/smartlist_foreach.h"
@@ -72,18 +73,18 @@ int smartlist_bsearch_idx(const smartlist_t *sl, const void *key,
void smartlist_pqueue_add(smartlist_t *sl,
int (*compare)(const void *a, const void *b),
- int idx_field_offset,
+ ptrdiff_t idx_field_offset,
void *item);
void *smartlist_pqueue_pop(smartlist_t *sl,
int (*compare)(const void *a, const void *b),
- int idx_field_offset);
+ ptrdiff_t idx_field_offset);
void smartlist_pqueue_remove(smartlist_t *sl,
int (*compare)(const void *a, const void *b),
- int idx_field_offset,
+ ptrdiff_t idx_field_offset,
void *item);
void smartlist_pqueue_assert_ok(smartlist_t *sl,
int (*compare)(const void *a, const void *b),
- int idx_field_offset);
+ ptrdiff_t idx_field_offset);
char *smartlist_join_strings(smartlist_t *sl, const char *join, int terminate,
size_t *len_out) ATTR_MALLOC;
@@ -91,6 +92,7 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join,
size_t join_len, int terminate, size_t *len_out)
ATTR_MALLOC;
+#ifndef COCCI
/* Helper: Given two lists of items, possibly of different types, such that
* both lists are sorted on some common field (as determined by a comparison
* expression <b>cmpexpr</b>), and such that one list (<b>sl1</b>) has no
@@ -164,5 +166,6 @@ char *smartlist_join_strings2(smartlist_t *sl, const char *join,
#define SMARTLIST_FOREACH_JOIN_END(var1, var2) \
} \
STMT_END
+#endif /* !defined(COCCI) */
-#endif /* !defined(TOR_CONTAINER_H) */
+#endif /* !defined(TOR_SMARTLIST_H) */
7apu2bq3rhoylwmucxizk54afw5jyda7pho4j5zdcqpwkufke7zdzwad.onion