Class: OsCtld::IdRange::AllocationTable

Inherits:
Object
  • Object
show all
Defined in:
lib/osctld/id_range/allocation_table.rb

Defined Under Namespace

Classes: Allocation

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(block_count) ⇒ AllocationTable

Returns a new instance of AllocationTable.

Parameters:

  • block_count (Integer) 


44
45
46
47
 
# File 'lib/osctld/id_range/allocation_table.rb', line 44

def initialize(block_count)
  @block_count = block_count
  @table = []
end

Instance Attribute Details

#block_count ⇒ Integer (readonly)

Returns:

  • (Integer) 


41
42
43
 
# File 'lib/osctld/id_range/allocation_table.rb', line 41

def block_count
  @block_count
end

#table ⇒ Object (readonly, protected)

Returns the value of attribute table.



198
199
200
 
# File 'lib/osctld/id_range/allocation_table.rb', line 198

def table
  @table
end

Class Method Details

.load(block_count, data) ⇒ Object 



29
30
31
32
33
34
35
36
37
38
 
# File 'lib/osctld/id_range/allocation_table.rb', line 29

def self.load(block_count, data)
  t = new(block_count)

  data.each do |v|
    allocation = Allocation.load(v)
    t.allocate_at(allocation.block_index, allocation.block_count, allocation.owner)
  end

  t
end

Instance Method Details

#all_segments {|type, table_index, block_index, count, owner| ... } ⇒ Enumerator (protected)

Iterate over allocated and free segments in the table

Yield Parameters:

  • type (:allocated, :free)
  • table_index (Integer) —

    index in @table

  • block_index (Integer) —

    index of the block in the entire allocation table

  • count (Integer) —

    number of free blocks at this position

  • owner (String)

Returns:

  • (Enumerator) 


208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
 
# File 'lib/osctld/id_range/allocation_table.rb', line 208

def all_segments
  Enumerator.new do |yielder|
    if table.empty?
      yielder << [:free, 0, 0, block_count, nil]
      next
    end

    t_i = 0

    # Check if there is space before the first allocation
    free = table.first.block_index
    yielder << [:free, t_i, 0, free, nil] if free > 0

    loop do
      next_t_i = t_i + 1
      a1 = table[t_i]
      a2 = table[next_t_i]

      # Yield allocated block
      yielder << [:allocated, t_i, a1.block_index, a1.block_count, a1.owner]

      if a2.nil?
        # a1 is the last allocation, check if there is free space behind it
        free_count = block_count - a1.last_index - 1

        if free_count > 0
          yielder << [:free, next_t_i, a1.last_index + 1, free_count, nil]
        end

        break
      end

      # Report free space between a1 and a2
      free = a2.block_index - a1.last_index - 1
      yielder << [:free, next_t_i, a1.last_index + 1, free, nil] if free > 0

      t_i = next_t_i
    end
  end
end

#allocate(count, owner) ⇒ Hash, false

Allocate blocks anywhere in the table

Parameters:

  • count (Integer) —

    number of blocks

  • owner (String) —

    arbitrary allocation owner

Returns:

  • (Hash, false) 


100
101
102
103
104
105
106
107
 
# File 'lib/osctld/id_range/allocation_table.rb', line 100

def allocate(count, owner)
  table_index, block_index, _count = free_segments(count).first
  return false if table_index.nil?

  alloc = Allocation.new(block_index, count, owner)
  table.insert(table_index, alloc)
  alloc.export
end

#allocate_at(index, count, owner) ⇒ Hash, false

Allocate blocks on a specific position

Parameters:

  • index (Integer) —

    block index

  • count (Integer) —

    number of blocks

  • owner (String) —

    arbitrary allocation owner

Returns:

  • (Hash, false) 


74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
# File 'lib/osctld/id_range/allocation_table.rb', line 74

def allocate_at(index, count, owner)
  alloc = Allocation.new(index, count, owner)

  if table.empty?
    table << alloc
    return alloc.export

  elsif !free_at?(index, count)
    raise ArgumentError, "unable to allocate #{count} blocks at #{index}"
  end

  table.each_with_index do |v, t_i|
    if v.block_index > index
      table.insert(t_i, alloc)
      return alloc.export
    end
  end

  table << alloc
  alloc.export
end

#count_allocated_blocks ⇒ Integer

Returns:

  • (Integer) 


135
136
137
 
# File 'lib/osctld/id_range/allocation_table.rb', line 135

def count_allocated_blocks
  table.inject(0) { |sum, v| sum + v.block_count }
end

#count_free_blocks ⇒ Integer

Returns:

  • (Integer) 


140
141
142
143
144
145
 
# File 'lib/osctld/id_range/allocation_table.rb', line 140

def count_free_blocks
  free_segments.inject(0) do |sum, v|
    _, _, count = v
    sum + count
  end
end

#dump ⇒ Object 



152
153
154
 
# File 'lib/osctld/id_range/allocation_table.rb', line 152

def dump
  table.map(&:dump)
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


148
149
150
 
# File 'lib/osctld/id_range/allocation_table.rb', line 148

def empty?
  table.empty?
end

#export_all ⇒ Object 



156
157
158
159
160
161
162
163
164
165
 
# File 'lib/osctld/id_range/allocation_table.rb', line 156

def export_all
  all_segments.map do |type, _table_index, block_index, count, owner|
    {
      type:,
      block_index:,
      block_count: count,
      owner:
    }
  end
end

#export_allocated ⇒ Object 



167
168
169
 
# File 'lib/osctld/id_range/allocation_table.rb', line 167

def export_allocated
  table.map(&:export)
end

#export_at(index) ⇒ Object

Parameters:

  • index (Integer) —

    block index

Raises:

  • (ArgumentError) 


181
182
183
184
185
186
187
188
189
190
191
192
193
194
 
# File 'lib/osctld/id_range/allocation_table.rb', line 181

def export_at(index)
  all_segments.each do |type, _table_index, block_index, count, owner|
    if index >= block_index && index <= (block_index + count - 1)
      return {
        type:,
        block_index:,
        block_count: count,
        owner:
      }
    end
  end

  raise ArgumentError, 'index out of range'
end

#export_free ⇒ Object 



171
172
173
174
175
176
177
178
 
# File 'lib/osctld/id_range/allocation_table.rb', line 171

def export_free
  free_segments.map do |_table_index, block_index, count|
    {
      block_index:,
      block_count: count
    }
  end
end

#free_at(index) ⇒ Boolean

Free allocation starting at a specified position

Parameters:

  • index (Integer) —

    block index

Returns:

  • (Boolean) 


112
113
114
115
116
117
118
119
120
121
 
# File 'lib/osctld/id_range/allocation_table.rb', line 112

def free_at(index)
  table.each_with_index do |alloc, t_i|
    if alloc.block_index == index
      table.delete_at(t_i)
      return true
    end
  end

  false
end

#free_at?(index, count) ⇒ Boolean

Check if blocks at specified position are free

Parameters:

  • index (Integer) —

    block index

  • count (Integer) —

    number of blocks from ‘index` that have to be free

Returns:

  • (Boolean) 


53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/osctld/id_range/allocation_table.rb', line 53

def free_at?(index, count)
  last_index = index + count - 1

  free_segments(count).each do |_, free_index, free_count|
    last_free_index = free_index + free_count - 1

    if index >= free_index && last_index <= last_free_index
      return true
    elsif free_index > last_index
      return false
    end
  end

  false
end

#free_by(owner) ⇒ Boolean

Free one allocation which is owned by ‘owner`

Parameters:

  • owner (String)

Returns:

  • (Boolean) 


126
127
128
129
130
131
132
 
# File 'lib/osctld/id_range/allocation_table.rb', line 126

def free_by(owner)
  table.delete_if.with_index do |alloc, _t_i|
    alloc.owner == owner
  end

  true
end

#free_segments(count = 1) {|table_index, block_index, count| ... } ⇒ Enumerator (protected)

Iterate over free segments in the table

Parameters:

  • count (Integer) (defaults to: 1) —

    specify a minimum free segment size, i.e. a number of blocks

Yield Parameters:

  • table_index (Integer) —

    index in @table

  • block_index (Integer) —

    index of the block in the entire allocation table

  • count (Integer) —

    number of free blocks at this position

Returns:

  • (Enumerator) 


257
258
259
260
261
262
263
 
# File 'lib/osctld/id_range/allocation_table.rb', line 257

def free_segments(count = 1)
  all_segments.select do |type, _, _, cnt|
    type == :free && cnt >= count
  end.map do |_type, t_i, b_i, cnt|
    [t_i, b_i, cnt]
  end
end