Gecko [ naturenectar.co.uk ]

Name	Size	Permission	Date
aes.h	1015 B	-rw-r--r--	2021-11-05 09:03
align.h	569 B	-rw-r--r--	2021-11-05 09:03
app.h	6.97 KB	-rw-r--r--	2021-11-05 09:03
assertions.h	2.17 KB	-rw-r--r--	2021-11-05 09:03
astack.h	1.11 KB	-rw-r--r--	2021-11-05 09:03
atomic.h	3.01 KB	-rw-r--r--	2021-11-05 09:03
backtrace.h	3.8 KB	-rw-r--r--	2021-11-05 09:03
barrier.h	1.03 KB	-rw-r--r--	2021-11-05 09:03
base32.h	4.35 KB	-rw-r--r--	2021-11-05 09:03
base64.h	2.8 KB	-rw-r--r--	2021-11-05 09:03
bind9.h	829 B	-rw-r--r--	2021-11-05 09:03
buffer.h	29.91 KB	-rw-r--r--	2021-11-05 09:03
bufferlist.h	1.42 KB	-rw-r--r--	2021-11-05 09:03
cmocka.h	1.35 KB	-rw-r--r--	2021-11-05 09:03
commandline.h	1.67 KB	-rw-r--r--	2021-11-05 09:03
condition.h	1.87 KB	-rw-r--r--	2021-11-05 09:03
counter.h	1.88 KB	-rw-r--r--	2021-11-05 09:03
crc64.h	998 B	-rw-r--r--	2021-11-05 09:03
deprecated.h	662 B	-rw-r--r--	2021-11-05 09:03
dir.h	1.51 KB	-rw-r--r--	2021-11-05 09:03
endian.h	4.75 KB	-rw-r--r--	2021-11-05 09:03
errno.h	659 B	-rw-r--r--	2021-11-05 09:03
errno2result.h	901 B	-rw-r--r--	2025-07-29 21:44
error.h	1.4 KB	-rw-r--r--	2021-11-05 09:03
event.h	3.36 KB	-rw-r--r--	2021-11-05 09:03
eventclass.h	1.41 KB	-rw-r--r--	2021-11-05 09:03
file.h	11.4 KB	-rw-r--r--	2021-11-05 09:03
formatcheck.h	940 B	-rw-r--r--	2021-11-05 09:03
fsaccess.h	7.28 KB	-rw-r--r--	2021-11-05 09:03
fuzz.h	593 B	-rw-r--r--	2021-11-05 09:03
hash.h	1.61 KB	-rw-r--r--	2021-11-05 09:03
heap.h	5.14 KB	-rw-r--r--	2021-11-05 09:03
hex.h	2.74 KB	-rw-r--r--	2021-11-05 09:03
hmac.h	3.88 KB	-rw-r--r--	2021-11-05 09:03
hp.h	4.48 KB	-rw-r--r--	2021-11-05 09:03
ht.h	4.38 KB	-rw-r--r--	2025-07-29 21:41
httpd.h	2.24 KB	-rw-r--r--	2021-11-05 09:03
interfaceiter.h	3.07 KB	-rw-r--r--	2021-11-05 09:03
iterated_hash.h	933 B	-rw-r--r--	2021-11-05 09:03
lang.h	686 B	-rw-r--r--	2021-11-05 09:03
lex.h	9.77 KB	-rw-r--r--	2021-11-05 09:03
lfsr.h	2.89 KB	-rw-r--r--	2021-11-05 09:03
lib.h	1.13 KB	-rw-r--r--	2021-11-05 09:03
likely.h	868 B	-rw-r--r--	2021-11-05 09:03
list.h	7.9 KB	-rw-r--r--	2021-11-05 09:03
log.h	25.88 KB	-rw-r--r--	2021-11-05 09:03
magic.h	999 B	-rw-r--r--	2021-11-05 09:03
managers.h	776 B	-rw-r--r--	2021-11-05 09:03
md.h	5.63 KB	-rw-r--r--	2021-11-05 09:03
mem.h	17.66 KB	-rw-r--r--	2021-11-05 09:03
meminfo.h	710 B	-rw-r--r--	2021-11-05 09:03
mutex.h	4.08 KB	-rw-r--r--	2021-11-05 09:03
mutexatomic.h	9.56 KB	-rw-r--r--	2021-11-05 09:03
mutexblock.h	1.13 KB	-rw-r--r--	2021-11-05 09:03
net.h	8.36 KB	-rw-r--r--	2021-11-05 09:03
netaddr.h	4.67 KB	-rw-r--r--	2021-11-05 09:03
netdb.h	860 B	-rw-r--r--	2021-11-05 09:03
netmgr.h	15.36 KB	-rw-r--r--	2025-07-29 21:41
netscope.h	966 B	-rw-r--r--	2021-11-05 09:03
nonce.h	743 B	-rw-r--r--	2021-11-05 09:03
offset.h	687 B	-rw-r--r--	2021-11-05 09:03
once.h	767 B	-rw-r--r--	2021-11-05 09:03
os.h	670 B	-rw-r--r--	2021-11-05 09:03
parseint.h	1.5 KB	-rw-r--r--	2021-11-05 09:03
platform.h	1.82 KB	-rw-r--r--	2025-07-29 21:41
pool.h	3.41 KB	-rw-r--r--	2021-11-05 09:03
portset.h	3.22 KB	-rw-r--r--	2021-11-05 09:03
print.h	680 B	-rw-r--r--	2021-11-05 09:03
queue.h	1.31 KB	-rw-r--r--	2021-11-05 09:03
quota.h	3.48 KB	-rw-r--r--	2021-11-05 09:03
radix.h	6.85 KB	-rw-r--r--	2021-11-05 09:03
random.h	1.45 KB	-rw-r--r--	2021-11-05 09:03
ratelimiter.h	3.41 KB	-rw-r--r--	2021-11-05 09:03
refcount.h	4.98 KB	-rw-r--r--	2021-11-05 09:03
regex.h	767 B	-rw-r--r--	2021-11-05 09:03
region.h	2.18 KB	-rw-r--r--	2021-11-05 09:03
resource.h	2.79 KB	-rw-r--r--	2021-11-05 09:03
result.h	5.45 KB	-rw-r--r--	2021-11-05 09:03
resultclass.h	1.56 KB	-rw-r--r--	2021-11-05 09:03
rwlock.h	2.48 KB	-rw-r--r--	2021-11-05 09:03
safe.h	1.12 KB	-rw-r--r--	2021-11-05 09:03
serial.h	1.33 KB	-rw-r--r--	2021-11-05 09:03
siphash.h	916 B	-rw-r--r--	2021-11-05 09:03
sockaddr.h	6.13 KB	-rw-r--r--	2021-11-05 09:03
socket.h	23.55 KB	-rw-r--r--	2021-11-05 09:03
stat.h	803 B	-rw-r--r--	2021-11-05 09:03
stats.h	6.53 KB	-rw-r--r--	2021-11-05 09:03
stdatomic.h	8.9 KB	-rw-r--r--	2021-11-05 09:03
stdio.h	1.69 KB	-rw-r--r--	2021-11-05 09:03
stdtime.h	1.36 KB	-rw-r--r--	2021-11-05 09:03
strerr.h	575 B	-rw-r--r--	2021-11-05 09:03
string.h	851 B	-rw-r--r--	2021-11-05 09:03
symtab.h	4.22 KB	-rw-r--r--	2021-11-05 09:03
syslog.h	843 B	-rw-r--r--	2021-11-05 09:03
task.h	16.72 KB	-rw-r--r--	2021-11-05 09:03
taskpool.h	3.2 KB	-rw-r--r--	2021-11-05 09:03
thread.h	1.86 KB	-rw-r--r--	2021-11-05 09:03
time.h	10.85 KB	-rw-r--r--	2021-11-05 09:03
timer.h	7.77 KB	-rw-r--r--	2021-11-05 09:03
tm.h	894 B	-rw-r--r--	2021-11-05 09:03
types.h	5.72 KB	-rw-r--r--	2021-11-05 09:03
url.h	2.62 KB	-rw-r--r--	2021-11-05 09:03
utf8.h	928 B	-rw-r--r--	2021-11-05 09:03
util.h	13.96 KB	-rw-r--r--	2021-11-05 09:03
version.h	499 B	-rw-r--r--	2021-11-05 09:03

Rename

/*
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
 */

#ifndef _RADIX_H
#define _RADIX_H

#include <inttypes.h>
#include <string.h>

#include <isc/magic.h>
#include <isc/mutex.h>
#include <isc/net.h>
#include <isc/refcount.h>
#include <isc/types.h>

#define NETADDR_TO_PREFIX_T(na, pt, bits)                                \
	do {                                                             \
		const void *p = na;                                      \
		memset(&(pt), 0, sizeof(pt));                            \
		if (p != NULL) {                                         \
			(pt).family = (na)->family;                      \
			(pt).bitlen = (bits);                            \
			if ((pt).family == AF_INET6) {                   \
				memmove(&(pt).add.sin6, &(na)->type.in6, \
					((bits) + 7) / 8);               \
			} else                                           \
				memmove(&(pt).add.sin, &(na)->type.in,   \
					((bits) + 7) / 8);               \
		} else {                                                 \
			(pt).family = AF_UNSPEC;                         \
			(pt).bitlen = 0;                                 \
		}                                                        \
		isc_refcount_init(&(pt).refcount, 0);                    \
	} while (0)

typedef struct isc_prefix {
	isc_mem_t	  *mctx;
	unsigned int family;   /* AF_INET | AF_INET6, or AF_UNSPEC for
				* "any" */
	unsigned int   bitlen; /* 0 for "any" */
	isc_refcount_t refcount;
	union {
		struct in_addr	sin;
		struct in6_addr sin6;
	} add;
} isc_prefix_t;

typedef void (*isc_radix_destroyfunc_t)(void *);
typedef void (*isc_radix_processfunc_t)(isc_prefix_t *, void **);

#define isc_prefix_tochar(prefix)  ((char *)&(prefix)->add.sin)
#define isc_prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)

/*
 * We need "first match" when we search the radix tree to preserve
 * compatibility with the existing ACL implementation. Radix trees
 * naturally lend themselves to "best match". In order to get "first match"
 * behavior, we keep track of the order in which entries are added to the
 * tree--and when a search is made, we find all matching entries, and
 * return the one that was added first.
 *
 * An IPv4 prefix and an IPv6 prefix may share a radix tree node if they
 * have the same length and bit pattern (e.g., 127/8 and 7f::/8).  To
 * disambiguate between them, node_num and data are two-element arrays:
 *
 *   - node_num[0] and data[0] are used for IPv4 client addresses
 *   - node_num[1] and data[1] are used for IPv6 client addresses
 *
 * A prefix of 0/0 (aka "any" or "none"), is always stored as IPv4,
 * but matches all IPv6 addresses too.
 */

#define RADIX_V4       0
#define RADIX_V6       1
#define RADIX_FAMILIES 2

#define ISC_RADIX_FAMILY(p) (((p)->family == AF_INET6) ? RADIX_V6 : RADIX_V4)

typedef struct isc_radix_node {
	isc_mem_t		  *mctx;
	uint32_t	       bit;    /* bit length of the prefix */
	isc_prefix_t	     *prefix; /* who we are in radix tree */
	struct isc_radix_node *l, *r;  /* left and right children */
	struct isc_radix_node *parent; /* may be used */
	void		     *data[RADIX_FAMILIES]; /* pointers to IPv4
						      * and IPV6 data */
	int node_num[RADIX_FAMILIES];		     /* which node
						      * this was in
						      * the tree,
						      * or -1 for glue
						      * nodes */
} isc_radix_node_t;

#define RADIX_TREE_MAGIC    ISC_MAGIC('R', 'd', 'x', 'T');
#define RADIX_TREE_VALID(a) ISC_MAGIC_VALID(a, RADIX_TREE_MAGIC);

typedef struct isc_radix_tree {
	unsigned int	  magic;
	isc_mem_t	  *mctx;
	isc_radix_node_t *head;
	uint32_t	  maxbits;	   /* for IP, 32 bit addresses */
	int		  num_active_node; /* for debugging purposes */
	int		  num_added_node;  /* total number of nodes */
} isc_radix_tree_t;

isc_result_t
isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
		 isc_prefix_t *prefix);
/*%<
 * Search 'radix' for the best match to 'prefix'.
 * Return the node found in '*target'.
 *
 * Requires:
 * \li	'radix' to be valid.
 * \li	'target' is not NULL and "*target" is NULL.
 * \li	'prefix' to be valid.
 *
 * Returns:
 * \li	ISC_R_NOTFOUND
 * \li	ISC_R_SUCCESS
 */

isc_result_t
isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
		 isc_radix_node_t *source, isc_prefix_t *prefix);
/*%<
 * Insert 'source' or 'prefix' into the radix tree 'radix'.
 * Return the node added in 'target'.
 *
 * Requires:
 * \li	'radix' to be valid.
 * \li	'target' is not NULL and "*target" is NULL.
 * \li	'prefix' to be valid or 'source' to be non NULL and contain
 *	a valid prefix.
 *
 * Returns:
 * \li	ISC_R_NOMEMORY
 * \li	ISC_R_SUCCESS
 */

void
isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node);
/*%<
 * Remove the node 'node' from the radix tree 'radix'.
 *
 * Requires:
 * \li	'radix' to be valid.
 * \li	'node' to be valid.
 */

isc_result_t
isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits);
/*%<
 * Create a radix tree with a maximum depth of 'maxbits';
 *
 * Requires:
 * \li	'mctx' to be valid.
 * \li	'target' to be non NULL and '*target' to be NULL.
 * \li	'maxbits' to be less than or equal to RADIX_MAXBITS.
 *
 * Returns:
 * \li	ISC_R_NOMEMORY
 * \li	ISC_R_SUCCESS
 */

void
isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
/*%<
 * Destroy a radix tree optionally calling 'func' to clean up node data.
 *
 * Requires:
 * \li	'radix' to be valid.
 */

void
isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func);
/*%<
 * Walk a radix tree calling 'func' to process node data.
 *
 * Requires:
 * \li	'radix' to be valid.
 * \li	'func' to point to a function.
 */

#define RADIX_MAXBITS  128
#define RADIX_NBIT(x)  (0x80 >> ((x)&0x7f))
#define RADIX_NBYTE(x) ((x) >> 3)

#define RADIX_WALK(Xhead, Xnode)                              \
	do {                                                  \
		isc_radix_node_t	 *Xstack[RADIX_MAXBITS + 1]; \
		isc_radix_node_t **Xsp = Xstack;              \
		isc_radix_node_t	 *Xrn = (Xhead);             \
		while ((Xnode = Xrn)) {                       \
			if (Xnode->prefix)

#define RADIX_WALK_END                       \
	if (Xrn->l) {                        \
		if (Xrn->r) {                \
			*Xsp++ = Xrn->r;     \
		}                            \
		Xrn = Xrn->l;                \
	} else if (Xrn->r) {                 \
		Xrn = Xrn->r;                \
	} else if (Xsp != Xstack) {          \
		Xrn = *(--Xsp);              \
	} else {                             \
		Xrn = (isc_radix_node_t *)0; \
	}                                    \
	}                                    \
	}                                    \
	while (0)

#endif /* _RADIX_H */