Re: [9front] New Balanced Search Tree Implementation

[Benjamin Purcell <benjapurcell@gmail.com>]

I'm giving it a lucent public license

On Mon, Dec 12, 2016 at 12:38 AM, Mehmet Erol Sanliturk
<m.e.sanliturk@gmail.com> wrote:
>
>
> On Sun, Dec 11, 2016 at 10:30 PM, Benjamin Purcell <benjapurcell@gmail.com>
> wrote:
>>
>> I have written a binary search tree C library for Plan 9.  It contains
>> implementations of both left leaning red-black trees and AVL trees.
>> In short, you create an AVL tree with
>>
>> Bsttree *t = bstcreate(AVL, cmp);
>>
>> and an LLRB tree with
>>
>> Bsttree *t = bstcreate(LLRB, cmp);
>>
>> Cmp is a comparison function.  All other implementation details are
>> hidden from the user.
>>
>> I intend to replace libavl with this library for the following reasons
>> (details can be found below):
>>
>> 1. You get a choice of BST with a single API.
>> 2. The AVL implementation is much faster.
>> 3. The AVL implementation is smaller and less complicated.
>> 4. The API is easier to use.
>>
>> Item 1. is self-explanatory.
>>
>> Item 2.
>> Measurements of the new AVL implementation against the old one shows
>> that on average:
>> Insertion is 21.9% faster.
>> Deletion is 23.9% faster.
>> Lookup is 14.95% faster.
>> 10 trials were conducted on random keys.  Sequential keys show similar
>> results.
>>
>> Item 3.
>> As for code size, the new AVL implementation plus walk code -- which
>> is shared with the LLRB tree -- comes to 362 source lines of idiomatic
>> C. The old AVL implementation 436 lines.  The old implementation also
>> contains more functions, and calls many of them unnecessarily.
>> Despite the fact that it has more functions, the individual functions
>> themselves are more complicated.
>>
>> Item 4.
>> The AVL implementation's api has the following signatures expressed as
>> abstract types:
>>
>> Avl *(*)(Avltree*, Avl*);
>> Avl *(*)(Avltree*, Avl*, int);
>> Avl *(*)(Avlwalk*);
>> Avltree *(*)(int(*)(Avl*, Avl*));
>> Avlwalk *(*)(Avltree*);
>> void (*)(Avltree*, Avl*, Avl**);
>> void (*)(Avlwalk*);
>>
>> Duplicate signatures have been removed in the above.  The new bst
>> implementation has the following de-duped signatures:
>>
>> Bst *(*)(Bsttree*);
>> Bsttree *(*)(int, int(*cmp)(Bst*, Bst*));
>> Channel *(*)(Bsttree*, Bst*, Bst*, int);
>>
>> but maintains the same functionality.  Which API would you rather use?
>>
>> The code can be found at the following locations:
>>
>> /n/contrib/spew/libbst
>> https://bitbucket.org/spewspews/libbst
>> https://github.com/spewspews/libbst
>>
>> A full man page is include and various tests are included in src/tests
>> including measurements of AVL vs. LLRB, and the new AVL implementation
>> against the old.
>>
>> If there are no objections I would like to remove libavl and add
>> libbst instead.  Libavl has no usages in the source tree.  If anyone tries
>> to compile a libavl program then tough.  There will be a better
>> implementation available and we can always keep it available in
>> contrib or extra.
>>
>> Spew
>
>
>
>
>
> There is no license information file in
>
> https://github.com/spewspews/libbst
>
>
> means , it can not be used in any way  or manner .
>
>
>
> Thank you very much .
>
>
> Mehmet Erol Sanliturk
>
>
>
>
>