I have (at least) two or three questions for this requirement, to
understand it better and to give a better advice:
1. is it necessary to access the individual items directly from outside,
that is: do they need a pointer or
a key or an ID or something, or is the sequential scan the only way to
access them (after the insertion)?
A pointer is no good solution for that, because it will change, when
items are moved (see 2.) ... even
if there is no second area. But there are easy solutions to overcome
this problem ... if an external "key"
is really needed.
2. if you are scanning the area sequentially and remove the items that
are no longer needed, you don't
need a second area, IMO. You simply move the remaining items "nearer to
the top", and eliminate the "holes".
3. can you give an upper limit to the size of the items (which then
gives us the possibility to define a
reasonable upper limit for the size of the complete area or structure)?
For me, several designs come to mind:
- sort of "records" with length information, like VSAM records in an
ESDS control interval
- something like DB2 data pages with row ids (fixed size - 4k, 8k, 32k -
with a row pointer vector
at the beginning or at the end; this would allow for external IDs
remaining constant,
even if the items were moved inside the page)
Kind regards
Bernd
Am 29.12.2024 um 21:51 schrieb Binyamin Dissen:
The data structure consists of various items of different lengths. The items
are added serially and periodically the area is scanned where most items are
removed. The remaining items are likely to be removed in a later scan (with
new items).
My thought was to have two data areas, and during the scan insert the
undeleted items into the alternate area. It will be a bit of data moves but is
simple.
Does Knuth talk about such a data structure?
--
Binyamin Dissen <bdis...@dissensoftware.com>
http://www.dissensoftware.com
Director, Dissen Software, Bar & Grill - Israel
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to lists...@listserv.ua.edu with the message: INFO IBM-MAIN
----------------------------------------------------------------------
For IBM-MAIN subscribe / signoff / archive access instructions,
send email to lists...@listserv.ua.edu with the message: INFO IBM-MAIN
