Commit | Line | Data |
a20d9a3f |
1 | package DBM::Deep::Engine; |
2 | |
460b1067 |
3 | use 5.6.0; |
4 | |
a20d9a3f |
5 | use strict; |
6 | |
c3aafc14 |
7 | our $VERSION = q(0.99_03); |
86867f3a |
8 | |
633df1fd |
9 | use Fcntl qw( :DEFAULT :flock ); |
359a01ac |
10 | use Scalar::Util (); |
a20d9a3f |
11 | |
21838116 |
12 | # File-wide notes: |
20b7f047 |
13 | # * To add to bucket_size, make sure you modify the following: |
14 | # - calculate_sizes() |
15 | # - _get_key_subloc() |
16 | # - add_bucket() - where the buckets are printed |
c3aafc14 |
17 | # |
83371fe3 |
18 | # * Every method in here assumes that the _storage has been appropriately |
c3aafc14 |
19 | # safeguarded. This can be anything from flock() to some sort of manual |
20 | # mutex. But, it's the caller's responsability to make sure that this has |
21 | # been done. |
21838116 |
22 | |
8db25060 |
23 | ## |
24 | # Setup file and tag signatures. These should never change. |
25 | ## |
26 | sub SIG_FILE () { 'DPDB' } |
460b1067 |
27 | sub SIG_HEADER () { 'h' } |
8db25060 |
28 | sub SIG_INTERNAL () { 'i' } |
29 | sub SIG_HASH () { 'H' } |
30 | sub SIG_ARRAY () { 'A' } |
8db25060 |
31 | sub SIG_NULL () { 'N' } |
32 | sub SIG_DATA () { 'D' } |
33 | sub SIG_INDEX () { 'I' } |
34 | sub SIG_BLIST () { 'B' } |
7b1e1aa1 |
35 | sub SIG_FREE () { 'F' } |
86867f3a |
36 | sub SIG_KEYS () { 'K' } |
8db25060 |
37 | sub SIG_SIZE () { 1 } |
38 | |
fb451ba6 |
39 | # This is the transaction ID for the HEAD |
40 | sub HEAD () { 0 } |
41 | |
c3aafc14 |
42 | ################################################################################ |
43 | # |
44 | # This is new code. It is a complete rewrite of the engine based on a new API |
45 | # |
46 | ################################################################################ |
47 | |
c3aafc14 |
48 | sub read_value { |
49 | my $self = shift; |
40956c06 |
50 | my ($trans_id, $offset, $key, $orig_key) = @_; |
c3aafc14 |
51 | |
40956c06 |
52 | my $dig_key = $self->_apply_digest( $key ); |
e5a9d386 |
53 | my $tag = $self->find_blist( $offset, $dig_key ) or return; |
54 | return $self->get_bucket_value( $tag, $dig_key, $orig_key ); |
c3aafc14 |
55 | } |
56 | |
c3aafc14 |
57 | sub key_exists { |
58 | my $self = shift; |
40956c06 |
59 | my ($trans_id, $offset, $key) = @_; |
c3aafc14 |
60 | |
40956c06 |
61 | my $dig_key = $self->_apply_digest( $key ); |
e5a9d386 |
62 | # exists() returns the empty string, not undef |
63 | my $tag = $self->find_blist( $offset, $dig_key ) or return ''; |
c3aafc14 |
64 | return $self->bucket_exists( $tag, $dig_key, $key ); |
65 | } |
66 | |
8b62364d |
67 | =pod |
68 | sub key_exists { |
69 | my $self = shift; |
70 | my ($trans_id, $base_offset, $key) = @_; |
71 | |
72 | my ($_val_offset, $_is_del) = $self->_find_value_offset({ |
73 | offset => $base_offset, |
74 | trans_id => $trans_id, |
75 | allow_head => 1, |
76 | }); |
77 | die "Attempt to use a deleted value" if $_is_del; |
78 | die "Internal error!" if !$_val_offset; |
79 | |
80 | my ($key_offset) = $self->_find_key_offset({ |
81 | offset => $_val_offset, |
82 | key_md5 => $self->_apply_digest( $key ), |
83 | create => 0, |
84 | }); |
85 | return if !$key_offset; |
86 | |
87 | my ($val_offset, $is_del) = $self->_find_value_offset({ |
88 | offset => $key_offset, |
89 | trans_id => $trans_id, |
90 | allow_head => 1, |
91 | }); |
92 | |
93 | return 1 if $is_del; |
94 | |
95 | die "Internal error!" if !$_val_offset; |
96 | return ''; |
97 | } |
98 | =cut |
99 | |
83c43bb5 |
100 | sub get_next_key { |
c3aafc14 |
101 | my $self = shift; |
40956c06 |
102 | my ($trans_id, $offset) = @_; |
c3aafc14 |
103 | |
83c43bb5 |
104 | # If the previous key was not specifed, start at the top and |
105 | # return the first one found. |
106 | my $temp; |
40956c06 |
107 | if ( @_ > 2 ) { |
83c43bb5 |
108 | $temp = { |
40956c06 |
109 | prev_md5 => $self->_apply_digest($_[2]), |
83c43bb5 |
110 | return_next => 0, |
111 | }; |
112 | } |
113 | else { |
114 | $temp = { |
115 | prev_md5 => chr(0) x $self->{hash_size}, |
116 | return_next => 1, |
117 | }; |
118 | } |
119 | |
120 | return $self->traverse_index( $temp, $offset, 0 ); |
c3aafc14 |
121 | } |
122 | |
83371fe3 |
123 | sub delete_key { |
124 | my $self = shift; |
40956c06 |
125 | my ($trans_id, $offset, $key, $orig_key) = @_; |
83371fe3 |
126 | |
40956c06 |
127 | my $dig_key = $self->_apply_digest( $key ); |
83371fe3 |
128 | my $tag = $self->find_blist( $offset, $dig_key ) or return; |
129 | my $value = $self->get_bucket_value( $tag, $dig_key, $orig_key ); |
130 | $self->delete_bucket( $tag, $dig_key, $orig_key ); |
131 | return $value; |
132 | } |
133 | |
83371fe3 |
134 | sub write_value { |
135 | my $self = shift; |
40956c06 |
136 | my ($trans_id, $offset, $key, $value, $orig_key) = @_; |
83371fe3 |
137 | |
40956c06 |
138 | my $dig_key = $self->_apply_digest( $key ); |
83371fe3 |
139 | my $tag = $self->find_blist( $offset, $dig_key, { create => 1 } ); |
140 | return $self->add_bucket( $tag, $dig_key, $key, $value, undef, $orig_key ); |
141 | } |
142 | |
c3aafc14 |
143 | ################################################################################ |
144 | # |
145 | # Below here is the old code. It will be folded into the code above as it can. |
146 | # |
147 | ################################################################################ |
148 | |
612969fb |
149 | sub new { |
150 | my $class = shift; |
151 | my ($args) = @_; |
152 | |
153 | my $self = bless { |
86867f3a |
154 | long_size => 4, |
155 | long_pack => 'N', |
156 | data_size => 4, |
157 | data_pack => 'N', |
251dfd0e |
158 | |
86867f3a |
159 | digest => \&Digest::MD5::md5, |
c3aafc14 |
160 | hash_size => 16, # In bytes |
251dfd0e |
161 | |
81d16922 |
162 | ## |
c3aafc14 |
163 | # Number of buckets per blist before another level of indexing is |
e0098e7f |
164 | # done. Increase this value for slightly greater speed, but larger database |
d5d7c51d |
165 | # files. DO NOT decrease this value below 16, due to risk of recursive |
166 | # reindex overrun. |
81d16922 |
167 | ## |
612969fb |
168 | max_buckets => 16, |
460b1067 |
169 | |
83371fe3 |
170 | storage => undef, |
359a01ac |
171 | obj => undef, |
612969fb |
172 | }, $class; |
173 | |
e0098e7f |
174 | if ( defined $args->{pack_size} ) { |
175 | if ( lc $args->{pack_size} eq 'small' ) { |
176 | $args->{long_size} = 2; |
c9b6d0d8 |
177 | $args->{long_pack} = 'n'; |
e0098e7f |
178 | } |
179 | elsif ( lc $args->{pack_size} eq 'medium' ) { |
180 | $args->{long_size} = 4; |
181 | $args->{long_pack} = 'N'; |
182 | } |
183 | elsif ( lc $args->{pack_size} eq 'large' ) { |
184 | $args->{long_size} = 8; |
185 | $args->{long_pack} = 'Q'; |
186 | } |
187 | else { |
188 | die "Unknown pack_size value: '$args->{pack_size}'\n"; |
189 | } |
190 | } |
191 | |
fde3db1a |
192 | # Grab the parameters we want to use |
193 | foreach my $param ( keys %$self ) { |
194 | next unless exists $args->{$param}; |
3e9498a1 |
195 | $self->{$param} = $args->{$param}; |
fde3db1a |
196 | } |
359a01ac |
197 | Scalar::Util::weaken( $self->{obj} ) if $self->{obj}; |
fde3db1a |
198 | |
e0098e7f |
199 | if ( $self->{max_buckets} < 16 ) { |
200 | warn "Floor of max_buckets is 16. Setting it to 16 from '$self->{max_buckets}'\n"; |
201 | $self->{max_buckets} = 16; |
202 | } |
203 | |
260a80b4 |
204 | return $self; |
205 | } |
206 | |
83371fe3 |
207 | sub _storage { return $_[0]{storage} } |
460b1067 |
208 | |
40956c06 |
209 | sub _apply_digest { |
c3aafc14 |
210 | my $self = shift; |
211 | return $self->{digest}->(@_); |
212 | } |
213 | |
260a80b4 |
214 | sub calculate_sizes { |
215 | my $self = shift; |
216 | |
633df1fd |
217 | # The 2**8 here indicates the number of different characters in the |
218 | # current hashing algorithm |
28394a1a |
219 | #XXX Does this need to be updated with different hashing algorithms? |
ea2f6d67 |
220 | $self->{hash_chars_used} = (2**8); |
221 | $self->{index_size} = $self->{hash_chars_used} * $self->{long_size}; |
222 | |
223 | $self->{bucket_size} = $self->{hash_size} + $self->{long_size} * 2; |
e0098e7f |
224 | $self->{bucket_list_size} = $self->{max_buckets} * $self->{bucket_size}; |
612969fb |
225 | |
ea2f6d67 |
226 | $self->{key_size} = $self->{long_size} * 2; |
227 | $self->{keyloc_size} = $self->{max_buckets} * $self->{key_size}; |
228 | |
260a80b4 |
229 | return; |
1bf65be7 |
230 | } |
231 | |
fde3db1a |
232 | sub write_file_header { |
0d0f3d5d |
233 | my $self = shift; |
0d0f3d5d |
234 | |
83371fe3 |
235 | my $loc = $self->_storage->request_space( length( SIG_FILE ) + 33 ); |
0d0f3d5d |
236 | |
83371fe3 |
237 | $self->_storage->print_at( $loc, |
260a80b4 |
238 | SIG_FILE, |
460b1067 |
239 | SIG_HEADER, |
240 | pack('N', 1), # header version |
eff6a245 |
241 | pack('N', 24), # header size |
242 | pack('N4', 0, 0, 0, 0), # currently running transaction IDs |
c9b6d0d8 |
243 | pack('n', $self->{long_size}), |
260a80b4 |
244 | pack('A', $self->{long_pack}), |
c9b6d0d8 |
245 | pack('n', $self->{data_size}), |
260a80b4 |
246 | pack('A', $self->{data_pack}), |
c9b6d0d8 |
247 | pack('n', $self->{max_buckets}), |
260a80b4 |
248 | ); |
0d0f3d5d |
249 | |
83371fe3 |
250 | $self->_storage->set_transaction_offset( 13 ); |
20b7f047 |
251 | |
0d0f3d5d |
252 | return; |
253 | } |
254 | |
fde3db1a |
255 | sub read_file_header { |
e064ccd1 |
256 | my $self = shift; |
e064ccd1 |
257 | |
83371fe3 |
258 | my $buffer = $self->_storage->read_at( 0, length(SIG_FILE) + 9 ); |
7dcefff3 |
259 | return unless length($buffer); |
460b1067 |
260 | |
261 | my ($file_signature, $sig_header, $header_version, $size) = unpack( |
262 | 'A4 A N N', $buffer |
42f79e07 |
263 | ); |
e064ccd1 |
264 | |
460b1067 |
265 | unless ( $file_signature eq SIG_FILE ) { |
83371fe3 |
266 | $self->_storage->close; |
e96daec8 |
267 | $self->_throw_error( "Signature not found -- file is not a Deep DB" ); |
460b1067 |
268 | } |
260a80b4 |
269 | |
460b1067 |
270 | unless ( $sig_header eq SIG_HEADER ) { |
83371fe3 |
271 | $self->_storage->close; |
e96daec8 |
272 | $self->_throw_error( "Old file version found." ); |
460b1067 |
273 | } |
9b2370e0 |
274 | |
83371fe3 |
275 | my $buffer2 = $self->_storage->read_at( undef, $size ); |
eff6a245 |
276 | my ($a1, $a2, $a3, $a4, @values) = unpack( 'N4 n A n A n', $buffer2 ); |
15ba72cc |
277 | |
83371fe3 |
278 | $self->_storage->set_transaction_offset( 13 ); |
15ba72cc |
279 | |
460b1067 |
280 | if ( @values < 5 || grep { !defined } @values ) { |
83371fe3 |
281 | $self->_storage->close; |
e96daec8 |
282 | $self->_throw_error("Corrupted file - bad header"); |
e064ccd1 |
283 | } |
284 | |
460b1067 |
285 | #XXX Add warnings if values weren't set right |
286 | @{$self}{qw(long_size long_pack data_size data_pack max_buckets)} = @values; |
287 | |
7dcefff3 |
288 | return length($buffer) + length($buffer2); |
e064ccd1 |
289 | } |
290 | |
460b1067 |
291 | sub setup_fh { |
292 | my $self = shift; |
293 | my ($obj) = @_; |
70b55428 |
294 | |
7dcefff3 |
295 | # Need to remove use of $fh here |
83371fe3 |
296 | my $fh = $self->_storage->{fh}; |
6fde4ed2 |
297 | flock $fh, LOCK_EX; |
118ba343 |
298 | |
260a80b4 |
299 | #XXX The duplication of calculate_sizes needs to go away |
6fde4ed2 |
300 | unless ( $obj->{base_offset} ) { |
e96daec8 |
301 | my $bytes_read = $self->read_file_header; |
118ba343 |
302 | |
260a80b4 |
303 | $self->calculate_sizes; |
304 | |
118ba343 |
305 | ## |
fde3db1a |
306 | # File is empty -- write header and master index |
118ba343 |
307 | ## |
308 | if (!$bytes_read) { |
83371fe3 |
309 | $self->_storage->audit( "# Database created on" ); |
359a01ac |
310 | |
e96daec8 |
311 | $self->write_file_header; |
118ba343 |
312 | |
83371fe3 |
313 | $obj->{base_offset} = $self->_storage->request_space( |
22e20cce |
314 | $self->tag_size( $self->{index_size} ), |
315 | ); |
118ba343 |
316 | |
9e4f83a0 |
317 | $self->write_tag( |
e96daec8 |
318 | $obj->_base_offset, $obj->_type, |
f37c15ab |
319 | chr(0)x$self->{index_size}, |
118ba343 |
320 | ); |
321 | |
322 | # Flush the filehandle |
323 | my $old_fh = select $fh; |
324 | my $old_af = $|; $| = 1; $| = $old_af; |
325 | select $old_fh; |
326 | } |
327 | else { |
328 | $obj->{base_offset} = $bytes_read; |
329 | |
330 | ## |
fde3db1a |
331 | # Get our type from master index header |
118ba343 |
332 | ## |
359a01ac |
333 | my $tag = $self->load_tag($obj->_base_offset); |
334 | unless ( $tag ) { |
335 | flock $fh, LOCK_UN; |
336 | $self->_throw_error("Corrupted file, no master index record"); |
337 | } |
118ba343 |
338 | |
e96daec8 |
339 | unless ($obj->_type eq $tag->{signature}) { |
359a01ac |
340 | flock $fh, LOCK_UN; |
e96daec8 |
341 | $self->_throw_error("File type mismatch"); |
118ba343 |
342 | } |
343 | } |
118ba343 |
344 | } |
260a80b4 |
345 | else { |
346 | $self->calculate_sizes; |
347 | } |
e06824f8 |
348 | |
673464d9 |
349 | #XXX We have to make sure we don't mess up when autoflush isn't turned on |
83371fe3 |
350 | $self->_storage->set_inode; |
70b55428 |
351 | |
6fde4ed2 |
352 | flock $fh, LOCK_UN; |
353 | |
70b55428 |
354 | return 1; |
355 | } |
356 | |
16d1ad9b |
357 | sub tag_size { |
358 | my $self = shift; |
359 | my ($size) = @_; |
360 | return SIG_SIZE + $self->{data_size} + $size; |
361 | } |
362 | |
9e4f83a0 |
363 | sub write_tag { |
20f7b20c |
364 | ## |
365 | # Given offset, signature and content, create tag and write to disk |
366 | ## |
d4b1166e |
367 | my $self = shift; |
e96daec8 |
368 | my ($offset, $sig, $content) = @_; |
f37c15ab |
369 | my $size = length( $content ); |
20f7b20c |
370 | |
83371fe3 |
371 | $self->_storage->print_at( |
7dcefff3 |
372 | $offset, |
373 | $sig, pack($self->{data_pack}, $size), $content, |
374 | ); |
20f7b20c |
375 | |
f37c15ab |
376 | return unless defined $offset; |
377 | |
20f7b20c |
378 | return { |
379 | signature => $sig, |
72e315ac |
380 | #XXX Is this even used? |
86867f3a |
381 | size => $size, |
f5677eab |
382 | start => $offset, |
86867f3a |
383 | offset => $offset + SIG_SIZE + $self->{data_size}, |
f5677eab |
384 | content => $content, |
385 | is_new => 1, |
20f7b20c |
386 | }; |
d4b1166e |
387 | } |
388 | |
389 | sub load_tag { |
20f7b20c |
390 | ## |
391 | # Given offset, load single tag and return signature, size and data |
392 | ## |
d4b1166e |
393 | my $self = shift; |
e96daec8 |
394 | my ($offset) = @_; |
20f7b20c |
395 | |
83371fe3 |
396 | my $storage = $self->_storage; |
20f7b20c |
397 | |
86867f3a |
398 | my ($sig, $size) = unpack( |
399 | "A $self->{data_pack}", |
83371fe3 |
400 | $storage->read_at( $offset, SIG_SIZE + $self->{data_size} ), |
86867f3a |
401 | ); |
20f7b20c |
402 | |
403 | return { |
404 | signature => $sig, |
c3aafc14 |
405 | size => $size, #XXX Is this even used? |
fb451ba6 |
406 | start => $offset, |
86867f3a |
407 | offset => $offset + SIG_SIZE + $self->{data_size}, |
83371fe3 |
408 | content => $storage->read_at( undef, $size ), |
20f7b20c |
409 | }; |
d4b1166e |
410 | } |
411 | |
ea2f6d67 |
412 | sub find_keyloc { |
413 | my $self = shift; |
414 | my ($tag, $transaction_id) = @_; |
83371fe3 |
415 | $transaction_id = $self->_storage->transaction_id |
ea2f6d67 |
416 | unless defined $transaction_id; |
417 | |
418 | for ( my $i = 0; $i < $self->{max_buckets}; $i++ ) { |
419 | my ($loc, $trans_id, $is_deleted) = unpack( |
420 | "$self->{long_pack} C C", |
421 | substr( $tag->{content}, $i * $self->{key_size}, $self->{key_size} ), |
422 | ); |
423 | |
fb451ba6 |
424 | next if $loc != HEAD && $transaction_id != $trans_id; |
425 | return( $loc, $is_deleted, $i * $self->{key_size} ); |
ea2f6d67 |
426 | } |
427 | |
428 | return; |
429 | } |
430 | |
20f7b20c |
431 | sub add_bucket { |
432 | ## |
433 | # Adds one key/value pair to bucket list, given offset, MD5 digest of key, |
434 | # plain (undigested) key and value. |
435 | ## |
d4b1166e |
436 | my $self = shift; |
359a01ac |
437 | my ($tag, $md5, $plain_key, $value, $deleted, $orig_key) = @_; |
75be6413 |
438 | |
eea0d863 |
439 | # This verifies that only supported values will be stored. |
440 | { |
441 | my $r = Scalar::Util::reftype( $value ); |
eea0d863 |
442 | |
86867f3a |
443 | last if !defined $r; |
eea0d863 |
444 | last if $r eq 'HASH'; |
445 | last if $r eq 'ARRAY'; |
446 | |
e96daec8 |
447 | $self->_throw_error( |
86867f3a |
448 | "Storage of references of type '$r' is not supported." |
eea0d863 |
449 | ); |
450 | } |
451 | |
83371fe3 |
452 | my $storage = $self->_storage; |
20f7b20c |
453 | |
21838116 |
454 | #ACID - This is a mutation. Must only find the exact transaction |
ea2f6d67 |
455 | my ($keyloc, $offset) = $self->_find_in_buckets( $tag, $md5, 1 ); |
c9b6d0d8 |
456 | |
457 | my @transactions; |
83371fe3 |
458 | if ( $storage->transaction_id == 0 ) { |
459 | @transactions = $storage->current_transactions; |
c9b6d0d8 |
460 | } |
75be6413 |
461 | |
e96daec8 |
462 | # $self->_release_space( $size, $subloc ); |
f9c33187 |
463 | #XXX This needs updating to use _release_space |
ea2f6d67 |
464 | |
86867f3a |
465 | my $location; |
ea2f6d67 |
466 | my $size = $self->_length_needed( $value, $plain_key ); |
019404df |
467 | |
ea2f6d67 |
468 | # Updating a known md5 |
469 | if ( $keyloc ) { |
470 | my $keytag = $self->load_tag( $keyloc ); |
471 | my ($subloc, $is_deleted, $offset) = $self->find_keyloc( $keytag ); |
472 | |
13ff93d5 |
473 | if ( $subloc && !$is_deleted && @transactions ) { |
ea2f6d67 |
474 | my $old_value = $self->read_from_loc( $subloc, $orig_key ); |
475 | my $old_size = $self->_length_needed( $old_value, $plain_key ); |
476 | |
477 | for my $trans_id ( @transactions ) { |
478 | my ($loc, $is_deleted, $offset2) = $self->find_keyloc( $keytag, $trans_id ); |
479 | unless ($loc) { |
83371fe3 |
480 | my $location2 = $storage->request_space( $old_size ); |
481 | $storage->print_at( $keytag->{offset} + $offset2, |
ea2f6d67 |
482 | pack($self->{long_pack}, $location2 ), |
483 | pack( 'C C', $trans_id, 0 ), |
484 | ); |
c3aafc14 |
485 | $self->_write_value( $location2, $plain_key, $old_value, $orig_key ); |
ea2f6d67 |
486 | } |
487 | } |
75be6413 |
488 | } |
504185fb |
489 | |
83371fe3 |
490 | $location = $self->_storage->request_space( $size ); |
ea2f6d67 |
491 | #XXX This needs to be transactionally-aware in terms of which keytag->{offset} to use |
83371fe3 |
492 | $storage->print_at( $keytag->{offset} + $offset, |
ea2f6d67 |
493 | pack($self->{long_pack}, $location ), |
83371fe3 |
494 | pack( 'C C', $storage->transaction_id, 0 ), |
ea2f6d67 |
495 | ); |
75be6413 |
496 | } |
386bab6c |
497 | # Adding a new md5 |
ea2f6d67 |
498 | else { |
83371fe3 |
499 | my $keyloc = $storage->request_space( $self->tag_size( $self->{keyloc_size} ) ); |
386bab6c |
500 | |
ea2f6d67 |
501 | # The bucket fit into list |
502 | if ( defined $offset ) { |
83371fe3 |
503 | $storage->print_at( $tag->{offset} + $offset, |
ea2f6d67 |
504 | $md5, pack( $self->{long_pack}, $keyloc ), |
505 | ); |
506 | } |
507 | # If bucket didn't fit into list, split into a new index level |
508 | else { |
509 | $self->split_index( $tag, $md5, $keyloc ); |
510 | } |
511 | |
512 | my $keytag = $self->write_tag( |
513 | $keyloc, SIG_KEYS, chr(0)x$self->{keyloc_size}, |
019404df |
514 | ); |
c9b6d0d8 |
515 | |
83371fe3 |
516 | $location = $self->_storage->request_space( $size ); |
517 | $storage->print_at( $keytag->{offset}, |
ea2f6d67 |
518 | pack( $self->{long_pack}, $location ), |
83371fe3 |
519 | pack( 'C C', $storage->transaction_id, 0 ), |
ea2f6d67 |
520 | ); |
521 | |
522 | my $offset = 1; |
523 | for my $trans_id ( @transactions ) { |
83371fe3 |
524 | $storage->print_at( $keytag->{offset} + $self->{key_size} * $offset++, |
13ff93d5 |
525 | pack( $self->{long_pack}, 0 ), |
ea2f6d67 |
526 | pack( 'C C', $trans_id, 1 ), |
527 | ); |
c9b6d0d8 |
528 | } |
386bab6c |
529 | } |
20f7b20c |
530 | |
c3aafc14 |
531 | $self->_write_value( $location, $plain_key, $value, $orig_key ); |
d5d7c51d |
532 | |
86867f3a |
533 | return 1; |
d5d7c51d |
534 | } |
535 | |
c3aafc14 |
536 | sub _write_value { |
d5d7c51d |
537 | my $self = shift; |
129ea236 |
538 | my ($key_loc, $location, $key, $value, $orig_key) = @_; |
d5d7c51d |
539 | |
83371fe3 |
540 | my $storage = $self->_storage; |
d5d7c51d |
541 | |
9d4fa373 |
542 | my $dbm_deep_obj = _get_dbm_object( $value ); |
83371fe3 |
543 | if ( $dbm_deep_obj && $dbm_deep_obj->_storage ne $storage ) { |
e96daec8 |
544 | $self->_throw_error( "Cannot cross-reference. Use export() instead" ); |
9d4fa373 |
545 | } |
d5d7c51d |
546 | |
20f7b20c |
547 | ## |
d5d7c51d |
548 | # Write signature based on content type, set content length and write |
549 | # actual value. |
20f7b20c |
550 | ## |
9d4fa373 |
551 | my $r = Scalar::Util::reftype( $value ) || ''; |
552 | if ( $dbm_deep_obj ) { |
7dcefff3 |
553 | $self->write_tag( $location, SIG_INTERNAL,pack($self->{long_pack}, $dbm_deep_obj->_base_offset) ); |
f37c15ab |
554 | } |
555 | elsif ($r eq 'HASH') { |
9d4fa373 |
556 | if ( !$dbm_deep_obj && tied %{$value} ) { |
e96daec8 |
557 | $self->_throw_error( "Cannot store something that is tied" ); |
019ab3a1 |
558 | } |
7dcefff3 |
559 | $self->write_tag( $location, SIG_HASH, chr(0)x$self->{index_size} ); |
f37c15ab |
560 | } |
561 | elsif ($r eq 'ARRAY') { |
9d4fa373 |
562 | if ( !$dbm_deep_obj && tied @{$value} ) { |
e96daec8 |
563 | $self->_throw_error( "Cannot store something that is tied" ); |
019ab3a1 |
564 | } |
7dcefff3 |
565 | $self->write_tag( $location, SIG_ARRAY, chr(0)x$self->{index_size} ); |
f37c15ab |
566 | } |
567 | elsif (!defined($value)) { |
7dcefff3 |
568 | $self->write_tag( $location, SIG_NULL, '' ); |
d5d7c51d |
569 | } |
570 | else { |
7dcefff3 |
571 | $self->write_tag( $location, SIG_DATA, $value ); |
d5d7c51d |
572 | } |
20f7b20c |
573 | |
d5d7c51d |
574 | ## |
575 | # Plain key is stored AFTER value, as keys are typically fetched less often. |
576 | ## |
83371fe3 |
577 | $storage->print_at( undef, pack($self->{data_pack}, length($key)) . $key ); |
20f7b20c |
578 | |
9a187d8c |
579 | # Internal references don't care about autobless |
9d4fa373 |
580 | return 1 if $dbm_deep_obj; |
9a187d8c |
581 | |
d5d7c51d |
582 | ## |
583 | # If value is blessed, preserve class name |
584 | ## |
83371fe3 |
585 | if ( $storage->{autobless} ) { |
633df1fd |
586 | if ( defined( my $c = Scalar::Util::blessed($value) ) ) { |
83371fe3 |
587 | $storage->print_at( undef, chr(1), pack($self->{data_pack}, length($c)) . $c ); |
20f7b20c |
588 | } |
d5d7c51d |
589 | else { |
83371fe3 |
590 | $storage->print_at( undef, chr(0) ); |
20f7b20c |
591 | } |
d5d7c51d |
592 | } |
20f7b20c |
593 | |
d5d7c51d |
594 | ## |
56ec4340 |
595 | # Tie the passed in reference so that changes to it are reflected in the |
596 | # datafile. The use of $location as the base_offset will act as the |
597 | # the linkage between parent and child. |
598 | # |
599 | # The overall assignment is a hack around the fact that just tying doesn't |
600 | # store the values. This may not be the wrong thing to do. |
d5d7c51d |
601 | ## |
9d4fa373 |
602 | if ($r eq 'HASH') { |
603 | my %x = %$value; |
604 | tie %$value, 'DBM::Deep', { |
129ea236 |
605 | base_offset => $key_loc, |
83371fe3 |
606 | storage => $storage, |
359a01ac |
607 | parent => $self->{obj}, |
608 | parent_key => $orig_key, |
9d4fa373 |
609 | }; |
610 | %$value = %x; |
bd01f6ec |
611 | bless $value, 'DBM::Deep::Hash' unless Scalar::Util::blessed( $value ); |
9d4fa373 |
612 | } |
613 | elsif ($r eq 'ARRAY') { |
614 | my @x = @$value; |
615 | tie @$value, 'DBM::Deep', { |
129ea236 |
616 | base_offset => $key_loc, |
83371fe3 |
617 | storage => $storage, |
359a01ac |
618 | parent => $self->{obj}, |
619 | parent_key => $orig_key, |
9d4fa373 |
620 | }; |
621 | @$value = @x; |
bd01f6ec |
622 | bless $value, 'DBM::Deep::Array' unless Scalar::Util::blessed( $value ); |
20f7b20c |
623 | } |
d4b1166e |
624 | |
d5d7c51d |
625 | return 1; |
d4b1166e |
626 | } |
627 | |
75be6413 |
628 | sub split_index { |
629 | my $self = shift; |
ea2f6d67 |
630 | my ($tag, $md5, $keyloc) = @_; |
75be6413 |
631 | |
83371fe3 |
632 | my $storage = $self->_storage; |
21838116 |
633 | |
83371fe3 |
634 | my $loc = $storage->request_space( |
e96daec8 |
635 | $self->tag_size( $self->{index_size} ), |
16d1ad9b |
636 | ); |
637 | |
83371fe3 |
638 | $storage->print_at( $tag->{ref_loc}, pack($self->{long_pack}, $loc) ); |
75be6413 |
639 | |
9e4f83a0 |
640 | my $index_tag = $self->write_tag( |
e96daec8 |
641 | $loc, SIG_INDEX, |
f37c15ab |
642 | chr(0)x$self->{index_size}, |
75be6413 |
643 | ); |
644 | |
7b1e1aa1 |
645 | my $keys = $tag->{content} |
ea2f6d67 |
646 | . $md5 . pack($self->{long_pack}, $keyloc); |
75be6413 |
647 | |
f9c33187 |
648 | my @newloc = (); |
75be6413 |
649 | BUCKET: |
633df1fd |
650 | # The <= here is deliberate - we have max_buckets+1 keys to iterate |
651 | # through, unlike every other loop that uses max_buckets as a stop. |
75be6413 |
652 | for (my $i = 0; $i <= $self->{max_buckets}; $i++) { |
ea2f6d67 |
653 | my ($key, $old_subloc) = $self->_get_key_subloc( $keys, $i ); |
75be6413 |
654 | |
f9c33187 |
655 | die "[INTERNAL ERROR]: No key in split_index()\n" unless $key; |
656 | die "[INTERNAL ERROR]: No subloc in split_index()\n" unless $old_subloc; |
75be6413 |
657 | |
75be6413 |
658 | my $num = ord(substr($key, $tag->{ch} + 1, 1)); |
659 | |
f9c33187 |
660 | if ($newloc[$num]) { |
83371fe3 |
661 | my $subkeys = $storage->read_at( $newloc[$num], $self->{bucket_list_size} ); |
75be6413 |
662 | |
f9c33187 |
663 | # This is looking for the first empty spot |
ea2f6d67 |
664 | my ($subloc, $offset) = $self->_find_in_buckets( |
f9c33187 |
665 | { content => $subkeys }, '', |
7b1e1aa1 |
666 | ); |
75be6413 |
667 | |
83371fe3 |
668 | $storage->print_at( |
633df1fd |
669 | $newloc[$num] + $offset, |
670 | $key, pack($self->{long_pack}, $old_subloc), |
671 | ); |
7b1e1aa1 |
672 | |
673 | next; |
75be6413 |
674 | } |
75be6413 |
675 | |
83371fe3 |
676 | my $loc = $storage->request_space( |
e96daec8 |
677 | $self->tag_size( $self->{bucket_list_size} ), |
7b1e1aa1 |
678 | ); |
2603d86e |
679 | |
83371fe3 |
680 | $storage->print_at( |
019404df |
681 | $index_tag->{offset} + ($num * $self->{long_size}), |
682 | pack($self->{long_pack}, $loc), |
683 | ); |
75be6413 |
684 | |
7b1e1aa1 |
685 | my $blist_tag = $self->write_tag( |
e96daec8 |
686 | $loc, SIG_BLIST, |
7b1e1aa1 |
687 | chr(0)x$self->{bucket_list_size}, |
688 | ); |
689 | |
83371fe3 |
690 | $storage->print_at( $blist_tag->{offset}, $key . pack($self->{long_pack}, $old_subloc) ); |
7b1e1aa1 |
691 | |
f9c33187 |
692 | $newloc[$num] = $blist_tag->{offset}; |
7b1e1aa1 |
693 | } |
694 | |
695 | $self->_release_space( |
e96daec8 |
696 | $self->tag_size( $self->{bucket_list_size} ), |
fb451ba6 |
697 | $tag->{start}, |
7b1e1aa1 |
698 | ); |
75be6413 |
699 | |
ea2f6d67 |
700 | return 1; |
75be6413 |
701 | } |
702 | |
8db25060 |
703 | sub read_from_loc { |
704 | my $self = shift; |
129ea236 |
705 | my ($key_loc, $subloc, $orig_key) = @_; |
8db25060 |
706 | |
83371fe3 |
707 | my $storage = $self->_storage; |
8db25060 |
708 | |
83371fe3 |
709 | my $signature = $storage->read_at( $subloc, SIG_SIZE ); |
8db25060 |
710 | |
711 | ## |
712 | # If value is a hash or array, return new DBM::Deep object with correct offset |
713 | ## |
714 | if (($signature eq SIG_HASH) || ($signature eq SIG_ARRAY)) { |
c3aafc14 |
715 | #XXX This needs to be a singleton |
bd01f6ec |
716 | # my $new_obj; |
717 | # my $is_autobless; |
718 | # if ( $signature eq SIG_HASH ) { |
719 | # $new_obj = {}; |
720 | # tie %$new_obj, 'DBM::Deep', { |
721 | # base_offset => $subloc, |
83371fe3 |
722 | # storage => $self->_storage, |
bd01f6ec |
723 | # parent => $self->{obj}, |
724 | # parent_key => $orig_key, |
725 | # }; |
83371fe3 |
726 | # $is_autobless = tied(%$new_obj)->_storage->{autobless}; |
bd01f6ec |
727 | # } |
728 | # else { |
729 | # $new_obj = []; |
730 | # tie @$new_obj, 'DBM::Deep', { |
731 | # base_offset => $subloc, |
83371fe3 |
732 | # storage => $self->_storage, |
bd01f6ec |
733 | # parent => $self->{obj}, |
734 | # parent_key => $orig_key, |
735 | # }; |
83371fe3 |
736 | # $is_autobless = tied(@$new_obj)->_storage->{autobless}; |
bd01f6ec |
737 | # } |
738 | # |
739 | # if ($is_autobless) { |
740 | |
685e40f1 |
741 | my $new_obj = DBM::Deep->new({ |
359a01ac |
742 | type => $signature, |
129ea236 |
743 | base_offset => $key_loc, |
83371fe3 |
744 | storage => $self->_storage, |
359a01ac |
745 | parent => $self->{obj}, |
746 | parent_key => $orig_key, |
685e40f1 |
747 | }); |
8db25060 |
748 | |
83371fe3 |
749 | if ($new_obj->_storage->{autobless}) { |
8db25060 |
750 | ## |
751 | # Skip over value and plain key to see if object needs |
752 | # to be re-blessed |
753 | ## |
83371fe3 |
754 | $storage->increment_pointer( $self->{data_size} + $self->{index_size} ); |
8db25060 |
755 | |
83371fe3 |
756 | my $size = $storage->read_at( undef, $self->{data_size} ); |
c6ea6b6c |
757 | $size = unpack($self->{data_pack}, $size); |
83371fe3 |
758 | if ($size) { $storage->increment_pointer( $size ); } |
8db25060 |
759 | |
83371fe3 |
760 | my $bless_bit = $storage->read_at( undef, 1 ); |
86867f3a |
761 | if ( ord($bless_bit) ) { |
762 | my $size = unpack( |
763 | $self->{data_pack}, |
83371fe3 |
764 | $storage->read_at( undef, $self->{data_size} ), |
86867f3a |
765 | ); |
7dcefff3 |
766 | |
86867f3a |
767 | if ( $size ) { |
83371fe3 |
768 | $new_obj = bless $new_obj, $storage->read_at( undef, $size ); |
86867f3a |
769 | } |
8db25060 |
770 | } |
771 | } |
772 | |
685e40f1 |
773 | return $new_obj; |
8db25060 |
774 | } |
775 | elsif ( $signature eq SIG_INTERNAL ) { |
83371fe3 |
776 | my $size = $storage->read_at( undef, $self->{data_size} ); |
8db25060 |
777 | $size = unpack($self->{data_pack}, $size); |
778 | |
779 | if ( $size ) { |
83371fe3 |
780 | my $new_loc = $storage->read_at( undef, $size ); |
7dcefff3 |
781 | $new_loc = unpack( $self->{long_pack}, $new_loc ); |
129ea236 |
782 | return $self->read_from_loc( $key_loc, $new_loc, $orig_key ); |
8db25060 |
783 | } |
784 | else { |
785 | return; |
786 | } |
787 | } |
788 | ## |
789 | # Otherwise return actual value |
790 | ## |
460b1067 |
791 | elsif ( $signature eq SIG_DATA ) { |
83371fe3 |
792 | my $size = $storage->read_at( undef, $self->{data_size} ); |
8db25060 |
793 | $size = unpack($self->{data_pack}, $size); |
794 | |
83371fe3 |
795 | my $value = $size ? $storage->read_at( undef, $size ) : ''; |
8db25060 |
796 | return $value; |
797 | } |
798 | |
799 | ## |
800 | # Key exists, but content is null |
801 | ## |
802 | return; |
803 | } |
804 | |
9020ee8c |
805 | sub get_bucket_value { |
beac1dff |
806 | ## |
807 | # Fetch single value given tag and MD5 digested key. |
808 | ## |
809 | my $self = shift; |
359a01ac |
810 | my ($tag, $md5, $orig_key) = @_; |
9020ee8c |
811 | |
21838116 |
812 | #ACID - This is a read. Can find exact or HEAD |
ea2f6d67 |
813 | my ($keyloc, $offset) = $self->_find_in_buckets( $tag, $md5 ); |
94e8af14 |
814 | |
ea2f6d67 |
815 | if ( !$keyloc ) { |
94e8af14 |
816 | #XXX Need to use real key |
ea2f6d67 |
817 | # $self->add_bucket( $tag, $md5, $orig_key, undef, $orig_key ); |
94e8af14 |
818 | # return; |
819 | } |
ea2f6d67 |
820 | # elsif ( !$is_deleted ) { |
821 | else { |
822 | my $keytag = $self->load_tag( $keyloc ); |
823 | my ($subloc, $is_deleted) = $self->find_keyloc( $keytag ); |
13ff93d5 |
824 | if (!$subloc && !$is_deleted) { |
ea2f6d67 |
825 | ($subloc, $is_deleted) = $self->find_keyloc( $keytag, 0 ); |
826 | } |
827 | if ( $subloc && !$is_deleted ) { |
828 | return $self->read_from_loc( $subloc, $orig_key ); |
829 | } |
386bab6c |
830 | } |
94e8af14 |
831 | |
beac1dff |
832 | return; |
9020ee8c |
833 | } |
ab0e4957 |
834 | |
835 | sub delete_bucket { |
beac1dff |
836 | ## |
837 | # Delete single key/value pair given tag and MD5 digested key. |
838 | ## |
839 | my $self = shift; |
a97c8f67 |
840 | my ($tag, $md5, $orig_key) = @_; |
ab0e4957 |
841 | |
22e20cce |
842 | #ACID - Although this is a mutation, we must find any transaction. |
843 | # This is because we need to mark something as deleted that is in the HEAD. |
ea2f6d67 |
844 | my ($keyloc, $offset) = $self->_find_in_buckets( $tag, $md5 ); |
633df1fd |
845 | |
ea2f6d67 |
846 | return if !$keyloc; |
633df1fd |
847 | |
83371fe3 |
848 | my $storage = $self->_storage; |
633df1fd |
849 | |
850 | my @transactions; |
83371fe3 |
851 | if ( $storage->transaction_id == 0 ) { |
852 | @transactions = $storage->current_transactions; |
633df1fd |
853 | } |
854 | |
83371fe3 |
855 | if ( $storage->transaction_id == 0 ) { |
ea2f6d67 |
856 | my $keytag = $self->load_tag( $keyloc ); |
7a960a12 |
857 | |
ea2f6d67 |
858 | my ($subloc, $is_deleted, $offset) = $self->find_keyloc( $keytag ); |
7a960a12 |
859 | return if !$subloc || $is_deleted; |
860 | |
633df1fd |
861 | my $value = $self->read_from_loc( $subloc, $orig_key ); |
862 | |
ea2f6d67 |
863 | my $size = $self->_length_needed( $value, $orig_key ); |
864 | |
865 | for my $trans_id ( @transactions ) { |
866 | my ($loc, $is_deleted, $offset2) = $self->find_keyloc( $keytag, $trans_id ); |
867 | unless ($loc) { |
83371fe3 |
868 | my $location2 = $storage->request_space( $size ); |
869 | $storage->print_at( $keytag->{offset} + $offset2, |
ea2f6d67 |
870 | pack($self->{long_pack}, $location2 ), |
871 | pack( 'C C', $trans_id, 0 ), |
872 | ); |
c3aafc14 |
873 | $self->_write_value( $location2, $orig_key, $value, $orig_key ); |
ea2f6d67 |
874 | } |
633df1fd |
875 | } |
876 | |
ea2f6d67 |
877 | $keytag = $self->load_tag( $keyloc ); |
878 | ($subloc, $is_deleted, $offset) = $self->find_keyloc( $keytag ); |
83371fe3 |
879 | $storage->print_at( $keytag->{offset} + $offset, |
ea2f6d67 |
880 | substr( $keytag->{content}, $offset + $self->{key_size} ), |
881 | chr(0) x $self->{key_size}, |
019404df |
882 | ); |
386bab6c |
883 | } |
633df1fd |
884 | else { |
ea2f6d67 |
885 | my $keytag = $self->load_tag( $keyloc ); |
7a960a12 |
886 | |
ea2f6d67 |
887 | my ($subloc, $is_deleted, $offset) = $self->find_keyloc( $keytag ); |
7a960a12 |
888 | |
83371fe3 |
889 | $storage->print_at( $keytag->{offset} + $offset, |
13ff93d5 |
890 | pack($self->{long_pack}, 0 ), |
83371fe3 |
891 | pack( 'C C', $storage->transaction_id, 1 ), |
ea2f6d67 |
892 | ); |
633df1fd |
893 | } |
894 | |
895 | return 1; |
ab0e4957 |
896 | } |
897 | |
912d50b1 |
898 | sub bucket_exists { |
beac1dff |
899 | ## |
900 | # Check existence of single key given tag and MD5 digested key. |
901 | ## |
902 | my $self = shift; |
e96daec8 |
903 | my ($tag, $md5) = @_; |
912d50b1 |
904 | |
21838116 |
905 | #ACID - This is a read. Can find exact or HEAD |
ea2f6d67 |
906 | my ($keyloc) = $self->_find_in_buckets( $tag, $md5 ); |
907 | my $keytag = $self->load_tag( $keyloc ); |
908 | my ($subloc, $is_deleted, $offset) = $self->find_keyloc( $keytag ); |
13ff93d5 |
909 | if ( !$subloc && !$is_deleted ) { |
ea2f6d67 |
910 | ($subloc, $is_deleted, $offset) = $self->find_keyloc( $keytag, 0 ); |
911 | } |
c9b6d0d8 |
912 | return ($subloc && !$is_deleted) && 1; |
912d50b1 |
913 | } |
914 | |
72e315ac |
915 | sub find_blist { |
beac1dff |
916 | ## |
917 | # Locate offset for bucket list, given digested key |
918 | ## |
919 | my $self = shift; |
e96daec8 |
920 | my ($offset, $md5, $args) = @_; |
d0b74c17 |
921 | $args = {} unless $args; |
922 | |
beac1dff |
923 | ## |
924 | # Locate offset for bucket list using digest index system |
925 | ## |
e96daec8 |
926 | my $tag = $self->load_tag( $offset ) |
927 | or $self->_throw_error( "INTERNAL ERROR - Cannot find tag" ); |
d0b74c17 |
928 | |
fb451ba6 |
929 | #XXX What happens when $ch >= $self->{hash_size} ?? |
930 | for (my $ch = 0; $tag->{signature} ne SIG_BLIST; $ch++) { |
d0b74c17 |
931 | my $num = ord substr($md5, $ch, 1); |
932 | |
933 | my $ref_loc = $tag->{offset} + ($num * $self->{long_size}); |
e96daec8 |
934 | $tag = $self->index_lookup( $tag, $num ); |
d0b74c17 |
935 | |
936 | if (!$tag) { |
29b01632 |
937 | return if !$args->{create}; |
d0b74c17 |
938 | |
83371fe3 |
939 | my $loc = $self->_storage->request_space( |
e96daec8 |
940 | $self->tag_size( $self->{bucket_list_size} ), |
16d1ad9b |
941 | ); |
942 | |
83371fe3 |
943 | $self->_storage->print_at( $ref_loc, pack($self->{long_pack}, $loc) ); |
d0b74c17 |
944 | |
9e4f83a0 |
945 | $tag = $self->write_tag( |
e96daec8 |
946 | $loc, SIG_BLIST, |
f37c15ab |
947 | chr(0)x$self->{bucket_list_size}, |
d5d7c51d |
948 | ); |
949 | |
950 | $tag->{ref_loc} = $ref_loc; |
951 | $tag->{ch} = $ch; |
952 | |
953 | last; |
d0b74c17 |
954 | } |
955 | |
fb451ba6 |
956 | $tag->{ch} = $ch; |
d0b74c17 |
957 | $tag->{ref_loc} = $ref_loc; |
beac1dff |
958 | } |
d0b74c17 |
959 | |
beac1dff |
960 | return $tag; |
6736c116 |
961 | } |
962 | |
d0b74c17 |
963 | sub index_lookup { |
964 | ## |
965 | # Given index tag, lookup single entry in index and return . |
966 | ## |
967 | my $self = shift; |
e96daec8 |
968 | my ($tag, $index) = @_; |
d0b74c17 |
969 | |
970 | my $location = unpack( |
971 | $self->{long_pack}, |
972 | substr( |
973 | $tag->{content}, |
974 | $index * $self->{long_size}, |
975 | $self->{long_size}, |
976 | ), |
977 | ); |
978 | |
979 | if (!$location) { return; } |
980 | |
e96daec8 |
981 | return $self->load_tag( $location ); |
d0b74c17 |
982 | } |
983 | |
6736c116 |
984 | sub traverse_index { |
beac1dff |
985 | ## |
986 | # Scan index and recursively step into deeper levels, looking for next key. |
987 | ## |
6736c116 |
988 | my $self = shift; |
ea2f6d67 |
989 | my ($xxxx, $offset, $ch, $force_return_next) = @_; |
d0b74c17 |
990 | |
e96daec8 |
991 | my $tag = $self->load_tag( $offset ); |
6736c116 |
992 | |
8db25060 |
993 | if ($tag->{signature} ne SIG_BLIST) { |
ea2f6d67 |
994 | my $start = $xxxx->{return_next} ? 0 : ord(substr($xxxx->{prev_md5}, $ch, 1)); |
d0b74c17 |
995 | |
ea2f6d67 |
996 | for (my $idx = $start; $idx < $self->{hash_chars_used}; $idx++) { |
e5fc7e69 |
997 | my $subloc = unpack( |
998 | $self->{long_pack}, |
e06824f8 |
999 | substr( |
ea2f6d67 |
1000 | $tag->{content}, |
e06824f8 |
1001 | $idx * $self->{long_size}, |
1002 | $self->{long_size}, |
1003 | ), |
e5fc7e69 |
1004 | ); |
1005 | |
beac1dff |
1006 | if ($subloc) { |
e5fc7e69 |
1007 | my $result = $self->traverse_index( |
ea2f6d67 |
1008 | $xxxx, $subloc, $ch + 1, $force_return_next, |
e5fc7e69 |
1009 | ); |
1010 | |
ea2f6d67 |
1011 | if (defined $result) { return $result; } |
beac1dff |
1012 | } |
1013 | } # index loop |
d0b74c17 |
1014 | |
ea2f6d67 |
1015 | $xxxx->{return_next} = 1; |
42717e46 |
1016 | } |
1017 | # This is the bucket list |
e5fc7e69 |
1018 | else { |
beac1dff |
1019 | my $keys = $tag->{content}; |
ea2f6d67 |
1020 | if ($force_return_next) { $xxxx->{return_next} = 1; } |
d0b74c17 |
1021 | |
beac1dff |
1022 | ## |
1023 | # Iterate through buckets, looking for a key match |
1024 | ## |
83371fe3 |
1025 | my $transaction_id = $self->_storage->transaction_id; |
8db25060 |
1026 | for (my $i = 0; $i < $self->{max_buckets}; $i++) { |
ea2f6d67 |
1027 | my ($key, $keyloc) = $self->_get_key_subloc( $keys, $i ); |
d0b74c17 |
1028 | |
8db25060 |
1029 | # End of bucket list -- return to outer loop |
ea2f6d67 |
1030 | if (!$keyloc) { |
1031 | $xxxx->{return_next} = 1; |
beac1dff |
1032 | last; |
1033 | } |
8db25060 |
1034 | # Located previous key -- return next one found |
ea2f6d67 |
1035 | elsif ($key eq $xxxx->{prev_md5}) { |
1036 | $xxxx->{return_next} = 1; |
beac1dff |
1037 | next; |
1038 | } |
8db25060 |
1039 | # Seek to bucket location and skip over signature |
ea2f6d67 |
1040 | elsif ($xxxx->{return_next}) { |
83371fe3 |
1041 | my $storage = $self->_storage; |
d0b74c17 |
1042 | |
ea2f6d67 |
1043 | my $keytag = $self->load_tag( $keyloc ); |
1044 | my ($subloc, $is_deleted) = $self->find_keyloc( $keytag ); |
13ff93d5 |
1045 | if ( $subloc == 0 && !$is_deleted ) { |
ea2f6d67 |
1046 | ($subloc, $is_deleted) = $self->find_keyloc( $keytag, 0 ); |
1047 | } |
1048 | next if $is_deleted; |
1049 | |
beac1dff |
1050 | # Skip over value to get to plain key |
83371fe3 |
1051 | my $sig = $storage->read_at( $subloc, SIG_SIZE ); |
8db25060 |
1052 | |
83371fe3 |
1053 | my $size = $storage->read_at( undef, $self->{data_size} ); |
e5fc7e69 |
1054 | $size = unpack($self->{data_pack}, $size); |
83371fe3 |
1055 | if ($size) { $storage->increment_pointer( $size ); } |
d0b74c17 |
1056 | |
beac1dff |
1057 | # Read in plain key and return as scalar |
83371fe3 |
1058 | $size = $storage->read_at( undef, $self->{data_size} ); |
e5fc7e69 |
1059 | $size = unpack($self->{data_pack}, $size); |
86867f3a |
1060 | |
7dcefff3 |
1061 | my $plain_key; |
83371fe3 |
1062 | if ($size) { $plain_key = $storage->read_at( undef, $size); } |
beac1dff |
1063 | return $plain_key; |
1064 | } |
8db25060 |
1065 | } |
d0b74c17 |
1066 | |
ea2f6d67 |
1067 | $xxxx->{return_next} = 1; |
42717e46 |
1068 | } |
d0b74c17 |
1069 | |
beac1dff |
1070 | return; |
6736c116 |
1071 | } |
1072 | |
75be6413 |
1073 | # Utilities |
1074 | |
9cec1360 |
1075 | sub _get_key_subloc { |
75be6413 |
1076 | my $self = shift; |
1077 | my ($keys, $idx) = @_; |
1078 | |
ea2f6d67 |
1079 | return unpack( |
28394a1a |
1080 | # This is 'a', not 'A'. Please read the pack() documentation for the |
1081 | # difference between the two and why it's important. |
ea2f6d67 |
1082 | "a$self->{hash_size} $self->{long_pack}", |
75be6413 |
1083 | substr( |
1084 | $keys, |
9cec1360 |
1085 | ($idx * $self->{bucket_size}), |
1086 | $self->{bucket_size}, |
75be6413 |
1087 | ), |
1088 | ); |
75be6413 |
1089 | } |
1090 | |
d608b06e |
1091 | sub _find_in_buckets { |
1092 | my $self = shift; |
ea2f6d67 |
1093 | my ($tag, $md5) = @_; |
21838116 |
1094 | |
d608b06e |
1095 | BUCKET: |
1096 | for ( my $i = 0; $i < $self->{max_buckets}; $i++ ) { |
ea2f6d67 |
1097 | my ($key, $subloc) = $self->_get_key_subloc( |
9a187d8c |
1098 | $tag->{content}, $i, |
1099 | ); |
d608b06e |
1100 | |
fb451ba6 |
1101 | next BUCKET if $subloc && $key ne $md5; |
1102 | return( $subloc, $i * $self->{bucket_size} ); |
d608b06e |
1103 | } |
1104 | |
1105 | return; |
1106 | } |
1107 | |
994ccd8e |
1108 | sub _release_space { |
1109 | my $self = shift; |
e96daec8 |
1110 | my ($size, $loc) = @_; |
994ccd8e |
1111 | |
7b1e1aa1 |
1112 | my $next_loc = 0; |
1113 | |
83371fe3 |
1114 | $self->_storage->print_at( $loc, |
019404df |
1115 | SIG_FREE, |
1116 | pack($self->{long_pack}, $size ), |
1117 | pack($self->{long_pack}, $next_loc ), |
7b1e1aa1 |
1118 | ); |
1119 | |
994ccd8e |
1120 | return; |
1121 | } |
1122 | |
e96daec8 |
1123 | sub _throw_error { |
1124 | die "DBM::Deep: $_[1]\n"; |
1125 | } |
1126 | |
86867f3a |
1127 | sub _get_dbm_object { |
1128 | my $item = shift; |
1129 | |
1130 | my $obj = eval { |
1131 | local $SIG{__DIE__}; |
1132 | if ($item->isa( 'DBM::Deep' )) { |
1133 | return $item; |
1134 | } |
1135 | return; |
1136 | }; |
1137 | return $obj if $obj; |
1138 | |
1139 | my $r = Scalar::Util::reftype( $item ) || ''; |
1140 | if ( $r eq 'HASH' ) { |
1141 | my $obj = eval { |
1142 | local $SIG{__DIE__}; |
1143 | my $obj = tied(%$item); |
1144 | if ($obj->isa( 'DBM::Deep' )) { |
1145 | return $obj; |
1146 | } |
1147 | return; |
1148 | }; |
1149 | return $obj if $obj; |
1150 | } |
1151 | elsif ( $r eq 'ARRAY' ) { |
1152 | my $obj = eval { |
1153 | local $SIG{__DIE__}; |
1154 | my $obj = tied(@$item); |
1155 | if ($obj->isa( 'DBM::Deep' )) { |
1156 | return $obj; |
1157 | } |
1158 | return; |
1159 | }; |
1160 | return $obj if $obj; |
1161 | } |
1162 | |
1163 | return; |
1164 | } |
1165 | |
1166 | sub _length_needed { |
1167 | my $self = shift; |
1168 | my ($value, $key) = @_; |
1169 | |
1170 | my $is_dbm_deep = eval { |
1171 | local $SIG{'__DIE__'}; |
1172 | $value->isa( 'DBM::Deep' ); |
1173 | }; |
1174 | |
1175 | my $len = SIG_SIZE |
1176 | + $self->{data_size} # size for value |
1177 | + $self->{data_size} # size for key |
1178 | + length( $key ); # length of key |
1179 | |
83371fe3 |
1180 | if ( $is_dbm_deep && $value->_storage eq $self->_storage ) { |
86867f3a |
1181 | # long_size is for the internal reference |
1182 | return $len + $self->{long_size}; |
1183 | } |
1184 | |
83371fe3 |
1185 | if ( $self->_storage->{autobless} ) { |
86867f3a |
1186 | # This is for the bit saying whether or not this thing is blessed. |
1187 | $len += 1; |
1188 | } |
1189 | |
1190 | my $r = Scalar::Util::reftype( $value ) || ''; |
1191 | unless ( $r eq 'HASH' || $r eq 'ARRAY' ) { |
1192 | if ( defined $value ) { |
1193 | $len += length( $value ); |
1194 | } |
1195 | return $len; |
1196 | } |
1197 | |
1198 | $len += $self->{index_size}; |
1199 | |
1200 | # if autobless is enabled, must also take into consideration |
1201 | # the class name as it is stored after the key. |
83371fe3 |
1202 | if ( $self->_storage->{autobless} ) { |
86867f3a |
1203 | my $c = Scalar::Util::blessed($value); |
1204 | if ( defined $c && !$is_dbm_deep ) { |
1205 | $len += $self->{data_size} + length($c); |
1206 | } |
1207 | } |
1208 | |
1209 | return $len; |
1210 | } |
1211 | |
a20d9a3f |
1212 | 1; |
1213 | __END__ |