1 /*
2
3 binsearch.c - general binary search functions
4
5 */
6
7 #include <stdio.h>
8 #include <string.h>
9
10 /* Binary search - looks for the key passed at the start of a line
11 in the file associated with open file descriptor fp, and returns
12 a buffer containing the line in the file. */
13
14 #define KEY_LEN (1024)
15 #ifdef UNIX
16 #define LINE_LEN (1024*25)
17 #endif
18 #ifdef MAC
19 #define LINE_LEN (1024*8)
20 #endif
21 #ifdef PC
22 #define LINE_LEN (1024*25)
23 #endif
24
25 static char line[LINE_LEN];
26 long last_bin_search_offset = 0;
27
28 /* General purpose binary search function to search for key as first
29 item on line in open file. Item is delimited by space. */
30
31 #undef getc
32
read_index(long offset,FILE * fp)33 char *read_index(long offset, FILE *fp) {
34 char *linep;
35
36 linep = line;
37 line[0] = '0';
38
39 fseek( fp, offset, SEEK_SET );
40 fgets(linep, LINE_LEN, fp);
41 return(line);
42 }
43
bin_search(char * searchkey,FILE * fp)44 char *bin_search(char *searchkey, FILE *fp)
45 {
46 int c;
47 long top, mid, bot, diff;
48 char *linep, key[KEY_LEN];
49 int length;
50
51 diff=666;
52 linep = line;
53 line[0] = '\0';
54
55 fseek(fp, 0L, 2);
56 top = 0;
57 bot = ftell(fp);
58 mid = (bot - top) / 2;
59
60 do {
61 fseek(fp, mid - 1, 0);
62 if(mid != 1)
63 while((c = getc(fp)) != '\n' && c != EOF);
64 last_bin_search_offset = ftell( fp );
65 fgets(linep, LINE_LEN, fp);
66 length = (int)(strchr(linep, ' ') - linep);
67 strncpy(key, linep, length);
68 key[length] = '\0';
69 if(strcmp(key, searchkey) < 0) {
70 top = mid;
71 diff = (bot - top) / 2;
72 mid = top + diff;
73 }
74 if(strcmp(key, searchkey) > 0) {
75 bot = mid;
76 diff = (bot - top) / 2;
77 mid = top + diff;
78 }
79 } while((strcmp(key, searchkey)) && (diff != 0));
80
81 if(!strcmp(key, searchkey))
82 return(line);
83 else
84 return(NULL);
85 }
86
87 static long offset;
88
bin_search_key(char * searchkey,FILE * fp)89 static int bin_search_key(char *searchkey, FILE *fp)
90 {
91 int c;
92 long top, mid, bot, diff;
93 char *linep, key[KEY_LEN];
94 int length, offset1, offset2;
95
96 /* do binary search to find correct place in file to insert line */
97
98 diff=666;
99 linep = line;
100 line[0] = '\0';
101
102 fseek(fp, 0L, 2);
103 top = 0;
104 bot = ftell(fp);
105 if (bot == 0) {
106 offset = 0;
107 return(0); /* empty file */
108 }
109 mid = (bot - top) / 2;
110
111 /* If only one line in file, don't work through loop */
112
113 length = 0;
114 rewind(fp);
115 while((c = getc(fp)) != '\n' && c != EOF)
116 line[length++] = c;
117 if (getc(fp) == EOF) { /* only 1 line in file */
118 length = (int)(strchr(linep, ' ') - linep);
119 strncpy(key, linep, length);
120 key[length] = '\0';
121 if(strcmp(key, searchkey) > 0) {
122 offset = 0;
123 return(0); /* line with key is not found */
124 } else if (strcmp(key, searchkey) < 0) {
125 offset = ftell(fp);
126 return(0); /* line with key is not found */
127 } else {
128 offset = 0;
129 return(1); /* line with key is found */
130 }
131 }
132
133 do {
134 fseek(fp, mid - 1, 0);
135 if(mid != 1)
136 while((c = getc(fp)) != '\n' && c != EOF);
137 offset1 = ftell(fp); /* offset at start of line */
138 if (fgets(linep, LINE_LEN, fp) != NULL) {
139 offset2 = ftell(fp); /* offset at start of next line */
140 length = (int)(strchr(linep, ' ') - linep);
141 strncpy(key, linep, length);
142 key[length] = '\0';
143 if(strcmp(key, searchkey) < 0) { /* further in file */
144 top = mid;
145 diff = (bot - top) / 2;
146 mid = top + diff;
147 offset = offset2;
148 }
149 if(strcmp(key, searchkey) > 0) { /* earlier in file */
150 bot = mid;
151 diff = (bot - top) / 2;
152 mid = top + diff;
153 offset = offset1;
154 }
155 } else {
156 bot = mid;
157 diff = (bot - top) / 2;
158 mid = top + diff;
159 }
160 } while((strcmp(key, searchkey)) && (diff != 0));
161
162 if(!strcmp(key, searchkey)) {
163 offset = offset1; /* get to start of current line */
164 return(1); /* line with key is found */
165 } else
166 return(0); /* line with key is not found */
167 }
168
169 /* Copy contents from one file to another. */
170
copyfile(FILE * fromfp,FILE * tofp)171 void copyfile(FILE *fromfp, FILE *tofp)
172 {
173 int c;
174
175 while ((c = getc(fromfp)) != EOF)
176 putc(c, tofp);
177 }
178
179 /* Function to replace a line in a file. Returns the original line,
180 or NULL in case of error. */
181
replace_line(char * new_line,char * searchkey,FILE * fp)182 char *replace_line(char *new_line, char *searchkey, FILE *fp)
183 {
184 FILE *tfp; /* temporary file pointer */
185
186 if (!bin_search_key(searchkey, fp))
187 return(NULL); /* line with key not found */
188
189 if ((tfp = tmpfile()) == NULL)
190 return(NULL); /* could not create temp file */
191 fseek(fp, offset, 0);
192 fgets(line, LINE_LEN, fp); /* read original */
193 copyfile(fp, tfp);
194 if (fseek(fp, offset, 0) == -1)
195 return(NULL); /* could not seek to offset */
196 fprintf(fp, new_line); /* write line */
197 rewind(tfp);
198 copyfile(tfp, fp);
199
200 fclose(tfp);
201 fflush(fp);
202
203 return(line);
204 }
205
206 /* Find location to insert line at in file. If line with this
207 key is already in file, return NULL. */
208
insert_line(char * new_line,char * searchkey,FILE * fp)209 char *insert_line(char *new_line, char *searchkey, FILE *fp)
210 {
211 FILE *tfp;
212
213 if (bin_search_key(searchkey, fp))
214 return(NULL);
215
216 if ((tfp = tmpfile()) == NULL)
217 return(NULL); /* could not create temp file */
218 if (fseek(fp, offset, 0) == -1)
219 return(NULL); /* could not seek to offset */
220 copyfile(fp, tfp);
221 if (fseek(fp, offset, 0) == -1)
222 return(NULL); /* could not seek to offset */
223 fprintf(fp, new_line); /* write line */
224 rewind(tfp);
225 copyfile(tfp, fp);
226
227 fclose(tfp);
228 fflush(fp);
229
230 return(new_line);
231 }
232