From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-vk0-f43.google.com ([209.85.213.43]) by ur; Mon Dec 12 01:40:41 EST 2016 Received: by mail-vk0-f43.google.com with SMTP id w194so36012493vkw.2 for <9front@9front.org>; Sun, 11 Dec 2016 22:40:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=m8IzD4PWTtpBP7jjI7tK54+VyM/fbcq5cgy6PbUHxQ8=; b=PMTbSdDL/vdI+aTUHJxXYNfROCsP+S8+msWH9PT5Z/G82aDsGsKT/SfP42+aBgpb2h olyLrd0v0gCSaxbJvKI2y0Mt776oy0J6/xBli0hLTqhgC/t7wSobzTE/3IovRUHUe0z0 RE6b/QBZnAo0yHDm+ZDu963A7ryDwLoJPVnwRkYoQG7v01uzYzIYw6Z4vH1UDBz6numH DNsy0Xj0u8m9Z9+19Xulkw5J/1a18CF6G4OxL8FQ5ttUDR8LlecdA1z792iAhj4Cp9zR htDi771FxdtNupW/g/wubtYsCLXpmlP3Yq8JOQAXsh4rLRsQzD1V+0QRnenVDLYT5TB7 kwWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=m8IzD4PWTtpBP7jjI7tK54+VyM/fbcq5cgy6PbUHxQ8=; b=jwZBd3EUxSnQXc4N83DeuZXN08VPhgutsDGhpZU1ASew5oyzQSzq7fJVUpWfx1uVhJ X4vpc7D6+Ct3jLnbhDerrdkpp7dp38atKiYr2O2/sWQmxZUjSX2vmX9K+yqq65hym0aj UHZDABlk6JPfx54G8rFMoJEW7tTIhnmJ5l2D+K2jrArrnZ9mSuqOQRgQOAu4yYLUr8/F BEX67+8Qmtw8L3UqyyfgeUxXvBGwevyzAtqSW4MqbjIm/pRVC/TP13dFRgDEKEO163po Nhqxxv+uhM8GDWZfKReG3/NlpFeZxs3oqyi7PU/c8MauLax1ed1WR1f4bznOE4jKve0s X5Xg== X-Gm-Message-State: AKaTC03Y7aIeq66PPKwK4tnjKsSCRq/vT0zBzQcrM6bVRncSwtDDQdGwWZFyjdjENfN7T+btmc/F0weJtJhi5Q== X-Received: by 10.31.72.69 with SMTP id v66mr35224305vka.156.1481524838989; Sun, 11 Dec 2016 22:40:38 -0800 (PST) MIME-Version: 1.0 Received: by 10.103.48.21 with HTTP; Sun, 11 Dec 2016 22:40:38 -0800 (PST) In-Reply-To: References: From: Benjamin Purcell Date: Mon, 12 Dec 2016 00:40:38 -0600 Message-ID: Subject: Re: [9front] New Balanced Search Tree Implementation To: 9front@9front.org Content-Type: text/plain; charset=UTF-8 List-ID: <9front.9front.org> List-Help: X-Glyph: ➈ X-Bullshit: firewall high-performance-oriented SOAP high-performance content-driven backend I'm giving it a lucent public license On Mon, Dec 12, 2016 at 12:38 AM, Mehmet Erol Sanliturk wrote: > > > On Sun, Dec 11, 2016 at 10:30 PM, Benjamin Purcell > 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 > > > > >