skein/hopper

view combined/skeintreepp.hpp @ 31:2cee2d6dcb85

find changesets by author, revision, files, or words in the commit message
I think I finally have a workable interface.
author Eric Hopper <hopper@omnifarious.org>
date Fri, 26 Jun 2009 23:26:10 -0700
parents 1c8aa49d116f
children b8b91d47e466
line source
1 #pragma once
2 #pragma interface
3 #include <string>
4 #include <cstddef>
5 #include <cstdint>
6 #include <algorithm>
7 #include "skeinpp.hpp"
8 #include "skeinpp_priv.hpp"
9 #define nullptr 0
10
11 namespace skein {
12
13 class SkeinLeafFetcher;
14
15 #ifdef __GNUG__
16 __attribute__((const)) inline short whichPowerOf2(::std::size_t v) {
17 if (v != 0) {
18 const short result = __builtin_ctzll(v);
19 if ((v >> result) == 1) {
20 return result;
21 }
22 }
23 return -1;
24 }
25 #else
26 inline short whichPowerOf2(::std::size_t v) {
27 if (v != 0) {
28 short result = 0;
29 while (!(v & 1u)) {
30 ++result;
31 v >>= 1;
32 }
33 if (v == 1) {
34 return result;
35 }
36 }
37 return -1;
38 }
39 #endif
40
41 //! A class for generating hash values using SKein's tree hash mode.
42 class SkeinTreeHasher {
43 public:
44 SkeinTreeHasher(const SkeinParameters &parameters,
45 ::std::uint64_t outputbits,
46 SkeinLeafFetcher &leaf_fetcher);
47
48 };
49
50 //! Data for an individual leaf managed by a SkeinLeafFetcher, follows the
51 //! auto_ptr pattern of being moveable but not copyable.
52 //
53 // \invariant
54 // isLast() || getLeafSize() == fetcher.leafSize(), meaning that all leaves
55 // except for the last should be the leaf size given by the leaf fetcher.
56 //
57 // \note
58 // This class is moveable, but not copyable. In c++0x this is handled in the
59 // correct way using rvalue references, move constructors and move assignment
60 // operators while disabling copy constructors and standard assignment.
61 //
62 // \para
63 // In earlier versions of C++ this is done with ::std::auto_ptr like kludges in
64 // which the copy constructor and assignment operators modify the right hand
65 // side argument.
66 class SkeinLeafData {
67 friend class SkeinLeafFetcher;
68 public:
69 SkeinLeafData()
70 : num_(0), data_(nullptr), len_(0), islast_(false), owner_(nullptr)
71 {
72 }
73 #ifdef HAVE_CXX0X
74 SkeinLeafData(SkeinLeafData &&rhs)
75 : num_(rhs.num_), data_(rhs.data_), len_(rhs.len_),
76 islast_(rhs.islast_), owner_(rhs.owner_)
77 {
78 rhs.data_ = nullptr;
79 rhs.owner_ = nullptr;
80 }
81 #else
82 SkeinLeafData(SkeinLeafData &rhs)
83 : num_(rhs.num_), data_(rhs.data_), len_(rhs.len_),
84 islast_(rhs.islast_), owner_(rhs.owner_)
85 {
86 rhs.data_ = nullptr;
87 rhs.owner_ = nullptr;
88 }
89 #endif
90 ~SkeinLeafData()
91 {
92 freeme();
93 }
94
95 //! Which leaf number is this?
96 ::std::uintmax_t getLeafNum() const { return num_; }
97 //! Give me a pointer to the data for this leaf (preferably page aligned).
98 const void *getLeafData() const { return isNull() ? nullptr : data_; }
99 //! How big is this leaf (they should all be the same size except the last).
100 ::std::size_t getLeafSize() const { return len_; }
101 //! Is this the last leaf?
102 bool isLast() const { return islast_; }
103 //! Is the data valid?
104 bool isNull() const { return !(data_ && owner_); }
105
106 #ifdef HAVE_CXX0X
107 SkeinLeafData &operator =(SkeinLeafData &&rhs)
108 #else
109 SkeinLeafData &operator =(SkeinLeafData &rhs)
110 #endif
111 {
112 const bool isnull = isNull();
113 if (isnull) {
114 num_ = rhs.num_;
115 } else {
116 ::std::swap(num_, rhs.num_);
117 }
118 if (isnull) {
119 // Done this way to properly handle self-assignment.
120 const void * const data = rhs.data_;
121 rhs.data_ = nullptr;
122 data_ = data;
123 } else {
124 ::std::swap(data_, rhs.data_);
125 }
126 if (isnull) {
127 len_ = rhs.len_;
128 } else {
129 ::std::swap(len_, rhs.len_);
130 }
131 if (isnull) {
132 islast_ = rhs.islast_;
133 } else {
134 ::std::swap(islast_, rhs.islast_);
135 }
136 if (isnull) {
137 // Done this way to properly handle self-assignment.
138 SkeinLeafFetcher * const owner = rhs.owner_;
139 rhs.owner_ = nullptr;
140 owner_ = owner;
141 } else {
142 ::std::swap(owner_, rhs.owner_);
143 }
144 return *this;
145 }
146
147 protected:
148 //! Construct leaf data from the components.
149 //
150 // \param owner This reference is saved until the SkeinLeafData object is
151 // destroyed.
152 SkeinLeafData(::std::uintmax_t num, const void *data,
153 ::std::size_t len, bool islast, SkeinLeafFetcher &owner)
154 : num_(num), data_(data), len_(len), islast_(islast), owner_(&owner)
155 {
156 }
157
158 inline void freeme();
159
160 private:
161 ::std::uintmax_t num_;
162 const void *data_;
163 ::std::size_t len_;
164 bool islast_;
165 SkeinLeafFetcher *owner_;
166
167 #ifdef HAVE_CXX0X
168 const SkeinLeafData &operator =(const SkeinLeafData &rhs) = delete;
169 SkeinLeafData(const SkeinLeafData &) = delete;
170 #endif
171 };
172
173 class SkeinLeafFetcher {
174 public:
175 enum FetcherResult {
176 FR_Success, //!< It worked!
177 FR_Block, //!< You'd have to wait and you said you didn't want to.
178 FR_Deadlock, //!< You need to free a leaf first.
179 FR_TooFar //!< You requested a leaf index that's past the last leaf.
180 };
181 SkeinLeafFetcher(::std::uint_least16_t blocksize, ::std::size_t leafsize)
182 : leafsize_(leafsize), fanout_(::std::max(::std::size_t(2U),
183 leafsize / blocksize)),
184 maxheight_(255U)
185 {
186 }
187 SkeinLeafFetcher(::std::size_t leafsize, ::std::size_t fanout,
188 ::std::uint_least8_t maxheight = 255U)
189 : leafsize_(leafsize), fanout_(::std::max(::std::size_t(2U), fanout)),
190 maxheight_(::std::min(::std::uint_least8_t(255U),
191 ::std::max(::std::uint_least8_t(2U),
192 maxheight)))
193 {
194 }
195
196 virtual ~SkeinLeafFetcher() = 0;
197
198 //! Size of each leaf.
199 ::std::size_t leafSize() const { return leafsize_; }
200 //! How many leaves are at each level of the tree, must be >= 2.
201 ::std::size_t fanout() const { return fanout_; }
202 //! Maximum height of tree from 2 to 255, 255 meaning unlimited.
203 ::std::uint_least8_t maxHeight() const { return maxheight_; }
204
205 //! Allocate a leaf and stuff it into the passed in SkeinLeafData object.
206 virtual FetcherResult allocateLeaf(::std::uint64_t leafnum,
207 SkeinLeafData &dest,
208 bool blocking = false) = 0;
209 //! Informs the SkeinLeafFetcher that a given leaf is no longer needed in
210 // memory.
211 virtual void freeLeaf(SkeinLeafData &leafdata) = 0;
212
213 private:
214 const ::std::size_t leafsize_;
215 const ::std::size_t fanout_;
216 const ::std::uint_least8_t maxheight_;
217
218 #ifdef HAVE_CXX0X
219 SkeinLeafFetcher(const SkeinLeafFetcher &) = delete;
220 const SkeinLeafFetcher &operator =(const SkeinLeafFetcher &) = delete;
221 #else
222 //! Purposefully undefined
223 SkeinLeafFetcher(const SkeinLeafFetcher &);
224 //! Purposefully undefined
225 const SkeinLeafFetcher &operator =(const SkeinLeafFetcher &);
226 #endif
227 };
228
229
230 inline void SkeinLeafData::freeme()
231 {
232 if (!isNull()) {
233 owner_->freeLeaf(*this);
234 data_ = nullptr;
235 owner_ = nullptr;
236 }
237 }
238
239
240 } // namespace skein