Certain computer applications require the programmer to keep track of time-constrained objects. This could be anything from the idle time of a network connection to the sleep time of a blocked system process. A programmer needs a way to efficiently keep track of these timings so that minimal processing time is allocated to their management.
If the objects were simply stored in an ordered list, every object would need to be visited on an update. If the programmer used one millisecond as a base delay between updates, then every object in the entire list would need to be visited, every millisecond. This is unacceptable due to the fact that as the number of objects increase, the processing time increases proportionally with it. So, with an ordered list, there exists some maximum on the number of objects in the list so that the processing time per update would remain under the programmer's base delay. In turn, this puts a maximum limit on the number of objects, whether they are idle network connections or blocked system processes, which can be reliably managed by the system. A delta list can be used to avoid this situation.
A delta list data structure is derived from a priority queue and can be used to manage timings such as timeouts and delays.
Objects are ordered so that their key is relative to the key of the object(s) preceding it. For example, let's say we have four objects, a, b, c and d, to insert into our queue with delays of 10, 15, 12 and 22 milliseconds, respectively. Representing the delays as keys in the priority queue, these objects would be ordered in the queue as a, c, b, d with keys 10, 2, 3 and 7, respectively.
For insertion, start at the highest priority object in the queue. The queue is traversed, decrementing the current object's key from the key of the object to be inserted if and only if the key of the current queue object is less then the key of the object to be inserted. Otherwise, insert the object with it's new, decremented key into the current index in the queue. Once the insertion is completed, decrement the following object's key by the inserted key value to account for the new delay inserted into the queue.
Insert a, with key 10 into an
empty delta list:
|a:10|
Insert b, with key 15:
|a:10| --> |b:5 |
(once a's 10ms
delay has expired, only 5ms left until b
expires, a = 10, b = 10+5 = 15)
Insert c, with key 12:
|a:10| --> |c:2| --> |b:3 |
(a = 10, c = 10+2 = 12, b = 10+2+3 = 15)
Insert d, with key 22:
|a:10| --> |c:2 | --> |b:3 | --> |d:7 |
(a = 10, c = 10+2 = 12, b = 10+2+3 = 15, d = 10+2+3+7 = 22)
To use the list, a second function is used to decrement the key of the object with the highest priority on some predefined interval.
Let t equal the amount of time, in milliseconds, that has passed. At t = 0, the delta list looks like:
|a:10| --> |c:2 | --> |b:3 | --> |d:7 |
At t = 3:
|a:7 | --> |c:2 | --> |b:3 | --> |d:7 |
At t = 11:
|c:1 | --> |b:3 | --> |d:7 |
This allows the program to remove and update all the delays in the list in constant time.
Concept taken from Operating System Design: The XINU Approach by Douglas Comer.