16 #define BLKMAX (2*BLKMIN)
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 */
34 typedef int filesize
; /* FIXME: should be larger */
36 static bt_element_t
bufblkcopy(void *state
, void *av
)
38 struct bufblk
*a
= (struct bufblk
*)av
;
42 ret
= (struct bufblk
*)malloc(sizeof(struct bufblk
));
46 ret
= (struct bufblk
*)malloc(sizeof(struct bufblk
) + BLKMAX
);
47 ret
->data
= (unsigned char *)(ret
+1);
48 memcpy(ret
->data
, a
->data
, BLKMAX
);
52 ret
->filepos
= a
->filepos
;
58 static void bufblkfree(void *state
, void *av
)
60 struct bufblk
*a
= (struct bufblk
*)av
;
65 if (a
->file
->refcount
== 0) {
74 void bufblkpropmake(void *state
, bt_element_t av
, void *destv
)
76 struct bufblk
*a
= (struct bufblk
*)av
;
77 filesize
*dest
= (filesize
*)destv
;
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
)
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);
92 static buffer
*buf_new_from_bt(btree
*bt
)
94 buffer
*buf
= (buffer
*)malloc(sizeof(buffer
));
101 static btree
*buf_bt_new(void)
103 return bt_new(NULL
, bufblkcopy
, bufblkfree
, sizeof(filesize
),
104 alignof(filesize
), bufblkpropmake
, bufblkpropmerge
,
108 extern void buf_free(buffer
*buf
)
114 static int bufblksearch(void *tstate
, void *sstate
, int ntrees
,
115 void **props
, int *counts
,
116 bt_element_t
*elts
, int *is_elt
)
118 int *disttogo
= (int *)sstate
;
122 for (i
= 0; i
< ntrees
; i
++) {
124 int sublen
= props
[i
] ?
*(filesize
*)props
[i
] : 0;
126 if ((props
[i
] && *disttogo
< distsofar
+ sublen
) ||
127 (*disttogo
== distsofar
+ sublen
&& i
== ntrees
-1)) {
128 *disttogo
-= distsofar
;
130 * Descend into this subtree.
139 blk
= (struct bufblk
*)elts
[i
];
141 if (*disttogo
< distsofar
+ blk
->len
) {
143 * Select this element.
145 *disttogo
-= distsofar
;
150 distsofar
+= blk
->len
;
154 assert(!"We should never reach here");
155 return 0; /* placate gcc */
158 static int buf_bt_find_pos(btree
*bt
, int pos
, int *poswithin
)
162 bt_propfind(bt
, bufblksearch
, &pos
, &index
);
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.
173 static struct bufblk
*buf_convert_to_literal(struct bufblk
*blk
)
175 if (blk
->file
&& blk
->len
<= BLKMAX
) {
177 (struct bufblk
*)malloc(sizeof(struct bufblk
) + BLKMAX
);
178 ret
->data
= (unsigned char *)(ret
+1);
182 fseek(blk
->file
->fp
, blk
->filepos
, SEEK_SET
);
183 fread(ret
->data
, blk
->len
, 1, blk
->file
->fp
);
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.
197 static int buf_bt_cleanup(btree
*bt
, int index
)
199 struct bufblk
*a
, *b
, *cvt
;
201 unsigned char tmpdata
[BLKMAX
*2];
203 if (index
< 0) return 0;
205 a
= (struct bufblk
*)bt_index(bt
, index
);
206 b
= (struct bufblk
*)bt_index(bt
, index
+1);
208 if ( a
&& (cvt
= buf_convert_to_literal(a
)) != NULL
) {
209 bt_replace(bt
, cvt
, index
);
214 if ( b
&& (cvt
= buf_convert_to_literal(b
)) != NULL
) {
215 bt_replace(bt
, cvt
, index
+1);
220 if (!a
|| !b
|| a
->file
|| b
->file
) return 0;
222 if (a
->len
>= BLKMIN
&& b
->len
>= BLKMIN
) return 0;
224 assert(a
->len
<= BLKMAX
&& b
->len
<= BLKMAX
);
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);
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
237 totallen
= a
->len
+ b
->len
;
238 memcpy(tmpdata
, a
->data
, a
->len
);
239 memcpy(tmpdata
+ a
->len
, b
->data
, b
->len
);
241 if (totallen
>= BLKMAX
) {
243 * Redistribute into two (nearly) equal-sized blocks.
245 a
->len
= totallen
/ 2;
246 b
->len
= totallen
- a
->len
;
248 memcpy(a
->data
, tmpdata
, a
->len
);
249 memcpy(b
->data
, tmpdata
+ a
->len
, b
->len
);
251 bt_replace(bt
, a
, index
);
252 bt_replace(bt
, b
, index
+1);
257 * Just merge into one.
260 memcpy(a
->data
, tmpdata
, a
->len
);
262 bt_replace(bt
, a
, index
);
263 free(bt_delpos(bt
, index
+1));
269 static int buf_bt_splitpoint(btree
*bt
, int pos
)
271 int poswithin
, index
;
272 struct bufblk
*blk
, *newblk
;
274 index
= buf_bt_find_pos(bt
, pos
, &poswithin
);
277 return index
; /* the nice simple case */
280 * Now split element `index' at position `poswithin'.
282 blk
= (struct bufblk
*)bt_index_w(bt
, index
); /* ensure ref count == 1 */
283 newblk
= (struct bufblk
*)bufblkcopy(NULL
, blk
);
286 memcpy(newblk
->data
, blk
->data
+ poswithin
, blk
->len
- poswithin
);
288 newblk
->filepos
+= poswithin
;
290 blk
->len
= poswithin
;
291 bt_replace(bt
, blk
, index
);
292 newblk
->len
-= poswithin
;
293 bt_addpos(bt
, newblk
, index
+1);
295 buf_bt_cleanup(bt
, index
+1);
296 index
-= buf_bt_cleanup(bt
, index
-1);
301 static btree
*buf_bt_split(btree
*bt
, int pos
, int before
)
303 int index
= buf_bt_splitpoint(bt
, pos
);
304 return bt_splitpos(bt
, index
, before
);
307 static btree
*buf_bt_join(btree
*a
, btree
*b
)
309 int index
= bt_count(a
) - 1;
314 buf_bt_cleanup(ret
, index
);
319 static void buf_insert_bt(buffer
*buf
, btree
*bt
, int pos
)
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
);
326 static int bufblklensearch(void *tstate
, void *sstate
, int ntrees
,
327 void **props
, int *counts
,
328 bt_element_t
*elts
, int *is_elt
)
330 int *output
= (int *)sstate
;
333 for (i
= 0; i
< ntrees
; i
++) {
337 size
+= *(filesize
*)props
[i
];
340 blk
= (struct bufblk
*)elts
[i
];
348 /* Actual return value doesn't matter */
353 static int buf_bt_length(btree
*bt
)
357 bt_propfind(bt
, bufblklensearch
, &length
, NULL
);
362 extern int buf_length(buffer
*buf
)
364 return buf_bt_length(buf
->bt
);
367 extern buffer
*buf_new_empty(void)
369 buffer
*buf
= (buffer
*)malloc(sizeof(buffer
));
371 buf
->bt
= buf_bt_new();
376 extern buffer
*buf_new_from_file(FILE *fp
)
378 buffer
*buf
= buf_new_empty();
382 file
= (struct file
*)malloc(sizeof(struct file
));
384 file
->refcount
= 1; /* the reference we're about to make */
386 blk
= (struct bufblk
*)malloc(sizeof(struct bufblk
));
391 fseek(fp
, 0, SEEK_END
);
392 blk
->len
= ftell(fp
);
394 bt_addpos(buf
->bt
, blk
, 0);
396 buf_bt_cleanup(buf
->bt
, 0);
401 extern void buf_fetch_data(buffer
*buf
, void *vdata
, int len
, int pos
)
403 int index
, poswithin
, thislen
;
404 unsigned char *data
= (unsigned char *)vdata
;
406 index
= buf_bt_find_pos(buf
->bt
, pos
, &poswithin
);
409 struct bufblk
*blk
= (struct bufblk
*)bt_index(buf
->bt
, index
);
411 thislen
= blk
->len
- poswithin
;
416 fseek(blk
->file
->fp
, blk
->filepos
+ poswithin
, SEEK_SET
);
417 fread(data
, thislen
, 1, blk
->file
->fp
);
419 memcpy(data
, blk
->data
+ poswithin
, thislen
);
431 extern void buf_insert_data(buffer
*buf
, void *vdata
, int len
, int pos
)
433 btree
*bt
= buf_bt_new();
434 int nblocks
, blklen1
, extra
;
435 int i
, origlen
= len
;
436 unsigned char *data
= (unsigned char *)vdata
;
438 nblocks
= len
/ ((BLKMIN
+ BLKMAX
)/2);
439 if (nblocks
* BLKMAX
< len
)
441 blklen1
= len
/ nblocks
;
442 extra
= len
% nblocks
;
443 assert(blklen1
>= BLKMIN
|| nblocks
== 1);
444 assert(blklen1
<= BLKMAX
- (extra
!=0));
446 for (i
= 0; i
< nblocks
; i
++) {
448 int blklen
= blklen1
+ (i
< extra
);
450 blk
= (struct bufblk
*)malloc(sizeof(struct bufblk
) + BLKMAX
);
451 blk
->data
= (unsigned char *)(blk
+1);
452 memcpy(blk
->data
, data
, blklen
);
460 bt_addpos(bt
, blk
, i
);
461 assert(origlen
== buf_bt_length(bt
) + len
);
465 assert(origlen
== buf_bt_length(bt
));
467 buf_insert_bt(buf
, bt
, pos
);
470 extern void buf_delete(buffer
*buf
, int len
, int pos
)
472 btree
*left
= buf_bt_split(buf
->bt
, pos
, TRUE
);
473 btree
*right
= buf_bt_split(buf
->bt
, len
, FALSE
);
477 buf
->bt
= buf_bt_join(left
, right
);
480 extern void buf_overwrite_data(buffer
*buf
, void *data
, int len
, int pos
)
482 buf_delete(buf
, len
, pos
);
483 buf_insert_data(buf
, data
, len
, pos
);
486 extern buffer
*buf_cut(buffer
*buf
, int len
, int pos
)
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
;
492 buf
->bt
= buf_bt_join(left
, right
);
494 return buf_new_from_bt(ret
);
497 extern buffer
*buf_copy(buffer
*buf
, int len
, int pos
)
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
);
503 buf
->bt
= buf_bt_join(left
, buf
->bt
);
504 buf
->bt
= buf_bt_join(buf
->bt
, right
);
506 return buf_new_from_bt(ret
);
509 extern void buf_paste(buffer
*buf
, buffer
*cutbuffer
, int pos
)
511 btree
*bt
= bt_clone(cutbuffer
->bt
);
512 buf_insert_bt(buf
, bt
, pos
);
516 static FILE *debugfp
= NULL
;
517 extern void buffer_diagnostic(buffer
*buf
, char *title
)
523 debugfp
= fdopen(3, "w");
525 debugfp
= fopen("debug.log", "w");
529 fprintf(debugfp
, "Buffer [%s] is null\n", title
);
533 fprintf(debugfp
, "Listing of buffer [%s]:\n", title
);
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
);
538 fprintf(debugfp
, " file %p pos %8d\n", blk
->file
, blk
->filepos
);
542 for (j
= 0; j
< blk
->len
; j
++)
543 fprintf(debugfp
, " %02x", blk
->data
[j
]);
545 fprintf(debugfp
, "\n");
549 fprintf(debugfp
, "Listing concluded\n\n");