Structure and method for maintaining ordered linked lists

• US 7,685,121 B2
• Filed: 10/10/2002
• Issued: 03/23/2010
• Est. Priority Date: 10/10/2002
• Status: Expired due to Fees

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Emulex Corporation (Broadcom, Inc.)
• Inventors: Lindeborg, Carl J., Sreekanth, Jonnavithula, Brown, Robin L., Kung, Hsiang-Tsung
• Primary Examiner(s): Ehichioya; Fred I
• Application Number:
  US10/268,178
• Publication Number:
  US 20040073553A1
• Time in Patent Office: 2,721 Days
• Field of Search: 707/3, 707/100, 707/102, 707/1, 707/6, 707/200, 370/328, 370/394, 370/469, 370/295, 370/395.72, 370/474, 711/136, 714/16, 709/228, 709/248, 709/204, 709/230, 713/502, 717/100, 717/116
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/166 IP fragmentation; TCP segmentation
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A hierarchically-organized linked list structure have a first level comprised of sections of sequentially-ordered segments, and a second level comprised of representatives of each of said sections at the first level. A method for maintaining the hierarchically-organized linked list structure to facilitate segment insertion, retrieval and removal.

Claims

1. In a packet-based communication system comprising a processor, a method for maintaining a linked list comprised of members ordered with respect to a predetermined ordering relationship, each member corresponding to a packet, for reassembling received packets into a message, the method comprising:

maintaining a plurality of first linked lists decoupled from each other, each comprised of a plurality of members continuously ordered with respect to said ordering relationship;

maintaining a second linked list different from any of the plurality of first linked lists, the second linked list comprised of a plurality of members, each of which includes starting and ending sequence numbers of a respective one of said plurality of first linked lists; and

walking through one or more members of the second linked list and comparing by the processor a starting sequence number of a segment to at least one of the starting and ending sequence numbers stored in each member of the second linked list to determine an appropriate first linked list from which to insert or remove the segment,

wherein each member of said second list is comprised of;

either a forward link to a next succeeding member of said second list or a null forward link; and

a field representing the relative relationship of said respective one of said first lists with respect to said ordering relationship.

2. The method of claim 1 wherein, in each of said first lists, each member is comprised of a load and either a forward link to a next succeeding member of said first list or a null forward link.

3. The method of claim 2 wherein, in each of said members of said first list, said forward link is comprises a null forward link in the absence of a next succeeding member of said first list.

4. The method of claim 1 wherein each member of said second list is comprised of either a forward link to a next succeeding member of said second list or a null forward link.

5. The method of claim 4 wherein, in each of said members of said second list, said forward link is comprises a null forward link in the absence of a next succeeding member of said second list.

6. The method of claim 4 wherein each member of said second list is further comprised of a forward link to a first member of said respective one of said first lists.

7. The method of claim 4 wherein each member of said second list is further comprised of a backward link to a last member of said respective one of said first lists.

8. The method of claim 4 wherein each member of said second list is further comprised of a starting sequence number of said first member of said respective one of said first lists.

9. The method of claim 4 wherein each member of said second list is further comprised of an ending sequence number of said last member of said respective one of said first lists.

10. The method of claim 1 wherein each member of said first list is comprised of:

a forward link to a next succeeding member of said first list or a null forward link; and

a field representing the relative relationship of said first lists with respect to said ordering relationship.

11. The method of claim 1 further comprising:

maintaining a control block comprising a forward link to a first member of said second list.

12. The method of claim 11 wherein said control block further comprises a backward link to a last member of said second list.

13. In a digital packet-based data processing system having a memory component, an ordered linked list structure of members resident in said memory component, each member corresponding to a packet, the ordered linked list structure for reassembling received packets into a message, the ordered linked list structure comprising:

a plurality of first ordered linked lists decoupled from each other, wherein, in each of said first ordered linked lists, the members are ordered in a continuous sequence, each member comprising a forward link to a next succeeding member of said first list or a null forward link; and

a second ordered linked list different from any of the plurality of the first ordered linked list, the second ordered linked list having a plurality of members, wherein each member contains starting and ending sequence numbers of the a respective one of said plurality of first ordered linked lists, the starting and ending sequence numbers usable to determine an appropriate first ordered linked list from which to insert or remove a segment,

wherein each member of said second list is comprised of a forward link to a next succeeding member of said second list or a null forward link.

14. The structure of claim 13 wherein, in each of said member members of said first list, said forward link is has a null forward link in the absence of a next succeeding member of said first list.

15. The structure of claim 13 wherein, in each of said member members of said second list, said forward link is has a null forward link in the absence of a next succeeding member of said second list.

16. The structure of claim 13 wherein each member of said second list is further comprised of a forward link to a first member of said respective one of said first lists.

17. The structure of claim 13 wherein each member of said second list is further comprised of a backward link to a last member of said respective one of said first lists.

18. The structure of claim 13 wherein each member of said second list is further comprised of a starting sequence number of said first member of said respective one of said first lists.

19. The structure of claim 13 wherein each member of said second list is further comprised of an ending sequence number of said last member of said respective one of said first lists.

20. The structure of claim 13 further comprising:

a control block comprising a forward link to a first member of said second list.

21. The structure of claim 20 wherein said control block further comprises a backward link to a last member of said second list.