Updating a data structure

An apparatus comprising one or more computer readable media having instructions stored thereon and configured to result in at least the following:

• retrieving data from a first element of a data structure;
• determining, based on the data retrieved from the first element, whether an update to data in the first element might necessitate an update to data in a second element of the data structure;
• and
• deciding, based on the determination, whether to lock the data structure during an update to data in the data structure.

An apparatus comprising:

• means for receiving data from a first portion of a data structure;
• means for determining, based on the data received from the first portion, whether an update to data in the first portion might cause a change to data in a second portion of the data structure;
• and
• means for determining, based on a result of determining whether an update to data in the first portion might cause a change to data in a second portion, whether to lock the data structure during an update to data in the data structure.

A method comprising:

• accessing data in a low-order portion of a target counter, the target counter also including a high-order portion;
• determining, based on the data accessed from the low-order portion, whether an update to the low-order portion could cause a roll-over of the low-order portion into the high-order portion;
• and
• determining, based on the roll-over determination, whether to lock the target counter during an update to data in the target counter.

An apparatus comprising one or more computer readable media having instructions stored thereon and configured to result in at least the following:

• receiving data in a low-order portion of a target counter, the target counter also including a high-order portion;
• determining, based on the data received from the low-order portion, that an update to the low-order portion could not cause a roll-over of the low-order portion into the high-order portion;
• deciding, based on the no-roll-over determination, not to lock the target counter during an update to data in the target counter;
• accessing data from a source counter, the source counter having a size that is smaller than a size of the target counter;
• determining that the data in the low-order portion of the target counter has not changed since the no roll-over determination;
• and
• updating, after determining that the data in the low-order portion has not changed, the low-order portion of the target counter with the data accessed from the source counter,
• wherein the determining that the data has not changed and the updating of the low-order portion are performed using a single atomic instruction.

A method comprising:

• accessing data in a first portion of a source data structure;
• determining, based on the data accessed from the first portion of the source data structure, whether data in a second portion of the source data structure may have changed since a previous access of the data in the first portion of the source data structure;
• and
• determining, based on the determination of whether the data in the second portion has changed, whether to lock a target data structure while storing all or part of data from the source data structure into the target data structure.