Browse Prior Art Database

Large List Manager

IP.com Disclosure Number: IPCOM000100459D
Original Publication Date: 1990-Apr-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 4 page(s) / 137K

Publishing Venue

IBM

Related People

Duffy, SA: AUTHOR [+2]

Abstract

Disclosed is a structure for handling a very large link list in a manner that is fast, flexible to immense inserting and deleting, can handle vast ranges and uses minimal storage.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 47% of the total text.

Large List Manager

       Disclosed is a structure for handling a very large link
list in a manner that is fast, flexible to immense inserting and
deleting, can handle vast ranges and uses minimal storage.

      This approach can be used to handle a very large link list that
must be kept in ascending order.  This process breaks the large link
list into small enough pieces that a simple calculation can locate
the element(s) at any point in the range.  This implementation could
be used to keep timer requests in order.  When the timer expires, an
interrupt is generated to process the function that created this
timer request.  If the function completes before the timeout
interrupt is sent, then the block is deleted from the list. In
summary this mechanism has the following features: locates elements
easily, structure that is dynamic in size, quick inserts and deletes,
sensitive to small and large granularities, and keeps the timeouts in
the order.

      To implement this mechanism, obtain contiguous storage. For
this example the storage is broken up into four sections: the active
segment and three subsequent time segment lists (Fig. 1).  This
contiguous storage could be broken up differently depending on the
granularity needed. The segments correspond to range times.

      The active segment handles timer request blocks that fall
within the first eight hours from the current top.  The active
segment is divided up into 30-second slots, each slot being 4 bytes
wide.  These slots corresponds to a time when the timeout should
occur.  All the timeouts that fall into the same 30-second range are
linked off the same slot.  For example, timeouts for 00:01:15 and
00:01:29 are both linked off slot 2.  Slot 2 would have a range of
00:01:00 - 00:01:29.  The granularity is refined to the point where
the blocks off the slots are not kept in any specific order.

      Second segment slot corresponds to the next 8 hours. It is one
four-byte slot.  This slot contains the address of the list of timer
request blocks to timeout in the next eight-hour interval.

      Third segment slot contains the address of the list of timeout
blocks that are greater than sixteen hours away from the current top
time.

      The fourth segment slot is for timeout blocks that are greater
than 24 hours away from the top time, but less than or equal to 24
hours away from the current time of day. This is also one four-byte
slot.

      To insert, if other segments exist besides the active,
determine into which one the block falls.  If the block falls into
the active segment, we then need to calculate the slot address.  To
calculate the slot address we subtract the top from the timeout value
and divide the result by the range, which in our case is thirty
seconds.
   Top Time = Starting TOD clock value
   for the first slot in the active segment
                   (i.e., TOD for 00:00:00)
              ...