From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail-ua0-f177.google.com ([209.85.217.177]) by ur; Mon Dec 12 01:30:23 EST 2016
Received: by mail-ua0-f177.google.com with SMTP id 20so73083522uak.0
        for <9front@9front.org>; Sun, 11 Dec 2016 22:30:20 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20120113;
        h=mime-version:from:date:message-id:subject:to;
        bh=WCBaE05Qs5HE5HYXnI+VGrQVdOR139iSsZSEFG3V+UM=;
        b=SHNDHHbw4aqcR+4FhtWWJL27JzC3hJc7dpwyXe2PBShTygVZNumJZ/XzxmU7rbatMw
         ImG+FCymkkp8oiFACOEMvJS8CFzAUcQH1bsA7sJOqle3/1jYblum4tFQSkedDW35OTv3
         wJTtssgbOizl4Dg7soZbJIEMadBXDBnrVUjV4z3oqXIq0evJP/yQEGjA/9tw3ljbyIpS
         4hT2tXq2Btswsxh5NH+p+NX/FaQWbOfnc+scLZVyzU0xjR6M5JdnuvakYNO7WpAyPdWo
         0Y5ccQVWk4B/AfVPe03/PiFyogx259VkXIFc/L5JwCIevwbWunZgvl++6bcqyL+dFU/u
         dt3w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20130820;
        h=x-gm-message-state:mime-version:from:date:message-id:subject:to;
        bh=WCBaE05Qs5HE5HYXnI+VGrQVdOR139iSsZSEFG3V+UM=;
        b=BBTGGa0mnmmGs4nsjct3XE7diUKGcrIk2suoH24LEqz9RC5Wa9QJNceaRNCNVq9BOx
         /+w6/ejGzarpQJYRd0qXdoL3hHqyv0P2h4SMXWEdg7bkRnQqSYEylD/slUo9HOCPJxtr
         23VBGUpOgdRHlDd8//xMp/QPQ6lGgj4qrOj8X48m8ADvwKNZfehxJBLsvWl/ZssB4H24
         O11UMCdSo22GnT/MqrJe4kmnSRoTVOGMDTUsWznyypRPIFySwWpko/DDFhjkKIEwvq2t
         bzCu7VKnU1oEb7nRTbKaF6z4OuVs1CqSL1jB3hkilRoloF/rC4evtpfAKKoxaR36wU2K
         II6w==
X-Gm-Message-State: AKaTC03XWgzkf2ZdRB+cc8jR3mmmr8A5R6LOKbcRzGCC6DSjHJcKH+K8FtinCaWLvpH/nM2/Hg07C2f2z/VHqw==
X-Received: by 10.176.81.178 with SMTP id g47mr72756526uaa.78.1481524220194;
 Sun, 11 Dec 2016 22:30:20 -0800 (PST)
MIME-Version: 1.0
Received: by 10.103.48.21 with HTTP; Sun, 11 Dec 2016 22:30:19 -0800 (PST)
From: Benjamin Purcell <benjapurcell@gmail.com>
Date: Mon, 12 Dec 2016 00:30:19 -0600
Message-ID: <CAAsuYKfQT3HzcfsqcFaAGWOH0h-pRjp8Osou4e2ecyYhj=MoJw@mail.gmail.com>
Subject: New Balanced Search Tree Implementation
To: 9front@9front.org
Content-Type: text/plain; charset=UTF-8
List-ID: <9front.9front.org>
List-Help: <http://lists.9front.org>
X-Glyph: ➈
X-Bullshit: overflow-preventing session session-based generator 

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