Change Details

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. Combine the left-case and right-case codes in the COLOR functions into a single code, in each case, with a variable indicating the direction of the case. Change the representation of the pointers from three named pointers to an array of three pointers, so that this code can use array indexing to avoid branching. ``` foreach ($list as $item) { work_miracles($item); } ``` 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.

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. Combine the left-case and right-case codes in the COLOR functions into a single code, in each case, with a variable indicating the direction of the case. Change the representation of the pointers from three named pointers to an array of three pointers, so that this code can use array indexing to avoid branching. 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.

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. Combine the left-case and right-case codes in the COLOR functions into a single code, in each case, with a variable indicating the direction of the case. Change the representation of the pointers from three named pointers to an array of three pointers, so that this code can use array indexing to avoid branching. ``` foreach ($list as $item) { work_miracles($item); } ``` 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.