mdw@git.distorted.org.uk Git - sgt/tweak/blob - buffer.c

   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