chat channel
joafip users mailing list
forums
The basic services are:
create a data record giving the data size needed and return its identifier
delete a data record giving its identifier
read a data record giving identifier and returning associated data
write a data record giving identifier and associated data
Heap file contains a list of one header record followed by
data or free record.
+--------+
|
header |
+--------+
|
record |
+--------+
..........
+--------+
|
record |
+--------+
|
record |
+--------+
Each data or free record have:
a type indicator ( free or data record )
an area size
and a previous record position in file
Area size and previous record position in file make able to linearly go to previous or next record.
Each data or free record have red black tree node fields:
parent node position in file
left node position in file
right node position in file
color
number of child
The data record are sorted using data record identifier field
( each data record have an uniq identifier ). This make able to quickly
find a data record in file knowing its identifier.. The root data
record is given by heap file header.
The free record are sorted by area size. This make able to find a free
record by size with best mach for needed area to store data ( data
record creation ). The root free record is given by heap file header.
Free record can be transform in data record, may be largest than needs
for data, a big data record can be split in to obtains a data record
and a new free record ( previous size minus size of data record created
).
Data record can be transform in free record when deleted, if
this new free record have free record before and/or after these are
joined in one free record.
Changing data record in free
record, or free record in data record, updates header field
containing total of free size and total of used size.
|
offset in file |
content type |
description |
|
0 |
8 bytes, long, integer 64 bits |
root free record position in file |
|
8 |
8 bytes, long, integer 64 bits |
root data record position in file |
|
16 |
8 bytes, long, integer 64 bits |
used size, sum of data record area size |
|
24 |
8 bytes, long, integer 64 bits |
free size, sum of free record area size |
|
32 |
16 bytes, 2 longs, 2 integer 64 bits |
next data record identifier |
|
48 |
4 bytes, int, integer 32 bits |
CRC 32 on previous fields |
|
offset |
content type |
description |
|
0 |
1 byte, boolean |
always 1 ( free record=true ) for free record |
|
1 |
8 bytes, long, integer 64 bits |
previous record position in file |
|
9 |
4 bytes, int, integer 32 bits |
record area size |
|
13 |
8 bytes, long, integer 64 bits |
parent free record position in file, -1 if no parent ( root node ) |
|
21 |
8 bytes, long, integer 64 bits |
left free record position in file, -1 if no left node |
|
29 |
8 bytes, long, integer 64 bits |
right free record position in file, -1 if no right node |
|
37 |
1 bytes, byte, integer 8 bits |
color, 0 no color set, 2 for red, 3 for black |
|
38 |
4 bytes, int, integer 32 bits |
node number of child |
|
42 |
4 bytes, int, integer 32 bits |
CRC 32 bits on previous fields |
|
43 thru |
data bytes |
free area for data ( size is record area size minus 43 ) |
|
offset |
content type |
description |
|
0 |
1 byte, boolean |
always 0 ( free record=false ) for data record |
|
1 |
8 bytes, long, integer 64 bits |
previous record position in file |
|
9 |
4 bytes, int, integer 32 bits |
record area size |
|
13 |
4 bytes, int, integer 32 bits |
data associated size |
|
17 |
8 bytes, long, integer 64 bits |
parent data record position in file, -1 if no parent ( root node ) |
|
25 |
8 bytes, long, integer 64 bits |
left data record position in file, -1 if no left data node |
|
33 |
8 bytes, long, integer 64 bits |
right data record position in file, -1 if no right data node |
|
41 |
1 bytes, byte, integer 8 bits |
color, 0 no color set, 2 for red, 3 for black |
|
42 |
4 bytes, int, integer 32 bits |
node number of child |
|
46 |
16 bytes, 2 longs, 2 integer 64 bits |
data node identifier |
|
62 |
1 byte, byte,integer 8 bits |
have data flag |
|
63 |
4 bytes, int, integer 32 bits |
CRC 32 bits on previous fields |
|
67 |
data, data size bytes |
area for record data |
|
67 + |
4 bytes, int, integer 32 bits |
CRC 32 bits on previous data bytes |
