| Disk ARchive 2.6.11 Full featured and portable backup and archiving tool

storage.hpp
Go to the documentation of this file.
1 /*********************************************************************/
2 // dar - disk archive - a backup/restoration program
3 // Copyright (C) 2002-2020 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 //
19 // to contact the author : http://dar.linux.free.fr/email.html
20 /*********************************************************************/
21
26
27 #ifndef STORAGE_HPP
28 #define STORAGE_HPP
29
30 #include "../my_config.h"
31 #include "integers.hpp"
32 #include "proto_generic_file.hpp"
33
34 #if LIBDAR_MODE == 32 || LIBDAR_MODE == 64
35 #include "infinint.hpp"
36 #else
37 namespace libdar
38 {
39 class infinint;
40 }
41 #endif
42
43 namespace libdar
44 {
45
48
50
52 class storage
53 {
54 private:
55 struct cellule
56 {
57 cellule() : next(nullptr), prev(nullptr), data(nullptr), size(0) {};
58 struct cellule *next, *prev;
59 unsigned char *data;
60 U_32 size;
61 };
62
63 public:
64 storage(U_32 size) { make_alloc(size, first, last); };
65 storage(const infinint & size);
66 storage(proto_generic_file & f, const infinint & size);
67 storage(const storage & ref) { copy_from(ref); };
68 storage(storage && ref) noexcept: first(nullptr), last(nullptr) { move_from(std::move(ref)); };
69 storage & operator = (const storage & val) { detruit(first); copy_from(val); return *this; };
70 storage & operator = (storage && val) noexcept { move_from(std::move(val)); return *this; };
71 ~storage() { detruit(first); };
72
73 bool operator < (const storage & ref) const noexcept
74 { return difference(ref) < 0; }; // true if arg uses more space than this
75 bool operator == (const storage & ref) const noexcept
76 { return difference(ref) == 0; }; // true if arg have same space than this
77 bool operator > (const storage & ref) const noexcept
78 { return difference(ref) > 0; };
79 bool operator <= (const storage & ref) const noexcept
80 { return difference(ref) <= 0; };
81 bool operator >= (const storage & ref) const noexcept
82 { return difference(ref) >= 0; };
83 bool operator != (const storage & ref) const noexcept
84 { return difference(ref) != 0; };
85 unsigned char & operator [](infinint position);
86 unsigned char operator [](const infinint & position) const;
87 infinint size() const noexcept;
88 void clear(unsigned char val = 0) noexcept;
89 void dump(proto_generic_file & f) const;
90
91 class iterator
92 {
93 public :
94 iterator() : ref(nullptr), cell(nullptr), offset(0) {};
95 iterator(const iterator & ref) = default;
96 iterator(iterator && ref) = default;
97 iterator & operator = (const iterator & ref) = default;
98 iterator & operator = (iterator && ref) = default;
99 ~iterator() = default;
100
101 iterator operator ++ (S_I x)
102 { iterator ret = *this; skip_plus_one(); return ret; };
103 iterator operator -- (S_I x)
104 { iterator ret = *this; skip_less_one(); return ret; };
105 iterator & operator ++ ()
106 { skip_plus_one(); return *this; };
107 iterator & operator -- ()
108 { skip_less_one(); return *this; };
109 iterator operator + (U_32 s) const
110 { iterator ret = *this; ret += s; return ret; };
111 iterator operator - (U_32 s) const
112 { iterator ret = *this; ret -= s; return ret; };
113 iterator & operator += (U_32 s);
114 iterator & operator -= (U_32 s);
115 unsigned char &operator *() const;
116
117 void skip_to(const storage & st, infinint val); // absolute position in st
118 infinint get_position() const;
119
120 bool operator == (const iterator & cmp) const noexcept
121 { return ref == cmp.ref && cell == cmp.cell && offset == cmp.offset; };
122 bool operator != (const iterator & cmp) const noexcept
123 { return ! (*this == cmp); };
124
125 private:
126 static constexpr U_32 OFF_BEGIN = 1;
127 static constexpr U_32 OFF_END = 2;
128
129 const storage *ref;
130 struct cellule *cell;
131 U_32 offset;
132
133 void relative_skip_to(S_32 val);
134 bool points_on_data() const noexcept
135 { return ref != nullptr && cell != nullptr && offset < cell->size; };
136
137 inline void skip_plus_one();
138 inline void skip_less_one();
139
140 friend class storage;
141 };
142
143 // public storage methode using iterator
144
145 iterator begin() const
146 { iterator ret; ret.cell = first; if(ret.cell != nullptr) ret.offset = 0; else ret.offset = iterator::OFF_END; ret.ref = this; return ret; };
147 iterator end() const
148 { iterator ret; ret.cell = nullptr; ret.offset = iterator::OFF_END; ret.ref = this; return ret; };
149
150 // WARNING for the two following methods :
151 // there is no "reverse_iterator" type, unlike the standart lib,
152 // thus when going from rbegin() to rend(), you must use the -- operator
153 // unlike the stdlib, that uses the ++ operator. this is the only difference in use with stdlib.
154 iterator rbegin() const
155 { iterator ret; ret.cell = last; ret.offset = last != nullptr ? last->size-1 : 0; ret.ref = this; return ret; };
156 iterator rend() const
157 { iterator ret; ret.cell = nullptr, ret.offset = iterator::OFF_BEGIN; ret.ref = this; return ret; };
158
160
164 U_I write(iterator & it, unsigned char *a, U_I size);
165 U_I read(iterator & it, unsigned char *a, U_I size) const;
166 bool write(iterator & it, unsigned char a)
167 { return write(it, &a, 1) == 1; };
168 bool read(iterator & it, unsigned char &a) const
169 { return read(it, &a, 1) == 1; };
170
171 // after one of these 3 calls, the iterator given in argument are undefined (they may point nowhere)
172 void insert_null_bytes_at_iterator(iterator it, U_I size);
173 void insert_const_bytes_at_iterator(iterator it, unsigned char a, U_I size);
174 void insert_bytes_at_iterator(iterator it, unsigned char *a, U_I size);
175 void insert_as_much_as_necessary_const_byte_to_be_as_wider_as(const storage & ref, const iterator & it, unsigned char value);
176 void remove_bytes_at_iterator(iterator it, U_I number);
177 void remove_bytes_at_iterator(iterator it, infinint number);
178
179 private:
180 struct cellule *first, *last;
181
182 void copy_from(const storage & ref);
183 void move_from(storage && ref) noexcept;
184 S_32 difference(const storage & ref) const;
185 void reduce(); // heuristic that tries to free some memory;
186 void insert_bytes_at_iterator_cmn(iterator it, bool constant, unsigned char *a, U_I size);
187 void fusionne(struct cellule *a_first, struct cellule *a_last, struct cellule *b_first, struct cellule *b_last,
188 struct cellule *&res_first, struct cellule * & res_last);
189
190 static void detruit(struct cellule *c); // destroy all cells following 'c' including 'c' itself
191 static void make_alloc(U_32 size, struct cellule * & begin, struct cellule * & end);
192 static void make_alloc(infinint size, cellule * & begin, struct cellule * & end);
193
194 friend class storage::iterator;
195 };
196
197 inline void storage::iterator::skip_plus_one()
198 {
199 if(cell != nullptr)
200 if(++offset >= cell->size)
201 {
202 cell = cell->next;
203 if(cell != nullptr)
204 offset = 0;
205 else
206 offset = OFF_END;
207 }
208 }
209
210 inline void storage::iterator::skip_less_one()
211 {
212 if(cell != nullptr)
213 {
214 if(offset > 0)
215 --offset;
216 else
217 {
218 cell = cell->prev;
219 if(cell != nullptr)
220 offset = cell->size - 1;
221 else
222 offset = OFF_BEGIN;
223 }
224 }
225 }
226
228
229 } // end of namespace
230
231 #endif
libdar::proto_generic_file
ancestor class of generic_file
Definition: proto_generic_file.hpp:55
integers.hpp
are defined here basic integer types that tend to be portable
infinint.hpp
switch module to limitint (32 ou 64 bits integers) or infinint
libdar::infinint
the arbitrary large positive integer class
Definition: real_infinint.hpp:62
libdar::storage
arbitrary large storage structure
Definition: storage.hpp:53
proto_generic_file.hpp
precursor class of generic_file used to avoid cyclic dependencies with storage and infinint
libdar::storage::write
U_I write(iterator &it, unsigned char *a, U_I size)
write data to the storage at the location pointed to by it
libdar::operator+=
std::vector< T > operator+=(std::vector< T > &a, const std::vector< T > &b)
template function to add two vectors
Definition: tools.hpp:230
libdar
libdar namespace encapsulate all libdar symbols
Definition: archive.hpp:47