6e182d98 |
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | #include <string.h> |
4 | #include <ctype.h> |
5 | #include <assert.h> |
6 | |
7 | #include "tweak.h" |
8 | #include "btree.h" |
9 | |
10 | #ifdef TEST_BUFFER |
11 | #define BLKMIN 4 |
12 | #else |
13 | #define BLKMIN 512 |
14 | #endif |
15 | |
16 | #define BLKMAX (2*BLKMIN) |
17 | |
18 | struct file { |
19 | FILE *fp; |
20 | int refcount; |
21 | }; |
22 | |
23 | struct buffer { |
24 | btree *bt; |
25 | }; |
26 | |
27 | struct bufblk { |
28 | int len; /* number of bytes in block, always */ |
29 | struct file *file; /* non-NULL indicates a file block */ |
30 | int filepos; /* only meaningful if fp!=NULL */ |
31 | unsigned char *data; /* only used if fp==NULL */ |
32 | }; |
33 | |
34 | typedef int filesize; /* FIXME: should be larger */ |
35 | |
36 | static bt_element_t bufblkcopy(void *state, void *av) |
37 | { |
38 | struct bufblk *a = (struct bufblk *)av; |
39 | struct bufblk *ret; |
40 | |
41 | if (a->file) { |
42 | ret = (struct bufblk *)malloc(sizeof(struct bufblk)); |
43 | ret->data = NULL; |
44 | a->file->refcount++; |
45 | } else { |
46 | ret = (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX); |
47 | ret->data = (unsigned char *)(ret+1); |
48 | memcpy(ret->data, a->data, BLKMAX); |
49 | } |
50 | |
51 | ret->file = a->file; |
52 | ret->filepos = a->filepos; |
53 | ret->len = a->len; |
54 | |
55 | return ret; |
56 | } |
57 | |
58 | static void bufblkfree(void *state, void *av) |
59 | { |
60 | struct bufblk *a = (struct bufblk *)av; |
61 | |
62 | if (a->file) { |
63 | a->file->refcount--; |
64 | |
65 | if (a->file->refcount == 0) { |
66 | fclose(a->file->fp); |
67 | free(a->file); |
68 | } |
69 | } |
70 | |
71 | free(a); |
72 | } |
73 | |
74 | void bufblkpropmake(void *state, bt_element_t av, void *destv) |
75 | { |
76 | struct bufblk *a = (struct bufblk *)av; |
77 | filesize *dest = (filesize *)destv; |
78 | |
79 | *dest = a->len; |
80 | } |
81 | |
82 | /* s1 may be NULL (indicating copy s2 into dest). s2 is never NULL. */ |
83 | void bufblkpropmerge(void *state, void *s1v, void *s2v, void *destv) |
84 | { |
85 | filesize *s1 = (filesize *)s1v; |
86 | filesize *s2 = (filesize *)s2v; |
87 | filesize *dest = (filesize *)destv; |
88 | if (!s1 && !s2) return; /* don't need to free anything */ |
89 | *dest = *s2 + (s1 ? *s1 : 0); |
90 | } |
91 | |
92 | static buffer *buf_new_from_bt(btree *bt) |
93 | { |
94 | buffer *buf = (buffer *)malloc(sizeof(buffer)); |
95 | |
96 | buf->bt = bt; |
97 | |
98 | return buf; |
99 | } |
100 | |
101 | static btree *buf_bt_new(void) |
102 | { |
103 | return bt_new(NULL, bufblkcopy, bufblkfree, sizeof(filesize), |
104 | alignof(filesize), bufblkpropmake, bufblkpropmerge, |
105 | NULL, 2); |
106 | } |
107 | |
108 | extern void buf_free(buffer *buf) |
109 | { |
110 | bt_free(buf->bt); |
111 | free(buf); |
112 | } |
113 | |
114 | static int bufblksearch(void *tstate, void *sstate, int ntrees, |
115 | void **props, int *counts, |
116 | bt_element_t *elts, int *is_elt) |
117 | { |
118 | int *disttogo = (int *)sstate; |
119 | int distsofar = 0; |
120 | int i; |
121 | |
122 | for (i = 0; i < ntrees; i++) { |
123 | struct bufblk *blk; |
124 | int sublen = props[i] ? *(filesize *)props[i] : 0; |
125 | |
126 | if ((props[i] && *disttogo < distsofar + sublen) || |
127 | (*disttogo == distsofar + sublen && i == ntrees-1)) { |
128 | *disttogo -= distsofar; |
129 | /* |
130 | * Descend into this subtree. |
131 | */ |
132 | *is_elt = FALSE; |
133 | return i; |
134 | } |
135 | |
136 | distsofar += sublen; |
137 | |
138 | if (i < ntrees-1) { |
139 | blk = (struct bufblk *)elts[i]; |
140 | |
141 | if (*disttogo < distsofar + blk->len) { |
142 | /* |
143 | * Select this element. |
144 | */ |
145 | *disttogo -= distsofar; |
146 | *is_elt = TRUE; |
147 | return i; |
148 | } |
149 | |
150 | distsofar += blk->len; |
151 | } |
152 | } |
153 | |
154 | assert(!"We should never reach here"); |
155 | return 0; /* placate gcc */ |
156 | } |
157 | |
158 | static int buf_bt_find_pos(btree *bt, int pos, int *poswithin) |
159 | { |
160 | int index; |
161 | |
162 | bt_propfind(bt, bufblksearch, &pos, &index); |
163 | |
164 | *poswithin = pos; |
165 | return index; |
166 | } |
167 | |
168 | /* |
169 | * Convert a file-data block of size at most BUFMAX into a |
170 | * literal-data block. Returns the replacement block (the old one |
171 | * still needs freeing) or NULL if no conversion performed. |
172 | */ |
173 | static struct bufblk *buf_convert_to_literal(struct bufblk *blk) |
174 | { |
175 | if (blk->file && blk->len <= BLKMAX) { |
176 | struct bufblk *ret = |
177 | (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX); |
178 | ret->data = (unsigned char *)(ret+1); |
179 | ret->file = NULL; |
180 | ret->filepos = 0; |
181 | ret->len = blk->len; |
182 | fseek(blk->file->fp, blk->filepos, SEEK_SET); |
183 | fread(ret->data, blk->len, 1, blk->file->fp); |
184 | |
185 | return ret; |
186 | } |
187 | |
188 | return NULL; |
189 | } |
190 | |
191 | /* |
192 | * Look at blocks `index' and `index+1' of buf. If they're both |
193 | * literal-data blocks and one of them is undersized, merge or |
194 | * redistribute. Returns 0 if it has not changed the number of |
195 | * blocks, or 1 if it has merged two. |
196 | */ |
197 | static int buf_bt_cleanup(btree *bt, int index) |
198 | { |
199 | struct bufblk *a, *b, *cvt; |
200 | int totallen; |
201 | unsigned char tmpdata[BLKMAX*2]; |
202 | |
203 | if (index < 0) return 0; |
204 | |
205 | a = (struct bufblk *)bt_index(bt, index); |
206 | b = (struct bufblk *)bt_index(bt, index+1); |
207 | |
208 | if ( a && (cvt = buf_convert_to_literal(a)) != NULL ) { |
209 | bt_replace(bt, cvt, index); |
210 | bufblkfree(NULL, a); |
211 | a = cvt; |
212 | } |
213 | |
214 | if ( b && (cvt = buf_convert_to_literal(b)) != NULL ) { |
215 | bt_replace(bt, cvt, index+1); |
216 | bufblkfree(NULL, b); |
217 | b = cvt; |
218 | } |
219 | |
220 | if (!a || !b || a->file || b->file) return 0; |
221 | |
222 | if (a->len >= BLKMIN && b->len >= BLKMIN) return 0; |
223 | |
224 | assert(a->len <= BLKMAX && b->len <= BLKMAX); |
225 | |
226 | /* Use bt_index_w to ensure reference count of 1 on both blocks */ |
227 | a = (struct bufblk *)bt_index_w(bt, index); |
228 | b = (struct bufblk *)bt_index_w(bt, index+1); |
229 | |
230 | /* |
231 | * So, we have one block with size at most BLKMIN, and another |
232 | * with size at most BLKMAX. Combined, their maximum possible |
233 | * size is in excess of BLKMAX, so we can't guaranteeably merge |
234 | * them into one. If they won't merge, we instead redistribute |
235 | * data between them. |
236 | */ |
237 | totallen = a->len + b->len; |
238 | memcpy(tmpdata, a->data, a->len); |
239 | memcpy(tmpdata + a->len, b->data, b->len); |
240 | |
241 | if (totallen >= BLKMAX) { |
242 | /* |
243 | * Redistribute into two (nearly) equal-sized blocks. |
244 | */ |
245 | a->len = totallen / 2; |
246 | b->len = totallen - a->len; |
247 | |
248 | memcpy(a->data, tmpdata, a->len); |
249 | memcpy(b->data, tmpdata + a->len, b->len); |
250 | |
251 | bt_replace(bt, a, index); |
252 | bt_replace(bt, b, index+1); |
253 | |
254 | return 0; |
255 | } else { |
256 | /* |
257 | * Just merge into one. |
258 | */ |
259 | a->len = totallen; |
260 | memcpy(a->data, tmpdata, a->len); |
261 | |
262 | bt_replace(bt, a, index); |
263 | free(bt_delpos(bt, index+1)); |
264 | |
265 | return 1; |
266 | } |
267 | } |
268 | |
269 | static int buf_bt_splitpoint(btree *bt, int pos) |
270 | { |
271 | int poswithin, index; |
272 | struct bufblk *blk, *newblk; |
273 | |
274 | index = buf_bt_find_pos(bt, pos, &poswithin); |
275 | |
276 | if (!poswithin) |
277 | return index; /* the nice simple case */ |
278 | |
279 | /* |
280 | * Now split element `index' at position `poswithin'. |
281 | */ |
282 | blk = (struct bufblk *)bt_index_w(bt, index); /* ensure ref count == 1 */ |
283 | newblk = (struct bufblk *)bufblkcopy(NULL, blk); |
284 | |
285 | if (!newblk->file) { |
286 | memcpy(newblk->data, blk->data + poswithin, blk->len - poswithin); |
287 | } else { |
288 | newblk->filepos += poswithin; |
289 | } |
290 | blk->len = poswithin; |
291 | bt_replace(bt, blk, index); |
292 | newblk->len -= poswithin; |
293 | bt_addpos(bt, newblk, index+1); |
294 | |
295 | buf_bt_cleanup(bt, index+1); |
296 | index -= buf_bt_cleanup(bt, index-1); |
297 | |
298 | return index + 1; |
299 | } |
300 | |
301 | static btree *buf_bt_split(btree *bt, int pos, int before) |
302 | { |
303 | int index = buf_bt_splitpoint(bt, pos); |
304 | return bt_splitpos(bt, index, before); |
305 | } |
306 | |
307 | static btree *buf_bt_join(btree *a, btree *b) |
308 | { |
309 | int index = bt_count(a) - 1; |
310 | btree *ret; |
311 | |
312 | ret = bt_join(a, b); |
313 | |
314 | buf_bt_cleanup(ret, index); |
315 | |
316 | return ret; |
317 | } |
318 | |
319 | static void buf_insert_bt(buffer *buf, btree *bt, int pos) |
320 | { |
321 | btree *right = buf_bt_split(buf->bt, pos, FALSE); |
322 | buf->bt = buf_bt_join(buf->bt, bt); |
323 | buf->bt = buf_bt_join(buf->bt, right); |
324 | } |
325 | |
326 | static int bufblklensearch(void *tstate, void *sstate, int ntrees, |
327 | void **props, int *counts, |
328 | bt_element_t *elts, int *is_elt) |
329 | { |
330 | int *output = (int *)sstate; |
331 | int i, size = 0; |
332 | |
333 | for (i = 0; i < ntrees; i++) { |
334 | struct bufblk *blk; |
335 | |
336 | if (props[i]) |
337 | size += *(filesize *)props[i]; |
338 | |
339 | if (i < ntrees-1) { |
340 | blk = (struct bufblk *)elts[i]; |
341 | |
342 | size += blk->len; |
343 | } |
344 | } |
345 | |
346 | *output = size; |
347 | |
348 | /* Actual return value doesn't matter */ |
349 | *is_elt = TRUE; |
350 | return 1; |
351 | } |
352 | |
353 | static int buf_bt_length(btree *bt) |
354 | { |
355 | int length; |
356 | |
357 | bt_propfind(bt, bufblklensearch, &length, NULL); |
358 | |
359 | return length; |
360 | } |
361 | |
362 | extern int buf_length(buffer *buf) |
363 | { |
364 | return buf_bt_length(buf->bt); |
365 | } |
366 | |
367 | extern buffer *buf_new_empty(void) |
368 | { |
369 | buffer *buf = (buffer *)malloc(sizeof(buffer)); |
370 | |
371 | buf->bt = buf_bt_new(); |
372 | |
373 | return buf; |
374 | } |
375 | |
376 | extern buffer *buf_new_from_file(FILE *fp) |
377 | { |
378 | buffer *buf = buf_new_empty(); |
379 | struct bufblk *blk; |
380 | struct file *file; |
381 | |
382 | file = (struct file *)malloc(sizeof(struct file)); |
383 | file->fp = fp; |
384 | file->refcount = 1; /* the reference we're about to make */ |
385 | |
386 | blk = (struct bufblk *)malloc(sizeof(struct bufblk)); |
387 | blk->data = NULL; |
388 | blk->file = file; |
389 | blk->filepos = 0; |
390 | |
391 | fseek(fp, 0, SEEK_END); |
392 | blk->len = ftell(fp); |
393 | |
394 | bt_addpos(buf->bt, blk, 0); |
395 | |
396 | buf_bt_cleanup(buf->bt, 0); |
397 | |
398 | return buf; |
399 | } |
400 | |
401 | extern void buf_fetch_data(buffer *buf, void *vdata, int len, int pos) |
402 | { |
403 | int index, poswithin, thislen; |
404 | unsigned char *data = (unsigned char *)vdata; |
405 | |
406 | index = buf_bt_find_pos(buf->bt, pos, &poswithin); |
407 | |
408 | while (len > 0) { |
409 | struct bufblk *blk = (struct bufblk *)bt_index(buf->bt, index); |
410 | |
411 | thislen = blk->len - poswithin; |
412 | if (thislen > len) |
413 | thislen = len; |
414 | |
415 | if (blk->file) { |
416 | fseek(blk->file->fp, blk->filepos + poswithin, SEEK_SET); |
417 | fread(data, thislen, 1, blk->file->fp); |
418 | } else { |
419 | memcpy(data, blk->data + poswithin, thislen); |
420 | } |
421 | |
422 | data += thislen; |
423 | len -= thislen; |
424 | |
425 | poswithin = 0; |
426 | |
427 | index++; |
428 | } |
429 | } |
430 | |
431 | extern void buf_insert_data(buffer *buf, void *vdata, int len, int pos) |
432 | { |
433 | btree *bt = buf_bt_new(); |
434 | int nblocks, blklen1, extra; |
435 | int i, origlen = len; |
436 | unsigned char *data = (unsigned char *)vdata; |
437 | |
438 | nblocks = len / ((BLKMIN + BLKMAX)/2); |
439 | if (nblocks * BLKMAX < len) |
440 | nblocks++; |
441 | blklen1 = len / nblocks; |
442 | extra = len % nblocks; |
443 | assert(blklen1 >= BLKMIN || nblocks == 1); |
444 | assert(blklen1 <= BLKMAX - (extra!=0)); |
445 | |
446 | for (i = 0; i < nblocks; i++) { |
447 | struct bufblk *blk; |
448 | int blklen = blklen1 + (i < extra); |
449 | |
450 | blk = (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX); |
451 | blk->data = (unsigned char *)(blk+1); |
452 | memcpy(blk->data, data, blklen); |
453 | blk->len = blklen; |
454 | blk->file = NULL; |
455 | blk->filepos = 0; |
456 | |
457 | data += blklen; |
458 | len -= blklen; |
459 | |
460 | bt_addpos(bt, blk, i); |
461 | assert(origlen == buf_bt_length(bt) + len); |
462 | } |
463 | |
464 | assert(len == 0); |
465 | assert(origlen == buf_bt_length(bt)); |
466 | |
467 | buf_insert_bt(buf, bt, pos); |
468 | } |
469 | |
470 | extern void buf_delete(buffer *buf, int len, int pos) |
471 | { |
472 | btree *left = buf_bt_split(buf->bt, pos, TRUE); |
473 | btree *right = buf_bt_split(buf->bt, len, FALSE); |
474 | |
475 | bt_free(buf->bt); |
476 | |
477 | buf->bt = buf_bt_join(left, right); |
478 | } |
479 | |
480 | extern void buf_overwrite_data(buffer *buf, void *data, int len, int pos) |
481 | { |
482 | buf_delete(buf, len, pos); |
483 | buf_insert_data(buf, data, len, pos); |
484 | } |
485 | |
486 | extern buffer *buf_cut(buffer *buf, int len, int pos) |
487 | { |
488 | btree *left = buf_bt_split(buf->bt, pos, TRUE); |
489 | btree *right = buf_bt_split(buf->bt, len, FALSE); |
490 | btree *ret = buf->bt; |
491 | |
492 | buf->bt = buf_bt_join(left, right); |
493 | |
494 | return buf_new_from_bt(ret); |
495 | } |
496 | |
497 | extern buffer *buf_copy(buffer *buf, int len, int pos) |
498 | { |
499 | btree *left = buf_bt_split(buf->bt, pos, TRUE); |
500 | btree *right = buf_bt_split(buf->bt, len, FALSE); |
501 | btree *ret = bt_clone(buf->bt); |
502 | |
503 | buf->bt = buf_bt_join(left, buf->bt); |
504 | buf->bt = buf_bt_join(buf->bt, right); |
505 | |
506 | return buf_new_from_bt(ret); |
507 | } |
508 | |
509 | extern void buf_paste(buffer *buf, buffer *cutbuffer, int pos) |
510 | { |
511 | btree *bt = bt_clone(cutbuffer->bt); |
512 | buf_insert_bt(buf, bt, pos); |
513 | } |
514 | |
515 | #ifdef TEST_BUFFER |
516 | static FILE *debugfp = NULL; |
517 | extern void buffer_diagnostic(buffer *buf, char *title) |
518 | { |
519 | int i, offset; |
520 | struct bufblk *blk; |
521 | |
522 | if (!debugfp) { |
523 | debugfp = fdopen(3, "w"); |
524 | if (!debugfp) |
525 | debugfp = fopen("debug.log", "w"); |
526 | } |
527 | |
528 | if (!buf) { |
529 | fprintf(debugfp, "Buffer [%s] is null\n", title); |
530 | return; |
531 | } |
532 | |
533 | fprintf(debugfp, "Listing of buffer [%s]:\n", title); |
534 | offset = 0; |
535 | for (i = 0; (blk = (struct bufblk *)bt_index(buf->bt, i)) != NULL; i++) { |
536 | fprintf(debugfp, "%08x: %p, len =%8d,", offset, blk, blk->len); |
537 | if (blk->file) { |
538 | fprintf(debugfp, " file %p pos %8d\n", blk->file, blk->filepos); |
539 | } else { |
540 | int j; |
541 | |
542 | for (j = 0; j < blk->len; j++) |
543 | fprintf(debugfp, " %02x", blk->data[j]); |
544 | |
545 | fprintf(debugfp, "\n"); |
546 | } |
547 | offset += blk->len; |
548 | } |
549 | fprintf(debugfp, "Listing concluded\n\n"); |
550 | |
551 | fflush(debugfp); |
552 | } |
553 | #endif |