1 + lY>mJq@p/\h bѿ e֞k_I|+? /* * 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 DNS_RBT_H #define DNS_RBT_H 1 /*! \file dns/rbt.h */ #include #include #include #include #include #include #include #include ISC_LANG_BEGINDECLS /*@{*/ /*% * Option values for dns_rbt_findnode() and dns_rbt_findname(). * These are used to form a bitmask. */ #define DNS_RBTFIND_NOOPTIONS 0x00 #define DNS_RBTFIND_EMPTYDATA 0x01 #define DNS_RBTFIND_NOEXACT 0x02 #define DNS_RBTFIND_NOPREDECESSOR 0x04 /*@}*/ #define DNS_RBT_USEMAGIC 1 #define DNS_RBT_LOCKLENGTH (sizeof(((dns_rbtnode_t *)0)->locknum) * 8) #define DNS_RBTNODE_MAGIC ISC_MAGIC('R', 'B', 'N', 'O') #if DNS_RBT_USEMAGIC #define DNS_RBTNODE_VALID(n) ISC_MAGIC_VALID(n, DNS_RBTNODE_MAGIC) #else /* if DNS_RBT_USEMAGIC */ #define DNS_RBTNODE_VALID(n) true #endif /* if DNS_RBT_USEMAGIC */ /*% * This is the structure that is used for each node in the red/black * tree of trees. NOTE WELL: the implementation manages this as a variable * length structure, with the actual wire-format name and other data * appended to this structure. Allocating a contiguous block of memory for * multiple dns_rbtnode structures will not work. */ typedef struct dns_rbtnode dns_rbtnode_t; enum { DNS_RBT_NSEC_NORMAL = 0, /* in main tree */ DNS_RBT_NSEC_HAS_NSEC = 1, /* also has node in nsec tree */ DNS_RBT_NSEC_NSEC = 2, /* in nsec tree */ DNS_RBT_NSEC_NSEC3 = 3 /* in nsec3 tree */ }; struct dns_rbtnode { #if DNS_RBT_USEMAGIC unsigned int magic; #endif /* if DNS_RBT_USEMAGIC */ /*@{*/ /*! * The following bitfields add up to a total bitwidth of 32. * The range of values necessary for each item is indicated, * but in the case of "attributes" the field is wider to accommodate * possible future expansion. * * In each case below the "range" indicated is what's _necessary_ for * the bitfield to hold, not what it actually _can_ hold. * * Note: Tree lock must be held before modifying these * bit-fields. * * Note: The two "unsigned int :0;" unnamed bitfields on either * side of the bitfields below are scaffolding that border the * set of bitfields which are accessed after acquiring the tree * lock. Please don't insert any other bitfield members between * the unnamed bitfields unless they should also be accessed * after acquiring the tree lock. */ unsigned int : 0; /* start of bitfields c/o tree lock */ unsigned int is_root : 1; /*%< range is 0..1 */ unsigned int color : 1; /*%< range is 0..1 */ unsigned int find_callback : 1; /*%< range is 0..1 */ unsigned int attributes : 3; /*%< range is 0..2 */ unsigned int nsec : 2; /*%< range is 0..3 */ unsigned int namelen : 8; /*%< range is 1..255 */ unsigned int offsetlen : 8; /*%< range is 1..128 */ unsigned int oldnamelen : 8; /*%< range is 1..255 */ /*@}*/ /* flags needed for serialization to file */ unsigned int is_mmapped : 1; unsigned int parent_is_relative : 1; unsigned int left_is_relative : 1; unsigned int right_is_relative : 1; unsigned int down_is_relative : 1; unsigned int data_is_relative : 1; /* * full name length; set during serialization, and used * during deserialization to calculate database size. * should be cleared after use. */ unsigned int fullnamelen : 8; /*%< range is 1..255 */ /* node needs to be cleaned from rpz */ unsigned int rpz : 1; unsigned int : 0; /* end of bitfields c/o tree lock */ /*% * These are needed for hashing. The 'uppernode' points to the * node's superdomain node in the parent subtree, so that it can * be reached