Mercurial > ~dholland > hg > ag > index.cgi
comparison 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 |
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 */ |