From mboxrd@z Thu Jan 1 00:00:00 1970 From: Ramkumar Ramachandra Subject: [PATCH 4/8] Add treap implementation Date: Thu, 15 Jul 2010 18:23:00 +0200 Message-ID: <1279210984-31604-5-git-send-email-artagnon@gmail.com> References: <1279210984-31604-1-git-send-email-artagnon@gmail.com> Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=ISO-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE Cc: David Michael Barr , Jonathan Nieder , Sverre Rabbelier , Junio C Hamano To: Git Mailing List X-From: git-owner@vger.kernel.org Thu Jul 15 18:22:12 2010 Return-path: Envelope-to: gcvg-git-2@lo.gmane.org Received: from vger.kernel.org ([209.132.180.67]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1OZRCL-0006nr-OQ for gcvg-git-2@lo.gmane.org; Thu, 15 Jul 2010 18:22:10 +0200 Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933685Ab0GOQVd (ORCPT ); Thu, 15 Jul 2010 12:21:33 -0400 X-Warning: Original message contained 8-bit characters, however during the SMTP transport session the receiving system did not announce capability of receiving 8-bit SMTP (RFC 1651-1653), and as this message does not have MIME headers (RFC 2045-2049) to enable encoding change, we had very little choice. X-Warning: We ASSUME it is less harmful to add the MIME headers, and convert the text to Quoted-Printable, than not to do so, and to strip the message to 7-bits.. (RFC 1428 Appendix A) X-Warning: We don't know what character set the user used, thus we had to write these MIME-headers with our local system default value. Received: from mail-ey0-f174.google.com ([209.85.215.174]:56031 "EHLO mail-ey0-f174.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933679Ab0GOQVa (ORCPT ); Thu, 15 Jul 2010 12:21:30 -0400 Received: by mail-ey0-f174.google.com with SMTP id 25so213063eya.19 for ; Thu, 15 Jul 2010 09:21:29 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:from:to:cc:subject:date :message-id:x-mailer:in-reply-to:references; bh=YjIRpjkkbdaRvLcrJO8RLt4WjPekgn3mBef5ZqLqiwY=; b=farcrSRdZTMXFiW6/Snvzk7De50iijKz0m/NkPcdLx/qXMGM3CCiR6UpOA2ReJGQaQ aj90G4JlK+Y5b8T7NuYfFiuox0eEzZpI1Un5wKBTbn2cNNFQ5Z5CEJiq4Px7jYR7J1X3 37IIK4/0Vzp/pzIdaOOfMEGU0JqvjC12wmOSU= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:to:cc:subject:date:message-id:x-mailer:in-reply-to:references; b=QplE1Z4pRuqb7s/Fh0ckZf26JmxCKhi/FMHGv2FZxzRuaEQVqT0B9gIJbY7b1EiCgP R52jzXdbVQGRv13h3csw52e0Sq1jimgTc7WK/1zliayV0K9ETCBz4cJwRr7R01ouwLd+ XEspuJ77nKERS7LhSXzr36LYDmURb1/CjnzLA= Received: by 10.213.32.141 with SMTP id c13mr2940096ebd.44.1279210889272; Thu, 15 Jul 2010 09:21:29 -0700 (PDT) Received: from localhost (nat-wireless.itu.dk [130.226.142.243]) by mx.google.com with ESMTPS id a48sm9363251eei.18.2010.07.15.09.21.27 (version=TLSv1/SSLv3 cipher=RC4-MD5); Thu, 15 Jul 2010 09:21:28 -0700 (PDT) X-Mailer: git-send-email 1.7.1 In-Reply-To: <1279210984-31604-1-git-send-email-artagnon@gmail.com> Sender: git-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: git@vger.kernel.org Archived-At: =46rom: Jason Evans Provide macros to generate a type-specific treap implementation and various functions to operate on it. It uses obj_pool.h to store memory nodes in a treap. Previously committed nodes are never removed from the pool; after any *_commit operation, it is assumed (correctly, in the case of svn-fast-export) that someone else must care about them. Treaps provide a memory-efficient binary search tree structure. Insertion/deletion/search are about as about as fast in the average case as red-black trees and the chances of worst-case behavior are vanishingly small, thanks to (pseudo-)randomness. The bad worst-case behavior is a small price to pay, given that treaps are much simpler to implement. =46rom http://www.canonware.com/download/trp/trp_hash/trp.h [db: Altered to reference nodes by offset from a common base pointer] [db: Bob Jenkins' hashing implementation dropped for Knuth's] [db: Methods unnecessary for search and insert dropped] Signed-off-by: David Barr Signed-off-by: Ramkumar Ramachandra Signed-off-by: Junio C Hamano Signed-off-by: Jonathan Nieder --- Makefile | 2 +- vcs-svn/LICENSE | 3 + vcs-svn/trp.h | 220 +++++++++++++++++++++++++++++++++++++++++++++++= ++++++++ vcs-svn/trp.txt | 102 +++++++++++++++++++++++++ 4 files changed, 326 insertions(+), 1 deletions(-) create mode 100644 vcs-svn/trp.h create mode 100644 vcs-svn/trp.txt diff --git a/Makefile b/Makefile index fc31ee0..663a366 100644 --- a/Makefile +++ b/Makefile @@ -1864,7 +1864,7 @@ xdiff-interface.o $(XDIFF_OBJS): \ xdiff/xutils.h xdiff/xprepare.h xdiff/xdiffi.h xdiff/xemit.h =20 $(VCSSVN_OBJS): \ - vcs-svn/obj_pool.h + vcs-svn/obj_pool.h vcs-svn/trp.h endif =20 exec_cmd.s exec_cmd.o: EXTRA_CPPFLAGS =3D \ diff --git a/vcs-svn/LICENSE b/vcs-svn/LICENSE index 6e52372..a3d384c 100644 --- a/vcs-svn/LICENSE +++ b/vcs-svn/LICENSE @@ -1,6 +1,9 @@ Copyright (C) 2010 David Barr . All rights reserved. =20 +Copyright (C) 2008 Jason Evans . +All rights reserved. + Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: diff --git a/vcs-svn/trp.h b/vcs-svn/trp.h new file mode 100644 index 0000000..dd7d5ee --- /dev/null +++ b/vcs-svn/trp.h @@ -0,0 +1,220 @@ +/* + * C macro implementation of treaps. + * + * Usage: + * #include + * #include "trp.h" + * trp_gen(...) + * + * Licensed under a two-clause BSD-style license. + * See LICENSE for details. + */ + +#ifndef TRP_H_ +#define TRP_H_ + +#define MAYBE_UNUSED __attribute__((__unused__)) + +/* Node structure. */ +struct trp_node { + uint32_t trpn_left; + uint32_t trpn_right; +}; + +/* Root structure. */ +struct trp_root { + uint32_t trp_root; +}; + +/* Pointer/Offset conversion. */ +#define trpn_pointer(a_base, a_offset) (a_base##_pointer(a_offset)) +#define trpn_offset(a_base, a_pointer) (a_base##_offset(a_pointer)) +#define trpn_modify(a_base, a_offset) \ + do { \ + if ((a_offset) < a_base##_pool.committed) { \ + uint32_t old_offset =3D (a_offset);\ + (a_offset) =3D a_base##_alloc(1); \ + *trpn_pointer(a_base, a_offset) =3D \ + *trpn_pointer(a_base, old_offset); \ + } \ + } while (0); + +/* Left accessors. */ +#define trp_left_get(a_base, a_field, a_node) \ + (trpn_pointer(a_base, a_node)->a_field.trpn_left) +#define trp_left_set(a_base, a_field, a_node, a_left) \ + do { \ + trpn_modify(a_base, a_node); \ + trp_left_get(a_base, a_field, a_node) =3D (a_left); \ + } while(0) + +/* Right accessors. */ +#define trp_right_get(a_base, a_field, a_node) \ + (trpn_pointer(a_base, a_node)->a_field.trpn_right) +#define trp_right_set(a_base, a_field, a_node, a_right) \ + do { \ + trpn_modify(a_base, a_node); \ + trp_right_get(a_base, a_field, a_node) =3D (a_right); \ + } while(0) + +/* + * Fibonacci hash function. + * The multiplier is the nearest prime to (2^32 times (=E2=88=9A5 - 1)= /2). + * See Knuth =C2=A76.4: volume 3, 3rd ed, p518. + */ +#define trpn_hash(a_node) (uint32_t) (2654435761u * (a_node)) + +/* Priority accessors. */ +#define trp_prio_get(a_node) trpn_hash(a_node) + +/* Node initializer. */ +#define trp_node_new(a_base, a_field, a_node) \ + do { \ + trp_left_set(a_base, a_field, (a_node), ~0); \ + trp_right_set(a_base, a_field, (a_node), ~0); \ + } while(0) + +/* Internal utility macros. */ +#define trpn_first(a_base, a_field, a_root, r_node) \ + do { \ + (r_node) =3D (a_root); \ + if ((r_node) =3D=3D ~0) \ + return NULL; \ + while (~trp_left_get(a_base, a_field, (r_node))) \ + (r_node) =3D trp_left_get(a_base, a_field, (r_node)); \ + } while (0) + +#define trpn_rotate_left(a_base, a_field, a_node, r_node) \ + do { \ + (r_node) =3D trp_right_get(a_base, a_field, (a_node)); \ + trp_right_set(a_base, a_field, (a_node), \ + trp_left_get(a_base, a_field, (r_node))); \ + trp_left_set(a_base, a_field, (r_node), (a_node)); \ + } while(0) + +#define trpn_rotate_right(a_base, a_field, a_node, r_node) \ + do { \ + (r_node) =3D trp_left_get(a_base, a_field, (a_node)); \ + trp_left_set(a_base, a_field, (a_node), \ + trp_right_get(a_base, a_field, (r_node))); \ + trp_right_set(a_base, a_field, (r_node), (a_node)); \ + } while(0) + +#define trp_gen(a_attr, a_pre, a_type, a_field, a_base, a_cmp) \ +a_attr a_type MAYBE_UNUSED *a_pre##first(struct trp_root *treap) \ +{ \ + uint32_t ret; \ + trpn_first(a_base, a_field, treap->trp_root, ret); \ + return trpn_pointer(a_base, ret); \ +} \ +a_attr a_type MAYBE_UNUSED *a_pre##next(struct trp_root *treap, a_type= *node) \ +{ \ + uint32_t ret; \ + uint32_t offset =3D trpn_offset(a_base, node); \ + if (~trp_right_get(a_base, a_field, offset)) { \ + trpn_first(a_base, a_field, \ + trp_right_get(a_base, a_field, offset), ret); \ + } else { \ + uint32_t tnode =3D treap->trp_root; \ + ret =3D ~0; \ + while (1) { \ + int cmp =3D (a_cmp)(trpn_pointer(a_base, offset), \ + trpn_pointer(a_base, tnode)); \ + if (cmp < 0) { \ + ret =3D tnode; \ + tnode =3D trp_left_get(a_base, a_field, tnode); \ + } else if (cmp > 0) { \ + tnode =3D trp_right_get(a_base, a_field, tnode); \ + } else { \ + break; \ + } \ + } \ + } \ + return trpn_pointer(a_base, ret); \ +} \ +a_attr a_type MAYBE_UNUSED *a_pre##search(struct trp_root *treap, a_ty= pe *key) \ +{ \ + int cmp; \ + uint32_t ret =3D treap->trp_root; \ + while (~ret && (cmp =3D (a_cmp)(key, trpn_pointer(a_base,ret)))) { \ + if (cmp < 0) \ + ret =3D trp_left_get(a_base, a_field, ret); \ + else \ + ret =3D trp_right_get(a_base, a_field, ret); \ + } \ + return trpn_pointer(a_base, ret); \ +} \ +a_attr uint32_t MAYBE_UNUSED a_pre##insert_recurse(uint32_t cur_node, = uint32_t ins_node) \ +{ \ + if (cur_node =3D=3D ~0) { \ + return (ins_node); \ + } else { \ + uint32_t ret; \ + int cmp =3D (a_cmp)(trpn_pointer(a_base, ins_node), \ + trpn_pointer(a_base, cur_node)); \ + if (cmp < 0) { \ + uint32_t left =3D a_pre##insert_recurse( \ + trp_left_get(a_base, a_field, cur_node), ins_node); \ + trp_left_set(a_base, a_field, cur_node, left); \ + if (trp_prio_get(left) < trp_prio_get(cur_node)) \ + trpn_rotate_right(a_base, a_field, cur_node, ret); \ + else \ + ret =3D cur_node; \ + } else { \ + uint32_t right =3D a_pre##insert_recurse( \ + trp_right_get(a_base, a_field, cur_node), ins_node); \ + trp_right_set(a_base, a_field, cur_node, right); \ + if (trp_prio_get(right) < trp_prio_get(cur_node)) \ + trpn_rotate_left(a_base, a_field, cur_node, ret); \ + else \ + ret =3D cur_node; \ + } \ + return (ret); \ + } \ +} \ +a_attr void MAYBE_UNUSED a_pre##insert(struct trp_root *treap, a_type = *node) \ +{ \ + uint32_t offset =3D trpn_offset(a_base, node); \ + trp_node_new(a_base, a_field, offset); \ + treap->trp_root =3D a_pre##insert_recurse(treap->trp_root, offset); \ +} \ +a_attr uint32_t MAYBE_UNUSED a_pre##remove_recurse(uint32_t cur_node, = uint32_t rem_node) \ +{ \ + int cmp =3D a_cmp(trpn_pointer(a_base, rem_node), \ + trpn_pointer(a_base, cur_node)); \ + if (cmp =3D=3D 0) { \ + uint32_t ret; \ + uint32_t left =3D trp_left_get(a_base, a_field, cur_node); \ + uint32_t right =3D trp_right_get(a_base, a_field, cur_node); \ + if (left =3D=3D ~0) { \ + if (right =3D=3D ~0) \ + return (~0); \ + } else if (right =3D=3D ~0 || trp_prio_get(left) < trp_prio_get(righ= t)) { \ + trpn_rotate_right(a_base, a_field, cur_node, ret); \ + right =3D a_pre##remove_recurse(cur_node, rem_node); \ + trp_right_set(a_base, a_field, ret, right); \ + return (ret); \ + } \ + trpn_rotate_left(a_base, a_field, cur_node, ret); \ + left =3D a_pre##remove_recurse(cur_node, rem_node); \ + trp_left_set(a_base, a_field, ret, left); \ + return (ret); \ + } else if (cmp < 0) { \ + uint32_t left =3D a_pre##remove_recurse( \ + trp_left_get(a_base, a_field, cur_node), rem_node); \ + trp_left_set(a_base, a_field, cur_node, left); \ + return (cur_node); \ + } else { \ + uint32_t right =3D a_pre##remove_recurse( \ + trp_right_get(a_base, a_field, cur_node), rem_node); \ + trp_right_set(a_base, a_field, cur_node, right); \ + return (cur_node); \ + } \ +} \ +a_attr void MAYBE_UNUSED a_pre##remove(struct trp_root *treap, a_type = *node) \ +{ \ + treap->trp_root =3D a_pre##remove_recurse(treap->trp_root, \ + trpn_offset(a_base, node)); \ +} \ + +#endif diff --git a/vcs-svn/trp.txt b/vcs-svn/trp.txt new file mode 100644 index 0000000..943c385 --- /dev/null +++ b/vcs-svn/trp.txt @@ -0,0 +1,102 @@ +Motivation +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +Treaps provide a memory-efficient binary search tree structure. +Insertion/deletion/search are about as about as fast in the average +case as red-black trees and the chances of worst-case behavior are +vanishingly small, thanks to (pseudo-)randomness. The bad worst-case +behavior is a small price to pay, given that treaps are much simpler +to implement. + =20 +From http://www.canonware.com/download/trp/trp_hash/trp.h + +API +=3D=3D=3D + +The trp API generates a data structure and functions to handle a +large growing set of objects stored in a pool. + +The caller: + +. Specifies parameters for the generated functions with the + trp_gen(static, foo_, ...) macro. + +. Allocates and clears a `struct trp_node` variable. + +. Adds new items to the set using `foo_insert`. + +. Can find a specific item in the set using `foo_search`. + +. Can iterate over items in the set using `foo_first` and `foo_next`. + +. Can remove an item from the set using `foo_remove`. + +. The set is never freed. + +Example: + +---- +struct ex_node { + const char *s; + struct trp_node ex_link; +}; +static struct trp_root ex_base; +obj_pool_gen(ex, struct ex_node, 4096); +trp_gen(static, ex_, struct ex_node, ex_link, ex, strcmp) +struct ex_node *item; + +item =3D ex_pointer(ex_alloc(1)); +item->s =3D "hello"; +ex_insert(&ex_base, item); +item =3D ex_pointer(ex_alloc(1)); +item->s =3D "goodbye"; +ex_insert(&ex_base, item); +for (item =3D ex_first(&ex_base); item; item =3D ex_next(&ex_base, ite= m)) + printf("%s\n", item->s); +---- + +Functions +--------- + +trp_gen(attr, foo_, node_type, link_field, pool, cmp):: + + Generate a type-specific treap implementation. ++ +. The storage class for generated functions will be 'attr' (e.g., `sta= tic`). +. Generated function names are prefixed with 'foo_' (e.g., `treap_`). +. Treap nodes will be of type 'node_type' (e.g., `struct treap_node`). + This type must be a struct with at least one `struct trp_node` field + to point to its children. +. The field used to access child nodes will be 'link_field'. +. All treap nodes must lie in the 'pool' object pool. +. Treap nodes must be totally ordered by the 'cmp' relation, with the + following prototype: ++ +int (*cmp)(node_type \*a, node_type \*b) ++ +and returning a value less than, equal to, or greater than zero +according to the result of comparison. + +void foo_insert(struct trp_root *treap, node_type \*node):: + + Insert node into treap. If inserted multiple times, + a node will appear in the treap multiple times. + +void foo_remove(struct trp_root *treap, node_type \*node):: + + Remove node from treap. Caller must ensure node is + present in treap before using this function. + +node_type *foo_search(struct trp_root \*treap, node_type \*key):: + + Search for a node that matches key. If no match is found, + return what would be key's successor, were key in treap + (NULL if no successor). + +node_type *foo_first(struct trp_root \*treap):: + + Find the first item from the treap, in sorted order. + +node_type *foo_next(struct trp_root \*treap, node_type \*node):: + + Find the next item. --=20 1.7.1