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
|
#include "stdio.h"
#include "ctype.h"
#include "tib.h"
#define nexttry ((high+low)/2)
#define pos(x) fseek(stream,x,0)
long int nextrecord(), recsize(), nextline();
/* alpha_seek(stream, word, s_size, fold)
seeks the first line in stream that is at least word.
assumes that stream is a sorted file of lines. (last char must be \n)
if fold, assumes that word is lowercase and folds stream to lowercase.
s_size = size of stream
returns 1 if word = line, 0 o.w.
*/
int alpha_seek(stream, word, s_size, fold)
FILE *stream;
char *word;
long int s_size;
int fold;
{ long int high, low, mid; /* point to beginning of a line in stream */
int ans; /* line(low) < word <= line(high) */
char line[MAXSTR];
/* initialize low (return if first line >= word) */
low= 0L;
pos(low); getline(stream, line);
if (fold) foldline(line);
ans= strcmp(line,word);
if ( ans >= 0)
{ pos(low); return(ans==0); }
/* initialize high to "line" after last line */
high= s_size;
mid= nextline(stream, nexttry );
while (mid < high )
{ getline(stream,line);
if (fold) foldline(line);
if (strcmp(line,word) < 0) low= mid;
else high= mid;
mid= nextline(stream, nexttry );
}
/* linear search from low to high */
low= nextline(stream,low);
for(;;)
{ if (low>=high) break;
getline(stream,line);
if (fold) foldline(line);
ans=strcmp(line,word);
if (ans>=0) break;
low= ftell(stream);
}
pos(low);
if (low==high) return(0);
else return(ans==0);
}
/* foldline(p): change all uppercase to lowercase in string p
*/
foldline(p)
char *p;
{ for (; *p!=NULL; p++)
{ if (isupper(*p)) *p = tolower(*p);
}
}
|
