cinelerra-5.1/cinelerra/undostack.C

   1
   2 /*
   3  * CINELERRA
   4  * Copyright (C) 2008 Adam Williams <broadcast at earthling dot net>
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  *
  20  */
  21
  22 #include "bcsignals.h"
  23 #include "bctimer.h"
  24 #include "clip.h"
  25 #include "cstrdup.h"
  26 #include "filexml.h"
  27 #include "undostack.h"
  28 #include <string.h>
  29
  30 UndoStack::UndoStack() : List<UndoStackItem>()
  31 {
  32         current = 0;
  33 }
  34
  35 UndoStack::~UndoStack()
  36 {
  37 }
  38
  39 UndoStackItem *UndoStack::get_current_undo()
  40 {
  41         UndoStackItem *item = current;
  42         if( item &&  (number_of(item) & 1) ) item = item->previous;
  43         if( item && !(number_of(item) & 1) ) item = item->previous;
  44         return item;
  45 }
  46
  47 UndoStackItem *UndoStack::get_current_redo()
  48 {
  49         UndoStackItem *item = current ? current : first;
  50         if( item &&  (number_of(item) & 1) ) item = item->next;
  51         if( item && !(number_of(item) & 1) ) item = item->next;
  52         return item;
  53 }
  54
  55
  56 UndoStackItem* UndoStack::push()
  57 {
  58 // current is only 0 if before first undo
  59         if( current )
  60                 current = insert_after(current);
  61         else
  62                 current = insert_before(first);
  63
  64 // delete future undos if necessary
  65         if( current && current->next ) {
  66                 while( current->next ) remove(last);
  67         }
  68
  69 // delete oldest 2 undos if necessary
  70         if( total() > UNDOLEVELS ) {
  71                 for( int i=0; i<2; ++i ) {
  72                         UndoStackItem *second = first->next;
  73                         char *temp_data = 0;
  74
  75
  76                         if( !second->is_key() ) {
  77                                 temp_data = second->get_data();
  78                         }
  79                         remove(first);
  80
  81 // Convert new first to key buffer.
  82                         if( !second->is_key() ) {
  83                                 second->set_data(temp_data);
  84                         }
  85                         delete [] temp_data;
  86                 }
  87         }
  88
  89         return current;
  90 }
  91
  92 UndoStackItem* UndoStack::pull_next()
  93 {
  94 // use first entry if none
  95         if( !current )
  96                 current = first;
  97         else
  98 // use next entry if there is a next entry
  99         if( current->next )
 100                 current = NEXT;
 101 // don't change current if there is no next entry
 102         else
 103                 return 0;
 104
 105         return current;
 106 }
 107
 108
 109 void UndoStack::dump(FILE *fp)
 110 {
 111         fprintf(fp,"UndoStack::dump\n");
 112         UndoStackItem *current = last;
 113 // Dump most recent
 114         for( int i=0; current && i<32; ++i,current=PREVIOUS ) {
 115                 fprintf(fp,"%c %2d %14p %-24s %8d %04jx %c\n", current->is_key() ? 'k' : ' ',
 116                         i, current, current->get_description(), current->get_size(),
 117                         current->get_flags(), current == this->current ? '*' : ' ');
 118 //char fn[BCSTRLEN]; sprintf(fn,"/tmp/undo%d", i); FILE *fp = fopen(fn,"w");
 119 //if( fp ) { char *cp=current->get_data(); fwrite(cp,strlen(cp),1,fp); fclose(fp); delete [] cp; }
 120         }
 121 }
 122
 123 // undo can be incremental or direct, from key to current
 124 //#define UNDO_INCREMENTAL
 125
 126 class undo_record {
 127 public:
 128         int32_t new_ofs;
 129         int32_t new_len;
 130         int32_t old_len;
 131 };
 132
 133 static unsigned char* apply_difference(unsigned char *before, int before_len,
 134                 unsigned char *patch, int patch_len, int *result_len)
 135 {
 136         XMLBuffer xbfr((const char *)patch, patch_len, 0);
 137         int32_t len = 0;
 138         xbfr.read((char *)&len, sizeof(len));
 139         char *result = new char[len];
 140         char *rp = result, *bp = (char*)before;
 141
 142         while( xbfr.itell() < patch_len ) {
 143                 undo_record urecd;
 144                 xbfr.read((char*)&urecd, sizeof(urecd));
 145                 int ofs = rp - result;
 146                 if( urecd.new_ofs > ofs ) {
 147                         int sz = urecd.new_ofs - ofs;
 148                         memcpy(rp, bp, sz);
 149                         bp += sz;  rp += sz;
 150                 }
 151                 if( urecd.new_len > 0 )
 152                         xbfr.read(rp, urecd.new_len);
 153                 bp += urecd.old_len;  rp += urecd.new_len;
 154         }
 155
 156 // All data from before_ptr to end of result buffer is identical
 157         int sz = bp - (char *)before;
 158         if( (before_len-=sz) > 0 ) {
 159                 memcpy(rp, bp, before_len);
 160                 rp += before_len;
 161         }
 162
 163         *result_len = rp - result;
 164         return (unsigned char *)result;
 165 }
 166
 167 UndoStackItem::UndoStackItem()
 168  : ListItem<UndoStackItem>()
 169 {
 170         description = data = 0;
 171         data_size = 0;
 172         key = 0;
 173         creator = 0;
 174         session_filename = 0;
 175 }
 176
 177 UndoStackItem::~UndoStackItem()
 178 {
 179         delete [] description;
 180         delete [] data;
 181         delete [] session_filename;
 182 }
 183
 184 void UndoStackItem::set_description(char *description)
 185 {
 186         delete [] this->description;
 187         this->description= 0;
 188         this->description = new char[strlen(description) + 1];
 189         strcpy(this->description, description);
 190 }
 191
 192 void UndoStackItem::set_filename(char *filename)
 193 {
 194         delete [] session_filename;
 195         this->session_filename = cstrdup(filename);
 196 }
 197
 198 char* UndoStackItem::get_filename()
 199 {
 200         return session_filename;
 201 }
 202
 203
 204 const char* UndoStackItem::get_description()
 205 {
 206         if( description )
 207                 return description;
 208         else
 209                 return "";
 210 }
 211
 212 // undo diff
 213
 214 UndoHash::UndoHash(char *txt, int len, UndoHash *nxt)
 215 {
 216         this->txt = txt;
 217         this->len = len;
 218         this->nxt = nxt;
 219         line[va] = line[vb] = -1;
 220         occurs[va] = occurs[vb] = 0;
 221 }
 222 UndoHash::~UndoHash()
 223 {
 224 }
 225
 226 UndoHashTable::UndoHashTable()
 227 {
 228         for( int i=0; i<hash_sz; ++i ) table[i] = 0;
 229         bof = new UndoHash(0, 0, 0);
 230         eof = new UndoHash(0, 0, 0);
 231 }
 232 UndoHashTable::~UndoHashTable()
 233 {
 234         delete bof;
 235         delete eof;
 236         for( int i=0; i<hash_sz; ++i ) {
 237                 for( UndoHash *nxt=0, *hp=table[i]; hp; hp=nxt ) {
 238                         nxt = hp->nxt;  delete hp;
 239                 }
 240         }
 241 }
 242
 243 UndoHash *UndoHashTable::add(char *txt, int len)
 244 {
 245         uint8_t *bp = (uint8_t *)txt;
 246         int v = 0;
 247         for( int i=len; --i>=0; ++bp ) {
 248                 v = (v<<1) + *bp;
 249                 v = (v + (v>>hash_sz2)) & hash_sz1;
 250         }
 251         UndoHash *hp = table[v];
 252         while( hp && strncmp(hp->txt,txt,len) ) hp = hp->nxt;
 253         if( !hp ) {
 254                 hp = new UndoHash(txt, len, table[v]);
 255                 table[v] = hp;
 256         }
 257         return hp;
 258 }
 259
 260 UndoLine::UndoLine(UndoHash *hash, char *tp)
 261 {
 262         this->txt = tp;  this->len = 0;
 263         this->hash = hash;
 264         hash->occurs[va] = hash->occurs[vb] = 1;
 265 }
 266
 267 UndoLine::UndoLine(UndoHashTable *hash, char *txt, int len)
 268 {
 269         this->txt = txt;  this->len = len;
 270         this->hash = hash->add(txt, len);
 271 }
 272 UndoLine::~UndoLine()
 273 {
 274 }
 275
 276 int UndoLine::eq(UndoLine *ln)
 277 {
 278         return hash == ln->hash ? 1 : 0;
 279 }
 280
 281 void UndoVersion::scan_lines(UndoHashTable *hash, char *sp, char *ep)
 282 {
 283         for( int line=1; sp<ep; ++line ) {
 284                 char *txt = sp;
 285                 while( sp<ep && *sp++ != '\n' );
 286                 UndoLine *ln = new UndoLine(hash, txt, sp-txt);
 287                 ln->hash->line[ver] = line;
 288                 ++ln->hash->occurs[ver];
 289                 append(ln);
 290         }
 291 }
 292
 293
 294 void UndoStackItem::set_data(char *data)
 295 {
 296         delete [] this->data;  this->data = 0;
 297         this->data_size = 0;   this->key = 0;
 298         int data_size = strlen(data)+1;
 299
 300         UndoStackItem *current = this;
 301 // Search for key buffer within interval
 302         for( int i=UNDO_KEY_INTERVAL; --i>=0 && current && !current->key; current=PREVIOUS );
 303
 304         int need_key = current ? 0 : 1;
 305 // setting need_key = 1 forces all undo data items to key (not diffd)
 306 //      int need_key = 1;
 307         char *prev = 0;  int prev_size = 0;
 308         if( !need_key ) {
 309 #ifdef UNDO_INCREMENTAL
 310                 prev = previous->get_data();
 311                 prev_size = prev ? strlen(prev)+1 : 0;
 312 #else
 313                 prev = current->data;
 314                 prev_size = current->data_size;
 315 #endif
 316                 int min_size = data_size/16;
 317 // if the previous is a sizable incremental diff
 318                 if( previous && !previous->key &&
 319                     previous->data_size > min_size ) {
 320 //  and this minimum diff distance is a lot different, need key
 321                         int dist = abs(data_size - prev_size);
 322                         if( abs(dist - previous->data_size) > min_size )
 323                                 need_key = 1;
 324                 }
 325         }
 326         if( !need_key ) {
 327                 int bfr_size = BCTEXTLEN;
 328                 char *bfr = new char[bfr_size];
 329                 XMLBuffer xbfr(bfr_size, bfr, 1);
 330                 xbfr.write((char*)&data_size, sizeof(data_size));
 331                 UndoHashTable hash;
 332                 UndoVersion alines(va), blines(vb);
 333                 char *asp = data, *aep = asp + data_size-1;
 334                 char *bsp = prev, *bep = bsp + prev_size-1;
 335                 alines.append(new UndoLine(hash.bof, asp));
 336                 blines.append(new UndoLine(hash.bof, bsp));
 337                 alines.scan_lines(&hash, asp, aep);
 338                 blines.scan_lines(&hash, bsp, bep);
 339                 int asz = alines.size(), bsz = blines.size();
 340 // trim matching suffix
 341                 while( asz > 0 && bsz > 0 && alines[asz-1]->eq(blines[bsz-1]) ) {
 342                         aep = alines[--asz]->txt;  alines.remove_object();
 343                         bep = blines[--bsz]->txt;  blines.remove_object();
 344                 }
 345 // include for matching last item
 346                 alines.append(new UndoLine(hash.eof, aep));
 347                 blines.append(new UndoLine(hash.eof, bep));
 348                 hash.eof->line[va] = asz++;
 349                 hash.eof->line[vb] = bsz++;
 350
 351                 int ai = 0, bi = 0;
 352                 while( ai < asz || bi < bsz ) {
 353 // skip running match
 354                         if( alines[ai]->eq(blines[bi]) ) { ++ai;  ++bi;  continue; }
 355                         char *adp = alines[ai]->txt, *bdp = blines[bi]->txt;
 356 // find best unique match
 357                         int ma = asz, mb = bsz;
 358                         int mx = ma + mb + 1;
 359                         for( int ia=ai; ia<asz && ia-ai<mx; ++ia ) {
 360                                 UndoHash *ah = alines[ia]->hash;
 361                                 if( ah->occurs[va] != 1 || ah->occurs[vb] != 1 ) continue;
 362                                 int m = (ah->line[va] - ai) + (ah->line[vb] - bi);
 363                                 if( m >= mx ) continue;
 364                                 ma = ah->line[va];  mb = ah->line[vb];  mx = m;
 365                         }
 366 // trim suffix
 367                         while( ma > 0 && mb > 0 && alines[ma-1]->eq(blines[mb-1]) ) { --ma;  --mb; }
 368                         char *ap = alines[ma]->txt, *bp = blines[mb]->txt;
 369                         ai = ma;  bi = mb;
 370                         undo_record urecd;
 371                         urecd.new_ofs = adp - data;
 372                         urecd.new_len = ap - adp;
 373                         urecd.old_len = bp - bdp;
 374                         xbfr.write((const char*)&urecd, sizeof(urecd));
 375                         xbfr.write((const char*)adp, urecd.new_len);
 376                 }
 377
 378                 int64_t pos = xbfr.otell();
 379                 if( abs(data_size-prev_size) < pos/2 ) {
 380                         this->data = new char[this->data_size = pos];
 381                         xbfr.iseek(0);
 382                         xbfr.read(this->data, pos);
 383 #if 1
 384                         int test_size = 0;
 385                         char *test_data = (char*)apply_difference(
 386                                 (unsigned char *)prev, prev_size,
 387                                 (unsigned char *)this->data, this->data_size,
 388                                 &test_size);
 389                         if( test_size != data_size || memcmp(test_data, data, test_size) ) {
 390                                 printf("UndoStackItem::set_data: *** incremental undo failed!\n");
 391                                 delete [] this->data;  this->data = 0;  this->data_size = 0;
 392                                 need_key = 1;
 393                         }
 394                         delete [] test_data;
 395 #endif
 396                 }
 397                 else
 398                         need_key = 1;
 399         }
 400
 401 #ifdef UNDO_INCREMENTAL
 402         delete [] prev;
 403 #endif
 404         if( need_key ) {
 405                 this->key = 1;
 406                 this->data = new char[this->data_size = data_size];
 407                 memcpy(this->data, data, this->data_size);
 408         }
 409 }
 410
 411 char* UndoStackItem::get_data()
 412 {
 413 // Find latest key buffer
 414         UndoStackItem *current = this;
 415         while( current && !current->key )
 416                 current = PREVIOUS;
 417         if( !current ) {
 418                 printf("UndoStackItem::get_data: no key buffer found!\n");
 419                 return 0;
 420         }
 421
 422 // This is the key buffer
 423         if( current == this ) {
 424                 char *result = new char[data_size];
 425                 memcpy(result, data, data_size);
 426                 return result;
 427         }
 428 #ifdef UNDO_INCREMENTAL
 429 // Get key buffer
 430         char *current_data = current->get_data();
 431         int current_size = current->data_size;
 432         current = NEXT;
 433         while( current ) {
 434 // Do incremental updates
 435                 int new_size;
 436                 char *new_data = (char*)apply_difference(
 437                         (unsigned char*)current_data, current_size,
 438                         (unsigned char*)current->data, current->data_size,
 439                         &new_size);
 440                 delete [] current_data;
 441
 442                 if( current == this )
 443                         return new_data;
 444                 current_data = new_data;
 445                 current_size = new_size;
 446                 current = NEXT;
 447         }
 448 // Never hit this object.
 449         delete [] current_data;
 450         printf("UndoStackItem::get_data: lost starting object!\n");
 451         return 0;
 452 #else
 453         int new_size;
 454         char *new_data = (char*)apply_difference(
 455                 (unsigned char*)current->data, current->data_size,
 456                 (unsigned char*)this->data, this->data_size, &new_size);
 457         return new_data;
 458 #endif
 459 }
 460
 461 int UndoStackItem::is_key()
 462 {
 463         return key;
 464 }
 465
 466 int UndoStackItem::get_size()
 467 {
 468         return data_size;
 469 }
 470
 471 void UndoStackItem::set_flags(uint64_t flags)
 472 {
 473         this->load_flags = flags;
 474 }
 475
 476 uint64_t UndoStackItem::get_flags()
 477 {
 478         return load_flags;
 479 }
 480
 481 void UndoStackItem::set_creator(void *creator)
 482 {
 483         this->creator = creator;
 484 }
 485
 486 void* UndoStackItem::get_creator()
 487 {
 488         return creator;
 489 }
 490
 491 void UndoStackItem::save(FILE *fp)
 492 {
 493         fwrite(&key,1,sizeof(key),fp);
 494         fwrite(&load_flags,1,sizeof(load_flags),fp);
 495         fwrite(&data_size,1,sizeof(data_size),fp);
 496         fwrite(data,1,data_size,fp);
 497         for( char *bp=session_filename; *bp; ++bp ) fputc(*bp, fp);
 498         fputc(0, fp);
 499         for( char *bp=description; *bp; ++bp ) fputc(*bp, fp);
 500         fputc(0, fp);
 501 }
 502
 503 void UndoStackItem::load(FILE *fp)
 504 {
 505         fread(&key,1,sizeof(key),fp);
 506         fread(&load_flags,1,sizeof(load_flags),fp);
 507         fread(&data_size,1,sizeof(data_size),fp);
 508         fread(data=new char[data_size],1,data_size,fp);
 509         char filename[BCTEXTLEN], descr[BCTEXTLEN];
 510         char *bp = filename, *ep = bp+sizeof(filename)-1;
 511         for( int ch; bp<ep && (ch=fgetc(fp))>0; ++bp ) *bp = ch;
 512         *bp = 0;
 513         session_filename = cstrdup(filename);
 514         bp = descr;  ep = bp+sizeof(descr)-1;
 515         for( int ch; bp<ep && (ch=fgetc(fp))>0; ++bp ) *bp = ch;
 516         *bp = 0;
 517         description = cstrdup(descr);
 518 //printf("read undo key=%d,flags=%jx,data_size=%d,data=%p,file=%s,descr=%s\n",
 519 // key, load_flags, data_size, data, session_filename, description);
 520 }
 521
 522 void UndoStack::save(FILE *fp)
 523 {
 524         for( UndoStackItem *item=first; item; item=item->next ) {
 525                 int is_current = item == current ? 1 : 0;
 526                 fwrite(&is_current,1,sizeof(is_current),fp);
 527                 item->save(fp);
 528 //              if( item == current ) break; // stop at current
 529         }
 530 }
 531
 532 void UndoStack::load(FILE *fp)
 533 {
 534         while( last ) delete last;
 535         current = 0;
 536         UndoStackItem *current_item = 0;
 537         int is_current = 0;
 538         while( fread(&is_current,1,sizeof(is_current),fp) == sizeof(is_current) ) {
 539                 UndoStackItem *item = push();
 540                 item->load(fp);
 541                 if( is_current ) current_item = item;
 542         }
 543         if( current_item ) current = current_item;
 544 }
 545