17 #define BLKMAX (2*BLKMIN)
29 fileoffset_t len
; /* number of bytes in block, always */
30 struct file
*file
; /* non-NULL indicates a file block */
31 fileoffset_t filepos
; /* only meaningful if fp!=NULL */
32 unsigned char *data
; /* only used if fp==NULL */
35 static bt_element_t
bufblkcopy(void *state
, void *av
)
37 struct bufblk
*a
= (struct bufblk
*)av
;
41 ret
= (struct bufblk
*)malloc(sizeof(struct bufblk
));
45 ret
= (struct bufblk
*)malloc(sizeof(struct bufblk
) + BLKMAX
);
46 ret
->data
= (unsigned char *)(ret
+1);
47 memcpy(ret
->data
, a
->data
, BLKMAX
);
51 ret
->filepos
= a
->filepos
;
57 static void bufblkfree(void *state
, void *av
)
59 struct bufblk
*a
= (struct bufblk
*)av
;
64 if (a
->file
->refcount
== 0) {
73 void bufblkpropmake(void *state
, bt_element_t av
, void *destv
)
75 struct bufblk
*a
= (struct bufblk
*)av
;
76 fileoffset_t
*dest
= (fileoffset_t
*)destv
;
81 /* s1 may be NULL (indicating copy s2 into dest). s2 is never NULL. */
82 void bufblkpropmerge(void *state
, void *s1v
, void *s2v
, void *destv
)
84 fileoffset_t
*s1
= (fileoffset_t
*)s1v
;
85 fileoffset_t
*s2
= (fileoffset_t
*)s2v
;
86 fileoffset_t
*dest
= (fileoffset_t
*)destv
;
87 if (!s1
&& !s2
) return; /* don't need to free anything */
88 *dest
= *s2
+ (s1 ?
*s1
: 0);
91 static buffer
*buf_new_from_bt(btree
*bt
)
93 buffer
*buf
= (buffer
*)malloc(sizeof(buffer
));
100 static btree
*buf_bt_new(void)
102 return bt_new(NULL
, bufblkcopy
, bufblkfree
, sizeof(fileoffset_t
),
103 alignof(fileoffset_t
), bufblkpropmake
, bufblkpropmerge
,
107 extern void buf_free(buffer
*buf
)
113 static int bufblksearch(void *tstate
, void *sstate
, int ntrees
,
114 void **props
, int *counts
,
115 bt_element_t
*elts
, int *is_elt
)
117 fileoffset_t
*disttogo
= (fileoffset_t
*)sstate
;
118 fileoffset_t distsofar
= 0;
121 for (i
= 0; i
< ntrees
; i
++) {
123 fileoffset_t sublen
= props
[i
] ?
*(fileoffset_t
*)props
[i
] : 0;
125 if ((props
[i
] && *disttogo
< distsofar
+ sublen
) ||
126 (*disttogo
== distsofar
+ sublen
&& i
== ntrees
-1)) {
127 *disttogo
-= distsofar
;
129 * Descend into this subtree.
138 blk
= (struct bufblk
*)elts
[i
];
140 if (*disttogo
< distsofar
+ blk
->len
) {
142 * Select this element.
144 *disttogo
-= distsofar
;
149 distsofar
+= blk
->len
;
153 assert(!"We should never reach here");
154 return 0; /* placate gcc */
157 static int buf_bt_find_pos(btree
*bt
, fileoffset_t pos
, fileoffset_t
*poswithin
)
161 bt_propfind(bt
, bufblksearch
, &pos
, &index
);
168 * Convert a file-data block of size at most BUFMAX into a
169 * literal-data block. Returns the replacement block (the old one
170 * still needs freeing) or NULL if no conversion performed.
172 static struct bufblk
*buf_convert_to_literal(struct bufblk
*blk
)
174 if (blk
->file
&& blk
->len
<= BLKMAX
) {
176 (struct bufblk
*)malloc(sizeof(struct bufblk
) + BLKMAX
);
177 ret
->data
= (unsigned char *)(ret
+1);
181 fseeko(blk
->file
->fp
, blk
->filepos
, SEEK_SET
);
182 fread(ret
->data
, blk
->len
, 1, blk
->file
->fp
);
191 * Look at blocks `index' and `index+1' of buf. If they're both
192 * literal-data blocks and one of them is undersized, merge or
193 * redistribute. Returns 0 if it has not changed the number of
194 * blocks, or 1 if it has merged two.
196 static int buf_bt_cleanup(btree
*bt
, int index
)
198 struct bufblk
*a
, *b
, *cvt
;
199 fileoffset_t totallen
;
200 unsigned char tmpdata
[BLKMAX
*2];
202 if (index
< 0) return 0;
204 a
= (struct bufblk
*)bt_index(bt
, index
);
205 b
= (struct bufblk
*)bt_index(bt
, index
+1);
207 if ( a
&& (cvt
= buf_convert_to_literal(a
)) != NULL
) {
208 bt_replace(bt
, cvt
, index
);
213 if ( b
&& (cvt
= buf_convert_to_literal(b
)) != NULL
) {
214 bt_replace(bt
, cvt
, index
+1);
219 if (!a
|| !b
|| a
->file
|| b
->file
) return 0;
221 if (a
->len
>= BLKMIN
&& b
->len
>= BLKMIN
) return 0;
223 assert(a
->len
<= BLKMAX
&& b
->len
<= BLKMAX
);
225 /* Use bt_index_w to ensure reference count of 1 on both blocks */
226 a
= (struct bufblk
*)bt_index_w(bt
, index
);
227 b
= (struct bufblk
*)bt_index_w(bt
, index
+1);
230 * So, we have one block with size at most BLKMIN, and another
231 * with size at most BLKMAX. Combined, their maximum possible
232 * size is in excess of BLKMAX, so we can't guaranteeably merge
233 * them into one. If they won't merge, we instead redistribute
236 totallen
= a
->len
+ b
->len
;
237 memcpy(tmpdata
, a
->data
, a
->len
);
238 memcpy(tmpdata
+ a
->len
, b
->data
, b
->len
);
240 if (totallen
>= BLKMAX
) {
242 * Redistribute into two (nearly) equal-sized blocks.
244 a
->len
= totallen
/ 2;
245 b
->len
= totallen
- a
->len
;
247 memcpy(a
->data
, tmpdata
, a
->len
);
248 memcpy(b
->data
, tmpdata
+ a
->len
, b
->len
);
250 bt_replace(bt
, a
, index
);
251 bt_replace(bt
, b
, index
+1);
256 * Just merge into one.
259 memcpy(a
->data
, tmpdata
, a
->len
);
261 bt_replace(bt
, a
, index
);
262 free(bt_delpos(bt
, index
+1));
268 static int buf_bt_splitpoint(btree
*bt
, fileoffset_t pos
)
270 fileoffset_t poswithin
;
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
, fileoffset_t 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
, fileoffset_t 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 fileoffset_t
*output
= (fileoffset_t
*)sstate
;
331 fileoffset_t size
= 0;
334 for (i
= 0; i
< ntrees
; i
++) {
338 size
+= *(fileoffset_t
*)props
[i
];
341 blk
= (struct bufblk
*)elts
[i
];
349 /* Actual return value doesn't matter */
354 static fileoffset_t
buf_bt_length(btree
*bt
)
358 bt_propfind(bt
, bufblklensearch
, &length
, NULL
);
363 extern fileoffset_t
buf_length(buffer
*buf
)
365 return buf_bt_length(buf
->bt
);
368 extern buffer
*buf_new_empty(void)
370 buffer
*buf
= (buffer
*)malloc(sizeof(buffer
));
372 buf
->bt
= buf_bt_new();
377 extern buffer
*buf_new_from_file(FILE *fp
)
379 buffer
*buf
= buf_new_empty();
383 file
= (struct file
*)malloc(sizeof(struct file
));
385 file
->refcount
= 1; /* the reference we're about to make */
387 blk
= (struct bufblk
*)malloc(sizeof(struct bufblk
));
392 fseeko(fp
, 0, SEEK_END
);
393 blk
->len
= ftello(fp
);
395 bt_addpos(buf
->bt
, blk
, 0);
397 buf_bt_cleanup(buf
->bt
, 0);
402 extern void buf_fetch_data(buffer
*buf
, void *vdata
, int len
, fileoffset_t pos
)
405 fileoffset_t poswithin
;
406 fileoffset_t thislen
;
407 unsigned char *data
= (unsigned char *)vdata
;
409 index
= buf_bt_find_pos(buf
->bt
, pos
, &poswithin
);
412 struct bufblk
*blk
= (struct bufblk
*)bt_index(buf
->bt
, index
);
414 thislen
= blk
->len
- poswithin
;
419 fseeko(blk
->file
->fp
, blk
->filepos
+ poswithin
, SEEK_SET
);
420 fread(data
, thislen
, 1, blk
->file
->fp
);
422 memcpy(data
, blk
->data
+ poswithin
, thislen
);
434 extern void buf_insert_data(buffer
*buf
, void *vdata
, int len
,
437 btree
*bt
= buf_bt_new();
438 int nblocks
, blklen1
, extra
;
439 int i
, origlen
= len
;
440 unsigned char *data
= (unsigned char *)vdata
;
442 nblocks
= len
/ ((BLKMIN
+ BLKMAX
)/2);
443 if (nblocks
* BLKMAX
< len
)
445 blklen1
= len
/ nblocks
;
446 extra
= len
% nblocks
;
447 assert(blklen1
>= BLKMIN
|| nblocks
== 1);
448 assert(blklen1
<= BLKMAX
- (extra
!=0));
450 for (i
= 0; i
< nblocks
; i
++) {
452 int blklen
= blklen1
+ (i
< extra
);
454 blk
= (struct bufblk
*)malloc(sizeof(struct bufblk
) + BLKMAX
);
455 blk
->data
= (unsigned char *)(blk
+1);
456 memcpy(blk
->data
, data
, blklen
);
464 bt_addpos(bt
, blk
, i
);
465 assert(origlen
== buf_bt_length(bt
) + len
);
469 assert(origlen
== buf_bt_length(bt
));
471 buf_insert_bt(buf
, bt
, pos
);
474 extern void buf_delete(buffer
*buf
, fileoffset_t len
, fileoffset_t pos
)
476 btree
*left
= buf_bt_split(buf
->bt
, pos
, TRUE
);
477 btree
*right
= buf_bt_split(buf
->bt
, len
, FALSE
);
481 buf
->bt
= buf_bt_join(left
, right
);
484 extern void buf_overwrite_data(buffer
*buf
, void *data
, int len
,
487 buf_delete(buf
, len
, pos
);
488 buf_insert_data(buf
, data
, len
, pos
);
491 extern buffer
*buf_cut(buffer
*buf
, fileoffset_t len
, fileoffset_t pos
)
493 btree
*left
= buf_bt_split(buf
->bt
, pos
, TRUE
);
494 btree
*right
= buf_bt_split(buf
->bt
, len
, FALSE
);
495 btree
*ret
= buf
->bt
;
497 buf
->bt
= buf_bt_join(left
, right
);
499 return buf_new_from_bt(ret
);
502 extern buffer
*buf_copy(buffer
*buf
, fileoffset_t len
, fileoffset_t pos
)
504 btree
*left
= buf_bt_split(buf
->bt
, pos
, TRUE
);
505 btree
*right
= buf_bt_split(buf
->bt
, len
, FALSE
);
506 btree
*ret
= bt_clone(buf
->bt
);
508 buf
->bt
= buf_bt_join(left
, buf
->bt
);
509 buf
->bt
= buf_bt_join(buf
->bt
, right
);
511 return buf_new_from_bt(ret
);
514 extern void buf_paste(buffer
*buf
, buffer
*cutbuffer
, fileoffset_t pos
)
516 btree
*bt
= bt_clone(cutbuffer
->bt
);
517 buf_insert_bt(buf
, bt
, pos
);
521 static FILE *debugfp
= NULL
;
522 extern void buffer_diagnostic(buffer
*buf
, char *title
)
529 debugfp
= fdopen(3, "w");
531 debugfp
= fopen("debug.log", "w");
535 fprintf(debugfp
, "Buffer [%s] is null\n", title
);
539 fprintf(debugfp
, "Listing of buffer [%s]:\n", title
);
541 for (i
= 0; (blk
= (struct bufblk
*)bt_index(buf
->bt
, i
)) != NULL
; i
++) {
542 fprintf(debugfp
, "%016"OFF
"x: %p, len =%8"OFF
"d,", offset
, blk
, blk
->len
);
544 fprintf(debugfp
, " file %p pos %8"OFF
"d\n", blk
->file
, blk
->filepos
);
548 for (j
= 0; j
< blk
->len
; j
++)
549 fprintf(debugfp
, " %02x", blk
->data
[j
]);
551 fprintf(debugfp
, "\n");
555 fprintf(debugfp
, "Listing concluded\n\n");