ACCESSING QUEUE DATA

• US 20200133855A1
• Filed: 10/31/2019
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Hangzhou Dptech Technologies Co., Ltd.
• Original Assignee: Hangzhou Dptech Technologies Co., Ltd.
• Inventors: TAN, Tian
• Granted Patent: US 11,385,900 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 2205/064 Linked list, i.e. structure using pointers, e.g. allowing non-contiguous address segments in one logical buffer or dynamic buffer space allocation
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 5/06 for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor G06F7/78 takes precedence
• CPC Class Codes: G06F 9/3856 Reordering of instructions, e.g. using queues or age tags

Abstract

A method and apparatus of accessing queue data is provided. According to the method, a double-layer circular queue is constructed, where the double-layer circular queue includes one or more inner-layer circular queues established based on an array, and the one or more inner-layer circular queues constitute an outer-layer circular queue of the double-layer circular queue based on a linked list. A management pointer of the outer-layer circular queue is set. Data accessing is performed on the inner-layer circular queues by using the management pointer.

Claims

1. A method of accessing queue data, comprising:

constructing a double-layer circular queue, wherein the double-layer circular queue comprises one or more inner-layer circular queues established in an array manner, and the one or more inner-layer circular queues constitute an outer-layer circular queue of the double-layer circular queue in a linked list manner;

setting a management pointer for the outer-layer circular queue; and

performing data accessing on the inner-layer circular queues based on the management pointer.

2. The method according to claim 1, wherein said constructing a double-layer circular queue comprises:

establishing one or more inner-layer circular queues in an array manner, and allocating a memory block with a continuous address space to each inner-layer circular queue, wherein the memory block is allocated in a page alignment manner and has a preset size;

obtaining an outer-layer circular queue by series-connecting each inner-layer circular queue as a node in a linked list manner.

3. The method according to claim 2, wherein, said setting a management pointer for the outer-layer circular queue comprises:

setting a FIRST pointer and a LAST pointer for the outer-layer circular queue;

wherein the FIRST pointer points to a first node of the outer-layer circular queue and the inner-layer circular queue corresponding to the first node is non-empty;

the LAST pointer points to a last node of the outer-layer circular queue and the inner-layer circular queue corresponding to the last node is non-empty.

4. The method according to claim 3, wherein said performing data accessing on the inner-layer circular queues based on the management pointer comprises:

storing data in a memory block corresponding to the inner-layer circular queue based on a space state of the inner-layer circular queue of a node pointed by the management pointer; and

reading data from the memory block corresponding to the inner-layer circular queue based on the space state of the inner-layer circular queue of the node pointed by the management pointer.

5. The method according to claim 4, wherein said storing data in a memory block corresponding to the inner-layer circular queue based on a space state of the inner-layer circular queue of a node pointed by the management pointer comprises:

determining whether there is an idle memory space in the inner-layer circular queue corresponding to the node pointed by the LAST pointer of the outer-layer circular queue;

storing data in the inner-layer circular queue when there is the idle memory space.

6. The method according to claim 5, wherein, the method further comprising:

determining whether there is a node after the node pointed by the LAST pointer of the outer-layer circular queue when there is no idle memory space;

when determining that there is a node,

pointing the LAST pointer of the outer-layer circular queue to the node after the node pointed by the LAST pointer;

when determining that there is no node,

establishing an inner-layer circular queue as a new node and adding the new node into the outer-layer circular queue, and pointing the LAST pointer of the outer-layer circular queue to the new node;

storing data into the inner-layer circular queue corresponding to the node pointed by the LAST pointer of the outer-layer circular queue.

7. The method according to claim 4, wherein said reading data from the memory block corresponding to the inner-layer circular queue based on the space state of the inner-layer circular queue of the node pointed by the management pointer comprises:

determining whether the inner-layer circular queue corresponding to the node pointed by the FIRST pointer of the outer-layer circular queue is empty;

determining that the double-layer circular queue is empty when the inner-layer circular queue is empty;

reading data out from the inner-layer circular queue corresponding to the node pointed by the FIRST pointer of the outer-layer circular queue when the inner-layer circular queue is non-empty.

8. The method according to claim 7, wherein, the method further comprising:

if the inner-layer circular queue corresponding to the node pointed by the FIRST pointer is empty after the data is taken out,

taking out the node pointed by the FIRST pointer from the outer-layer circular queue and inserting the node pointed by the FIRST pointer after the node pointed by the LAST pointer of the outer-layer circular queue.

9. An apparatus for accessing queue data, comprising:

a processor; and

a non-transitory storage medium storing machine-executable instructions, wherein by reading and executing the machine executable instructions, the processor is caused to;

construct a double-layer circular queue, wherein the double-layer circular queue comprises one or more inner-layer circular queues established in an array manner, and the one or more inner-layer circular queues constitute an outer-layer circular queue of the double-layer circular queue in a linked list manner;

set a management pointer for the outer-layer circular queue; and

perform data accessing on the inner-layer circular queues based on the management pointer.

10. The apparatus according to claim 9, wherein when the double-layer circular queue is constructed, the processor is further caused by the machine executable instructions to:

establish one or more inner-layer circular queues in an array manner, and allocate a memory block with a continuous address space to each inner-layer circular queue, wherein the memory block is allocated in a page alignment manner and has a preset size;

obtain an outer-layer circular queue by series-connecting each inner-layer circular queue as a node in a linked list manner.

11. The apparatus according to claim 10, wherein the management pointer for the outer-layer circular queue comprises a FIRST pointer and a LAST pointer;

wherein the FIRST pointer points to a first node of the outer-layer circular queue and the inner-layer circular queue corresponding to the first node is non-empty;

the LAST pointer points to a last node of the outer-layer circular queue and the inner-layer circular queue corresponding to the last node is non-empty.

12. The apparatus according to claim 11, wherein when data accessing is performed on the inner-layer circular queues based on the management pointer, the processor is further caused by the machine executable instructions to:

store data in a memory block corresponding to the inner-layer circular queue based on a space state of the inner-layer circular queue of a node pointed by the management pointer; and

read data from the memory block corresponding to the inner-layer circular queue based on the space state of the inner-layer circular queue of the node pointed by the management pointer.

13. The apparatus according to claim 12, wherein when data is stored in a memory block corresponding to the inner-layer circular queue based on a space state of the inner-layer circular queue of a node pointed by the management pointer, the processor is further caused by the machine executable instructions to:

determine whether there is an idle memory space in the inner-layer circular queue corresponding to the node pointed by the LAST pointer of the outer-layer circular queue;

store data in the inner-layer circular queue when there is the idle memory space.

14. The apparatus according to claim 13, wherein the processor is further caused by the machine executable instructions to:

determine whether there is a node after the node pointed by the LAST pointer of the outer-layer circular queue when there is no idle memory space;

when determining that there is a node,

point the LAST pointer of the outer-layer circular queue to the node after the node pointed by the LAST pointer;

when determining that there is no node,

establish an inner-layer circular queue as a new node and add the new node into the outer-layer circular queue, and point the LAST pointer of the outer-layer circular queue to the new node;

store data into the inner-layer circular queue corresponding to the node pointed by the LAST pointer of the outer-layer circular queue.

15. The apparatus according to claim 12, wherein when data is read from the memory block corresponding to the inner-layer circular queue based on the space state of the inner-layer circular queue of the node pointed by the management pointer, the processor is further caused by the machine executable instructions to:

determine whether the inner-layer circular queue corresponding to the node pointed by the FIRST pointer of the outer-layer circular queue is empty;

determine that the double-layer circular queue is empty when the inner-layer circular queue is empty;

read data out from the inner-layer circular queue corresponding to the node pointed by the FIRST pointer of the outer-layer circular queue when the inner-layer circular queue is non-empty.

16. The apparatus according to claim 15, wherein the processor is further caused by the machine executable instructions to:

if the inner-layer circular queue corresponding to the node pointed by the FIRST pointer is empty after the data is taken out,

take out the node pointed by the FIRST pointer from the outer-layer circular queue and insert the node pointed by the FIRST pointer after the node pointed by the LAST pointer of the outer-layer circular queue.