| 1 | #include "tweak.h" |
| 2 | |
| 3 | #include <stdio.h> |
| 4 | #include <stdlib.h> |
| 5 | #include <string.h> |
| 6 | #include <ctype.h> |
| 7 | #include <assert.h> |
| 8 | |
| 9 | #include "btree.h" |
| 10 | |
| 11 | #ifdef TEST_BUFFER |
| 12 | #define BLKMIN 4 |
| 13 | #else |
| 14 | #define BLKMIN 512 |
| 15 | #endif |
| 16 | |
| 17 | #define BLKMAX (2*BLKMIN) |
| 18 | |
| 19 | struct file { |
| 20 | FILE *fp; |
| 21 | int refcount; |
| 22 | }; |
| 23 | |
| 24 | struct buffer { |
| 25 | btree *bt; |
| 26 | }; |
| 27 | |
| 28 | struct bufblk { |
| 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 */ |
| 33 | }; |
| 34 | |
| 35 | static bt_element_t bufblkcopy(void *state, void *av) |
| 36 | { |
| 37 | struct bufblk *a = (struct bufblk *)av; |
| 38 | struct bufblk *ret; |
| 39 | |
| 40 | if (a->file) { |
| 41 | ret = (struct bufblk *)malloc(sizeof(struct bufblk)); |
| 42 | ret->data = NULL; |
| 43 | a->file->refcount++; |
| 44 | } else { |
| 45 | ret = (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX); |
| 46 | ret->data = (unsigned char *)(ret+1); |
| 47 | memcpy(ret->data, a->data, BLKMAX); |
| 48 | } |
| 49 | |
| 50 | ret->file = a->file; |
| 51 | ret->filepos = a->filepos; |
| 52 | ret->len = a->len; |
| 53 | |
| 54 | return ret; |
| 55 | } |
| 56 | |
| 57 | static void bufblkfree(void *state, void *av) |
| 58 | { |
| 59 | struct bufblk *a = (struct bufblk *)av; |
| 60 | |
| 61 | if (a->file) { |
| 62 | a->file->refcount--; |
| 63 | |
| 64 | if (a->file->refcount == 0) { |
| 65 | fclose(a->file->fp); |
| 66 | free(a->file); |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | free(a); |
| 71 | } |
| 72 | |
| 73 | void bufblkpropmake(void *state, bt_element_t av, void *destv) |
| 74 | { |
| 75 | struct bufblk *a = (struct bufblk *)av; |
| 76 | fileoffset_t *dest = (fileoffset_t *)destv; |
| 77 | |
| 78 | *dest = a->len; |
| 79 | } |
| 80 | |
| 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) |
| 83 | { |
| 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); |
| 89 | } |
| 90 | |
| 91 | static buffer *buf_new_from_bt(btree *bt) |
| 92 | { |
| 93 | buffer *buf = (buffer *)malloc(sizeof(buffer)); |
| 94 | |
| 95 | buf->bt = bt; |
| 96 | |
| 97 | return buf; |
| 98 | } |
| 99 | |
| 100 | static btree *buf_bt_new(void) |
| 101 | { |
| 102 | return bt_new(NULL, bufblkcopy, bufblkfree, sizeof(fileoffset_t), |
| 103 | alignof(fileoffset_t), bufblkpropmake, bufblkpropmerge, |
| 104 | NULL, 2); |
| 105 | } |
| 106 | |
| 107 | extern void buf_free(buffer *buf) |
| 108 | { |
| 109 | bt_free(buf->bt); |
| 110 | free(buf); |
| 111 | } |
| 112 | |
| 113 | static int bufblksearch(void *tstate, void *sstate, int ntrees, |
| 114 | void **props, int *counts, |
| 115 | bt_element_t *elts, int *is_elt) |
| 116 | { |
| 117 | fileoffset_t *disttogo = (fileoffset_t *)sstate; |
| 118 | fileoffset_t distsofar = 0; |
| 119 | int i; |
| 120 | |
| 121 | for (i = 0; i < ntrees; i++) { |
| 122 | struct bufblk *blk; |
| 123 | fileoffset_t sublen = props[i] ? *(fileoffset_t *)props[i] : 0; |
| 124 | |
| 125 | if ((props[i] && *disttogo < distsofar + sublen) || |
| 126 | (*disttogo == distsofar + sublen && i == ntrees-1)) { |
| 127 | *disttogo -= distsofar; |
| 128 | /* |
| 129 | * Descend into this subtree. |
| 130 | */ |
| 131 | *is_elt = FALSE; |
| 132 | return i; |
| 133 | } |
| 134 | |
| 135 | distsofar += sublen; |
| 136 | |
| 137 | if (i < ntrees-1) { |
| 138 | blk = (struct bufblk *)elts[i]; |
| 139 | |
| 140 | if (*disttogo < distsofar + blk->len) { |
| 141 | /* |
| 142 | * Select this element. |
| 143 | */ |
| 144 | *disttogo -= distsofar; |
| 145 | *is_elt = TRUE; |
| 146 | return i; |
| 147 | } |
| 148 | |
| 149 | distsofar += blk->len; |
| 150 | } |
| 151 | } |
| 152 | |
| 153 | assert(!"We should never reach here"); |
| 154 | return 0; /* placate gcc */ |
| 155 | } |
| 156 | |
| 157 | static int buf_bt_find_pos(btree *bt, fileoffset_t pos, fileoffset_t *poswithin) |
| 158 | { |
| 159 | int index; |
| 160 | |
| 161 | bt_propfind(bt, bufblksearch, &pos, &index); |
| 162 | |
| 163 | *poswithin = pos; |
| 164 | return index; |
| 165 | } |
| 166 | |
| 167 | /* |
| 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. |
| 171 | */ |
| 172 | static struct bufblk *buf_convert_to_literal(struct bufblk *blk) |
| 173 | { |
| 174 | if (blk->file && blk->len <= BLKMAX) { |
| 175 | struct bufblk *ret = |
| 176 | (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX); |
| 177 | ret->data = (unsigned char *)(ret+1); |
| 178 | ret->file = NULL; |
| 179 | ret->filepos = 0; |
| 180 | ret->len = blk->len; |
| 181 | fseeko(blk->file->fp, blk->filepos, SEEK_SET); |
| 182 | fread(ret->data, blk->len, 1, blk->file->fp); |
| 183 | |
| 184 | return ret; |
| 185 | } |
| 186 | |
| 187 | return NULL; |
| 188 | } |
| 189 | |
| 190 | /* |
| 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. |
| 195 | */ |
| 196 | static int buf_bt_cleanup(btree *bt, int index) |
| 197 | { |
| 198 | struct bufblk *a, *b, *cvt; |
| 199 | fileoffset_t totallen; |
| 200 | unsigned char tmpdata[BLKMAX*2]; |
| 201 | |
| 202 | if (index < 0) return 0; |
| 203 | |
| 204 | a = (struct bufblk *)bt_index(bt, index); |
| 205 | b = (struct bufblk *)bt_index(bt, index+1); |
| 206 | |
| 207 | if ( a && (cvt = buf_convert_to_literal(a)) != NULL ) { |
| 208 | bt_replace(bt, cvt, index); |
| 209 | bufblkfree(NULL, a); |
| 210 | a = cvt; |
| 211 | } |
| 212 | |
| 213 | if ( b && (cvt = buf_convert_to_literal(b)) != NULL ) { |
| 214 | bt_replace(bt, cvt, index+1); |
| 215 | bufblkfree(NULL, b); |
| 216 | b = cvt; |
| 217 | } |
| 218 | |
| 219 | if (!a || !b || a->file || b->file) return 0; |
| 220 | |
| 221 | if (a->len >= BLKMIN && b->len >= BLKMIN) return 0; |
| 222 | |
| 223 | assert(a->len <= BLKMAX && b->len <= BLKMAX); |
| 224 | |
| 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); |
| 228 | |
| 229 | /* |
| 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 |
| 234 | * data between them. |
| 235 | */ |
| 236 | totallen = a->len + b->len; |
| 237 | memcpy(tmpdata, a->data, a->len); |
| 238 | memcpy(tmpdata + a->len, b->data, b->len); |
| 239 | |
| 240 | if (totallen >= BLKMAX) { |
| 241 | /* |
| 242 | * Redistribute into two (nearly) equal-sized blocks. |
| 243 | */ |
| 244 | a->len = totallen / 2; |
| 245 | b->len = totallen - a->len; |
| 246 | |
| 247 | memcpy(a->data, tmpdata, a->len); |
| 248 | memcpy(b->data, tmpdata + a->len, b->len); |
| 249 | |
| 250 | bt_replace(bt, a, index); |
| 251 | bt_replace(bt, b, index+1); |
| 252 | |
| 253 | return 0; |
| 254 | } else { |
| 255 | /* |
| 256 | * Just merge into one. |
| 257 | */ |
| 258 | a->len = totallen; |
| 259 | memcpy(a->data, tmpdata, a->len); |
| 260 | |
| 261 | bt_replace(bt, a, index); |
| 262 | free(bt_delpos(bt, index+1)); |
| 263 | |
| 264 | return 1; |
| 265 | } |
| 266 | } |
| 267 | |
| 268 | static int buf_bt_splitpoint(btree *bt, fileoffset_t pos) |
| 269 | { |
| 270 | fileoffset_t poswithin; |
| 271 | int 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, fileoffset_t 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, fileoffset_t 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 | fileoffset_t *output = (fileoffset_t *)sstate; |
| 331 | fileoffset_t size = 0; |
| 332 | int i; |
| 333 | |
| 334 | for (i = 0; i < ntrees; i++) { |
| 335 | struct bufblk *blk; |
| 336 | |
| 337 | if (props[i]) |
| 338 | size += *(fileoffset_t *)props[i]; |
| 339 | |
| 340 | if (i < ntrees-1) { |
| 341 | blk = (struct bufblk *)elts[i]; |
| 342 | |
| 343 | size += blk->len; |
| 344 | } |
| 345 | } |
| 346 | |
| 347 | *output = size; |
| 348 | |
| 349 | /* Actual return value doesn't matter */ |
| 350 | *is_elt = TRUE; |
| 351 | return 1; |
| 352 | } |
| 353 | |
| 354 | static fileoffset_t buf_bt_length(btree *bt) |
| 355 | { |
| 356 | fileoffset_t length; |
| 357 | |
| 358 | bt_propfind(bt, bufblklensearch, &length, NULL); |
| 359 | |
| 360 | return length; |
| 361 | } |
| 362 | |
| 363 | extern fileoffset_t buf_length(buffer *buf) |
| 364 | { |
| 365 | return buf_bt_length(buf->bt); |
| 366 | } |
| 367 | |
| 368 | extern buffer *buf_new_empty(void) |
| 369 | { |
| 370 | buffer *buf = (buffer *)malloc(sizeof(buffer)); |
| 371 | |
| 372 | buf->bt = buf_bt_new(); |
| 373 | |
| 374 | return buf; |
| 375 | } |
| 376 | |
| 377 | extern buffer *buf_new_from_file(FILE *fp) |
| 378 | { |
| 379 | buffer *buf = buf_new_empty(); |
| 380 | struct bufblk *blk; |
| 381 | struct file *file; |
| 382 | |
| 383 | file = (struct file *)malloc(sizeof(struct file)); |
| 384 | file->fp = fp; |
| 385 | file->refcount = 1; /* the reference we're about to make */ |
| 386 | |
| 387 | blk = (struct bufblk *)malloc(sizeof(struct bufblk)); |
| 388 | blk->data = NULL; |
| 389 | blk->file = file; |
| 390 | blk->filepos = 0; |
| 391 | |
| 392 | fseeko(fp, 0, SEEK_END); |
| 393 | blk->len = ftello(fp); |
| 394 | |
| 395 | bt_addpos(buf->bt, blk, 0); |
| 396 | |
| 397 | buf_bt_cleanup(buf->bt, 0); |
| 398 | |
| 399 | return buf; |
| 400 | } |
| 401 | |
| 402 | extern void buf_fetch_data(buffer *buf, void *vdata, int len, fileoffset_t pos) |
| 403 | { |
| 404 | int index; |
| 405 | fileoffset_t poswithin; |
| 406 | fileoffset_t thislen; |
| 407 | unsigned char *data = (unsigned char *)vdata; |
| 408 | |
| 409 | index = buf_bt_find_pos(buf->bt, pos, &poswithin); |
| 410 | |
| 411 | while (len > 0) { |
| 412 | struct bufblk *blk = (struct bufblk *)bt_index(buf->bt, index); |
| 413 | |
| 414 | thislen = blk->len - poswithin; |
| 415 | if (thislen > len) |
| 416 | thislen = len; |
| 417 | |
| 418 | if (blk->file) { |
| 419 | fseeko(blk->file->fp, blk->filepos + poswithin, SEEK_SET); |
| 420 | fread(data, thislen, 1, blk->file->fp); |
| 421 | } else { |
| 422 | memcpy(data, blk->data + poswithin, thislen); |
| 423 | } |
| 424 | |
| 425 | data += thislen; |
| 426 | len -= thislen; |
| 427 | |
| 428 | poswithin = 0; |
| 429 | |
| 430 | index++; |
| 431 | } |
| 432 | } |
| 433 | |
| 434 | extern void buf_insert_data(buffer *buf, void *vdata, int len, |
| 435 | fileoffset_t pos) |
| 436 | { |
| 437 | btree *bt = buf_bt_new(); |
| 438 | int nblocks, blklen1, extra; |
| 439 | int i, origlen = len; |
| 440 | unsigned char *data = (unsigned char *)vdata; |
| 441 | |
| 442 | nblocks = len / ((BLKMIN + BLKMAX)/2); |
| 443 | if (nblocks * BLKMAX < len) |
| 444 | nblocks++; |
| 445 | blklen1 = len / nblocks; |
| 446 | extra = len % nblocks; |
| 447 | assert(blklen1 >= BLKMIN || nblocks == 1); |
| 448 | assert(blklen1 <= BLKMAX - (extra!=0)); |
| 449 | |
| 450 | for (i = 0; i < nblocks; i++) { |
| 451 | struct bufblk *blk; |
| 452 | int blklen = blklen1 + (i < extra); |
| 453 | |
| 454 | blk = (struct bufblk *)malloc(sizeof(struct bufblk) + BLKMAX); |
| 455 | blk->data = (unsigned char *)(blk+1); |
| 456 | memcpy(blk->data, data, blklen); |
| 457 | blk->len = blklen; |
| 458 | blk->file = NULL; |
| 459 | blk->filepos = 0; |
| 460 | |
| 461 | data += blklen; |
| 462 | len -= blklen; |
| 463 | |
| 464 | bt_addpos(bt, blk, i); |
| 465 | assert(origlen == buf_bt_length(bt) + len); |
| 466 | } |
| 467 | |
| 468 | assert(len == 0); |
| 469 | assert(origlen == buf_bt_length(bt)); |
| 470 | |
| 471 | buf_insert_bt(buf, bt, pos); |
| 472 | } |
| 473 | |
| 474 | extern void buf_delete(buffer *buf, fileoffset_t len, fileoffset_t pos) |
| 475 | { |
| 476 | btree *left = buf_bt_split(buf->bt, pos, TRUE); |
| 477 | btree *right = buf_bt_split(buf->bt, len, FALSE); |
| 478 | |
| 479 | bt_free(buf->bt); |
| 480 | |
| 481 | buf->bt = buf_bt_join(left, right); |
| 482 | } |
| 483 | |
| 484 | extern void buf_overwrite_data(buffer *buf, void *data, int len, |
| 485 | fileoffset_t pos) |
| 486 | { |
| 487 | buf_delete(buf, len, pos); |
| 488 | buf_insert_data(buf, data, len, pos); |
| 489 | } |
| 490 | |
| 491 | extern buffer *buf_cut(buffer *buf, fileoffset_t len, fileoffset_t pos) |
| 492 | { |
| 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; |
| 496 | |
| 497 | buf->bt = buf_bt_join(left, right); |
| 498 | |
| 499 | return buf_new_from_bt(ret); |
| 500 | } |
| 501 | |
| 502 | extern buffer *buf_copy(buffer *buf, fileoffset_t len, fileoffset_t pos) |
| 503 | { |
| 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); |
| 507 | |
| 508 | buf->bt = buf_bt_join(left, buf->bt); |
| 509 | buf->bt = buf_bt_join(buf->bt, right); |
| 510 | |
| 511 | return buf_new_from_bt(ret); |
| 512 | } |
| 513 | |
| 514 | extern void buf_paste(buffer *buf, buffer *cutbuffer, fileoffset_t pos) |
| 515 | { |
| 516 | btree *bt = bt_clone(cutbuffer->bt); |
| 517 | buf_insert_bt(buf, bt, pos); |
| 518 | } |
| 519 | |
| 520 | #ifdef TEST_BUFFER |
| 521 | static FILE *debugfp = NULL; |
| 522 | extern void buffer_diagnostic(buffer *buf, char *title) |
| 523 | { |
| 524 | int i; |
| 525 | fileoffset_t offset; |
| 526 | struct bufblk *blk; |
| 527 | |
| 528 | if (!debugfp) { |
| 529 | debugfp = fdopen(3, "w"); |
| 530 | if (!debugfp) |
| 531 | debugfp = fopen("debug.log", "w"); |
| 532 | } |
| 533 | |
| 534 | if (!buf) { |
| 535 | fprintf(debugfp, "Buffer [%s] is null\n", title); |
| 536 | return; |
| 537 | } |
| 538 | |
| 539 | fprintf(debugfp, "Listing of buffer [%s]:\n", title); |
| 540 | offset = 0; |
| 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); |
| 543 | if (blk->file) { |
| 544 | fprintf(debugfp, " file %p pos %8"OFF"d\n", blk->file, blk->filepos); |
| 545 | } else { |
| 546 | int j; |
| 547 | |
| 548 | for (j = 0; j < blk->len; j++) |
| 549 | fprintf(debugfp, " %02x", blk->data[j]); |
| 550 | |
| 551 | fprintf(debugfp, "\n"); |
| 552 | } |
| 553 | offset += blk->len; |
| 554 | } |
| 555 | fprintf(debugfp, "Listing concluded\n\n"); |
| 556 | |
| 557 | fflush(debugfp); |
| 558 | } |
| 559 | #endif |