Change Details

Change RB_REMOVE to avoid reading the same values from memory more than once, avoid modifying the fields of the item being removed, and to avoid writing the same data twice.

Make changes to the code that alters rb-trees so that the same memory isn't read several times to get information that could have been read and remembered the first time, and so that a write to memory isn't made when it would be quickly be followed by another write of different data to the same location. Change RB_REMOVE to read all the fields from the departing node at the start, to avoid reading any of them again. Avoid writing to any of them either. Change the RB_COLOR routines to read the parent+color bits one time, not several times. Also, change rotation macros to stop establishing the links between the rising node and its new parent; in double-rotation, those links are short-lived after the first rotation, so its better to fix the parent-child pointers after all rotations complete. Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up a value already available. Change the RB_SWAP_CHILD macro to take a parent parameter, instead of extracting the parent value from the out parameter. Make adjustments to a linux rbtree header, which invokes each of these.

Change RB_REMOVE to avoid reading the same values from memory more than onceMake changes to the code that alters rb-trees so that the same memory isn't read several times to get information that could have been read and remembered the first time, and so that a write to memory isn't made when it would be quickly be followed by another write of different data to the same location. Change RB_REMOVE to read all the fields from the departing node at the start, to avoid reading any of them again. Avoid writing to any of them either. Change the RB_COLOR routines to read the parent+color bits one time, not several times. Also, change rotation macros to stop establishing the links between the rising node and its new parent; in double-rotation, those links are short-lived after the first rotation, so its better to fix the parent-child pointers after all rotations complete. Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up a value already available. Change the RB_SWAP_CHILD macro to take a parent parameter, avoid modifyinstead of extracting the fields ofparent value from the item being removedout parameter. Make adjustments to a linux rbtree header, and to avoid writing the same data twicewhich invokes each of these.