RPM Package Manager, CVS Repository
  http://rpm5.org/cvs/
  ____________________________________________________________________________

  Server: rpm5.org                         Name:   Jeff Johnson
  Root:   /v/rpm/cvs                       Email:  jbj@rpm5.org
  Module: rpm                              Date:   30-Jan-2008 14:12:52
  Branch: HEAD                             Handle: 2008013013125100

  Added files:
    rpm/lib                 tsbt.c
  Modified files:
    rpm/lib                 .cvsignore Makefile.am

  Log:
    - add toy tsort with Stern-Brocot labeling.

  Summary:
    Revision    Changes     Path
    1.11        +1  -0      rpm/lib/.cvsignore
    2.173       +3  -1      rpm/lib/Makefile.am
    2.1         +172 -0     rpm/lib/tsbt.c
  ____________________________________________________________________________

  patch -p0 <<'@@ .'
  Index: rpm/lib/.cvsignore
  ============================================================================
  $ cvs diff -u -r1.10 -r1.11 .cvsignore
  --- rpm/lib/.cvsignore	28 Dec 2007 18:15:40 -0000	1.10
  +++ rpm/lib/.cvsignore	30 Jan 2008 13:12:51 -0000	1.11
  @@ -6,6 +6,7 @@
   getdate.c
   rpmversion.h
   tpgp
  +tsbt
   .libs
   *.la
   *.lcd
  @@ .
  patch -p0 <<'@@ .'
  Index: rpm/lib/Makefile.am
  ============================================================================
  $ cvs diff -u -r2.172 -r2.173 Makefile.am
  --- rpm/lib/Makefile.am	1 Jan 2008 20:52:22 -0000	2.172
  +++ rpm/lib/Makefile.am	30 Jan 2008 13:12:51 -0000	2.173
  @@ -28,7 +28,7 @@
   
   EXTRA_DIST = genpgp.sh getdate.y librpm.vers tpgp.c
   
  -EXTRA_PROGRAMS = tpgp
  +EXTRA_PROGRAMS = tpgp tsbt
   
   pkgincdir = $(pkgincludedir)$(WITH_PATH_VERSIONED_SUFFIX)
   pkginc_HEADERS = \
  @@ -134,3 +134,5 @@
   genpgp.h: genpgp.sh
   	-sh ./genpgp.sh > genpgp.h
   
  +tsbt_SOURCES = tsbt.c
  +tsbt_LDADD = $(RPM_LDADD)
  @@ .
  patch -p0 <<'@@ .'
  Index: rpm/lib/tsbt.c
  ============================================================================
  $ cvs diff -u -r0 -r2.1 tsbt.c
  --- /dev/null	2008-01-30 14:11:00 +0100
  +++ tsbt.c	2008-01-30 14:12:52 +0100
  @@ -0,0 +1,172 @@
  +#include <system.h>
  +#include <rpmio.h>
  +#include <rpmcli.h>
  +#include <argv.h>
  +#include <popt.h>
  +#include <debug.h>
  +
  +static int an[256];
  +static int bn[256];
  +static int nn[256];
  +static int rn[256];
  +
  +/* Activate nodes, count incoming edgees. */
  +static int count(const char * s)
  +{
  +    int ax = (int)s[0];
  +    int bx;
  +    int i;
  +
  +    if (bn[ax] == 0)
  +	bn[ax] = 1;
  +    for (i = 1; (bx = (int)s[i]) != 0; i++) {
  +	/* Prevent dependencies on self. */
  +	if (bx == ax)
  +	    continue;
  +	if (bn[bx] == 0)
  +	    bn[bx] = 1;
  +	/* Count an incoming edge. */
  +	nn[ax]++;
  +    }
  +    return 0;
  +}
  +
  +/* Compute paths to tree roots. */
  +static int parent(const char * s)
  +{
  +    int ax = (int)s[0];
  +    int bx;
  +    int i;
  +
  +    for (i = 1; (bx = (int)s[i]) != 0; i++) {
  +	/* Prevent dependencies on self. */
  +	if (bx == ax)
  +	    continue;
  +	/* Save first parent. */
  +	if (rn[bx] == 0) {
  +	    rn[bx] = ax;
  +	    continue;
  +	}
  +	/* Multiple parents: prefer parent with fewest edges. */
  +	if (nn[bx] < nn[rn[bx]])
  +	    rn[bx] = ax;
  +    }
  +    return 0;
  +}
  +
  +/* Find node with (a,b) label. */
  +static int SBTfind(int a, int b)
  +{
  +    int i;
  +    for (i = 0; i < 256; i++) {
  +	if (bn[i] == 0)
  +	    continue;
  +	if (a == an[i] && b == bn[i])
  +	    return i;
  +    }
  +    return 0;
  +}
  +
  +/* Mark chains with S-B labels. */
  +static int SBTmark(int i)
  +{
  +    if (i >= 1) {
  +	int px = rn[i];
  +	int rx, lx;
  +
  +	if (px) {
  +	    /* Mark all parent nodes first. */
  +	    rn[i] = 0;		/* Prevent loops. */
  +	    SBTmark(px);
  +	    rn[i] = px;
  +
  +	    /* Does an Lnode already exist? */
  +	    rx = lx = SBTfind(an[px], an[px] + bn[px]);
  +	    while (rx > 0) {
  +		lx = rx;
  +		rx = SBTfind(an[lx] + bn[lx], bn[lx]);
  +	    }
  +	    if (lx < 1) {
  +		/* Add Lnode from parent */
  +		an[i] = an[px];
  +		bn[i] = an[px] + bn[px];
  +	    } else {
  +		/* Append Rnode to Lnode's end-of-chain. */
  +		an[i] = an[lx] + bn[lx];
  +		bn[i] = bn[lx];
  +	    }
  +	}
  +    }
  +    return 0;
  +}
  +
  +static int SBTprnode(int i)
  +{
  +    int a = an[i];
  +    int b = bn[i];
  +
  +    if (b == 1) {
  +	printf("Pnode['%c'] (%d, %d)\n", i, a, b);
  +    } else if (a > b) {
  +	printf("Rnode['%c'] (%d, %d) has Pnode (%d, %d)\n", i, a, b,
  +		(a-b), b);
  +    } else {
  +	printf("Lnode['%c'] (%d, %d)  has Pnode (%d, %d)\n", i, a, b,
  +		a, (b-a));
  +    }
  +
  +    return 0;
  +}
  +
  +static struct poptOption optionsTable[] = {
  + { NULL, '\0', POPT_ARG_INCLUDE_TABLE, rpmcliAllPoptTable, 0,
  +        N_("Common options:"),
  +        NULL },
  +
  +   POPT_AUTOALIAS
  +   POPT_AUTOHELP
  +   POPT_TABLEEND
  +};
  +
  +int
  +main(int argc, char *argv[])
  +{
  +    poptContext optCon = rpmcliInit(argc, argv, optionsTable);
  +    ARGV_t av = NULL;
  +    int ac = 0;
  +    int rc = 0;
  +    int i;
  +
  +    for (i = 0; i < 256; i++) {
  +	an[i] = i;
  +	bn[i] = 0;
  +	nn[i] = 0;
  +	rn[i] = 0;
  +    }
  +
  +    av = poptGetArgs(optCon);
  +    ac = argvCount(av);
  +
  +    /* Activate nodes, count edges. */
  +    for (i = 0; i < ac; i++)
  +	count(av[i]);
  +
  +    /* Save parents of nodes. */
  +    for (i = 0; i < ac; i++)
  +	parent(av[i]);
  +
  +    /* Compute Stern-Brocot labels. */
  +    for (i = 0; i < 256; i++)
  +	SBTmark(i);
  +
  +    /* Print results. */
  +    for (i = 0; i < 256; i++) {
  +	if (bn[i] == 0)
  +	    continue;
  +	SBTprnode(i);
  +    }
  +
  +    optCon = rpmcliFini(optCon);
  +
  +    return rc;
  +}
  @@ .