summaryrefslogtreecommitdiff
path: root/doc/genps.pl
diff options
context:
space:
mode:
authorH. Peter Anvin (Intel) <hpa@zytor.com>2020-06-29 23:23:51 -0700
committerH. Peter Anvin (Intel) <hpa@zytor.com>2020-06-29 23:23:51 -0700
commit367350319b8c5d2a79f400915d7a51be9cb98209 (patch)
tree69f024f48914ca49b5a95e966f3c178535fc4810 /doc/genps.pl
parent2770fc7ac6674a7fd3ef895cecae5d9b5b722dc1 (diff)
downloadnasm-367350319b8c5d2a79f400915d7a51be9cb98209.tar.gz
rbtree: implement a "threaded LLRB tree"
Change the left-leaning red-black (LLRB) trees into left-leaning threaded red-black trees. Instead of NULL pointers at leaf nodes, use the otherwise unused field as a pointer to the lexical predecessor (left) or successor (right). This allows fast previous/next interator operation without needing to keep track of the root of the tree at all times. The additional metadata that needs to be kept can be done for "free" simply by changing "bool red" into a flag field. Signed-off-by: H. Peter Anvin (Intel) <hpa@zytor.com>
Diffstat (limited to 'doc/genps.pl')
0 files changed, 0 insertions, 0 deletions