Mercurial > ~dholland > hg > ag > index.cgi

comparison anagram/agcore/binsort.cpp @ 0:13d2b8934445

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import AnaGram (near-)release tree into Mercurial.
author David A. Holland
date Sat, 22 Dec 2007 17:52:45 -0500
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:13d2b8934445
1 /*
2 * AnaGram, A System for Syntax Directed Programming
3 * Copyright 1993-1999 Parsifal Software. All Rights Reserved.
4 * See the file COPYING for license and usage terms.
5 *
6 * binsort.cpp - Bin sort module (also known as radix sort)
7 */
8
9 #include <string.h>
10 #include "port.h"
11
12 #include "binsort.h"
13 #include "minmax.h"
14 #include "myalloc.h"
15 #include "tsd.h"
16
17
18 static long *bin_sort_tuples(
19 unsigned char *ss,
20 unsigned w,
21 long *x,
22 unsigned nt,
23 unsigned *cp
24 ) {
25 unsigned bin_tail[256];
26 unsigned bin_a[256];
27 unsigned bin_b[256];
28 unsigned *bins[2];
29 unsigned *new_bin_head;
30 unsigned *old_bin_head;
31 int m;
32 unsigned i,j,k;
33 unsigned bin,old_bin;
34 unsigned *link;
35 long *y, *yp;
36 unsigned char *sp;
37
38 yp = y = ALLOCATE(nt, long);
39 ALLOCATE_ST(link, nt);
40 //link = ALLOCATE(nt, unsigned);
41 bins[0] = bin_a;
42 bins[1] = bin_b;
43 m = 0;
44 new_bin_head = bins[m];
45 m ^= 1;
46 memset(new_bin_head, 0xff, 256*sizeof(*new_bin_head));
47 memset(bin_tail, 0xff, 256*sizeof(*bin_tail));
48 sp = ss + *cp++;
49 for (i = 0; i<nt; i++) {
50 bin = sp[(int) x[i]];
51 if ((k = bin_tail[bin]) == (unsigned) -1) {
52 new_bin_head[bin] = i;
53 }
54 else {
55 link[k] = i;
56 }
57 bin_tail[bin] = i;
58 link[i] = (unsigned) -1;
59 }
60 while (--w) {
61 sp = ss + *cp++;
62 old_bin_head = new_bin_head;
63 new_bin_head = bins[m];
64 m ^= 1;
65 memset(new_bin_head, 0xff, 256*sizeof(*new_bin_head));
66 memset(bin_tail, 0xff, 256*sizeof(*bin_tail));
67 for (old_bin = 0; old_bin < 256; old_bin++) {
68 j = old_bin_head[old_bin];
69 while (j != (unsigned) -1) {
70 j = link[i=j];
71 bin = sp[(int) x[i]];
72 if ((k = bin_tail[bin]) == (unsigned) -1){
73 new_bin_head[bin] = i;
74 }
75 else {
76 link[k] = i;
77 }
78 bin_tail[bin] = i;
79 link[i] = (unsigned) -1;
80 }
81 }
82 }
83 for (i = 256; i-- > 0;) {
84 j = *new_bin_head++;
85 while (j != (unsigned) -1){
86 *yp++ = j;
87 j = link[j];
88 }
89 }
90 DEALLOCATE(link);
91 return y;
92 }
93
94 void sort_tuples(tsd *ts, unsigned nc) {
95 long *x,p, *y;
96 unsigned nt;
97 unsigned i,j;
98 unsigned wb,sw;
99 unsigned char *data, *newdata;
100 unsigned tw;
101 unsigned pv[100];
102
103 ok_ptr(ts);
104 nt = ts->nt;
105 tw = ts->tw;
106 if (nt == 0 || nc == 0 || tw == 0) {
107 return;
108 }
109 p = 0;
110 i = min(nc,tw);
111 sw = i*sizeof(*ts->sb);
112 wb = tw * sizeof(*ts->sb);
113 j = 0;
114 while (i--) {
115 unsigned k;
116 for (k = 0; k < sizeof(*ts->sb); k++) {
117 pv[j++] = i*sizeof(*ts->sb) + k;
118 }
119 }
120
121 ALLOCATE_ST(x, nt);
122 /* x = allocate(nt, long); */
123 for (i = 0; i< nt; i++) {
124 x[i] = p;
125 p += wb;
126 }
127 data = (unsigned char *) ts->sb;
128 y = bin_sort_tuples(data, sw, x, nt,pv);
129 newdata = (unsigned char *)(ALLOCATE_ST(ts->sb, nt * tw));
130 /*
131 ts->sb = allocate(nt*tw, int);
132 newdata = (unsigned char *) ts->sb;
133 */
134 ts->na = nt;
135 for (i = 0; i < nt; i++) {
136 memmove(newdata + (int) x[i], data + (int) x[(int) y[i]], wb);
137 }
138 DEALLOCATE(x);
139 DEALLOCATE(data);
140 DEALLOCATE(y);
141 }
142
143 /* End BINSORT.C */