1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
$NetBSD: patch-bsearch,v 1.1.1.1 2002/05/31 12:59:59 seb Exp $
Binary search patch.
Originally from skk-users mailing list
(Masahiro Doteguchi, Mailinglist-Id: 1779).
--- skkserv/skkserv.c.patch1 Mon Nov 6 00:12:57 2000
+++ skkserv/skkserv.c Mon Nov 6 00:15:00 2000
@@ -109,7 +109,7 @@
* Global Variables
*/
-char pgmver[] = "3.9.4nb1 "; /* version number */
+char pgmver[] = "3.9.4nb1 (binary search) "; /* version number */
char *pgmnm; /* program name */
char *jname; /* name of shared dictionary */
@@ -622,7 +622,7 @@
}
/*
- * reply to client: linear search
+ * reply to client: binary search
*/
search(commsock)
@@ -635,6 +635,7 @@
int n; /* number of characters from client */
int sttpnt; /* start point of searching */
int endpnt; /* end point of searching */
+ int curpnt; /* current point of searching */
int errcod = 0; /* error flag */
int sstyle; /* search style */
@@ -743,18 +744,36 @@
endpnt = jtab1[KANA_END - code + 1];
}
}
- fseek(jisho, sttpnt, 0);
if (debug)
- fprintf(stderr, "from %d to %d\n", sttpnt, endpnt);
+ fprintf(errout, "from %d to %d\n", sttpnt, endpnt);
- while ((c = fgetc(jisho)) != EOF) {
+ for (;;) {
+ if ((sstyle & 0x4) == 0) { /* binary search? */
+ curpnt = (sttpnt + endpnt) / 2;
+ fseek(jisho, curpnt, 0);
+ while ((c = fgetc(jisho)) != EOF) {
+ curpnt++;
+ if (c == EOL) break;
+ }
+ if (c == EOF) break;
+ if (curpnt >= endpnt) {
+ fseek(jisho, sttpnt, 0);
+ sstyle |= 0x4; /* linear search */
+ }
+ }
+
+ if (debug) {fprintf(errout, "%d:%d\t%d\t%d\t", sstyle, sttpnt, curpnt, endpnt);}
+ c = fgetc(jisho);
pbuf = &combuf[1]; /* ' ' is end-symbol */
while (c == *pbuf && c != ' ' && c != EOL) {
- if (debug) {fprintf(errout, "1:%d:%d:%d:%d:\n", c, *pbuf, ' ', EOL);}
+/* if (debug) {fprintf(errout, "1:%d:%d:%d:%d:", c, *pbuf, ' ', EOL);}*/
+ if (debug) {fprintf(errout, "%c", c);}
c = fgetc(jisho); pbuf++;
- }
- if (debug) {fprintf(errout, "1:%d:%d:%d:%d:\n", c, *pbuf, ' ', EOL);}
+ }
+/* if (debug) {fprintf(errout, "1:%d:%d:%d:%d:", c, *pbuf, ' ', EOL);}*/
+ if (debug) {fprintf(errout, "%c", c);}
if (c == ' ' && (*pbuf == ' ' || *pbuf == '\n')) { /* found */
+ if (debug) {fprintf(errout, "found\n");}
if ((errcod = write(commsock, SERVER_FOUND, 1)) >= 0)
while ((c = fgetc(jisho)) != EOF) {
*pbuf = c;
@@ -770,18 +789,35 @@
}
return(0);
}
- if (comp(*pbuf, c, sstyle)) {
- if (debug) {
- fprintf(stderr, "comp break %d \n", ftell(jisho));
- }
- break;
+ if (debug) {
+ int ch;
+
+ if (c != ' ')
+ do {
+ ch = fgetc(jisho);
+ fprintf(errout, "%c", ch);
+ } while (ch != ' ' && ch != EOL);
+ fprintf(errout, "unmatched\n");
}
- /* fix 1992/3/6 under suggestion */
- /* of guchi@pfu.fujitsu.co.jp */
- while ((c = fgetc(jisho)) != EOF) {
- if (c == EOL) break;
+ if (sstyle & 0x4) {
+ if (comp(*pbuf, c, sstyle&~0x4)) {
+ if (debug) {
+ fprintf(stderr, "comp break %d \n", ftell(jisho));
+ }
+ break;
+ }
+ /* fix 1992/3/6 under suggestion */
+ /* of guchi@pfu.fujitsu.co.jp */
+ while ((c = fgetc(jisho)) != EOF) {
+ if (c == EOL) break;
+ }
+ if (ftell(jisho) >= endpnt) break;
+ } else {
+ if (comp(*pbuf, c, sstyle&~0x4))
+ endpnt = curpnt;
+ else
+ sttpnt = curpnt;
}
- if (ftell(jisho) >= endpnt) break;
}
if ((errcod = write(commsock, SERVER_NOT_FOUND, 1)) >= 0) {
|
