Using queue specific variable(s) to efficiently delete expired items in an ordered queue without necessarily checking each queued item's expiry time
US7487272B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Nov 17, 2005 |
| Grant date | Feb 3, 2009 |
| Priority date | — |
| Expiry date | Sep 20, 2026 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F5/06
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for deleting expired items in a queue data structure, the queue data structure comprising a sequential list of ordered data items including a queue head at one end of the sequential list and a queue tail at another end of the sequential list, wherein each data item includes an expiry time, the method comprising: generating a maximum interval value corresponding to a maximum time interval between an expiry time of a first item in the queue and an expiry time of a second item in the queue, wherein the second item is nearer the queue head than the first item; sequentially scanning the list of ordered items from the queue head; responsive to a determination that a scanned item is expired, deleting the scanned item; responsive to a determination that a scanned item will not expire for a time interval greater than the maximum interval value, terminating scanning of the list of ordered items.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.