Repository: jjhelmus/pyfive (language: python)

Issue:
Fails for groups with order tracking
h5py: 2.10.0, h5py: 1.10.4

```python
filename = "test.h5"
n = 8  # PASSES
n = 9  # FAILS
with h5py.File(filename, mode="w", track_order=True) as f:
    for i in range(n):
        f.create_group(str(i))
with pyfive.File(filename) as f:
    assert len(f.keys()) == n
```

Perhaps related `h5py` issue: https://github.com/h5py/h5py/issues/1385


Discussion / hints:
I have no idea how `h5py` gets hold of the top-level groups when more than 8 groups are added with tracking enabled for the root node. The v2 B-TREE addresses in LINK_INFO  are 0xffffffffffffff so there are no links in there either. GROUP_INFO doesn't have links and then there is the NIL. No other dataobjects messages are present. Very weird.

### Root dataobjects (9 top-level groups)

```python
Superblock version: 0
Root dataobjects:
{'access_time': 1613422645,
 'birth_time': 1613422645,
 'change_time': 1613422645,
 'flags': 44,
 'modification_time': 1613422645,
 'signature': b'OHDR',
 'size_of_chunk_0': 224,
 'version': 2}
 LINK_INFO (flags:0):
 GROUP_INFO (flags:1):
   b'\x00\x00'
 NIL (flags:0):
   b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
```

```python
ROOT LINKS: {}
```


### Root dataobjects (8 top-level groups)
```python
Superblock version: 0
Root dataobjects:
{'access_time': 1613422597,
 'birth_time': 1613422597,
 'change_time': 1613422597,
 'flags': 44,
 'modification_time': 1613422597,
 'signature': b'OHDR',
 'size_of_chunk_0': 224,
 'version': 2}
 LINK_INFO (flags:0):
 GROUP_INFO (flags:1):
   b'\x00\x00'
 OBJECT_CONTINUATION (flags:0):
   b'\x9b\x14\x00\x00\x00\x00\x00\x00<\x00\x00\x00\x00\x00\x00\x00'
 LINK (flags:0):
   b'\x01\x04\x01\x00\x00\x00\x00\x00\x00\x00\x011\x1b\x04\x00\x00\x00\x00\x00\x00'
 LINK (flags:0):
   b'\x01\x04\x02\x00\x00\x00\x00\x00\x00\x00\x012\xdb\x06\x00\x00\x00\x00\x00\x00'
 LINK (flags:0):
   b'\x01\x04\x03\x00\x00\x00\x00\x00\x00\x00\x013\x9b\t\x00\x00\x00\x00\x00\x00'
 LINK (flags:0):
   b'\x01\x04\x04\x00\x00\x00\x00\x00\x00\x00\x014[\x0c\x00\x00\x00\x00\x00\x00'
 LINK (flags:0):
   b'\x01\x04\x05\x00\x00\x00\x00\x00\x00\x00\x015\x1b\x0f\x00\x00\x00\x00\x00\x00'
 OBJECT_CONTINUATION (flags:0):
   b'\x97\x17\x00\x00\x00\x00\x00\x00"\x00\x00\x00\x00\x00\x00\x00'
 LINK (flags:0):
   b'\x01\x04\x00\x00\x00\x00\x00\x00\x00\x00\x010[\x01\x00\x00\x00\x00\x00\x00'
 LINK (flags:0):
   b'\x01\x04\x06\x00\x00\x00\x00\x00\x00\x00\x016\xdb\x11\x00\x00\x00\x00\x00\x00'
 LINK (flags:0):
   b'\x01\x04\x07\x00\x00\x00\x00\x00\x00\x00\x017\xd7\x14\x00\x00\x00\x00\x00\x00'
```

```python
ROOT LINKS: {'1': 1051, '2': 1755, '3': 2459, '4': 3163, '5': 3867, '0': 347, '6': 4571, '7': 5335}
```

HDF5 looks to be using "new style" groups when `track_order=True` and there are more than 8 groups.  Information on these groups looks to be stored in [Link Info](https://support.hdfgroup.org/HDF5/doc/H5.format.html#LinkInfoMessage) (type 0x002) and [Group Info](https://support.hdfgroup.org/HDF5/doc/H5.format.html#GroupInfoMessage) (type 0x000A, decimal 10) messages which pyfive does not read but can see:

``` python
from pprint import pprint
import h5py
import pyfive

filename = "test.h5"
n = 9
with h5py.File(filename, mode="w", track_order=True) as f:
    for i in range(n):
        f.create_group(str(i))

with pyfive.File(filename) as f:
    pprint(f._dataobjects.msgs)
```

```
[OrderedDict([('type', 2),
              ('size', 34),
              ('flags', 0),
              ('offset_to_message', 6)]),
 OrderedDict([('type', 10),
              ('size', 2),
              ('flags', 1),
              ('offset_to_message', 46)]),
 OrderedDict([('type', 0),
              ('size', 170),
              ('flags', 0),
              ('offset_to_message', 54)])]
```
Yes I thought so too so I tried reading the Link info message data but the heap and btree addresses are 0xffffffffffffff which means they are not used. I'll reinvestigate, maybe I missed something.

Fix patch:
diff --git a/pyfive/btree.py b/pyfive/btree.py
index ba9152c..38518fc 100644
--- a/pyfive/btree.py
+++ b/pyfive/btree.py
@@ -11,39 +11,91 @@
 from .core import Reference
 
 
-class BTree(object):
-    """
-    HDF5 version 1 B-Tree.
-    """
+class AbstractBTree(object):
+    B_LINK_NODE = None
+    NODE_TYPE = None
 
     def __init__(self, fh, offset):
         """ initalize. """
         self.fh = fh
+        self.offset = offset
+        self.depth = None
+        self.all_nodes = {}
+
+        self._read_root_node()
+        self._read_children()
+
+    def _read_children(self):
+        # Leaf nodes: level 0
+        # Root node: level "depth"
+        node_level = self.depth
+        for node_level in range(self.depth, 0, -1):
+            for parent_node in self.all_nodes[node_level]:
+                for child_addr in parent_node['addresses']:
+                    child_node = self._read_node(child_addr, node_level-1)
+                    self._add_node(child_node)
+
+    def _read_root_node(self):
+        root_node = self._read_node(self.offset, None)
+        self._add_node(root_node)
+        self.depth = root_node['node_level']
+
+    def _add_node(self, node):
+        node_level = node['node_level']
+        if node_level in self.all_nodes:
+            self.all_nodes[node_level].append(node)
+        else:
+            self.all_nodes[node_level] = [node]
 
-        # read in the root node
-        root_node = self._read_node(offset)
-        self.root_node = root_node
-
-        # read in all nodes
-        all_nodes = {}
-        node_level = root_node['node_level']
-        all_nodes[node_level] = [root_node]
-        while node_level != 0:
-            new_nodes = []
-            for parent_node in all_nodes[node_level]:
-                for addr in parent_node['addresses']:
-                    new_nodes.append(self._read_node(addr))
-            new_node_level = new_nodes[0]['node_level']
-            all_nodes[new_node_level] = new_nodes
-            node_level = new_node_level
-        self.all_nodes = all_nodes
-
-    def _read_node(self, offset):
+    def _read_node(self, offset, node_level):
         """ Return a single node in the B-Tree located at a given offset. """
+        node = self._read_node_header(offset, node_level)
+        node['keys'] = []
+        node['addresses'] = []
+        return node
+
+    def _read_node_header(self, offset):
+        """ Return a single node header in the b-tree located at a give offset. """
+        raise NotImplementedError
+
+
+class BTreeV1(AbstractBTree):
+    """
+    HDF5 version 1 B-Tree.
+    """
+
+    # III.A.1. Disk Format: Level 1A1 - Version 1 B-trees
+    B_LINK_NODE = OrderedDict((
+        ('signature', '4s'),
+
+        ('node_type', 'B'),
+        ('node_level', 'B'),
+        ('entries_used', 'H'),
+
+        ('left_sibling', 'Q'),     # 8 byte addressing
+        ('right_sibling', 'Q'),    # 8 byte addressing
+    ))
+
+    def _read_node_header(self, offset, node_level):
+        """ Return a single node header in the b-tree located at a give offset. """
         self.fh.seek(offset)
-        node = _unpack_struct_from_file(B_LINK_NODE_V1, self.fh)
+        node = _unpack_struct_from_file(self.B_LINK_NODE, self.fh)
         assert node['signature'] == b'TREE'
+        assert node['node_type'] == self.NODE_TYPE
+        if node_level is not None:
+            assert node["node_level"] == node_level
+        return node
 
+
+class BTreeV1Groups(BTreeV1):
+    """
+    HDF5 version 1 B-Tree storing group nodes (type 0).
+    """
+    NODE_TYPE = 0
+
+    def _read_node(self, offset, node_level):
+        """ Return a single node in the B-Tree located at a given offset. """
+        node = self._read_node_header(offset, node_level)
         keys = []
         addresses = []
         for _ in range(node['entries_used']):
@@ -65,42 +117,20 @@ def symbol_table_addresses(self):
         return all_address
 
 
-class BTreeRawDataChunks(object):
+class BTreeV1RawDataChunks(BTreeV1):
     """
     HDF5 version 1 B-Tree storing raw data chunk nodes (type 1).
     """
+    NODE_TYPE = 1
 
     def __init__(self, fh, offset, dims):
         """ initalize. """
-        self.fh = fh
         self.dims = dims
+        super().__init__(fh, offset)
 
-        # read in the root node
-        root_node = self._read_node(offset)
-        self.root_node = root_node
-
-        # read in all other nodes
-        all_nodes = {}
-        node_level = root_node['node_level']
-        all_nodes[node_level] = [root_node]
-        while node_level != 0:
-            new_nodes = []
-            for parent_node in all_nodes[node_level]:
-                for addr in parent_node['addresses']:
-                    new_nodes.append(self._read_node(addr))
-            new_node_level = new_nodes[0]['node_level']
-            all_nodes[new_node_level] = new_nodes
-            node_level = new_node_level
-
-        self.all_nodes = all_nodes
-
-    def _read_node(self, offset):
+    def _read_node(self, offset, node_level):
         """ Return a single node in the b-tree located at a give offset. """
-        self.fh.seek(offset)
-        node = _unpack_struct_from_file(B_LINK_NODE_V1, self.fh)
-        assert node['signature'] == b'TREE'
-        assert node['node_type'] == 1
-
+        node = self._read_node_header(offset, node_level)
         keys = []
         addresses = []
         for _ in range(node['entries_used']):
@@ -170,8 +200,8 @@ def construct_data_from_chunks(
         non_padded_region = tuple([slice(i) for i in data_shape])
         return data[non_padded_region]
 
-    @staticmethod
-    def _filter_chunk(chunk_buffer, filter_mask, filter_pipeline, itemsize):
+    @classmethod
+    def _filter_chunk(cls, chunk_buffer, filter_mask, filter_pipeline, itemsize):
         """ Apply decompression filters to a chunk of data. """
         num_filters = len(filter_pipeline)
         for i, pipeline_entry in enumerate(filter_pipeline[::-1]):
@@ -185,7 +215,6 @@ def _filter_chunk(chunk_buffer, filter_mask, filter_pipeline, itemsize):
             filter_id = pipeline_entry['filter_id']
             if filter_id == GZIP_DEFLATE_FILTER:
                 chunk_buffer = zlib.decompress(chunk_buffer)
-
             elif filter_id == SHUFFLE_FILTER:
                 buffer_size = len(chunk_buffer)
                 unshuffled_buffer = bytearray(buffer_size)
@@ -196,7 +225,7 @@ def _filter_chunk(chunk_buffer, filter_mask, filter_pipeline, itemsize):
                     unshuffled_buffer[j::itemsize] = chunk_buffer[start:end]
                 chunk_buffer = unshuffled_buffer
             elif filter_id == FLETCH32_FILTER:
-                _verify_fletcher32(chunk_buffer)
+                cls._verify_fletcher32(chunk_buffer)
                 # strip off 4-byte checksum from end of buffer
                 chunk_buffer = chunk_buffer[:-4]
             else:
@@ -204,40 +233,213 @@ def _filter_chunk(chunk_buffer, filter_mask, filter_pipeline, itemsize):
                     "Filter with id: %i import supported" % (filter_id))
         return chunk_buffer
 
+    @staticmethod
+    def _verify_fletcher32(chunk_buffer):
+        """ Verify a chunk with a fletcher32 checksum. """
+        # calculate checksums
+        if len(chunk_buffer) % 2:
+            arr = np.frombuffer(chunk_buffer[:-4]+b'\x00', '<u2')
+        else:
+            arr = np.frombuffer(chunk_buffer[:-4], '<u2')
+        sum1 = sum2 = 0
+        for i in arr:
+            sum1 = (sum1 + i) % 65535
+            sum2 = (sum2 + sum1) % 65535
+
+        # extract stored checksums
+        ref_sum1, ref_sum2 = np.frombuffer(chunk_buffer[-4:], '>u2')
+        ref_sum1 = ref_sum1 % 65535
+        ref_sum2 = ref_sum2 % 65535
+
+        # compare
+        if sum1 != ref_sum1 or sum2 != ref_sum2:
+            raise ValueError("fletcher32 checksum invalid")
+        return True
+
+
+class BTreeV2(AbstractBTree):
+    """
+    HDF5 version 2 B-Tree.
+    """
+
+    # III.A.2. Disk Format: Level 1A2 - Version 2 B-trees
+    B_TREE_HEADER = OrderedDict((
+        ('signature', '4s'),
+
+        ('version', 'B'),
+        ('node_type', 'B'),
+        ('node_size', 'I'),
+        ('record_size', 'H'),
+        ('depth', 'H'),
+        ('split_percent', 'B'),
+        ('merge_percent', 'B'),
+
+        ('root_address', 'Q'),     # 8 byte addressing
+        ('root_nrecords', 'H'),
+        ('total_nrecords', 'Q'),     # 8 byte addressing
+    ))
+
+    B_LINK_NODE = OrderedDict((
+        ('signature', '4s'),
+
+        ('version', 'B'),
+        ('node_type', 'B'),
+    ))
+
+    def _read_root_node(self):
+        h = self._read_tree_header(self.offset)
+        self.address_formats = self._calculate_address_formats(h)
+        self.header = h
+        self.depth = h["depth"]
+
+        address = (h["root_address"], h["root_nrecords"], h["total_nrecords"])
+        root_node = self._read_node(address, self.depth)
+        self._add_node(root_node)
+
+    def _read_tree_header(self, offset):
+        self.fh.seek(self.offset)
+        header = _unpack_struct_from_file(self.B_TREE_HEADER, self.fh)
+        assert header['signature'] == b'BTHD'
+        assert header['node_type'] == self.NODE_TYPE
+        return header
+
+    def _calculate_address_formats(self, header):
+        node_size = header["node_size"]
+        record_size = header["record_size"]
+
+        nrecords_max = 0
+        ntotalrecords_max = 0
+        address_formats = []
+        for node_level in range(header["depth"]+1):
+            offset_fmt = ""
+            num1_fmt = ""
+            num2_fmt = ""
+            if node_level == 0:  # leaf node
+                offset_size = 0
+                num1_size = 0
+                num2_size = 0
+            elif node_level == 1:  # internal node (twig node)
+                offset_size = 8
+                offset_fmt = "<Q"
+                num1_size = self._required_bytes(nrecords_max)
+                num1_fmt = "<{}s".format(num1_size)
+                num2_size = 0
+            else:  # internal node
+                offset_size = 8
+                offset_fmt = "<Q"
+                num1_size = self._required_bytes(nrecords_max)
+                num1_fmt = "<{}s".format(num1_size)
+                num2_size = self._required_bytes(ntotalrecords_max)
+                num2_fmt = "<{}s".format(num2_size)
+            address_formats.append((
+                offset_size, num1_size, num2_size,
+                offset_fmt, num1_fmt, num2_fmt))
+            if node_level < header["depth"]:
+                addr_size = offset_size + num1_size + num2_size
+                nrecords_max = self._nrecords_max(node_size, record_size, addr_size)
+                if ntotalrecords_max:
+                    ntotalrecords_max *= nrecords_max
+                else:
+                    ntotalrecords_max = nrecords_max
+
+        return address_formats
+
+    @staticmethod
+    def _nrecords_max(node_size, record_size, addr_size):
+        """ Calculate the maximal records a node can contain. """
+        # node_size = overhead + nrecords_max*record_size + (nrecords_max+1)*addr_size
+        #
+        # overhead = size(B_LINK_NODE) + 4 (checksum)
+        #
+        # Leaf node (node_level = 0)
+        #   addr_size = 0
+        # Internal node (node_level = 1)
+        #   addr_size = offset_size + num1_size
+        # Internal node (node_level > 1)
+        #   addr_size = offset_size + num1_size + num2_size
+        return (node_size - 10 - addr_size)//(record_size + addr_size)
+
+    @staticmethod
+    def _required_bytes(integer):
+        """ Calculate the minimal required bytes to contain an integer. """
+        return (max(integer.bit_length(), 1) + 7) // 8
+
+    def _read_node(self, address, node_level):
+        """ Return a single node in the B-Tree located at a given offset. """
+        offset, nrecords, ntotalrecords = address
+        node = self._read_node_header(offset, node_level)
+
+        record_size = self.header['record_size']
+
+        keys = []
+        for _ in range(nrecords):
+            record = self.fh.read(record_size)
+            keys.append(self._parse_record(record))
+
+        addresses = []
+        fmts = self.address_formats[node_level]
+        if fmts[0]:
+            offset_size, num1_size, num2_size, offset_fmt, num1_fmt, num2_fmt = fmts
+            for _ in range(nrecords+1):
+                offset = struct.unpack(offset_fmt, self.fh.read(offset_size))[0]
+                num1 = struct.unpack(num1_fmt, self.fh.read(num1_size))[0]
+                num1 = int.from_bytes(num1, byteorder="little", signed=False)
+                if num2_size:
+                    num2 = struct.unpack(num2_fmt, self.fh.read(num2_size))[0]
+                    num2 = int.from_bytes(num2, byteorder="little", signed=False)
+                else:
+                    num2 = num1
+                addresses.append((offset, num1, num2))
+
+        node['keys'] = keys
+        node['addresses'] = addresses
+        return node
+
+    def _read_node_header(self, offset, node_level):
+        """ Return a single node header in the b-tree located at a give offset. """
+        self.fh.seek(offset)
+        node = _unpack_struct_from_file(self.B_LINK_NODE, self.fh)
+        assert node['node_type'] == self.NODE_TYPE
+        if node_level:
+            # Internal node (has children)
+            assert node['signature'] == b'BTIN'
+        else:
+            # Leaf node (has no children)
+            assert node['signature'] == b'BTLF'
+        node["node_level"] = node_level
+        return node
+
+    def iter_records(self):
+        """ Iterate over all records. """
+        for nodelist in self.all_nodes.values():
+            for node in nodelist:
+                yield from node["keys"]
+
+    def _parse_record(self, record):
+        raise NotImplementedError
 
-def _verify_fletcher32(chunk_buffer):
-    """ Verify a chunk with a fletcher32 checksum. """
-    # calculate checksums
-    if len(chunk_buffer) % 2:
-        arr = np.frombuffer(chunk_buffer[:-4]+b'\x00', '<u2')
-    else:
-        arr = np.frombuffer(chunk_buffer[:-4], '<u2')
-    sum1 = sum2 = 0
-    for i in arr:
-        sum1 = (sum1 + i) % 65535
-        sum2 = (sum2 + sum1) % 65535
 
-    # extract stored checksums
-    ref_sum1, ref_sum2 = np.frombuffer(chunk_buffer[-4:], '>u2')
-    ref_sum1 = ref_sum1 % 65535
-    ref_sum2 = ref_sum2 % 65535
+class BTreeV2GroupNames(BTreeV2):
+    """
+    HDF5 version 2 B-Tree storing group names (type 5).
+    """
+    NODE_TYPE = 5
 
-    # compare
-    if sum1 != ref_sum1 or sum2 != ref_sum2:
-        raise ValueError("fletcher32 checksum invalid")
-    return True
+    def _parse_record(self, record):
+        namehash = struct.unpack_from("<I", record, 0)[0]
+        return {'namehash': namehash, 'heapid':record[4:4+7]}
 
 
-B_LINK_NODE_V1 = OrderedDict((
-    ('signature', '4s'),
+class BTreeV2GroupOrders(BTreeV2):
+    """
+    HDF5 version 2 B-Tree storing group creation orders (type 6).
+    """
+    NODE_TYPE = 6
 
-    ('node_type', 'B'),
-    ('node_level', 'B'),
-    ('entries_used', 'H'),
+    def _parse_record(self, record):
+        creationorder = struct.unpack_from("<Q", record, 0)[0]
+        return {'creationorder': creationorder, 'heapid':record[8:8+7]}
 
-    ('left_sibling', 'Q'),     # 8 byte addressing
-    ('right_sibling', 'Q'),    # 8 byte addressing
-))
 
 # IV.A.2.l The Data Storage - Filter Pipeline message
 RESERVED_FILTER = 0
diff --git a/pyfive/core.py b/pyfive/core.py
index 3afd7f1..b0d2718 100644
--- a/pyfive/core.py
+++ b/pyfive/core.py
@@ -7,6 +7,9 @@
 import struct
 
 
+UNDEFINED_ADDRESS = 0xffffffffffffffff
+
+
 class InvalidHDF5File(Exception):
     """ Exception raised when an invalid HDF5 file is detected. """
     pass
@@ -50,3 +53,10 @@ def _unpack_struct_from(structure, buf, offset=0):
     fmt = '<' + ''.join(structure.values())
     values = struct.unpack_from(fmt, buf, offset=offset)
     return OrderedDict(zip(structure.keys(), values))
+
+
+def _unpack_integer(nbytes, buf, offset=0):
+    """ Read an integer with an uncommon number of bytes. """
+    fmt = "{}s".format(nbytes)
+    values = struct.unpack_from(fmt, buf, offset=offset)
+    return int.from_bytes(values[0], byteorder="little", signed=False)
diff --git a/pyfive/dataobjects.py b/pyfive/dataobjects.py
index 8af28db..38cb9a9 100644
--- a/pyfive/dataobjects.py
+++ b/pyfive/dataobjects.py
@@ -13,9 +13,11 @@
 from .core import _unpack_struct_from, _unpack_struct_from_file
 from .core import InvalidHDF5File
 from .core import Reference
-from .btree import BTree, BTreeRawDataChunks
+from .core import UNDEFINED_ADDRESS
+from .btree import BTreeV1Groups, BTreeV1RawDataChunks
+from .btree import BTreeV2GroupNames, BTreeV2GroupOrders
 from .btree import GZIP_DEFLATE_FILTER, SHUFFLE_FILTER, FLETCH32_FILTER
-from .misc_low_level import Heap, SymbolTable, GlobalHeap
+from .misc_low_level import Heap, SymbolTable, GlobalHeap, FractalHeap
 
 
 class DataObjects(object):
@@ -384,10 +386,35 @@ def get_data(self):
         version, dims, layout_class, property_offset = (
             self._get_data_message_properties(msg_offset))
 
+        if layout_class == 0:  # compact storage
+            raise NotImplementedError("Compact storage")
+        elif layout_class == 1:  # contiguous storage
+            return self._get_contiguous_data(property_offset)
         if layout_class == 2:  # chunked storage
             return self._get_chunked_data(msg_offset)
 
-        assert layout_class == 1
+    def _get_data_message_properties(self, msg_offset):
+        """ Return the message properties of the DataObject. """
+        dims, layout_class, property_offset = None, None, None
+        version, arg1, arg2 = struct.unpack_from(
+            '<BBB', self.msg_data, msg_offset)
+        if (version == 1) or (version == 2):
+            dims = arg1
+            layout_class = arg2
+            property_offset = msg_offset
+            property_offset += struct.calcsize('<BBB')
+            # reserved fields: 1 byte, 1 int
+            property_offset += struct.calcsize('<BI')
+            # compact storage (layout class 0) not supported:
+            assert (layout_class == 1) or (layout_class == 2)
+        elif (version == 3) or (version == 4):
+            layout_class = arg1
+            property_offset = msg_offset
+            property_offset += struct.calcsize('<BB')
+        assert (version >= 1) and (version <= 4)
+        return version, dims, layout_class, property_offset
+
+    def _get_contiguous_data(self, property_offset):
         data_offset, = struct.unpack_from('<Q', self.msg_data, property_offset)
 
         if data_offset == UNDEFINED_ADDRESS:
@@ -411,31 +438,10 @@ def get_data(self):
             else:
                 raise NotImplementedError('datatype not implemented')
 
-    def _get_data_message_properties(self, msg_offset):
-        """ Return the message properties of the DataObject. """
-        dims, layout_class, property_offset = None, None, None
-        version, arg1, arg2 = struct.unpack_from(
-            '<BBB', self.msg_data, msg_offset)
-        if (version == 1) or (version == 2):
-            dims = arg1
-            layout_class = arg2
-            property_offset = msg_offset
-            property_offset += struct.calcsize('<BBB')
-            # reserved fields: 1 byte, 1 int
-            property_offset += struct.calcsize('<BI')
-            # compact storage (layout class 0) not supported:
-            assert (layout_class == 1) or (layout_class == 2)
-        elif (version == 3) or (version == 4):
-            layout_class = arg1
-            property_offset = msg_offset
-            property_offset += struct.calcsize('<BB')
-        assert (version >= 1) and (version <= 4)
-        return version, dims, layout_class, property_offset
-
     def _get_chunked_data(self, offset):
         """ Return data which is chunked. """
         self._get_chunk_params()
-        chunk_btree = BTreeRawDataChunks(
+        chunk_btree = BTreeV1RawDataChunks(
             self.fh, self._chunk_address, self._chunk_dims)
         return chunk_btree.construct_data_from_chunks(
             self.chunks, self.shape, self.dtype, self.filter_pipeline)
@@ -482,74 +488,130 @@ def find_msg_type(self, msg_type):
 
     def get_links(self):
         """ Return a dictionary of link_name: offset """
-        sym_tbl_msgs = self.find_msg_type(SYMBOL_TABLE_MSG_TYPE)
-        if sym_tbl_msgs:
-            return self._get_links_from_symbol_tables(sym_tbl_msgs)
-        return self._get_links_from_link_msgs()
-
-    def _get_links_from_symbol_tables(self, sym_tbl_msgs):
+        return dict(self.iter_links())
+
+    def iter_links(self):
+        for msg in self.msgs:
+            if msg['type'] == SYMBOL_TABLE_MSG_TYPE:
+                yield from self._iter_links_from_symbol_tables(msg)
+            elif msg['type'] == LINK_MSG_TYPE:
+                yield self._get_link_from_link_msg(msg)
+            elif msg['type'] == LINK_INFO_MSG_TYPE:
+                yield from self._iter_link_from_link_info_msg(msg)
+
+    def _iter_links_from_symbol_tables(self, sym_tbl_msg):
         """ Return a dict of link_name: offset from a symbol table. """
-        assert len(sym_tbl_msgs) == 1
-        assert sym_tbl_msgs[0]['size'] == 16
-        symbol_table_message = _unpack_struct_from(
+        assert sym_tbl_msg['size'] == 16
+        data = _unpack_struct_from(
             SYMBOL_TABLE_MSG, self.msg_data,
-            sym_tbl_msgs[0]['offset_to_message'])
+            sym_tbl_msg['offset_to_message'])
+        yield from self._iter_links_btree_v1(data['btree_address'], data['heap_address'])
 
-        btree = BTree(self.fh, symbol_table_message['btree_address'])
-        heap = Heap(self.fh, symbol_table_message['heap_address'])
-        links = {}
+    def _iter_links_btree_v1(self, btree_address, heap_address):
+        """ Retrieve links from symbol table message. """
+        btree = BTreeV1Groups(self.fh, btree_address)
+        heap = Heap(self.fh, heap_address)
         for symbol_table_address in btree.symbol_table_addresses():
             table = SymbolTable(self.fh, symbol_table_address)
             table.assign_name(heap)
-            links.update(table.get_links(heap))
-        return links
-
-    def _get_links_from_link_msgs(self):
-        """ Retrieve links from link messages. """
-        links = {}
-        link_msgs = self.find_msg_type(LINK_MSG_TYPE)
-        for link_msg in link_msgs:
-            offset = link_msg['offset_to_message']
-            version, flags = struct.unpack_from('<BB', self.msg_data, offset)
+            yield from table.get_links(heap).items()
+
+    def _get_link_from_link_msg(self, link_msg):
+        """ Retrieve link from link message. """
+        offset = link_msg['offset_to_message']
+        return self._decode_link_msg(self.msg_data, offset)[1]
+
+    @staticmethod
+    def _decode_link_msg(data, offset):
+        version, flags = struct.unpack_from('<BB', data, offset)
+        offset += 2
+        assert version == 1
+
+        size_of_length_of_link_name = 2**(flags & 3)
+        link_type_field_present = flags & 2**3
+        link_name_character_set_field_present = flags & 2**4
+        ordered = flags & 2**2
+
+        if link_type_field_present:
+            link_type = struct.unpack_from('<B', data, offset)[0]
+            offset += 1
+        else:
+            link_type = 0
+        assert link_type in [0,1]
+
+        if ordered:
+            creationorder = struct.unpack_from('<Q', data, offset)[0]
+            offset += 8
+        else:
+            creationorder = None
+
+        if link_name_character_set_field_present:
+            link_name_character_set = struct.unpack_from('<B', data, offset)[0]
+            offset += 1
+        else:
+            link_name_character_set = 0
+
+        encoding = 'ascii' if link_name_character_set == 0 else 'utf-8'
+
+        name_size_fmt = ["<B", "<H", "<I", "<Q"][flags & 3]
+        name_size = struct.unpack_from(name_size_fmt, data, offset)[0]
+        offset += size_of_length_of_link_name
+
+        name = data[offset:offset+name_size].decode(encoding)
+        offset += name_size
+
+        if link_type == 0:
+            # hard link
+            address = struct.unpack_from('<Q', data, offset)[0]
+        elif link_type == 1:
+            # soft link
+            length_of_soft_link_value = struct.unpack_from('<H', data, offset)[0]
             offset += 2
-            assert version == 1
-            size_of_length_of_link_name = 2**(flags & 3)
-            link_type_field_present = flags & 2**3
-            link_name_character_set_field_present = flags & 2**4
-            if link_type_field_present:
-                link_type = struct.unpack_from('<B', self.msg_data, offset)[0]
-                offset += 1
-            else:
-                link_type = 0
-            assert link_type in [0,1]
-
-            if flags & 2**2:
-                # creation order present
-                offset += 8
-            if link_name_character_set_field_present:
-                link_name_character_set = struct.unpack_from('<B', self.msg_data, offset)[0]
-                offset += 1
-            else:
-                link_name_character_set = 0
-
-            encoding = 'ascii' if link_name_character_set == 0 else 'utf-8'
-
-            name_size_fmt = ["<B", "<H", "<I", "<Q"][flags & 3]
-            name_size = struct.unpack_from(name_size_fmt, self.msg_data, offset)[0]
-            offset += size_of_length_of_link_name
-            name = self.msg_data[offset:offset+name_size].decode(encoding)
-            offset += name_size
-
-            if link_type == 0:
-                # hard link
-                address = struct.unpack_from('<Q', self.msg_data, offset)[0]
-                links[name] = address
-            elif link_type == 1:
-                # soft link
-                length_of_soft_link_value = struct.unpack_from('<H', self.msg_data, offset)[0]
-                offset += 2
-                links[name] = self.msg_data[offset:offset+length_of_soft_link_value].decode(encoding)
-        return links
+            address = data[offset:offset+length_of_soft_link_value].decode(encoding)
+
+        return creationorder, (name, address)
+
+    def _iter_link_from_link_info_msg(self, info_msg):
+        """ Retrieve links from link info message. """
+        offset = info_msg['offset_to_message']
+        data = self._decode_link_info_msg(self.msg_data, offset)
+
+        heap_address = data["heap_address"]
+        name_btree_address = data["name_btree_address"]
+        order_btree_address = data.get("order_btree_address", None)
+        if name_btree_address:
+            yield from self._iter_links_btree_v2(name_btree_address, order_btree_address, heap_address)
+
+    def _iter_links_btree_v2(self, name_btree_address, order_btree_address, heap_address):
+        """ Retrieve links from symbol table message. """
+        heap = FractalHeap(self.fh, heap_address)
+        if order_btree_address:
+            btree = BTreeV2GroupOrders(self.fh, order_btree_address)
+        else:
+            btree = BTreeV2GroupNames(self.fh, name_btree_address)
+        adict = dict()
+        for record in btree.iter_records():
+            data = heap.get_data(record["heapid"])
+            creationorder, item = self._decode_link_msg(data, 0)
+            adict[creationorder] = item
+        for creationorder, value in sorted(adict.items()):
+            yield value
+
+    @staticmethod
+    def _decode_link_info_msg(data, offset):
+        version, flags = struct.unpack_from('<BB', data, offset)
+        assert version == 0
+        offset += 2
+        if flags & 1:
+            # creation order present
+            offset += 8
+
+        if flags & 2:
+            fmt = LINK_INFO_MSG2
+        else:
+            fmt = LINK_INFO_MSG1
+        data = _unpack_struct_from(fmt, data, offset)
+        return {k: None if v == UNDEFINED_ADDRESS else v for k, v in data.items()}
 
     @property
     def is_dataset(self):
@@ -583,8 +645,6 @@ def determine_data_shape(buf, offset):
 # integers, unless otherwise noted in the description of a field. Additionally,
 # all metadata fields are stored in little-endian byte order.
 
-UNDEFINED_ADDRESS = struct.unpack('<Q', b'\xff\xff\xff\xff\xff\xff\xff\xff')[0]
-
 
 GLOBAL_HEAP_ID = OrderedDict((
     ('collection_address', 'Q'),  # 8 byte addressing
@@ -678,6 +738,20 @@ def determine_data_shape(buf, offset):
     ('heap_address', 'Q'),      # 8 byte addressing
 ))
 
+
+LINK_INFO_MSG1 = OrderedDict((
+    ('heap_address', 'Q'),         # 8 byte addressing
+    ('name_btree_address', 'Q'),   # 8 bytes addressing
+))
+
+
+LINK_INFO_MSG2 = OrderedDict((
+    ('heap_address', 'Q'),         # 8 byte addressing
+    ('name_btree_address', 'Q'),   # 8 bytes addressing
+    ('order_btree_address', 'Q')   # 8 bytes addressing
+))
+
+
 # IV.A.2.f. The Data Storage - Fill Value Message
 FILLVAL_MSG_V1V2 = OrderedDict((
     ('version', 'B'),
diff --git a/pyfive/misc_low_level.py b/pyfive/misc_low_level.py
index 9f45875..40d39f0 100644
--- a/pyfive/misc_low_level.py
+++ b/pyfive/misc_low_level.py
@@ -1,11 +1,16 @@
 """ Misc low-level representation of HDF5 objects. """
 
 import struct
+from math import log2
 from collections import OrderedDict
 
-from .core import _padded_size, _structure_size
-from .core import _unpack_struct_from, _unpack_struct_from_file
+from .core import _padded_size
+from .core import _structure_size
+from .core import _unpack_struct_from
+from .core import _unpack_struct_from_file
+from .core import _unpack_integer
 from .core import InvalidHDF5File
+from .core import UNDEFINED_ADDRESS
 
 
 class SuperBlock(object):
@@ -157,6 +162,178 @@ def objects(self):
         return self._objects
 
 
+class FractalHeap(object):
+    """
+    HDF5 Fractal Heap.
+    """
+
+    def __init__(self, fh, offset):
+
+        fh.seek(offset)
+        header = _unpack_struct_from_file(FRACTAL_HEAP_HEADER, fh)
+        assert header['signature'] == b'FRHP'
+        assert header['version'] == 0
+
+        if header['filter_info_size']:
+            raise NotImplementedError
+
+        if header["btree_address_huge_objects"] == UNDEFINED_ADDRESS:
+            header["btree_address_huge_objects"] = None
+        else:
+            raise NotImplementedError
+
+        if header["root_block_address"] == UNDEFINED_ADDRESS:
+            header["root_block_address"] = None
+
+        nbits = header["log2_maximum_heap_size"]
+        block_offset_size = self._min_size_nbits(nbits)
+        h = OrderedDict((
+            ('signature', '4s'),
+            ('version', 'B'),
+            ('heap_header_adddress', 'Q'),
+            ('block_offset', '{}s'.format(block_offset_size))
+        ))
+        self.indirect_block_header = h.copy()
+        self.indirect_block_header_size = _structure_size(h)
+        if (header["flags"] & 2) == 2:
+            h['checksum'] = 'I'
+        self.direct_block_header = h
+        self.direct_block_header_size = _structure_size(h)
+
+        maximum_dblock_size = header['maximum_direct_block_size']
+        nbits = header['log2_maximum_heap_size']
+        self._managed_object_offset_size = self._min_size_nbits(nbits)
+        value = min(maximum_dblock_size, header['max_managed_object_size'])
+        self._managed_object_length_size = self._min_size_integer(value)
+
+        start_block_size = header['starting_block_size']
+        table_width = header['table_width']
+        if not start_block_size:
+            assert NotImplementedError
+
+        log2_maximum_dblock_size = int(log2(maximum_dblock_size))
+        assert 2**log2_maximum_dblock_size == maximum_dblock_size
+        log2_start_block_size = int(log2(start_block_size))
+        assert 2**log2_start_block_size == start_block_size
+        self._max_direct_nrows = log2_maximum_dblock_size - log2_start_block_size + 2
+
+        log2_table_width = int(log2(table_width))
+        assert 2**log2_table_width == table_width
+        self._indirect_nrows_sub = log2_table_width + log2_start_block_size - 1
+
+        self.header = header
+        self.nobjects = header["managed_object_count"] + header["huge_object_count"] + header["tiny_object_count"]
+
+        managed = []
+        root_address = header["root_block_address"]
+        if root_address:
+            nrows = header["indirect_current_rows_count"]
+            if nrows:
+                for data in self._iter_indirect_block(fh, root_address, nrows):
+                    managed.append(data)
+            else:
+                data = self._read_direct_block(fh, root_address, start_block_size)
+                managed.append(data)
+        self.managed = b"".join(managed)
+
+    def _read_direct_block(self, fh, offset, block_size):
+        fh.seek(offset)
+        data = fh.read(block_size)
+        header = _unpack_struct_from(self.direct_block_header, data)
+        header["signature"] == b"FHDB"
+        return data
+
+    def get_data(self, heapid):
+        firstbyte = heapid[0]
+        reserved = firstbyte & 15  # bit 0-3
+        idtype = (firstbyte >> 4) & 3  # bit 4-5
+        version = firstbyte >> 6  # bit 6-7
+        data_offset = 1
+        if idtype == 0: # managed
+            assert version == 0
+            nbytes = self._managed_object_offset_size
+            offset = _unpack_integer(nbytes, heapid, data_offset)
+            data_offset += nbytes
+
+            nbytes = self._managed_object_length_size
+            size = _unpack_integer(nbytes, heapid, data_offset)
+
+            return self.managed[offset:offset+size]
+        elif idtype == 1: # tiny
+            raise NotImplementedError
+        elif idtype == 2: # huge
+            raise NotImplementedError
+        else:
+            raise NotImplementedError
+
+    def _min_size_integer(self, integer):
+        """ Calculate the minimal required bytes to contain an integer. """
+        return self._min_size_nbits(integer.bit_length())
+
+    @staticmethod
+    def _min_size_nbits(nbits):
+        """ Calculate the minimal required bytes to contain a number of bits. """
+        return nbits // 8 + min(nbits % 8, 1)
+
+    def _read_integral(self, fh, nbytes):
+        num = fh.read(nbytes)
+        num = struct.unpack("{}s".format(nbytes))[0]
+        return int.from_bytes(num, byteorder="little", signed=False)
+
+    def _iter_indirect_block(self, fh, offset, nrows):
+        fh.seek(offset)
+        header = _unpack_struct_from_file(self.indirect_block_header, fh)
+        header["signature"] == b"FHIB"
+        header["block_offset"] = int.from_bytes(header["block_offset"], byteorder="little", signed=False)
+        ndirect, nindirect = self._indirect_info(nrows)
+
+        direct_blocks = list()
+        for i in range(ndirect):
+            address = struct.unpack('<Q', fh.read(8))[0]
+            if address == UNDEFINED_ADDRESS:
+                break
+            block_size = self._calc_block_size(i)
+            direct_blocks.append((address, block_size))
+
+        indirect_blocks = list()
+        for i in range(ndirect, ndirect+nindirect):
+            address = struct.unpack('<Q', fh.read(8))[0]
+            if address == UNDEFINED_ADDRESS:
+                break
+            block_size = self._calc_block_size(i)
+            nrows = self._iblock_nrows_from_block_size(block_size)
+            indirect_blocks.append((address, nrows))
+
+        for address, block_size in direct_blocks:
+            obj = self._read_direct_block(fh, address, block_size)
+            yield obj
+
+        for address, nrows in indirect_blocks:
+            for obj in self._iter_indirect_block(fh, address, nrows):
+                yield obj
+
+    def _calc_block_size(self, iblock):
+        row = iblock//self.header["table_width"]
+        return 2**max(row-1, 0) * self.header['starting_block_size']
+
+    def _iblock_nrows_from_block_size(self, block_size):
+        log2_block_size = int(log2(block_size))
+        assert 2**log2_block_size == block_size
+        return log2_block_size - self._indirect_nrows_sub
+
+    def _indirect_info(self, nrows):
+        table_width = self.header['table_width']
+        nobjects = nrows * table_width
+        ndirect_max = self._max_direct_nrows * table_width
+        if nrows <= ndirect_max:
+            ndirect = nobjects
+            nindirect = 0
+        else:
+            ndirect = ndirect_max
+            nindirect = nobjects - ndirect_max
+        return ndirect, nindirect
+
+
 FORMAT_SIGNATURE = b'\211HDF\r\n\032\n'
 
 # Version 0 SUPERBLOCK
@@ -248,3 +425,37 @@ def objects(self):
     ('object_size', 'Q')    # 8 byte addressing
 ))
 GLOBAL_HEAP_OBJECT_SIZE = _structure_size(GLOBAL_HEAP_OBJECT)
+
+# III.G. Disk Format: Level 1G - Fractal Heap
+FRACTAL_HEAP_HEADER = OrderedDict((
+    ('signature', '4s'),
+    ('version', 'B'),
+
+    ('object_index_size', 'H'),
+    ('filter_info_size', 'H'),
+    ('flags', 'B'),
+
+    ('max_managed_object_size', 'I'),
+    ('next_huge_object_index', 'Q'),       # 8 byte addressing
+    ('btree_address_huge_objects', 'Q'),   # 8 byte addressing
+
+    ('managed_freespace_size', 'Q'),       # 8 byte addressing
+    ('freespace_manager_address', 'Q'),    # 8 byte addressing
+    ('managed_space_size', 'Q'),           # 8 byte addressing
+    ('managed_alloc_size', 'Q'),           # 8 byte addressing
+    ('next_directblock_iterator_address', 'Q'), # 8 byte addressing
+
+    ('managed_object_count', 'Q'),         # 8 byte addressing
+    ('huge_objects_total_size', 'Q'),      # 8 byte addressing
+    ('huge_object_count', 'Q'),            # 8 byte addressing
+    ('tiny_objects_total_size', 'Q'),      # 8 byte addressing
+    ('tiny_object_count', 'Q'),            # 8 byte addressing
+
+    ('table_width', 'H'),
+    ('starting_block_size', 'Q'),          # 8 byte addressing
+    ('maximum_direct_block_size', 'Q'),    # 8 byte addressing
+    ('log2_maximum_heap_size', 'H'),
+    ('indirect_starting_rows_count', 'H'),
+    ('root_block_address', 'Q'),           # 8 byte addressing
+    ('indirect_current_rows_count', 'H'),
+))


Test patch:
diff --git a/tests/make_new_style_groups_file.py b/tests/make_new_style_groups_file.py
new file mode 100644
index 0000000..9e55cb4
--- /dev/null
+++ b/tests/make_new_style_groups_file.py
@@ -0,0 +1,9 @@
+#! /usr/bin/env python
+""" Create a HDF5 file with new-style groups. """
+import h5py
+import numpy as np
+
+
+f = h5py.File('new_style_groups.hdf5', 'w', track_order=True)
+for i in range(9):
+    f.create_group('group' + str(i))
diff --git a/tests/new_style_groups.hdf5 b/tests/new_style_groups.hdf5
new file mode 100644
index 0000000..555a1c7
Binary files /dev/null and b/tests/new_style_groups.hdf5 differ
diff --git a/tests/test_fletcher32.py b/tests/test_fletcher32.py
index e7858ea..40b41d1 100644
--- a/tests/test_fletcher32.py
+++ b/tests/test_fletcher32.py
@@ -6,7 +6,7 @@
 from numpy.testing import assert_array_equal
 
 import pyfive
-from pyfive.btree import _verify_fletcher32
+from pyfive.btree import BTreeV1RawDataChunks
 
 DIRNAME = os.path.dirname(__file__)
 DATASET_FLETCHER_HDF5_FILE = os.path.join(DIRNAME, 'fletcher32.hdf5')
@@ -35,4 +35,4 @@ class TestChunkFletcher32(unittest.TestCase):
     def test_fletcher32_invalid(self):
         bad_chunk = b'\x00\x00\x00\x01'
         with self.assertRaises(ValueError) as context:
-            _verify_fletcher32(bad_chunk)
+            BTreeV1RawDataChunks._verify_fletcher32(bad_chunk)
diff --git a/tests/test_new_style_groups.py b/tests/test_new_style_groups.py
new file mode 100644
index 0000000..db6d534
--- /dev/null
+++ b/tests/test_new_style_groups.py
@@ -0,0 +1,15 @@
+""" Test new style groups in pyfive. """
+import os
+import pyfive
+
+DIRNAME = os.path.dirname(__file__)
+NEW_STYLE_GROUPS_HDF5_FILE = os.path.join(DIRNAME, "new_style_groups.hdf5")
+
+
+def test_groups():
+    with pyfive.File(NEW_STYLE_GROUPS_HDF5_FILE) as hfile:
+        assert len(hfile) == 9
+        # test that the objects are stored in the correct order
+        # (file was created with track_order=True)
+        for i, grp in enumerate(hfile):
+            assert grp == "group{:d}".format(i)