Granted Patent B1

US 10,303,383 · App. 15/374,991 · Granted May 28, 2019

Inventor: Bryan Karr (Fort Collins, CO)

Assignee: TRAVELPORT, LP

G06F3/0631G06F3/0607G06F3/0673G06F16/2255G06F17/3033

Abstract

Claims (47)

1. A computer-implemented method of resizing a hash index data structure, the method comprising:

storing a first hash index comprising x elements, wherein x is a positive integer greater than two;

creating an update counter and bit map in a cache line block structure associated with the hash index, the update counter atomically incremented in response to a bit map value being modified, the bit map indicating which elements are occupied by a value;

determining that the first hash index needs to expand;

allocating a second hash index, wherein the second index contains at least x+1 elements;

attempting, by a first thread, to advance a first pointer from the first hash index to the second hash index; and

attempting, by a second thread, to advance the first pointer from the first hash index to the second hash index;

wherein only one of the first thread or the second thread will advance the first pointer based on an atomic operation.

2. The method of claim 1 , further comprising advancing the first pointer from the first hash index to the second hash index using a compare and swap.

3. The method of claim 1 , wherein determining that the hash index needs to expand comprises determining an overflow condition of the hash index.

4. The method of claim 1 , wherein, when x>3, the second hash index contains a quantity of elements equal to x times y, where y=2 or a positive multiple of 2.

5. The method of claim 1 , wherein a write operation is performed on an element of the second hash index because the last element of the first hash index is occupied by a value.

6. The method of claim 1 , wherein added write operations are blocked to the first hash index.

7. The method of claim 1 , wherein a fill pointer in a hash set is directed from the first hash index to the second hash index.

8. The method of claim 1 , wherein a current element of the first hash index is determined by performing a modulo operation wherein the numerator is derived from a value in an index field and the divisor equals x.

9. The method of claim 8 , wherein the current element represents a logical position corresponding to a value in an index field.

10. The method of claim 1 , wherein the first hash index and second hash index are associated based on a linked list data structure.

11. The method of claim 1 , further comprising storing at least one queue attribute that points to at least one attribute of a first hash index, wherein the at least one queue attribute includes one or more of:

a head pointer,

a read pointer, or

a value corresponding to a quantity of accessors.

12. The method of claim 1 , further comprising blocking added write operations to the first hash index.

13. A computer-implemented method of resizing a data structure, the method comprising:

setting a field of a first hash index to block a thread from finding an empty slot in a bucket in the first hash index;

creating an update counter and a bit map in a cache line block structure associated with the first hash index, the update counter atomically incremented in response to a bit map value being modified, and the bit map indicating which elements are occupied by a value;

attempting to allocate a second hash index, wherein the second hash index is greater in size than the first hash index;

attempting to allocate a third hash index, wherein the third hash index is greater in size than the first hash index;

linking the second hash index to the first hash index;

and

deallocating the third hash index.

14. The method of claim 13 , wherein linking the second hash index to the first hash index comprises setting a local variable equal to a next pointer of the first hash index, and wherein if the next pointer of the first hash index is empty, attempting to update the next pointer of the first hash index to the second hash index, and advancing a write pointer from the first hash index to the second hash index.

15. The method of claim 13 , wherein if the attempt to allocate the second hash index was unsuccessful, return a result indicating that there is not sufficient memory.

16. The method of claim 15 , wherein if the compare and swap operation with the second hash index was successful, advancing the write pointer of the first hash index to the second hash index and free the second hash index.

17. The method of claim 13 , wherein if the next pointer of the first hash index is not empty, determine whether a compare and swap operation with the second hash index was successful.

18. A computer-implemented method of resizing a hash index data structure, the method comprising:

storing a first hash index comprising x elements, wherein x is a positive integer greater than two;

creating an update counter and a bit map in a cache line block structure associated with the first hash index, the update counter atomically incremented in response to a bit map value being modified, and the bit map indicating which elements are occupied by a value;

determining that the first hash index needs to expand; and

allocating a second hash index, wherein the second index contains at least x+1 elements; and

allocating a third hash index, wherein the third index contains at least x+1 elements; and

advancing a first pointer from the first hash index to the second hash index; and

deallocating the third hash index.

19. The method of claim 18 , wherein the first hash index and second hash index are associated based on a linked list data structure.

20. The method of claim 18 , further comprising storing at least one queue attribute that points to at least one attribute of the first hash index, wherein the at least one queue attribute includes one or more of:

a head pointer,

a read pointer, or

a value corresponding to a quantity of accessors.

Assignments (25)

Continuity (1)

Cited By (1)

US 12,360,985