11f85f6edSrrh #ifndef lint
2*99c1622cSbostic static char sccsid[] = "@(#)alpha.seek.c 2.3 05/27/93";
31f85f6edSrrh #endif not lint
41736625fSgarrison #
572ee55f5Sgarrison
672ee55f5Sgarrison # include "stdio.h"
772ee55f5Sgarrison # include "ctype.h"
872ee55f5Sgarrison # include "streams.h"
972ee55f5Sgarrison # define nexttry ((high+low)/2)
1072ee55f5Sgarrison
1172ee55f5Sgarrison /* alpha_seek(stream, word, s_size, fold)
1272ee55f5Sgarrison seeks the first line in stream that is at least word.
1372ee55f5Sgarrison assumes that stream is a sorted file of lines. (last char must be \n)
1472ee55f5Sgarrison if fold, assumes that word is lowercase and folds stream to lowercase.
1572ee55f5Sgarrison s_size = size of stream
1672ee55f5Sgarrison returns 1 if word = line, 0 o.w.
1772ee55f5Sgarrison */
alpha_seek(stream,word,s_size,fold)1872ee55f5Sgarrison int alpha_seek(stream, word, s_size, fold)
1972ee55f5Sgarrison FILE *stream;
2072ee55f5Sgarrison char *word;
2172ee55f5Sgarrison long int s_size;
2272ee55f5Sgarrison int fold;
2372ee55f5Sgarrison { long int high, low, mid; /* point to beginning of a line in stream */
2472ee55f5Sgarrison int ans; /* line(low) < word <= line(high) */
2572ee55f5Sgarrison char line[maxstr];
2672ee55f5Sgarrison
2772ee55f5Sgarrison
2872ee55f5Sgarrison /* initialize low (return if first line >= word) */
2972ee55f5Sgarrison low= 0L;
3072ee55f5Sgarrison pos(low); getline(stream, line);
3172ee55f5Sgarrison if (fold) foldline(line);
3272ee55f5Sgarrison ans= strcmp(line,word);
3372ee55f5Sgarrison
3472ee55f5Sgarrison if ( ans >= 0)
3572ee55f5Sgarrison { pos(low); return(ans==0); }
3672ee55f5Sgarrison
3772ee55f5Sgarrison /* initialize high to "line" after last line */
3872ee55f5Sgarrison high= s_size;
3972ee55f5Sgarrison
4072ee55f5Sgarrison mid= nextline(stream, nexttry );
4172ee55f5Sgarrison while (mid < high )
4272ee55f5Sgarrison { getline(stream,line);
4372ee55f5Sgarrison if (fold) foldline(line);
4472ee55f5Sgarrison if (strcmp(line,word) < 0) low= mid;
4572ee55f5Sgarrison else high= mid;
4672ee55f5Sgarrison mid= nextline(stream, nexttry );
4772ee55f5Sgarrison }
4872ee55f5Sgarrison
4972ee55f5Sgarrison /* linear search from low to high */
5072ee55f5Sgarrison low= nextline(stream,low);
5172ee55f5Sgarrison for(;;)
5272ee55f5Sgarrison { if (low>=high) break;
5372ee55f5Sgarrison
5472ee55f5Sgarrison getline(stream,line);
5572ee55f5Sgarrison if (fold) foldline(line);
5672ee55f5Sgarrison ans=strcmp(line,word);
5772ee55f5Sgarrison
5872ee55f5Sgarrison if (ans>=0) break;
5972ee55f5Sgarrison low= ftell(stream);
6072ee55f5Sgarrison }
6172ee55f5Sgarrison
6272ee55f5Sgarrison pos(low);
631736625fSgarrison if (low==high) return(0);
6472ee55f5Sgarrison else return(ans==0);
6572ee55f5Sgarrison }
6672ee55f5Sgarrison
6772ee55f5Sgarrison
6872ee55f5Sgarrison /* foldline(p): change all uppercase to lowercase in string p
6972ee55f5Sgarrison */
foldline(p)7072ee55f5Sgarrison foldline(p)
7172ee55f5Sgarrison char *p;
7272ee55f5Sgarrison { for (; *p!=NULL; p++)
7372ee55f5Sgarrison { if (isupper(*p)) *p = tolower(*p);
7472ee55f5Sgarrison }
7572ee55f5Sgarrison }
76