GitLab

about what happens with "name" and "origin" parameters when a chain
points to ".".

Cleanup of redundant/useless header file inclusion.

ISC style lint, primarily for function declarations and standalone
comments -- ie, those that appear on a line without any code, which
should be written as follows:
   /*
    * This is a comment.
    */

headers and adding it to source files that need it.

                        to conform to the same style for multiple inclusion
                        protection.

dns_rbt_find* is when no options are passed.

Add DNS_RBTFIND_NOPREDECESSOR to specify that the predecessor
searching code of dns_rbt_findnode should be skipped.

Much comment cleanup w.r.t. DNS_RBTFIND_* options.

Prototyped and documented dns_rbt_deletenode.

Updated documentation for dns_rbt_findnode to describe more what
happens with various return values, and that the chain points to the
DNSSEC predecessor for all non-error returns.

New documentation for dns_rbtnodechain_{prev,next}.

Updated documentation for other dns_rbtnodechain_*.

represent.  point out that memory is only allocated for ancestors in a chain
when ancestor_maxitems > DNS_RBT_ANCESTORBLOCK.

miscellaneous other comment updates.

in a lot of places now.  It _returns_ if it fails to get the necessary memory,
so any function using it should be returning a dns_result_t.

chain_name moved toward start of file, for inlining by findnode.

move_chain_to_last broke out some functionality of dns_rbtnodechain_last
(which now calls it), also for the benefit of findnode.

dns_rbtnodechain_init on the chain used by addnode.

All of the new_foundname concatenation gook was removed from findnode,
which now just sets foundname by using chain_name.

The chain set up by findnode points to the predecessor when the searched
for name is not found.

nodechain_current was changed to take name, origin and node parameters while
returning a dns_result_t.  This allows the chain returned by findnode to
be named.

The nodechain_{first,last,prev} use nodechain_current to set their
names and origins.  nodechain_next does not need it because it will never
have to do the "set the origin to '.' and remove '.' from names in the
root level" bit.  The root level will never be more than one name, and
everything in the megatree is a successor to that node, so 'next' never
reaches the root level.

  I added support for the full search algorithm to the RBT database
  code.  The database has some special needs in searching, in particular
  certain nodes need to be examined before the DOWN pointer is followed.

  I solved this problem by adding a 'callback' bit to the node structure.
  When findnode is called, the caller can supply a callback.  Before we go
  DOWN at a node, we call the callback if the callback bit is set at the
  node.  If the callback returns DNS_R_CONTINUE, we proceed.  Otherwise, we
  will stop right there and return what the caller said to return.  I
  added an 'empty_data_ok' flag to findnode as well, so that nodes with
  empty data can be made candidates for partial match status.

  I also wanted to make dns_rbtnodechain_t public, so that a chain could
  be allocated on the stack by the caller.  I added two routines,
  dns_rbtnodechain_init() and dns_rbtnodechain_reset() to work with them.
  The latter routine frees any dynamically allocated memory associated with
  the chain.  The chain structure now contains the memory context.  I also
  moved get_ancestor_mem() and put_ancestor_mem() up in the file, so that
  inlining could be more effective.

  In the nits department, you wrote

                  *node = result == DNS_R_SUCCESS ? current : NULL;

  In the future, please write this instead (the patch has this change in it):

                  if (result == DNS_R_SUCCESS)
                          *node = current;
                  else
                          *node = NULL;

that adding the name would create too many logical levels in the
tree of trees.

of the node that is found.

Avoids doing any memory allocation when building ancestor chain in 99%
of the cases.

removed some print support function declarations; made static to rbt.c.

bitfields that are used by RBT DB.

name attributes, name length, offset length, and number of bytes
of "padding" that are left over when a node is split.

adjusted node splitting algorithm to preserve the original location
of the lower portion of the split node (eg, when a node has "a.b" as
its name and is split into "a" and "b", "a" retains the same address
space as "a.b".)

when an exact match cannot be found.  This changed the calling interface,
which necessitated changes to rbtdb.c and compress.c.

after the structure.

color stored in single bit

references bitfield width decrease by one

typedef for a node_chain structure, used by dns_rbt_findnode

dns_rbt_create takes a new second argument that is a pointer to a function
which frees node data when the node is deleted.

dns_rbt_addnode provided to return the node that was added.

all the code.

  dns_rbt_node_t changed to dns_rbtnode_t to match ISC conventions.

  main() test routine and support functions removed, to be put in
    bin/tests/rbt_test.c

  adding a node and rotating left/right taught to not use parent pointers.

  deletion disabled because it currently does not know how to not use
    parent pointers, and since they are not being maintained by insertion,
    deleting has no prayer of working.

  several isc_result_t returns changed to dns_result_t.

	Initial (committed) implementation of red/black tree of trees.

Makefile.in:
	add redblack.o to libdns.