Disk ARchive  2.4.2
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
storage.hpp
Go to the documentation of this file.
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 // $Id: storage.hpp,v 1.20 2011/01/22 22:39:10 edrusb Rel $
22 //
23 /*********************************************************************/
24 
28 
29 #include "../my_config.h"
30 #include "erreurs.hpp"
31 #include "integers.hpp"
32 
33 #ifdef LIBDAR_MODE
34 #include "infinint.hpp"
35 #endif
36 
37  // it is necessary to not protect the previous inclusion inside
38  // the STORAGE_HPP protection to avoid cyclic dependancies.
39 
40 #ifndef STORAGE_HPP
41 #define STORAGE_HPP
42 
43 #ifndef LIBDAR_MODE
44 namespace libdar
45 {
46  class infinint;
47 }
48 #endif
49 
50 namespace libdar
51 {
52  class generic_file;
53 
55 
58 
59  class storage
60  {
61  private:
62  struct cellule
63  {
64  cellule() : next(NULL), prev(NULL), data(NULL), size(0) {};
65  struct cellule *next, *prev;
66  unsigned char *data;
67  U_32 size;
68  };
69 
70  public:
71  storage(U_32 size)
72  { E_BEGIN; make_alloc(size, first, last); E_END("storage::storage","U_32"); };
73  storage(const infinint & size);
74  storage(const storage & ref)
75  { E_BEGIN; copy_from(ref); E_END("storage::storage", "storage &"); };
76  storage(generic_file & f, const infinint &size);
77  ~storage()
78  { E_BEGIN; detruit(first); E_END("storage::~storage", ""); };
79 
80  const storage & operator = (const storage & val)
81  { E_BEGIN; detruit(first); copy_from(val); return *this; E_END("storage::operator=",""); };
82 
83  bool operator < (const storage & ref) const
84  { E_BEGIN; return difference(ref) < 0; E_END("storage::operator <",""); }; // true if arg uses more space than this
85  bool operator == (const storage & ref) const
86  { E_BEGIN; return difference(ref) == 0; E_END("storage::operator ==",""); }; //true if arg have same space than this
87  bool operator > (const storage & ref) const
88  { E_BEGIN; return difference(ref) > 0; E_END("storage::operator >", ""); };
89  bool operator <= (const storage & ref) const
90  { E_BEGIN; return difference(ref) <= 0; E_END("storage::operator <=", ""); };
91  bool operator >= (const storage & ref) const
92  { E_BEGIN; return difference(ref) >= 0; E_END("storage::operator >=", ""); };
93  bool operator != (const storage & ref) const
94  { E_BEGIN; return difference(ref) != 0; E_END("storage::operator !=", ""); };
95  unsigned char & operator [](infinint position);
96  unsigned char operator [](const infinint & position) const;
97  infinint size() const;
98  void clear(unsigned char val = 0);
99  void dump(generic_file & f) const;
100 
101  class iterator
102  {
103  public :
104  iterator() : ref(NULL), cell(NULL), offset(0) {};
105  // default constructor by reference is OK
106  // default destructor is OK
107  // default operator = is OK
108 
109  iterator operator ++ (S_I x)
110  { E_BEGIN; iterator ret = *this; skip_plus_one(); return ret; E_END("storage::iterator::operator++", "(S_I)"); };
111  iterator operator -- (S_I x)
112  { E_BEGIN; iterator ret = *this; skip_less_one(); return ret; E_END("storage::iterator::operator--", "(S_I)");};
113  iterator & operator ++ ()
114  { E_BEGIN; skip_plus_one(); return *this; E_END("storage::iterator::operator++", "()"); };
115  iterator & operator -- ()
116  { E_BEGIN; skip_less_one(); return *this; E_END("storage::iterator::operator--", "()"); };
117  iterator operator + (U_32 s) const
118  { E_BEGIN; iterator ret = *this; ret += s; return ret; E_END("storage::iterator::operator +", ""); };
119  iterator operator - (U_32 s) const
120  { E_BEGIN; iterator ret = *this; ret -= s; return ret; E_END("storage::iterator::operator -", ""); };
121  iterator & operator += (U_32 s);
122  iterator & operator -= (U_32 s);
123  unsigned char &operator *() const;
124 
125  void skip_to(const storage & st, infinint val); // absolute position in st
126  infinint get_position() const;
127 
128  bool operator == (const iterator & cmp) const
129  { E_BEGIN; return ref == cmp.ref && cell == cmp.cell && offset == cmp.offset; E_END("storage::iterator::operator ==", ""); };
130  bool operator != (const iterator & cmp) const
131  { E_BEGIN; return ! (*this == cmp); E_END("storage::iterator::operator !=", ""); };
132 
133  private:
134  static const U_32 OFF_BEGIN = 1;
135  static const U_32 OFF_END = 2;
136 
137  const storage *ref;
138  struct cellule *cell;
139  U_32 offset;
140 
141  void relative_skip_to(S_32 val);
142  bool points_on_data() const
143  { E_BEGIN; return ref != NULL && cell != NULL && offset < cell->size; E_END("storage::iterator::point_on_data", "");};
144 
145  inline void skip_plus_one();
146  inline void skip_less_one();
147 
148  friend class storage;
149  };
150 
151  // public storage methode using iterator
152 
153  iterator begin() const
154  { E_BEGIN; iterator ret; ret.cell = first; if(ret.cell != NULL) ret.offset = 0; else ret.offset = iterator::OFF_END; ret.ref = this; return ret; E_END("storage::begin", ""); };
155  iterator end() const
156  { E_BEGIN; iterator ret; ret.cell = NULL; ret.offset = iterator::OFF_END; ret.ref = this; return ret; E_END("storage::end", ""); };
157 
158  // WARNING for the two following methods :
159  // there is no "reverse_iterator" type, unlike the standart lib,
160  // thus when going from rbegin() to rend(), you must use the -- operator
161  // unlike the stdlib, that uses the ++ operator. this is the only difference in use with stdlib.
162  iterator rbegin() const
163  { E_BEGIN; iterator ret; ret.cell = last; ret.offset = last != NULL ? last->size-1 : 0; ret.ref = this; return ret; E_END("storage::rbegin", ""); };
164  iterator rend() const
165  { E_BEGIN; iterator ret; ret.cell = NULL, ret.offset = iterator::OFF_BEGIN; ret.ref = this; return ret; E_END("storage::rend", ""); };
166 
168 
172  U_I write(iterator & it, unsigned char *a, U_I size);
173  U_I read(iterator & it, unsigned char *a, U_I size) const;
174  bool write(iterator & it, unsigned char a)
175  { E_BEGIN; return write(it, &a, 1) == 1; E_END("storage::write", "unsigned char"); };
176  bool read(iterator & it, unsigned char &a) const
177  { E_BEGIN; return read(it, &a, 1) == 1; E_END("storage::read", "unsigned char"); };
178 
179  // after one of these 3 calls, the iterator given in argument are undefined (they may point nowhere)
180  void insert_null_bytes_at_iterator(iterator it, U_I size);
181  void insert_const_bytes_at_iterator(iterator it, unsigned char a, U_I size);
182  void insert_bytes_at_iterator(iterator it, unsigned char *a, U_I size);
183  void insert_as_much_as_necessary_const_byte_to_be_as_wider_as(const storage & ref, const iterator & it, unsigned char value);
184  void remove_bytes_at_iterator(iterator it, U_I number);
185  void remove_bytes_at_iterator(iterator it, infinint number);
186 
187 
188  private:
189  struct cellule *first, *last;
190 
191  void copy_from(const storage & ref);
192  S_32 difference(const storage & ref) const;
193  void reduce(); // heuristic that tries to free some memory;
194  void insert_bytes_at_iterator_cmn(iterator it, bool constant, unsigned char *a, U_I size);
195  void fusionne(struct cellule *a_first, struct cellule *a_last, struct cellule *b_first, struct cellule *b_last,
196  struct cellule *&res_first, struct cellule * & res_last);
197 
199  // STATIC statments :
200  //
201 
202  static void detruit(struct cellule *c);
203  static void make_alloc(U_32 size, struct cellule * & begin, struct cellule * & end);
204  static void make_alloc(infinint size, cellule * & begin, struct cellule * & end);
205 
206  friend class storage::iterator;
207  };
208 
209  inline void storage::iterator::skip_plus_one()
210  {
211  E_BEGIN;
212  if(cell != NULL)
213  if(++offset >= cell->size)
214  {
215  cell = cell->next;
216  if(cell != NULL)
217  offset = 0;
218  else
219  offset = OFF_END;
220  }
221  E_END("storage::iterator::slik_plus_one", "");
222  }
223 
224  inline void storage::iterator::skip_less_one()
225  {
226  E_BEGIN;
227  if(cell != NULL)
228  {
229  if(offset > 0)
230  --offset;
231  else
232  {
233  cell = cell->prev;
234  if(cell != NULL)
235  offset = cell->size - 1;
236  else
237  offset = OFF_BEGIN;
238  }
239  }
240  E_END("storage::iterator::slik_plus_one", "");
241  }
242 
243 } // end of namespace
244 
245 #endif