[patch #5827] Plain balanced tree data structure

[Ben Pfaff]

URL:
  <http://savannah.gnu.org/patch/?5827>

                 Summary: Plain balanced tree data structure
                 Project: PSPP
            Submitted by: blp
            Submitted on: Tuesday 03/27/07 at 21:58
                Category: None
              Item Group: None
                  Status: Ready For Test/Review
             Assigned to: None
        Originator Email: 
             Open/Closed: Open
         Discussion Lock: Any

    _______________________________________________________

Details:

While implementing the data structures backing the new datasheet, I
discovered that I had a need for a plain balanced tree data structure, that
is, one without the augmentations provided by libpspp/abt.[ch].  So this
patch implements one.  The use of a scapegoat tree instead of an AVL or
red-black or splay tree, as would be typical, is just for my own amusement,
but it does perform well and saves a small amount of per-node memory at the
same time.

The patch is against the simpler-proc branch, to which I've already committed
this code, but post-review I propose to commit it, with any suggested
modifications, to the main branch as well.



    _______________________________________________________

File Attachments:


-------------------------------------------------------
Date: Tuesday 03/27/07 at 21:58  Name: bt.patch  Size: 40kB   By: blp
patch
<http://savannah.gnu.org/patch/download.php?file_id=12316>

    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/patch/?5827>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/