1 /*********************************************************************/ 2 // dar - disk archive - a backup/restoration program 3 // Copyright (C) 2002-2052 Denis Corbin 4 // 5 // This program is free software; you can redistribute it and/or 6 // modify it under the terms of the GNU General Public License 7 // as published by the Free Software Foundation; either version 2 8 // of the License, or (at your option) any later version. 9 // 10 // This program is distributed in the hope that it will be useful, 11 // but WITHOUT ANY WARRANTY; without even the implied warranty of 12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 // GNU General Public License for more details. 14 // 15 // You should have received a copy of the GNU General Public License 16 // along with this program; if not, write to the Free Software 17 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. 18 // 19 // to contact the author : http://dar.linux.free.fr/email.html 20 /*********************************************************************/ 21 22 #include "../my_config.h" 23 24 extern "C" 25 { 26 #if HAVE_STRING_H 27 #include <string.h> 28 #endif 29 30 #if HAVE_STRINGS_H 31 #include <strings.h> 32 #endif 33 34 #if STDC_HEADERS 35 # include <string.h> 36 #else 37 # if !HAVE_STRCHR 38 # define strchr index 39 # define strrchr rindex 40 # endif 41 char *strchr (), *strrchr (); 42 # if !HAVE_MEMCPY 43 # define memcpy(d, s, n) bcopy ((s), (d), (n)) 44 # define memmove(d, s, n) bcopy ((s), (d), (n)) 45 # endif 46 #endif 47 48 } // end of extern "C" 49 50 #include "storage.hpp" 51 #include "infinint.hpp" 52 #include "generic_file.hpp" 53 #include "integers.hpp" 54 55 using namespace std; 56 57 namespace libdar 58 { 59 storage(const infinint & size)60 storage::storage(const infinint & size) 61 { 62 make_alloc(size, first, last); 63 } 64 storage(generic_file & f,const infinint & size)65 storage::storage(generic_file & f, const infinint & size) 66 { 67 U_32 lu, tmp; 68 make_alloc(size, first, last); 69 struct cellule *ptr = first; 70 71 try 72 { 73 while(ptr != nullptr) 74 { 75 lu = 0; 76 77 do 78 { 79 tmp = f.read(((char *)(ptr->data))+lu, ptr->size - lu); 80 lu += tmp; 81 } 82 while(lu < ptr->size && tmp != 0); 83 84 if(lu < ptr->size) 85 throw Erange("storage::storage", gettext("Not enough data to initialize storage field")); 86 ptr = ptr->next; 87 } 88 } 89 catch(...) 90 { 91 detruit(first); 92 first = nullptr; 93 last = nullptr; 94 throw; 95 } 96 } 97 operator [](const infinint & position) const98 unsigned char storage::operator [](const infinint &position) const 99 { 100 return const_cast<storage &>(*this)[position]; 101 } 102 operator [](infinint position)103 unsigned char & storage::operator [](infinint position) 104 { 105 U_32 offset = 0; 106 struct cellule *ptr = first; 107 108 do { 109 if(ptr == nullptr) 110 throw Erange("storage::operator[]", gettext("Asking for an element out of array")); 111 if(offset > ptr->size) 112 { 113 offset -= ptr->size; 114 ptr = ptr->next; 115 } 116 else 117 position.unstack(offset); 118 } while(offset > ptr->size); 119 120 return ptr->data[offset]; 121 } 122 size() const123 infinint storage::size() const 124 { 125 infinint ret = 0; 126 struct cellule *ptr = first; 127 128 while(ptr != nullptr) 129 { 130 ret += ptr->size; 131 ptr = ptr->next; 132 } 133 134 return ret; 135 } 136 clear(unsigned char val)137 void storage::clear(unsigned char val) 138 { 139 struct cellule *cur = first; 140 141 while(cur != nullptr) 142 { 143 (void)memset(cur->data, val, cur->size); 144 cur = cur->next; 145 } 146 } 147 dump(generic_file & f) const148 void storage::dump(generic_file & f) const 149 { 150 const struct cellule *ptr = first; 151 152 while(ptr != nullptr) 153 { 154 f.write((const char *)(ptr->data), ptr->size); 155 ptr = ptr->next; 156 } 157 } 158 write(iterator & it,unsigned char * a,U_I size)159 U_I storage::write(iterator & it, unsigned char *a, U_I size) 160 { 161 if(it.ref != this) 162 throw Erange("storage::write", gettext("The iterator is not indexing the object it has been asked to write to")); 163 164 U_I wrote = 0; 165 while(wrote < size && it != end()) 166 { 167 U_32 to_write = size - wrote; 168 U_32 space = it.cell->size - it.offset; 169 170 if(to_write <= space) 171 { 172 // enough room in current data block 173 (void)memcpy(it.cell->data + it.offset, a + wrote, to_write); 174 wrote += to_write; 175 it.offset += to_write; 176 } 177 else 178 { 179 // more to copy than available in current data block 180 (void)memcpy(it.cell->data + it.offset, a + wrote, space); 181 wrote += space; 182 it.cell = it.cell->next; 183 if(it.cell != nullptr) 184 it.offset = 0; 185 else 186 it.offset = iterator::OFF_END; 187 } 188 } 189 190 return wrote; 191 } 192 read(iterator & it,unsigned char * a,U_I size) const193 U_I storage::read(iterator & it, unsigned char *a, U_I size) const 194 { 195 if(it.ref != this) 196 throw Erange("storage::read", gettext("The iterator is not indexing the object it has been asked to read from")); 197 198 U_I read = 0; 199 while(read < size && it != end()) 200 { 201 U_32 to_read = size - read; 202 U_32 space = it.cell->size - it.offset; 203 204 if(to_read <= space) 205 { 206 // enough room in current data block 207 (void)memcpy(a + read, it.cell->data + it.offset, to_read); 208 read += to_read; 209 it.offset += to_read; 210 } 211 else 212 { 213 // more to copy than available in current data block 214 (void)memcpy(a + read, it.cell->data + it.offset, space); 215 read += space; 216 it.cell = it.cell->next; 217 if(it.cell != nullptr) 218 it.offset = 0; 219 else 220 it.offset = iterator::OFF_END; 221 } 222 } 223 224 return read; 225 } 226 insert_null_bytes_at_iterator(iterator it,U_I size)227 void storage::insert_null_bytes_at_iterator(iterator it, U_I size) 228 { 229 unsigned char a = 0; 230 231 insert_bytes_at_iterator_cmn(it, true, &a, size); 232 } 233 insert_const_bytes_at_iterator(iterator it,unsigned char a,U_I size)234 void storage::insert_const_bytes_at_iterator(iterator it, unsigned char a, U_I size) 235 { 236 insert_bytes_at_iterator_cmn(it, true, &a, size); 237 } 238 insert_bytes_at_iterator(iterator it,unsigned char * a,U_I size)239 void storage::insert_bytes_at_iterator(iterator it, unsigned char *a, U_I size) 240 { 241 insert_bytes_at_iterator_cmn(it, false, a, size); 242 } 243 insert_as_much_as_necessary_const_byte_to_be_as_wider_as(const storage & ref,const iterator & it,unsigned char value)244 void storage::insert_as_much_as_necessary_const_byte_to_be_as_wider_as(const storage & ref, const iterator &it, unsigned char value) 245 { 246 S_32 to_add = 0; 247 const cellule *c_ref = ref.first; 248 cellule *c_me = first; 249 250 while((c_ref != nullptr || to_add > 0) && (c_me != nullptr || to_add <= 0)) 251 { 252 if(to_add > 0) 253 { 254 to_add -= c_me->size; 255 c_me = c_me->next; 256 } 257 else 258 { 259 to_add += c_ref->size; 260 c_ref = c_ref->next; 261 } 262 } 263 264 while(to_add > 0) 265 { 266 insert_const_bytes_at_iterator(it, value, to_add); 267 if(c_ref != nullptr) 268 { 269 to_add = c_ref->size; 270 c_ref = c_ref->next; 271 } 272 else 273 to_add = 0; 274 } 275 } 276 remove_bytes_at_iterator(iterator it,U_I number)277 void storage::remove_bytes_at_iterator(iterator it, U_I number) 278 { 279 while(number > 0 && it.cell != nullptr) 280 { 281 U_I can_rem = it.cell->size - it.offset; 282 283 if(can_rem < number) 284 { 285 if(it.offset > 0) 286 { 287 unsigned char *p = nullptr; 288 meta_new(p, it.offset); 289 290 if(p != nullptr) 291 { 292 (void)memcpy(p, it.cell->data, it.offset); 293 meta_delete(it.cell->data); 294 295 it.cell->data = p; 296 it.cell->size -= can_rem; 297 it.cell = it.cell->next; 298 it.offset = 0; 299 number -= can_rem; 300 } 301 else 302 throw Ememory("storage::remove_bytes_at_iterator"); 303 } 304 else 305 { 306 struct cellule *t = it.cell->next; 307 308 if(t != nullptr) 309 it.cell->next->prev = it.cell->prev; 310 else 311 last = it.cell->prev; 312 313 if(it.cell->prev != nullptr) 314 it.cell->prev->next = t; 315 else 316 first = t; 317 318 number -= it.cell->size; 319 it.cell->next = nullptr; 320 it.cell->prev = nullptr; 321 detruit(it.cell); 322 it.cell = t; 323 } 324 } 325 else // can_rem >= number 326 { 327 unsigned char *p = nullptr; 328 meta_new(p, it.cell->size - number); 329 330 if(p != nullptr) 331 { 332 (void)memcpy(p, it.cell->data, it.offset); 333 (void)memcpy(p + it.offset, it.cell->data + it.offset + number, it.cell->size - it.offset - number); 334 meta_delete(it.cell->data); 335 336 it.cell->data = p; 337 it.cell->size -= number; 338 number = 0; 339 } 340 else 341 throw Ememory("storage::remove_bytes_at_iterator"); 342 } 343 } 344 reduce(); 345 } 346 remove_bytes_at_iterator(iterator it,infinint number)347 void storage::remove_bytes_at_iterator(iterator it, infinint number) 348 { 349 U_32 sz = 0; 350 number.unstack(sz); 351 352 while(sz > 0) 353 { 354 remove_bytes_at_iterator(it, sz); 355 sz = 0; 356 number.unstack(sz); 357 } 358 } 359 fusionne(struct cellule * a_first,struct cellule * a_last,struct cellule * b_first,struct cellule * b_last,struct cellule * & res_first,struct cellule * & res_last)360 void storage::fusionne(struct cellule *a_first, struct cellule *a_last, struct cellule *b_first, struct cellule *b_last, 361 struct cellule *&res_first, struct cellule * & res_last) 362 { 363 if((a_first == nullptr) ^ (a_last == nullptr)) 364 throw SRC_BUG; 365 366 if((b_first == nullptr) ^ (b_last == nullptr)) 367 throw SRC_BUG; 368 369 if(a_last != nullptr && b_first != nullptr) 370 { 371 a_last->next = b_first; 372 b_first->prev = a_last; 373 res_first = a_first; 374 res_last = b_last; 375 } 376 else 377 if(a_first == nullptr) 378 { 379 res_first = b_first; 380 res_last = b_last; 381 } 382 else 383 { 384 res_first = a_first; 385 res_last = a_last; 386 } 387 } 388 copy_from(const storage & ref)389 void storage::copy_from(const storage & ref) 390 { 391 U_32 pas = 0, delta; 392 struct cellule *ptr = ref.first; 393 first = last = nullptr; 394 395 try 396 { 397 while(ptr != nullptr || pas > 0) 398 { 399 if(ptr != nullptr) 400 { 401 delta = pas + ptr->size; 402 ptr = ptr->next; 403 } 404 else 405 delta = 0; 406 if(delta < pas) // must make the allocation 407 { 408 struct cellule *debut, *fin; 409 make_alloc(pas, debut, fin); 410 fusionne(first, last, debut, fin, first, last); 411 pas = delta; 412 } 413 else 414 pas = delta; 415 } 416 } 417 catch(Ememory & e) 418 { 419 detruit(first); 420 first = last = nullptr; 421 throw; 422 } 423 424 iterator i_ref = ref.begin(); 425 iterator i_new = begin(); 426 427 while(i_ref != ref.end()) 428 { 429 *i_new = *i_ref; 430 ++i_new; 431 ++i_ref; 432 } 433 } 434 difference(const storage & ref) const435 S_32 storage::difference(const storage & ref) const 436 { 437 struct cellule *b = last, *a = ref.last; 438 S_32 superior = 0; 439 440 while((a != nullptr || superior <= 0) && (b != nullptr || superior >= 0) && (a != nullptr || b != nullptr)) 441 { 442 if(superior >= 0 && a != nullptr) 443 { 444 superior -= a->size; 445 a = a->next; 446 } 447 if(superior <= 0 && b != nullptr) 448 { 449 superior += b->size; 450 b = b->next; 451 } 452 } 453 return superior; 454 } 455 reduce()456 void storage::reduce() 457 { 458 struct cellule *glisseur = first; 459 U_32 failed_alloc = ~0; 460 461 while(glisseur != nullptr) 462 { 463 if(glisseur->next != nullptr) 464 { 465 U_I somme = glisseur->next->size + glisseur->size; 466 467 if(somme < failed_alloc) 468 { 469 unsigned char *p = nullptr; 470 meta_new(p, somme); 471 472 if(p != nullptr) 473 { 474 struct cellule *tmp = glisseur->next; 475 476 (void)memcpy(p, glisseur->data, glisseur->size); 477 (void)memcpy(p + glisseur->size, tmp->data, somme - glisseur->size); 478 meta_delete(glisseur->data); 479 480 glisseur->data = p; 481 glisseur->size = somme; 482 483 glisseur->next = tmp->next; 484 if(glisseur->next != nullptr) 485 glisseur->next->prev = glisseur; 486 else 487 last = glisseur; 488 489 tmp->next = tmp->prev = nullptr; 490 detruit(tmp); 491 } 492 else // alloc failed 493 { 494 failed_alloc = somme; 495 glisseur = glisseur->next; 496 } 497 } 498 else // no fusion possible 499 glisseur = glisseur->next; 500 } 501 else // no next cellule 502 glisseur = glisseur->next; 503 } 504 } 505 insert_bytes_at_iterator_cmn(iterator it,bool constant,unsigned char * a,U_I size)506 void storage::insert_bytes_at_iterator_cmn(iterator it, bool constant, unsigned char *a, U_I size) 507 { 508 if(it.ref != this) 509 throw Erange("storage::insert_bytes_at_iterator_cmn", gettext("The iterator is not indexing the object it has been defined for")); 510 511 512 if(it.cell != nullptr) 513 { 514 storage temp = size+it.cell->size; 515 struct cellule *before, *after; 516 iterator gliss = temp.begin(); 517 518 if(constant) 519 temp.clear(*a); 520 temp.write(gliss, it.cell->data, it.offset); 521 if(!constant) 522 temp.write(gliss, a, size); 523 else 524 gliss += size; 525 temp.write(gliss, it.cell->data+it.offset, it.cell->size-it.offset); 526 527 if(temp.first == nullptr || temp.last == nullptr) 528 throw SRC_BUG; 529 530 // now we move the chain of cellule from the temp object into the current object (this) 531 // first we release the cellule that has been copied to "temp" object 532 before = it.cell->prev; 533 after = it.cell->next; 534 it.cell->prev = nullptr; 535 it.cell->next = nullptr; 536 detruit(it.cell); 537 it.cell = nullptr; 538 539 if(before != nullptr) 540 before->next = temp.first; 541 else 542 first = temp.first; 543 temp.first->prev = before; 544 545 if(after != nullptr) 546 after->prev = temp.last; 547 else 548 last = temp.last; 549 temp.last->next = after; 550 551 temp.first = temp.last = nullptr; 552 // this way when "temp" object will be destroyed 553 // it will not affect the chain of cells which is now 554 // part of "this" (current object). 555 556 } 557 else // it_cell == nullptr 558 { 559 storage temp = size; 560 561 if(constant) 562 temp.clear(*a); 563 else 564 { 565 iterator ut = temp.begin(); 566 temp.write(ut, a,size); 567 } 568 569 switch(it.offset) 570 { 571 case iterator::OFF_END : 572 if(last != nullptr) 573 last->next = temp.first; 574 else 575 first = temp.first; 576 if(temp.first == nullptr) 577 throw SRC_BUG; 578 temp.first->prev = last; 579 last = temp.last; 580 break; 581 case iterator::OFF_BEGIN : 582 if(first != nullptr) 583 first->prev = temp.last; 584 else 585 last = temp.last; 586 if(temp.last == nullptr) 587 throw SRC_BUG; 588 temp.last->next = first; 589 first = temp.first; 590 break; 591 default: 592 throw SRC_BUG; 593 } 594 595 temp.last = temp.first = nullptr; 596 } 597 598 reduce(); 599 } 600 detruit(struct cellule * c)601 void storage::detruit(struct cellule *c) 602 { 603 struct cellule *t; 604 605 while(c != nullptr) 606 { 607 if(c->size == 0 && c->data != nullptr) 608 throw SRC_BUG; 609 if(c->data != nullptr) 610 { 611 meta_delete(c->data); 612 c->data = nullptr; 613 } 614 t = c->next; 615 meta_delete(c); 616 c = t; 617 } 618 } 619 make_alloc(U_32 size,struct cellule * & begin,struct cellule * & end)620 void storage::make_alloc(U_32 size, struct cellule * & begin, struct cellule * & end) 621 { 622 struct cellule *newone; 623 struct cellule *previous = nullptr; 624 U_32 dsize = size; 625 626 begin = end = nullptr; 627 628 if(size > 0) 629 { 630 do 631 { 632 meta_new(newone, 1); 633 if(newone != nullptr) 634 { 635 newone->prev = previous; 636 newone->next = nullptr; 637 if(previous != nullptr) 638 previous->next = newone; 639 else 640 begin = newone; 641 } 642 else 643 { 644 detruit(begin); 645 begin = nullptr; 646 throw Ememory("storage::make_alloc"); 647 } 648 649 do 650 { 651 meta_new(newone->data, dsize); 652 if(newone->data != nullptr) 653 { 654 size -= dsize; 655 newone->size = dsize; 656 previous = newone; 657 } 658 else 659 if(dsize > 2) 660 dsize /= 2; 661 else 662 { 663 newone->size = 0; 664 detruit(begin); 665 begin = nullptr; 666 throw Ememory("storage::make_alloc"); 667 } 668 } 669 while(dsize > 1 && newone->data == nullptr); 670 } 671 while (size > 0); 672 673 end = newone; 674 } 675 } 676 make_alloc(infinint size,struct cellule * & begin,struct cellule * & end)677 void storage::make_alloc(infinint size, struct cellule * & begin, struct cellule * &end) 678 { 679 struct cellule *debut; 680 struct cellule *fin; 681 U_32 sz = 0; 682 begin = end = nullptr; 683 684 if(!size.is_zero()) 685 { 686 size.unstack(sz); 687 688 do 689 { 690 try 691 { 692 make_alloc(sz, debut, fin); 693 if(end != nullptr) 694 { 695 end->next = debut; 696 debut->prev = end; 697 end = fin; 698 } 699 else 700 if(begin != nullptr) 701 throw SRC_BUG; 702 else 703 { 704 begin = debut; 705 end = fin; 706 } 707 } 708 catch(Ememory & e) 709 { 710 if(begin != nullptr) 711 { 712 detruit(begin); 713 begin = nullptr; 714 end = nullptr; 715 } 716 717 throw; 718 } 719 sz = 0; 720 size.unstack(sz); 721 } 722 while(sz > 0); 723 } 724 } 725 726 /////////////////////////////////////////////////////////// 727 //////////////////////// ITERATOR ///////////////////////// 728 /////////////////////////////////////////////////////////// 729 730 operator +=(U_32 s)731 storage::iterator & storage::iterator::operator += (U_32 s) 732 { 733 S_32 t = s >> 1; 734 S_32 r = s & 0x1; 735 736 relative_skip_to(t); 737 relative_skip_to(t+r); 738 return *this; 739 } 740 operator -=(U_32 s)741 storage::iterator & storage::iterator::operator -= (U_32 s) 742 { 743 static const U_32 max = (U_32)(~0) >> 1; // maximum U_32 that can also be S_32 744 if(s > max) 745 { 746 S_32 t = s >> 1; // equivalent to s/2; 747 S_32 r = s & 0x01; // equivalent to s%2; 748 relative_skip_to(-t); 749 relative_skip_to(-t); 750 relative_skip_to(-r); 751 } 752 else 753 relative_skip_to(-(S_32)(s)); 754 755 return *this; 756 } 757 operator *() const758 unsigned char & storage::iterator::operator *() const 759 { 760 if(points_on_data()) 761 return cell->data[offset]; 762 else 763 throw Erange("storage::iterator::operator *()", gettext("Iterator does not point to data")); 764 } 765 skip_to(const storage & st,infinint val)766 void storage::iterator::skip_to(const storage & st, infinint val) 767 { 768 U_16 pas = 0; // relative_skip_to has S_32 as argument, cannot call it with U_32 769 770 *this = st.begin(); 771 val.unstack(pas); 772 do 773 { 774 relative_skip_to(pas); 775 pas = 0; 776 val.unstack(pas); 777 } 778 while(pas > 0); 779 } 780 relative_skip_to(S_32 val)781 void storage::iterator::relative_skip_to(S_32 val) 782 { 783 if(val >= 0) 784 { 785 while(val > 0 && cell != nullptr) 786 { 787 if(offset + val >= cell->size) 788 { 789 val -= cell->size - offset; 790 cell = cell->next; 791 offset = 0; 792 } 793 else 794 { 795 offset += val; 796 val = 0; 797 } 798 } 799 if(cell == nullptr) 800 offset = OFF_END; 801 } 802 else 803 while(val < 0 && cell != nullptr) 804 { 805 val += offset; 806 if(val < 0) 807 { 808 cell = cell->prev; 809 if(cell != nullptr) 810 offset = cell->size; 811 else 812 offset = OFF_BEGIN; 813 } 814 else 815 offset = val; 816 } 817 } 818 get_position() const819 infinint storage::iterator::get_position() const 820 { 821 if(ref == nullptr || ref->first == nullptr) 822 throw Erange("storage::iterator::get_position", gettext("Reference storage of the iterator is empty or non existent")); 823 824 struct cellule *p = ref->first; 825 infinint ret = 0; 826 827 if(cell == nullptr) 828 throw Erange("storage::iterator::get_position", gettext("Iterator does not point to data")); 829 830 while(p != nullptr && p != cell) 831 { 832 ret += p->size; 833 p = p->next; 834 } 835 836 if(p != nullptr) 837 ret += offset; 838 else 839 throw Erange("storage::iterator::get_position", gettext("The iterator position is not inside the storage of reference")); 840 841 return ret; 842 } 843 844 } // end of namespace 845