Change Details

Maintain a pointer to an element in the iommu_gas_entries tree that is left of the first free gap in the tree and start the search for free space there, rather than at the root of the tree. The element is the rightmost such element, except possibly after an insertion that exactly fills up the first free gap. In that case, the next insertion finds the first free gap and updates the pointer.

Maintain a pointer to an element in the iommu_gas_entries tree that is left of the first sufficiently large free gap in the tree and start the search for free space there, rather than at the root of the tree. The element is the rightmost such element, except possibly after an insertion that exactly fills up the first free gap. Define RB_INSERT_NEXT and RB_INSERT_PREV to insert items in the RB tree that are known to follow or precede a given item, to avoid starting a search at the tree root or using comparisons. Use these to insert a new node when space is found in the iommu_gas_entries tree.

Maintain a pointer to an element in the iommu_gas_entries tree that is left of the first sufficiently large free gap in the tree and start the search for free space there, rather than at the root of the tree. The element is the rightmost such element, except possibly after an insertion that exactly fills up the first free gap. In that case Define RB_INSERT_NEXT and RB_INSERT_PREV to insert items in the RB tree that are known to follow or precede a given item, the next insertion finds the first free gap and updates the pointero avoid starting a search at the tree root or using comparisons. Use these to insert a new node when space is found in the iommu_gas_entries tree.