Patent ID: 8312457

Claim:
A computer implemented method for maintaining a count of nodes in a stack in a lock free manner, the stack represented by a linked list of nodes, each node including a data field, a next pointer field, and an index field, the data field storing a data value, the next pointer field storing a next pointer value, the next point value pointing to the next node following the node in the stack, the index field storing an index value used to calculate how many other nodes exist on the stack prior to the node, the method being implemented by a computer system having at least one processor and system memory, the stack being accessible by a plurality of concurrently executing threads running at the computer system, the method comprising: an act of receiving an indication from one of the concurrently executing threads that a first node is to be added to the stack; an act of using a head pointer to access a current head node of the stack, the head pointer pointing to the current head node; an act of accessing an index value from an index value field of the current head node, the index value being an numeric value representative of the current number of nodes linked within the stack; an act of generating an updated index value for the first node based on the index value of the current head node and subsequent to accessing the index value; an act of storing the updated index value in an index field of the first node, the updated index value being a numeric value representative of the current number of nodes linked within the stack including the first node; an act of updating the head pointer to point to the first node, updating the head pointer making the first node the head node for the stack such that the number of nodes linked within the stack remains accessible via the head pointer.