Self-ordering buffer

1. A method comprising:

generating a plurality of nodes forming a linked list, each node in the linked list having a directional pointer referencing a subsequent node in the linked list and a data pointer referencing a corresponding memory block from a plurality of memory blocks;

generating a head pointer, the head pointer referencing a beginning node in the linked list;

generating a tail pointer, the tail pointer referencing an end node in the linked list;

generating a next pointer, the next pointer referencing a next node of the linked list; and

generating a free pointer, the free pointer referencing a free node of the linked list,

wherein the plurality of nodes forming the linked list, the corresponding memory blocks, the head pointer, the tail pointer, the next pointer, and the free pointer form a buffer,

wherein the buffer is a self-ordering buffer capable of maintaining an order while a read request, a write request, and a delete request are executed simultaneously and utilizing free memory blocks as a result of out of order deletions.

2. The method of claim 1 , further comprising:

receiving the read request;

identifying the next node of the linked list referenced by the next pointer;

returning data stored in a memory block referenced by the data pointer of the next node; and

modifying the next pointer to reference a subsequent node of the linked list.

3. The method of claim 1 , further comprising:

receiving the write request, the write request including data to be written to the buffer;

identifying the free node referenced by the free pointer;

writing the data to a memory block referenced by a data pointer of the free node; and

modifying the free pointer to reference a subsequent node from the linked list.

4. The method of claim 1 , further comprising:

receiving the delete request to delete data, the data being stored in a memory block and the memory block being referenced by a data pointer included in a specific node of the linked list; and

moving the specific node to a free section of the linked list.

5. The method of claim 4 , wherein moving the specific node to a free section of the linked list comprises:

identifying a directional pointer of a prior node to the specific node in the linked list, the prior node including a directional pointer referencing the specific node;

identifying a subsequent node to the specific node of the linked list, the subsequent node being referenced by a directional pointer of the specific node;

modifying the directional pointer of the prior node to reference the subsequent node of the linked list;

modifying a directional pointer of the end node to reference the specific node;

modifying the directional pointer of the specific node to reference a null indicator; and

modifying the tail pointer to reference the specific node.

6. The method of claim 5 , further comprising:

applying a deletion lock to the buffer in response to receiving two or more simultaneous delete requests; and

removing the deletion lock from the buffer upon completion of the delete requests.

7. The method of claim 1 , wherein the buffer is a part of a single-producer, multi-reader, and multi-remover software pipeline system.

8. The method of claim 1 , further comprising:

receiving simultaneous commands at different nodes in the linked list, the commands including one or more of the read request, the write request, and the delete request.

9. The method of claim 1 , further comprising:

determining that two or more of the head pointer, the tail pointer, the free pointer, and the next pointer reference a common node of the linked list; and

providing an indication to the buffer in response to that determination.

10. A system comprising:

a processor: and

a memory storing instructions that, when executed by the processor, cause the system to:

generate a plurality of nodes forming a linked list, each node in the linked list having a directional pointer referencing a subsequent node in the linked list and a data pointer referencing a corresponding memory block from a plurality of memory blocks;

generate a head pointer, the head pointer referencing a beginning node in the linked list;

generate a tail pointer, the tail pointer referencing an end node in the linked list;

generate a next pointer, the next pointer referencing a next node of the linked list; and

generate a free pointer, the free pointer referencing a free node of the linked list,

wherein the plurality of nodes forming the linked list, the corresponding memory blocks, the head pointer, the tail pointer, the next pointer, and the free pointer form a buffer, wherein the buffer is a self-ordering buffer capable of maintaining an order while a read request, a write request, and a delete request are executed simultaneously and utilizing free memory blocks as a result of out of order deletions.

11. The system of claim 10 , wherein the instructions, when executed, further cause the system to:

receive the read request;

identify the next node of the linked list referenced by the next pointer;

return data stored in a memory block referenced by the data pointer of the next node; and

modify the next pointer to reference a subsequent node of the linked list.

12. The system of claim 10 , wherein the instructions, when executed, further cause the system to:

receive the write request, the write request including data to be written to the buffer;

identify the free node referenced by the free pointer;

write the data to a memory block referenced by a data pointer of the free node; and

modify the free pointer to reference a subsequent node from the linked list.

13. The system of claim 10 , wherein the instructions, when executed, further cause the system to:

receive the delete request to delete data, the data being stored in a memory block and the memory block being referenced by a data pointer included in a specific node of the linked list; and

move the specific node to a free section of the linked list.

14. The system of claim 13 , wherein the instruction to move the specific node to a free section of the linked list causes the system to:

identify a directional pointer of a prior node to the specific node in the linked list, the prior node including a directional pointer referencing the specific node;

identify a subsequent node to the specific node of the linked list, the subsequent node being referenced by a directional pointer of the specific node;

modify the directional pointer of the prior node to reference the subsequent node of the linked list;

modify a directional pointer of the end node to reference the specific node;

modify the directional pointer of the specific node to reference a null indicator; and

modify the tail pointer to reference the specific node.

15. The system of claim 10 , wherein the buffer is a part of a single-producer, multi-reader, and multi-remover software pipeline system.

16. The system of claim 10 , wherein the instructions, when executed, further cause the system to:

receive simultaneous commands at different nodes in the linked list, the commands including one or more of the read request, the write request, and the delete request.

17. A computer program product comprising a non-transitory computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

generate a plurality of nodes forming a linked list, each node in the linked list having a directional pointer referencing a subsequent node in the linked list and a data pointer referencing a corresponding memory block from a plurality of memory blocks;

generate a head pointer, the head pointer referencing a beginning node in the linked list;

generate a tail pointer, the tail pointer referencing an end node in the linked list;

generate a next pointer, the next pointer referencing a next node of the linked list; and

generate a free pointer, the free pointer referencing a free node of the linked list,

wherein the plurality of nodes forming the linked list, the corresponding memory blocks,

the head pointer, the tail pointer, the next pointer, and the free pointer form a buffer,

wherein the buffer is a self-ordering buffer capable of maintaining an order while a read request, a write request, and a delete request are executed simultaneously and utilizing free memory blocks as a result of out of order deletions.

18. The computer program product of claim 17 , wherein the computer readable program, when executed on a computer, further causes the computer to:

receive the read request;

identify the next node of the linked list referenced by the next pointer;

return data stored in a memory block referenced by the data pointer of the next node; and

modify the next pointer to reference a subsequent node of the linked list.

19. The computer program product of claim 17 , wherein the computer readable program, when executed on a computer, further causes the computer to:

receive the write request, the write request including data to be written to the buffer;

identify the free node referenced by the free pointer;

write the data to a memory block referenced by a data pointer of the free node; and

modify the free pointer to reference a subsequent node from the linked list.

20. The computer program product of claim 17 , wherein the computer readable program, when executed on a computer, further causes the computer to:

receive the delete request to delete data, the data being stored in a memory block and the memory block being referenced by a data pointer included in a specific node of the linked list; and

move the specific node to a free section of the linked list.

21. The computer program product of claim 20 , wherein the computer readable program, when executed on a computer, causes the computer to:

identify a directional pointer of a prior node to the specific node in the linked list, the prior node including a directional pointer referencing the specific node;

identify a subsequent node to the specific node of the linked list, the subsequent node being referenced by a directional pointer of the specific node;

modify the directional pointer of the prior node to reference the subsequent node of the linked list;

modify a directional pointer of the end node to reference the specific node;

modify the directional pointer of the specific node to reference a null indicator; and

modify the tail pointer to reference the specific node.

22. The computer program product of claim 17 , wherein the buffer is a part of a single-producer, multi-reader, and multi-remover software pipeline system.

23. The computer program product of claim 17 , wherein the computer readable program, when executed on a computer, further causes the computer to:

receive simultaneous commands at different nodes in the linked list, the commands including one or more of the read request, the write request, and the delete request.