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