| 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 |