Mercurial > ~dholland > hg > ag > index.cgi
diff anagram/agcore/binsort.cpp @ 0:13d2b8934445
Import AnaGram (near-)release tree into Mercurial.
author | David A. Holland |
---|---|
date | Sat, 22 Dec 2007 17:52:45 -0500 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/anagram/agcore/binsort.cpp Sat Dec 22 17:52:45 2007 -0500 @@ -0,0 +1,143 @@ +/* + * AnaGram, A System for Syntax Directed Programming + * Copyright 1993-1999 Parsifal Software. All Rights Reserved. + * See the file COPYING for license and usage terms. + * + * binsort.cpp - Bin sort module (also known as radix sort) + */ + +#include <string.h> +#include "port.h" + +#include "binsort.h" +#include "minmax.h" +#include "myalloc.h" +#include "tsd.h" + + +static long *bin_sort_tuples( + unsigned char *ss, + unsigned w, + long *x, + unsigned nt, + unsigned *cp +) { + unsigned bin_tail[256]; + unsigned bin_a[256]; + unsigned bin_b[256]; + unsigned *bins[2]; + unsigned *new_bin_head; + unsigned *old_bin_head; + int m; + unsigned i,j,k; + unsigned bin,old_bin; + unsigned *link; + long *y, *yp; + unsigned char *sp; + + yp = y = ALLOCATE(nt, long); + ALLOCATE_ST(link, nt); + //link = ALLOCATE(nt, unsigned); + bins[0] = bin_a; + bins[1] = bin_b; + m = 0; + new_bin_head = bins[m]; + m ^= 1; + memset(new_bin_head, 0xff, 256*sizeof(*new_bin_head)); + memset(bin_tail, 0xff, 256*sizeof(*bin_tail)); + sp = ss + *cp++; + for (i = 0; i<nt; i++) { + bin = sp[(int) x[i]]; + if ((k = bin_tail[bin]) == (unsigned) -1) { + new_bin_head[bin] = i; + } + else { + link[k] = i; + } + bin_tail[bin] = i; + link[i] = (unsigned) -1; + } + while (--w) { + sp = ss + *cp++; + old_bin_head = new_bin_head; + new_bin_head = bins[m]; + m ^= 1; + memset(new_bin_head, 0xff, 256*sizeof(*new_bin_head)); + memset(bin_tail, 0xff, 256*sizeof(*bin_tail)); + for (old_bin = 0; old_bin < 256; old_bin++) { + j = old_bin_head[old_bin]; + while (j != (unsigned) -1) { + j = link[i=j]; + bin = sp[(int) x[i]]; + if ((k = bin_tail[bin]) == (unsigned) -1){ + new_bin_head[bin] = i; + } + else { + link[k] = i; + } + bin_tail[bin] = i; + link[i] = (unsigned) -1; + } + } + } + for (i = 256; i-- > 0;) { + j = *new_bin_head++; + while (j != (unsigned) -1){ + *yp++ = j; + j = link[j]; + } + } + DEALLOCATE(link); + return y; +} + +void sort_tuples(tsd *ts, unsigned nc) { + long *x,p, *y; + unsigned nt; + unsigned i,j; + unsigned wb,sw; + unsigned char *data, *newdata; + unsigned tw; + unsigned pv[100]; + + ok_ptr(ts); + nt = ts->nt; + tw = ts->tw; + if (nt == 0 || nc == 0 || tw == 0) { + return; + } + p = 0; + i = min(nc,tw); + sw = i*sizeof(*ts->sb); + wb = tw * sizeof(*ts->sb); + j = 0; + while (i--) { + unsigned k; + for (k = 0; k < sizeof(*ts->sb); k++) { + pv[j++] = i*sizeof(*ts->sb) + k; + } + } + + ALLOCATE_ST(x, nt); +/* x = allocate(nt, long); */ + for (i = 0; i< nt; i++) { + x[i] = p; + p += wb; + } + data = (unsigned char *) ts->sb; + y = bin_sort_tuples(data, sw, x, nt,pv); + newdata = (unsigned char *)(ALLOCATE_ST(ts->sb, nt * tw)); +/* + ts->sb = allocate(nt*tw, int); + newdata = (unsigned char *) ts->sb; +*/ + ts->na = nt; + for (i = 0; i < nt; i++) { + memmove(newdata + (int) x[i], data + (int) x[(int) y[i]], wb); + } + DEALLOCATE(x); + DEALLOCATE(data); + DEALLOCATE(y); +} + +/* End BINSORT.C */