1*12908Sgarrison # 2*12908Sgarrison 3*12908Sgarrison # include "stdio.h" 4*12908Sgarrison # include "ctype.h" 5*12908Sgarrison # include "streams.h" 6*12908Sgarrison # define nexttry ((high+low)/2) 7*12908Sgarrison 8*12908Sgarrison /* alpha_seek(stream, word, s_size, fold) 9*12908Sgarrison seeks the first line in stream that is at least word. 10*12908Sgarrison assumes that stream is a sorted file of lines. (last char must be \n) 11*12908Sgarrison if fold, assumes that word is lowercase and folds stream to lowercase. 12*12908Sgarrison s_size = size of stream 13*12908Sgarrison returns 1 if word = line, 0 o.w. 14*12908Sgarrison */ 15*12908Sgarrison int alpha_seek(stream, word, s_size, fold) 16*12908Sgarrison FILE *stream; 17*12908Sgarrison char *word; 18*12908Sgarrison long int s_size; 19*12908Sgarrison int fold; 20*12908Sgarrison { long int high, low, mid; /* point to beginning of a line in stream */ 21*12908Sgarrison int ans; /* line(low) < word <= line(high) */ 22*12908Sgarrison char line[maxstr]; 23*12908Sgarrison 24*12908Sgarrison 25*12908Sgarrison /* initialize low (return if first line >= word) */ 26*12908Sgarrison low= 0L; 27*12908Sgarrison pos(low); getline(stream, line); 28*12908Sgarrison if (fold) foldline(line); 29*12908Sgarrison ans= strcmp(line,word); 30*12908Sgarrison 31*12908Sgarrison if ( ans >= 0) 32*12908Sgarrison { pos(low); return(ans==0); } 33*12908Sgarrison 34*12908Sgarrison /* initialize high to "line" after last line */ 35*12908Sgarrison high= s_size; 36*12908Sgarrison 37*12908Sgarrison mid= nextline(stream, nexttry ); 38*12908Sgarrison while (mid < high ) 39*12908Sgarrison { getline(stream,line); 40*12908Sgarrison if (fold) foldline(line); 41*12908Sgarrison if (strcmp(line,word) < 0) low= mid; 42*12908Sgarrison else high= mid; 43*12908Sgarrison mid= nextline(stream, nexttry ); 44*12908Sgarrison } 45*12908Sgarrison 46*12908Sgarrison /* linear search from low to high */ 47*12908Sgarrison low= nextline(stream,low); 48*12908Sgarrison for(;;) 49*12908Sgarrison { if (low>=high) break; 50*12908Sgarrison 51*12908Sgarrison getline(stream,line); 52*12908Sgarrison if (fold) foldline(line); 53*12908Sgarrison ans=strcmp(line,word); 54*12908Sgarrison 55*12908Sgarrison if (ans>=0) break; 56*12908Sgarrison low= ftell(stream); 57*12908Sgarrison } 58*12908Sgarrison 59*12908Sgarrison pos(low); 60*12908Sgarrison if (low=high) return(0); 61*12908Sgarrison else return(ans==0); 62*12908Sgarrison } 63*12908Sgarrison 64*12908Sgarrison 65*12908Sgarrison /* foldline(p): change all uppercase to lowercase in string p 66*12908Sgarrison */ 67*12908Sgarrison foldline(p) 68*12908Sgarrison char *p; 69*12908Sgarrison { for (; *p!=NULL; p++) 70*12908Sgarrison { if (isupper(*p)) *p = tolower(*p); 71*12908Sgarrison } 72*12908Sgarrison } 73