4 * Copyright (C) 2008 Adam Williams <broadcast at earthling dot net>
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.
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.
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
22 #include "bcsignals.h"
27 #include "undostack.h"
30 // undo can be incremental or direct, from key to current
31 //#define UNDO_INCREMENTAL
33 UndoStack::UndoStack() : List<UndoStackItem>()
38 UndoStack::~UndoStack()
42 UndoStackItem *UndoStack::get_current_undo()
44 UndoStackItem *item = current;
45 if( item && (number_of(item) & 1) ) item = item->previous;
46 if( item && !(number_of(item) & 1) ) item = item->previous;
50 UndoStackItem *UndoStack::get_current_redo()
52 UndoStackItem *item = current ? current : first;
53 if( item && (number_of(item) & 1) ) item = item->next;
54 if( item && !(number_of(item) & 1) ) item = item->next;
59 UndoStackItem* UndoStack::push()
61 // delete oldest 2 undos if necessary
62 if( total() > UNDOLEVELS ) {
63 UndoStackItem *item = first, *key = item;
64 #ifdef UNDO_INCREMENTAL
65 for( int i=2; --i>=0; item=item->next );
67 for( int i=2; --i>=0; item=item->next )
68 if( item->is_key() ) key = item;
70 char *data = !item->is_key() ? key->get_data() : 0;
71 while( first != item ) {
72 if( current == first ) current = first->next;
81 // current is only 0 if before first undo
82 current = current ? insert_after(current) : insert_before(first);
83 // delete future undos if necessary
84 while( current->next ) remove(last);
88 UndoStackItem* UndoStack::pull_next()
90 // use first entry if none
94 // use next entry if there is a next entry
97 // don't change current if there is no next entry
105 void UndoStack::dump(FILE *fp)
107 fprintf(fp,"UndoStack::dump\n");
108 UndoStackItem *current = last;
110 for( int i=0; current && i<32; ++i,current=PREVIOUS ) {
111 fprintf(fp,"%c %2d %14p %-24s %8d %04jx %c\n", current->is_key() ? 'k' : ' ',
112 i, current, current->get_description(), current->get_size(),
113 current->get_flags(), current == this->current ? '*' : ' ');
114 //char fn[BCSTRLEN]; sprintf(fn,"/tmp/undo%d", i); FILE *fp = fopen(fn,"w");
115 //if( fp ) { char *cp=current->get_data(); fwrite(cp,strlen(cp),1,fp); fclose(fp); delete [] cp; }
126 static unsigned char* apply_difference(unsigned char *before, int before_len,
127 unsigned char *patch, int patch_len, int *result_len)
129 XMLBuffer xbfr((const char *)patch, patch_len, 0);
131 xbfr.read((char *)&len, sizeof(len));
132 char *result = new char[len];
133 char *rp = result, *bp = (char*)before;
135 while( xbfr.itell() < patch_len ) {
137 xbfr.read((char*)&urecd, sizeof(urecd));
138 int ofs = rp - result;
139 if( urecd.new_ofs > ofs ) {
140 int sz = urecd.new_ofs - ofs;
144 if( urecd.new_len > 0 )
145 xbfr.read(rp, urecd.new_len);
146 bp += urecd.old_len; rp += urecd.new_len;
149 // All data from before_ptr to end of result buffer is identical
150 int sz = bp - (char *)before;
151 if( (before_len-=sz) > 0 ) {
152 memcpy(rp, bp, before_len);
156 *result_len = rp - result;
157 return (unsigned char *)result;
160 UndoStackItem::UndoStackItem()
161 : ListItem<UndoStackItem>()
163 description = data = 0;
167 session_filename = 0;
170 UndoStackItem::~UndoStackItem()
172 delete [] description;
174 delete [] session_filename;
177 void UndoStackItem::set_description(char *description)
179 delete [] this->description;
180 this->description= 0;
181 this->description = new char[strlen(description) + 1];
182 strcpy(this->description, description);
185 void UndoStackItem::set_filename(char *filename)
187 delete [] session_filename;
188 this->session_filename = cstrdup(filename);
191 char* UndoStackItem::get_filename()
193 return session_filename;
197 const char* UndoStackItem::get_description()
207 UndoHash::UndoHash(char *txt, int len, UndoHash *nxt)
212 line[va] = line[vb] = -1;
213 occurs[va] = occurs[vb] = 0;
215 UndoHash::~UndoHash()
219 UndoHashTable::UndoHashTable()
221 for( int i=0; i<hash_sz; ++i ) table[i] = 0;
222 bof = new UndoHash(0, 0, 0);
223 eof = new UndoHash(0, 0, 0);
225 UndoHashTable::~UndoHashTable()
229 for( int i=0; i<hash_sz; ++i ) {
230 for( UndoHash *nxt=0, *hp=table[i]; hp; hp=nxt ) {
231 nxt = hp->nxt; delete hp;
236 UndoHash *UndoHashTable::add(char *txt, int len)
238 uint8_t *bp = (uint8_t *)txt;
240 for( int i=len; --i>=0; ++bp ) {
242 v = (v + (v>>hash_sz2)) & hash_sz1;
244 UndoHash *hp = table[v];
245 while( hp && strncmp(hp->txt,txt,len) ) hp = hp->nxt;
247 hp = new UndoHash(txt, len, table[v]);
253 UndoLine::UndoLine(UndoHash *hash, char *tp)
255 this->txt = tp; this->len = 0;
257 hash->occurs[va] = hash->occurs[vb] = 1;
260 UndoLine::UndoLine(UndoHashTable *hash, char *txt, int len)
262 this->txt = txt; this->len = len;
263 this->hash = hash->add(txt, len);
265 UndoLine::~UndoLine()
269 int UndoLine::eq(UndoLine *ln)
271 return hash == ln->hash ? 1 : 0;
274 void UndoVersion::scan_lines(UndoHashTable *hash, char *sp, char *ep)
276 for( int line=1; sp<ep; ++line ) {
278 while( sp<ep && *sp++ != '\n' );
279 UndoLine *ln = new UndoLine(hash, txt, sp-txt);
280 ln->hash->line[ver] = line;
281 ++ln->hash->occurs[ver];
287 void UndoStackItem::set_data(char *data)
289 delete [] this->data; this->data = 0;
290 this->data_size = 0; this->key = 0;
291 int data_size = strlen(data)+1;
293 UndoStackItem *current = this;
294 // Search for key buffer within interval
295 for( int i=UNDO_KEY_INTERVAL; --i>=0 && current && !current->key; current=PREVIOUS );
297 int need_key = current ? 0 : 1;
298 // setting need_key = 1 forces all undo data items to key (not diffd)
300 char *prev = 0; int prev_size = 0;
302 #ifdef UNDO_INCREMENTAL
303 prev = previous->get_data();
304 prev_size = prev ? strlen(prev)+1 : 0;
306 prev = current->data;
307 prev_size = current->data_size;
309 int min_size = data_size/16;
310 // if the previous is a sizable incremental diff
311 if( previous && !previous->key &&
312 previous->data_size > min_size ) {
313 // and this minimum diff distance is a lot different, need key
314 int dist = abs(data_size - prev_size);
315 if( abs(dist - previous->data_size) > min_size )
320 int bfr_size = BCTEXTLEN;
321 char *bfr = new char[bfr_size];
322 XMLBuffer xbfr(bfr_size, bfr, 1);
323 xbfr.write((char*)&data_size, sizeof(data_size));
325 UndoVersion alines(va), blines(vb);
326 char *asp = data, *aep = asp + data_size-1;
327 char *bsp = prev, *bep = bsp + prev_size-1;
328 alines.append(new UndoLine(hash.bof, asp));
329 blines.append(new UndoLine(hash.bof, bsp));
330 alines.scan_lines(&hash, asp, aep);
331 blines.scan_lines(&hash, bsp, bep);
332 int asz = alines.size(), bsz = blines.size();
333 // trim matching suffix
334 while( asz > 0 && bsz > 0 && alines[asz-1]->eq(blines[bsz-1]) ) {
335 aep = alines[--asz]->txt; alines.remove_object();
336 bep = blines[--bsz]->txt; blines.remove_object();
338 // include for matching last item
339 alines.append(new UndoLine(hash.eof, aep));
340 blines.append(new UndoLine(hash.eof, bep));
341 hash.eof->line[va] = asz++;
342 hash.eof->line[vb] = bsz++;
345 while( ai < asz || bi < bsz ) {
346 // skip running match
347 if( alines[ai]->eq(blines[bi]) ) { ++ai; ++bi; continue; }
348 char *adp = alines[ai]->txt, *bdp = blines[bi]->txt;
349 // find best unique match
350 int ma = asz, mb = bsz;
351 int mx = ma + mb + 1;
352 for( int ia=ai; ia<asz && ia-ai<mx; ++ia ) {
353 UndoHash *ah = alines[ia]->hash;
354 if( ah->occurs[va] != 1 || ah->occurs[vb] != 1 ) continue;
355 int m = (ah->line[va] - ai) + (ah->line[vb] - bi);
356 if( m >= mx ) continue;
357 ma = ah->line[va]; mb = ah->line[vb]; mx = m;
360 while( ma > 0 && mb > 0 && alines[ma-1]->eq(blines[mb-1]) ) { --ma; --mb; }
361 char *ap = alines[ma]->txt, *bp = blines[mb]->txt;
364 urecd.new_ofs = adp - data;
365 urecd.new_len = ap - adp;
366 urecd.old_len = bp - bdp;
367 xbfr.write((const char*)&urecd, sizeof(urecd));
368 xbfr.write((const char*)adp, urecd.new_len);
371 int64_t pos = xbfr.otell();
372 if( abs(data_size-prev_size) < pos/2 ) {
373 this->data = new char[this->data_size = pos];
375 xbfr.read(this->data, pos);
378 char *test_data = (char*)apply_difference(
379 (unsigned char *)prev, prev_size,
380 (unsigned char *)this->data, this->data_size,
382 if( test_size != data_size || memcmp(test_data, data, test_size) ) {
383 printf("UndoStackItem::set_data: *** incremental undo failed!\n");
384 delete [] this->data; this->data = 0; this->data_size = 0;
394 #ifdef UNDO_INCREMENTAL
399 this->data = new char[this->data_size = data_size];
400 memcpy(this->data, data, this->data_size);
404 char* UndoStackItem::get_data()
406 // Find latest key buffer
407 UndoStackItem *current = this;
408 while( current && !current->key )
411 printf("UndoStackItem::get_data: no key buffer found!\n");
415 // This is the key buffer
416 if( current == this ) {
417 char *result = new char[data_size];
418 memcpy(result, data, data_size);
421 #ifdef UNDO_INCREMENTAL
423 char *current_data = current->get_data();
424 int current_size = current->data_size;
427 // Do incremental updates
429 char *new_data = (char*)apply_difference(
430 (unsigned char*)current_data, current_size,
431 (unsigned char*)current->data, current->data_size,
433 delete [] current_data;
435 if( current == this )
437 current_data = new_data;
438 current_size = new_size;
441 // Never hit this object.
442 delete [] current_data;
443 printf("UndoStackItem::get_data: lost starting object!\n");
447 char *new_data = (char*)apply_difference(
448 (unsigned char*)current->data, current->data_size,
449 (unsigned char*)this->data, this->data_size, &new_size);
454 int UndoStackItem::is_key()
459 int UndoStackItem::get_size()
464 void UndoStackItem::set_flags(uint64_t flags)
466 this->load_flags = flags;
469 uint64_t UndoStackItem::get_flags()
474 void UndoStackItem::set_creator(void *creator)
476 this->creator = creator;
479 void* UndoStackItem::get_creator()
484 void UndoStackItem::save(FILE *fp)
486 fwrite(&key,1,sizeof(key),fp);
487 fwrite(&load_flags,1,sizeof(load_flags),fp);
488 fwrite(&data_size,1,sizeof(data_size),fp);
489 fwrite(data,1,data_size,fp);
490 for( char *bp=session_filename; *bp; ++bp ) fputc(*bp, fp);
492 for( char *bp=description; *bp; ++bp ) fputc(*bp, fp);
496 void UndoStackItem::load(FILE *fp)
498 fread(&key,1,sizeof(key),fp);
499 fread(&load_flags,1,sizeof(load_flags),fp);
500 fread(&data_size,1,sizeof(data_size),fp);
501 fread(data=new char[data_size],1,data_size,fp);
502 char filename[BCTEXTLEN], descr[BCTEXTLEN];
503 char *bp = filename, *ep = bp+sizeof(filename)-1;
504 for( int ch; bp<ep && (ch=fgetc(fp))>0; ++bp ) *bp = ch;
506 session_filename = cstrdup(filename);
507 bp = descr; ep = bp+sizeof(descr)-1;
508 for( int ch; bp<ep && (ch=fgetc(fp))>0; ++bp ) *bp = ch;
510 description = cstrdup(descr);
511 //printf("read undo key=%d,flags=%jx,data_size=%d,data=%p,file=%s,descr=%s\n",
512 // key, load_flags, data_size, data, session_filename, description);
515 void UndoStack::save(FILE *fp)
517 for( UndoStackItem *item=first; item; item=item->next ) {
518 int is_current = item == current ? 1 : 0;
519 fwrite(&is_current,1,sizeof(is_current),fp);
521 // if( item == current ) break; // stop at current
525 void UndoStack::load(FILE *fp)
527 while( last ) delete last;
529 UndoStackItem *current_item = 0;
531 while( fread(&is_current,1,sizeof(is_current),fp) == sizeof(is_current) ) {
532 UndoStackItem *item = push();
534 if( is_current ) current_item = item;
536 if( current_item ) current = current_item;