Disk ARchive  2.4.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines
src/libdar/storage.hpp
00001 /*********************************************************************/
00002 // dar - disk archive - a backup/restoration program
00003 // Copyright (C) 2002-2052 Denis Corbin
00004 //
00005 // This program is free software; you can redistribute it and/or
00006 // modify it under the terms of the GNU General Public License
00007 // as published by the Free Software Foundation; either version 2
00008 // of the License, or (at your option) any later version.
00009 //
00010 // This program is distributed in the hope that it will be useful,
00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00013 // GNU General Public License for more details.
00014 //
00015 // You should have received a copy of the GNU General Public License
00016 // along with this program; if not, write to the Free Software
00017 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
00018 //
00019 // to contact the author : http://dar.linux.free.fr/email.html
00020 /*********************************************************************/
00021 // $Id$
00022 //
00023 /*********************************************************************/
00024 
00028 
00029 #include "../my_config.h"
00030 #include "erreurs.hpp"
00031 #include "integers.hpp"
00032 #include "special_alloc.hpp"
00033 
00034 #ifdef LIBDAR_MODE
00035 #include "infinint.hpp"
00036 #endif
00037 
00038     // it is necessary to not protect the previous inclusion inside
00039     // the STORAGE_HPP protection to avoid cyclic dependancies.
00040 
00041 #ifndef STORAGE_HPP
00042 #define STORAGE_HPP
00043 
00044 #ifndef LIBDAR_MODE
00045 namespace libdar
00046 {
00047     class infinint;
00048 }
00049 #endif
00050 
00051 namespace libdar
00052 {
00053     class generic_file;
00054 
00056 
00059 
00060     class storage
00061     {
00062     private:
00063         struct cellule
00064         {
00065             cellule() : next(NULL), prev(NULL), data(NULL), size(0) {};
00066             struct cellule *next, *prev;
00067             unsigned char *data;
00068             U_32 size;
00069         };
00070 
00071     public:
00072         storage(U_32 size)
00073             { make_alloc(size, first, last); };
00074         storage(const infinint & size);
00075         storage(const storage & ref)
00076             { copy_from(ref); };
00077         storage(generic_file & f, const infinint &size);
00078         ~storage()
00079             {  detruit(first); };
00080 
00081         const storage & operator = (const storage & val)
00082             {  detruit(first); copy_from(val); return *this; };
00083 
00084         bool operator < (const storage & ref) const
00085             { return difference(ref) < 0; }; // true if arg uses more space than this
00086         bool operator == (const storage & ref) const
00087             { return difference(ref) == 0; }; //true if arg have same space than this
00088         bool operator > (const storage & ref) const
00089             { return difference(ref) > 0; };
00090         bool operator <= (const storage & ref) const
00091             { return difference(ref) <= 0; };
00092         bool operator >= (const storage & ref) const
00093             { return difference(ref) >= 0; };
00094         bool operator != (const storage & ref) const
00095             { return difference(ref) != 0; };
00096         unsigned char & operator [](infinint position);
00097         unsigned char operator [](const infinint & position) const;
00098         infinint size() const;
00099         void clear(unsigned char val = 0);
00100         void dump(generic_file & f) const;
00101 
00102         class iterator
00103         {
00104         public :
00105             iterator() : ref(NULL), cell(NULL), offset(0) {};
00106                 // default constructor by reference is OK
00107                 // default destructor is OK
00108                 // default operator = is OK
00109 
00110             iterator operator ++ (S_I x)
00111                 { iterator ret = *this; skip_plus_one(); return ret; };
00112             iterator operator -- (S_I x)
00113                 { iterator ret = *this; skip_less_one(); return ret; };
00114             iterator & operator ++ ()
00115                 { skip_plus_one(); return *this; };
00116             iterator & operator -- ()
00117                 { skip_less_one(); return *this; };
00118             iterator operator + (U_32 s) const
00119                 { iterator ret = *this; ret += s; return ret; };
00120             iterator operator - (U_32 s) const
00121                 { iterator ret = *this; ret -= s; return ret; };
00122             iterator & operator += (U_32 s);
00123             iterator & operator -= (U_32 s);
00124             unsigned char &operator *() const;
00125 
00126             void skip_to(const storage & st, infinint val); // absolute position in st
00127             infinint get_position() const;
00128 
00129             bool operator == (const iterator & cmp) const
00130                 { return ref == cmp.ref && cell == cmp.cell && offset == cmp.offset; };
00131             bool operator != (const iterator & cmp) const
00132                 { return ! (*this == cmp); };
00133 
00134         private:
00135             static const U_32 OFF_BEGIN = 1;
00136             static const U_32 OFF_END = 2;
00137 
00138             const storage *ref;
00139             struct cellule *cell;
00140             U_32 offset;
00141 
00142             void relative_skip_to(S_32 val);
00143             bool points_on_data() const
00144                 {  return ref != NULL && cell != NULL && offset < cell->size; };
00145 
00146             inline void skip_plus_one();
00147             inline void skip_less_one();
00148 
00149             friend class storage;
00150         };
00151 
00152             // public storage methode using iterator
00153 
00154         iterator begin() const
00155             { iterator ret; ret.cell = first; if(ret.cell != NULL) ret.offset = 0; else ret.offset = iterator::OFF_END; ret.ref = this; return ret; };
00156         iterator end() const
00157             { iterator ret; ret.cell = NULL; ret.offset = iterator::OFF_END; ret.ref = this; return ret;  };
00158 
00159             // WARNING for the two following methods :
00160             // there is no "reverse_iterator" type, unlike the standart lib,
00161             // thus when going from rbegin() to rend(), you must use the -- operator
00162             // unlike the stdlib, that uses the ++ operator. this is the only difference in use with stdlib.
00163         iterator rbegin() const
00164             { iterator ret; ret.cell = last; ret.offset = last != NULL ? last->size-1 : 0; ret.ref = this; return ret; };
00165         iterator rend() const
00166             { iterator ret; ret.cell = NULL, ret.offset = iterator::OFF_BEGIN; ret.ref = this; return ret; };
00167 
00169 
00173         U_I write(iterator & it, unsigned char *a, U_I size);
00174         U_I read(iterator & it, unsigned char *a, U_I size) const;
00175         bool write(iterator & it, unsigned char a)
00176             { return write(it, &a, 1) == 1; };
00177         bool read(iterator & it, unsigned char &a) const
00178             { return read(it, &a, 1) == 1; };
00179 
00180             // after one of these 3 calls, the iterator given in argument are undefined (they may point nowhere)
00181         void insert_null_bytes_at_iterator(iterator it, U_I size);
00182         void insert_const_bytes_at_iterator(iterator it, unsigned char a, U_I size);
00183         void insert_bytes_at_iterator(iterator it, unsigned char *a, U_I size);
00184         void insert_as_much_as_necessary_const_byte_to_be_as_wider_as(const storage & ref, const iterator & it, unsigned char value);
00185         void remove_bytes_at_iterator(iterator it, U_I number);
00186         void remove_bytes_at_iterator(iterator it, infinint number);
00187 
00188 #ifdef LIBDAR_SPECIAL_ALLOC
00189         USE_SPECIAL_ALLOC(storage);
00190 #endif
00191     private:
00192         struct cellule *first, *last;
00193 
00194         void copy_from(const storage & ref);
00195         S_32 difference(const storage & ref) const;
00196         void reduce(); // heuristic that tries to free some memory;
00197         void insert_bytes_at_iterator_cmn(iterator it, bool constant, unsigned char *a, U_I size);
00198         void fusionne(struct cellule *a_first, struct cellule *a_last, struct cellule *b_first, struct cellule *b_last,
00199                       struct cellule *&res_first, struct cellule * & res_last);
00200 
00202             // STATIC statments :
00203             //
00204 
00205         static void detruit(struct cellule *c);
00206         static void make_alloc(U_32 size, struct cellule * & begin, struct cellule * & end);
00207         static void make_alloc(infinint size, cellule * & begin, struct cellule * & end);
00208 
00209         friend class storage::iterator;
00210     };
00211 
00212     inline void storage::iterator::skip_plus_one()
00213     {
00214         if(cell != NULL)
00215             if(++offset >= cell->size)
00216             {
00217                 cell = cell->next;
00218                 if(cell != NULL)
00219                     offset = 0;
00220                 else
00221                     offset = OFF_END;
00222             }
00223     }
00224 
00225     inline void storage::iterator::skip_less_one()
00226     {
00227         if(cell != NULL)
00228         {
00229             if(offset > 0)
00230                 --offset;
00231             else
00232             {
00233                 cell = cell->prev;
00234                 if(cell != NULL)
00235                     offset = cell->size - 1;
00236                 else
00237                     offset = OFF_BEGIN;
00238             }
00239         }
00240     }
00241 
00242 } // end of namespace
00243 
00244 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines