Here are my red/black tree implementations. They support the usual insert(),
delete(), and find() functions, and also two additions: 1) They function like
multimaps, that is, you can insert multiple nodes with the same key. 2) There
is a findClosest() function which returns the node with the value closest to
(but not less than) the desired key.
Some documentation is in rbtree.h, and there is a commented out main() in
rbtree.c which demonstrates the basics.
All you need to do is change the #define in rbtree.h to store what you want
in your nodes. For XBlockFile the key should be the block size, and the node
should also hold a reference to the actual block. Then you can use
findClosest() to find the smallest (but large enough) block available.
I wasn't sure on the status for FTP-ing, so I uploaded it to my space on AOL:
http://members.aol.com/yennie/rbtree.c
http://members.aol.com/yennie/rbtree.h
Brian
