Class: Ole::Storage::AllocationTable

Inherits:
Object
  • Object
show all
Defined in:
lib/ole/storage.rb

Overview

AllocationTable‘s hold the chains corresponding to files. Given an initial index, AllocationTable#chain follows the chain, returning the blocks that make up that file.

There are 2 allocation tables, the bbat, and sbat, for big and small blocks respectively. The block chain should be loaded using either Storage#read_big_blocks or Storage#read_small_blocks as appropriate.

Whether or not big or small blocks are used for a file depends on whether its size is over the Header#threshold level.

An Ole::Storage document is serialized as a series of directory objects, which are stored in blocks throughout the file. The blocks are either big or small, and are accessed using the AllocationTable.

The bbat allocation table’s data is stored in the spare room in the header block, and in extra blocks throughout the file as referenced by the meta bat. That chain is linear, as there is no higher level table.

Direct Known Subclasses

Big, Small

Defined Under Namespace

Classes: Big, Small

Constant Summary collapse

AVAIL =

a free block (I don’t currently leave any blocks free), although I do pad out the allocation table with AVAIL to the block size.

0xffffffff
EOC =

end of a chain

0xfffffffe
BAT =

these blocks correspond to the bat, and aren’t part of a file, nor available. (I don’t currently output these)

0xfffffffd
META_BAT = 
0xfffffffc

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(ole) ⇒ AllocationTable

Returns a new instance of AllocationTable.



428
429
430
431
 
# File 'lib/ole/storage.rb', line 428

def initialize ole
	@ole = ole
	@table = []
end

Instance Attribute Details

#block_size ⇒ Object (readonly)

Returns the value of attribute block_size.



427
428
429
 
# File 'lib/ole/storage.rb', line 427

def block_size
  @block_size
end

#io ⇒ Object (readonly)

Returns the value of attribute io.



427
428
429
 
# File 'lib/ole/storage.rb', line 427

def io
  @io
end

#ole ⇒ Object (readonly)

Returns the value of attribute ole.



427
428
429
 
# File 'lib/ole/storage.rb', line 427

def ole
  @ole
end

#table ⇒ Object (readonly)

Returns the value of attribute table.



427
428
429
 
# File 'lib/ole/storage.rb', line 427

def table
  @table
end

Instance Method Details

#blocks_to_ranges(chain, size = nil) ⇒ Object

Turn a chain (an array given by chain) of big blocks, optionally truncated to size, into an array of arrays describing the stretches of bytes in the file that it belongs to.

Big blocks are of size Ole::Storage::Header#b_size, and are stored directly in the parent file. truncate the chain if required convert chain to ranges of the block size truncate final range if required



486
487
488
489
490
491
 
# File 'lib/ole/storage.rb', line 486

def blocks_to_ranges chain, size=nil
	chain = chain[0...(size.to_f / block_size).ceil] if size
	ranges = chain.map { |i| [block_size * i, block_size] }
	ranges.last[1] -= (ranges.length * block_size - size) if ranges.last and size
	ranges
end

#chain(start) ⇒ Object

rewriting this to be non-recursive. it broke on a large attachment building up the chain, causing a stack error. need tail-call elimination…



459
460
461
462
463
464
465
466
467
468
469
 
# File 'lib/ole/storage.rb', line 459

def chain start
	a = []
	idx = start
	until idx >= META_BAT
		raise "broken allocationtable chain" if idx < 0 || idx > @table.length
		a << idx
		idx = @table[idx]
	end
	Log.warn "invalid chain terminator #{idx}" unless idx == EOC
	a
end

#get_free_block ⇒ Object 



513
514
515
516
517
 
# File 'lib/ole/storage.rb', line 513

def get_free_block
	@table.each_index { |i| return i if @table[i] == AVAIL }
	@table.push AVAIL
	@table.length - 1
end

#load(data) ⇒ Object 



433
434
435
 
# File 'lib/ole/storage.rb', line 433

def load data
	@table = data.unpack('L*')
end

#open(chain, size = nil) ⇒ Object

quick shortcut. chain can be either a head (in which case the table is used to turn it into a chain), or a chain. it is converted to ranges, then to rangesio. its not resizeable or migrateable. it probably could be resizeable though, using self as the bat. but what would the first_block be?



497
498
499
500
501
502
503
504
505
 
# File 'lib/ole/storage.rb', line 497

def open chain, size=nil
	io = RangesIO.new @io, ranges(chain, size)
	if block_given?
		begin   yield io
		ensure; io.close
		end
	else io
	end
end

#ranges(chain, size = nil) ⇒ Object 



471
472
473
474
 
# File 'lib/ole/storage.rb', line 471

def ranges chain, size=nil
	chain = self.chain(chain) unless Array === chain
	blocks_to_ranges chain, size
end

#read(chain, size = nil) ⇒ Object 



507
508
509
 
# File 'lib/ole/storage.rb', line 507

def read chain, size=nil
	open chain, size, &:read
end

#resize_chain(first_block, size) ⇒ Object

must return first_block



520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
 
# File 'lib/ole/storage.rb', line 520

def resize_chain first_block, size
	new_num_blocks = (size / block_size.to_f).ceil
	blocks = chain first_block
	old_num_blocks = blocks.length
	if new_num_blocks < old_num_blocks
		# de-allocate some of our old blocks. TODO maybe zero them out in the file???
		(new_num_blocks...old_num_blocks).each { |i| @table[blocks[i]] = AVAIL }
		# if we have a chain, terminate it and return head, otherwise return EOC
		if new_num_blocks > 0
			@table[blocks[new_num_blocks-1]] = EOC
			first_block
		else EOC
		end
	elsif new_num_blocks > old_num_blocks
		# need some more blocks.
		last_block = blocks.last
		(new_num_blocks - old_num_blocks).times do
			block = get_free_block
			# connect the chain. handle corner case of blocks being [] initially
			if last_block
				@table[last_block] = block
			else
				first_block = block
			end
			last_block = block
			# this is just to inhibit the problem where it gets picked as being a free block
			# again next time around.
			@table[last_block] = EOC
		end
		first_block
	else first_block
	end
end

#save ⇒ Object 



447
448
449
450
451
452
453
454
455
 
# File 'lib/ole/storage.rb', line 447

def save
	table = truncated_table #@table
	# pad it out some
	num = @ole.bbat.block_size / 4
	# do you really use AVAIL? they probably extend past end of file, and may shortly
	# be used for the bat. not really good.
	table += [AVAIL] * (num - (table.length % num)) if (table.length % num) != 0
	table.pack 'L*'
end

#truncated_table ⇒ Object 



437
438
439
440
441
442
443
444
445
 
# File 'lib/ole/storage.rb', line 437

def truncated_table
	# this strips trailing AVAILs. come to think of it, this has the potential to break
	# bogus ole. if you terminate using AVAIL instead of EOC, like I did before. but that is
	# very broken. however, if a chain ends with AVAIL, it should probably be fixed to EOC
	# at load time.
	temp = @table.reverse
	not_avail = temp.find { |b| b != AVAIL } and temp = temp[temp.index(not_avail)..-1]
	temp.reverse
end