Disk ARchive 2.7.15
Full featured and portable backup and archiving tool
Loading...
Searching...
No Matches
storage.hpp
Go to the documentation of this file.
1/*********************************************************************/
2// dar - disk archive - a backup/restoration program
3// Copyright (C) 2002-2024 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, see the AUTHOR file
20/*********************************************************************/
21
26
27#ifndef STORAGE_HPP
28#define STORAGE_HPP
29
30#include "../my_config.h"
31#include "integers.hpp"
33
34#if LIBDAR_MODE == 32 || LIBDAR_MODE == 64
35#include "infinint.hpp"
36#else
37namespace libdar
38{
39 class infinint;
40}
41#endif
42
43namespace 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 void truncate(const infinint & pos);
179
180 private:
181 struct cellule *first, *last;
182
183 void copy_from(const storage & ref);
184 void move_from(storage && ref) noexcept;
185 S_32 difference(const storage & ref) const;
186 void reduce(); // heuristic that tries to free some memory;
187 void insert_bytes_at_iterator_cmn(iterator it, bool constant, unsigned char *a, U_I size);
188 void fusionne(struct cellule *a_first, struct cellule *a_last, struct cellule *b_first, struct cellule *b_last,
189 struct cellule *&res_first, struct cellule * & res_last);
190
191 static void detruit(struct cellule *c); // destroy all cells following 'c' including 'c' itself
192 static void make_alloc(U_32 size, struct cellule * & begin, struct cellule * & end);
193 static void make_alloc(infinint size, cellule * & begin, struct cellule * & end);
194
195 friend class storage::iterator;
196 };
197
198 inline void storage::iterator::skip_plus_one()
199 {
200 if(cell != nullptr)
201 if(++offset >= cell->size)
202 {
203 cell = cell->next;
204 if(cell != nullptr)
205 offset = 0;
206 else
207 offset = OFF_END;
208 }
209 }
210
211 inline void storage::iterator::skip_less_one()
212 {
213 if(cell != nullptr)
214 {
215 if(offset > 0)
216 --offset;
217 else
218 {
219 cell = cell->prev;
220 if(cell != nullptr)
221 offset = cell->size - 1;
222 else
223 offset = OFF_BEGIN;
224 }
225 }
226 }
227
229
230} // end of namespace
231
232#endif
the arbitrary large positive integer class
ancestor class of generic_file
arbitrary large storage structure
Definition storage.hpp:53
U_I write(iterator &it, unsigned char *a, U_I size)
write data to the storage at the location pointed to by it
switch module to limitint (32 ou 64 bits integers) or infinint
are defined here basic integer types that tend to be portable
libdar namespace encapsulate all libdar symbols
Definition archive.hpp:47
precursor class of generic_file used to avoid cyclic dependencies with storage and infinint