1 /*
2
3 binsearch.c - general binary search functions
4
5 */
6
7 #include "wn.h"
8 #include <stdio.h>
9 #include <string.h>
10
11 __FBSDID("$Id: binsrch.c,v 1.15 2005/02/01 16:46:43 wn Rel $");
12
13 /* Binary search - looks for the key passed at the start of a line
14 in the file associated with open file descriptor fp, and returns
15 a buffer containing the line in the file. */
16
17 #define LINE_LEN (1024*25)
18
19 static char line[LINE_LEN];
20 long last_bin_search_offset = 0;
21
22 /* General purpose binary search function to search for key as first
23 item on line in open file. Item is delimited by space. */
24
25 #undef getc
26
27 const char *
read_index(long offset,FILE * fp)28 read_index(long offset, FILE *fp) {
29
30 line[0] = '0';
31
32 fseek(fp, offset, SEEK_SET);
33 fgets(line, LINE_LEN, fp);
34 return(line);
35 }
36
37 static int
sign(int number)38 sign(int number)
39 {
40 if (number > 0)
41 return 1;
42 if (number < 0)
43 return -1;
44 return 0;
45 }
46
47 const char *
bin_search(const char * searchkey,FILE * fp)48 bin_search(const char *searchkey, FILE *fp)
49 {
50 int c;
51 long top, mid, bot; /* should be off_t */
52 int length, keylen;
53
54 fseek(fp, 0L, 2);
55 bot = ftell(fp);
56 mid = bot / 2;
57 keylen = strlen(searchkey);
58
59 for (top = 0; bot - top >= 2; mid = (top + bot) / 2) {
60 fseek(fp, mid - 1, 0);
61 if(mid != 1)
62 while((c = getc(fp)) != '\n' && c != EOF);
63 last_bin_search_offset = ftell(fp);
64 if (fgets(line, LINE_LEN, fp) == NULL)
65 return(NULL);
66 length = strchr(line, ' ') - line;
67 switch (sign(strncmp(line, searchkey, length))) {
68 case 0:
69 /* a match up to the length! */
70 if (length == keylen)
71 return(line);
72 if (length > keylen)
73 /* the word read is longer than ours */
74 goto up;
75 /* FALLTHROUGH */
76 case -1:
77 top = mid;
78 continue;
79 case 1:
80 up:
81 bot = mid;
82 }
83 }
84 return(NULL);
85 }
86