| 主权项 |
1. A computer-implemented method for popping a tail element off of an N-way linked list in a computer memory, the N-way linked list for storing a plurality of elements, and having N linked sub-lists, a list order, and a handle, the handle having a sub-list tail handle for each of the sub-lists, each sub-list tail handle identifying a location of a tail of element of the respective sub-list or a maker indicating that the sub-list is empty, each element being in one of the N sub-lists and including a pointer to a next sequential element in a same sub-list, comprising:
performing a first atomic memory operation to:
determine which particular sub-list includes the tail element of the list,mark a sub-list tail handle of the particular sub-list with a designation indicating that the particular sub-list is involved in a pop process, anddetermine the location of the tail element of the particular sub-list; reading the tail element to determine a location of a next sequential element in the particular sub-list; and performing a second atomic memory operation to:
write the location of the next sequential element in the particular sub-list to the sub-list tail handle of the particular sub-list, thereby designating the next sequential element as a new tail element of the particular sub-list, andremove the mark designating that the particular sub-list is involved in a pop process from the sub-list tail handle of the particular sub-list. |
