Creating and searching a data structure ordered by ranges of key masks associated with the data structure

• US 6,061,679 A
• Filed: 11/25/1997
• Issued: 05/09/2000
• Est. Priority Date: 11/25/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bournas, Redha M., Garger, Valery I.
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): HAVAN, THU THAO
• Application Number:
  US08/976,933
• Time in Patent Office: 896 Days
• Field of Search: 707/3, 707/103, 707/101, 707/7, 707/102, 707/5, 707/4, 707/202, 711/202, 711/1.08, 370/392, 370/422, 370/230, 370/398, 364/253, 364/251
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A data structure, which includes a plurality of sub-data structures, is created. The sub-data structures are ordered based on ranges of key masks associated with the sub-data structures. In particular, in one example, the sub-data structures are linked in a list in ascending order of key mask ranges, thus, creating an ordered list of sub-data structures. The ordered data structure can be modified by adding new nodes to existing sub-data structures or by adding new sub-data structures. Further, nodes or sub-data structures can be removed from the ordered data structure. The data structure can also be searched in order to collect target records associated with requested keys of the data structure.

Claims

1. A method of creating a data structure in a computing environment, said method comprising:

obtaining a plurality of sub-data structures; and

ordering said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.

2. The method of claim 1, wherein said ordering comprises ordering said plurality of sub-data structures based on an ascending order of said ranges of key masks.

3. The method of claim 2, wherein said ordering comprises linking said plurality of sub-data structures in a linked list in ascending order of said ranges of key masks.

4. The method of claim 1, wherein a sub-data structure of said plurality of sub-data structures represents at least one group of one or more keys, and wherein any group associated with said sub-data structure has the same range of key mask as any other group that may be associated with said sub-data structure.

5. The method of claim 1, further comprising determining said ranges of key masks associated with said plurality of sub-data structures.

6. The method of claim 5, wherein said determining comprises for a key mask associated with a sub-data structure:

converting said key mask into a binary notation; and

counting a number of zeros within said binary notation, said number of zeros providing an indication of the range of said key mask.

7. The method of claim 6, wherein said range of said key mask is two to the power of said number of zeros.

8. The method of claim 1, wherein said plurality of sub-data structures comprises a plurality of trees.

9. The method of claim 8, wherein said plurality of trees comprises a plurality of PATRICIA trees.

10. The method of claim 1, further comprising adding another sub-data structure to said data structure, wherein said another sub-data structure is inserted in order in said data structure based on its key mask range.

11. The method of claim 1, further comprising inserting a new key into said data structure.

12. The method of claim 11, wherein said inserting comprises:

determining a key mask range for said new key;

creating a new sub-data structure when said key mask range is not within said data structure;

adding a key mask associated with said new key to an existing sub-data structure when said key mask range is within said data structure and said key mask is not among the key masks of said existing sub-data structure; and

adding said new key to said new sub-data structure or said existing sub-data structure.

13. The method of claim 1, further comprising removing one of said plurality of sub-data structures.

14. The method of claim 1, wherein said plurality of sub-data structures includes a plurality of keys, and wherein said method further comprises removing one key of said plurality of keys from one sub-data structure of said plurality of sub-data structures.

15. The method of claim 14, wherein said removing comprises using a key mask range of said one key to be removed to locate said one sub-data structure.

16. The method of claim 1, further comprising searching said data structure.

17. The method of claim 16, wherein said searching comprises searching said data structure for one or more target records associated with a requested key, said searching beginning with a more specific sub-data structure of said plurality of sub-data structures and proceeding to less specific sub-data structures of said plurality of sub-data structures until said one or more target records is collected.

18. The method of claim 16, wherein said searching comprises:

determining whether a requested key belongs to a sub-data structure of said ordered plurality of sub-data structures, said determining beginning with a first sub-data structure of said ordered plurality of sub-data structures;

selecting one or more target records associated with said requested key from said sub-data structure, when said requested key belongs to said sub-data structure;

deciding whether one or more target records is still needed for said requested key;

proceeding to a next sub-data structure of said ordered plurality of sub-data structures when said one or more target records is still needed for said requested key;

repeating said determining, selecting, and deciding at said next sub-data structure and said proceeding until no more target records are needed for said requested key.

19. The method of claim 18, wherein said determining comprises performing a bit wise AND operation with said requested key and a key mask of said sub-data structure to determine whether said requested key belongs to said sub-data structure.

20. The method of claim 1, wherein said key masks designate variations in keys of said sub-data structures.

21. The method of claim 20, wherein said keys comprise addresses.

22. The method of claim 1, wherein said obtaining comprises defining said plurality of sub-data structures.

23. The method of claim 1, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.

24. The method of claim 23, wherein each of said one or more addresses has a corresponding key mask.

25. The method of claim 1, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.

26. A memory comprising a data structure, said data structure comprising a plurality of sub-data structures ordered based on ranges of key masks associated with said plurality of sub-data structures.

27. The memory of claim 26, wherein said plurality of sub-data structures are linked in a linked list in ascending order of said ranges of key masks.

28. The memory of claim 26, wherein said key masks designate variations in keys of said sub-data structures.

29. The memory of claim 28, wherein said keys comprise addresses.

30. The memory of claim 26, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.

31. The memory of claim 30, wherein each of said one or more addresses has a corresponding key mask.

32. The memory of claim 26, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.

33. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of creating a data structure, said method comprising:

obtaining a plurality of sub-data structures; and

ordering said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.

34. The at least one program storage device of claim 33, wherein said ordering comprises ordering said plurality of sub-data structures based on an ascending order of said ranges of key masks.

35. The at least one program storage device of claim 33, wherein a sub-data structure of said plurality of sub-data structures represents at least one group of one or more keys, and wherein any group associated with said sub-data structure has the same range of key mask as any other group that may be associated with said sub-data structure.

36. The at least one program storage device of claim 33, wherein said method further comprises determining said ranges of key masks associated with said plurality of sub-data structures.

37. The at least one program storage device of claim 36, wherein said determining comprises for a key mask associated with a sub-data structure:

converting said key mask into a binary notation; and

counting a number of zeros within said binary notation, said number of zeros providing an indication of the range of said key mask.

38. The at least one program storage device of claim 37, wherein said range of said key mask is two to the power of said number of zeros.

39. The at least one program storage device of claim 33, wherein said plurality of sub-data structures comprises a plurality of trees.

40. The at least one program storage device of claim 33, wherein said method further comprises adding another sub-data structure to said data structure, wherein said another sub-data structure is inserted in order in said data structure based on its key mask range.

41. The at least one program storage device of claim 33, wherein said method further comprises inserting a new key into said data structure.

42. The at least one program storage device of claim 41, wherein said inserting comprises:

determining a key mask range for said new key;

creating a new sub-data structure when said key mask range is not within said data structure;

adding a key mask associated with said new key to an existing sub-data structure when said key mask range is within said data structure and said key mask is not among the key masks of said existing sub-data structure; and

adding said new key to said new sub-data structure or said existing sub-data structure.

43. The at least one program storage device of claim 33, wherein said method further comprises removing one of said plurality of sub-data structures.

44. The at least one program storage device of claim 33, wherein said plurality of sub-data structures includes a plurality of keys, and wherein said method further comprises removing one key of said plurality of keys from one sub-data structure of said plurality of sub-data structures.

45. The at least one program storage device of claim 44, wherein said removing comprises using a key mask range of said one key to be removed to locate said one sub-data structure.

46. The at least one program storage device of claim 33, further comprising searching said data structure.

47. The at least one program storage device of claim 46, wherein said searching comprises searching said data structure for one or more target records associated with a requested key, said searching beginning with a more specific sub-data structure of said plurality of sub-data structures and proceeding to less specific sub-data structures of said plurality of sub-data structures until said one or more target records is collected.

48. The at least one program storage device of claim 46, wherein said searching comprises:

determining whether a requested key belongs to a sub-data structure of said ordered plurality of sub-data structures, said determining beginning with a first sub-data structure of said ordered plurality of sub-data structures;

selecting one or more target records associated with said requested key from said sub-data structure, when said requested key belongs to said sub-data structure;

deciding whether one or more target records is still needed for said requested key;

proceeding to a next sub-data structure of said ordered plurality of sub-data structures when said one or more target records is still needed for said requested key;

repeating said determining, selecting, and deciding at said next sub-data structure and said proceeding until no more target records are needed for said requested key.

49. The at least one program storage device of claim 48, wherein said determining comprises performing a bit wise AND operation with said requested key and a key mask of said sub-data structure to determine whether said requested key belongs to said sub-data structure.

50. The at least one program storage device of claim 33, wherein said key masks designate variations in keys of said sub-data structures.

51. The at least one program storage device of claim 50, wherein said keys comprise addresses.

52. The at least one program storage device of claim 33, wherein said obtaining comprises defining said plurality of sub-data structures.

53. The at least one program storage device of claim 33, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.

54. The at least one program storage device of claim 53, wherein each of said one or more addresses has a corresponding key mask.

55. The at least one program storage device of claim 33, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.

56. An article of manufacture, comprising:

at least one computer useable medium having computer readable program code means embodied therein for causing the creating of a data structure, the computer readable program code means in said article of manufacture comprising;

computer readable program code means for causing a computer to obtain a plurality of sub-data structures; and

computer readable program code means for causing a computer to order said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.

57. The article of manufacture of claim 56, further comprising computer readable program code means for causing a computer to determine said ranges of key masks associated with said plurality of sub-data structures.

58. The article of manufacture of claim 56, further comprising computer readable program code means for causing a computer to add another sub-data structure to said data structure, wherein said another sub-data structure is inserted in order in said data structure based on its key mask range.

59. The article of manufacture of claim 56, further comprising computer readable program code means for causing a computer to perform at least one of inserting a new key into said data structure and removing one of said plurality of sub-data structures.

60. The article of manufacture of claim 56, wherein said plurality of sub-data structures includes a plurality of keys, and further comprising computer readable program code means for causing a computer to remove one key of said plurality of keys from one sub-data structure of said plurality of sub-data structures.

61. The article of manufacture of claim 56, further comprising computer readable program code means for causing a computer to search said data structure.

62. The article of manufacture of claim 56, wherein said key masks designate variations in keys of said sub-data structures.

63. The article of manufacture of claim 62, wherein said keys comprise addresses.

64. The article of manufacture of claim 56, wherein said computer readable program code means for causing a computer to obtain comprises computer readable program code means for causing a computer to define said plurality of sub-data structures.

65. The article of manufacture of claim 56, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.

66. The article of manufacture of claim 65, wherein each of said one or more addresses has a corresponding key mask.

67. The article of manufacture of claim 56, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.

68. A system of creating a data structure, said system comprising:

a plurality of sub-data structures; and

means for ordering said plurality of sub-data structures based on ranges of key masks associated with said plurality of sub-data structures, wherein said data structure comprises said ordered plurality of sub-data structures.

69. The system of claim 68, further comprising means for determining said ranges of key masks associated with said plurality of sub-data structures.

70. The system of claim 68, further comprising means for adding another sub-data structure to said data structure, wherein said another sub-data structure is inserted in order in said data structure based on its key mask range.

71. The system of claim 68, further comprising at least one of means for inserting a new key into said data structure and means for removing one of said plurality of sub-data structures.

72. The system of claim 68, wherein said plurality of sub-data structures includes a plurality of keys, and wherein said system further comprises means for removing one key of said plurality of keys from one sub-data structure of said plurality of sub-data structures.

73. The system of claim 68, further comprising means for searching said data structure.

74. The system of claim 73, wherein said means for searching comprises means for searching said data structure for one or more target records associated with a requested key, said searching beginning with a more specific sub-data structure of said plurality of sub-data structures and proceeding to less specific sub-data structures of said plurality of sub-data structures until said one or more target records is collected.

75. The system of claim 68, wherein said key masks designate variations in keys of said sub-data structures.

76. The system of claim 75, wherein said keys comprise addresses.

77. The system of claim 68, further comprising means for defining said plurality of sub-data structures.

78. The system of claim 68, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.

79. The system of claim 78, wherein each of said one or more addresses has a corresponding key mask.

80. The system of claim 68, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.

81. A method of creating a data structure in a computing environment, said method comprising:

obtaining a plurality of sub-data structures; and

providing a key mask range for each sub-data structure of said plurality of sub-data structures, wherein said data structure comprises said plurality of sub-data structures.

82. The method of claim 81, wherein each sub-data structure comprises a PATRICIA tree.

83. The method of claim 81, wherein each key mask range is associated with one or more key masks, said key masks designating variations in keys of said sub-data structures.

84. The method of claim 83, wherein said keys comprise addresses.

85. The method of claim 81, wherein said obtaining comprises defining a plurality of sub-data structures.

86. The method of claim 81, wherein each sub-data structure of said plurality of sub-data structures has associated therewith one or more addresses.

87. The method of claim 86, wherein each of said one or more addresses has a corresponding key mask.

88. A memory comprising a data structure, said data structure comprising a plurality of sub-data structures, wherein each sub-data structure of said plurality of sub-data structures has associated therewith a key mask range.

89. The memory of claim 88, wherein each key mask range is associated with one or more key masks, said key masks designating variations in keys of said sub-data structures.

90. At least one program storage device readable by a machine, tangibly embodying at least one program of instructions executable by the machine to perform a method of creating a data structure, said method comprising:

obtaining a plurality of sub-data structures; and

providing a key mask range for each sub-data structure of said plurality of sub-data structures, wherein said data structure comprises said plurality of sub-data structures.

91. The at least one program storage device of claim 90, wherein each key mask range is associated with one or more key masks, said key masks designating variations of keys of said sub-data structures.

92. A system of creating a data structure, said system comprising:

a plurality of sub-data structures; and

means for providing a key mask range for each sub-data structure of said plurality of sub-data structures, wherein said data structure comprises said plurality of sub-data structures.