chris@mimsy.UUCP (Chris Torek) (02/27/89)
Here is the situation: I have a piece of hardware with multiplane (either 4 or 8 plane) memory, in which it can perform rasterops. I need to allocate either 1 plane or all 4 or 8 planes, in a rectangular (rasterop-shaped) region, somewhere in this multiplane memory. I would like to find a reasonably optimimal algorithm (in terms of both time to locate the region and space wasted between and among regions) for finding a suitable rectangle or, if no such rectangle is available, choosing a suitable old region to kick out. (The memory functions essentially as a cache.) The best suggestion I have heard so far is to use a quadtree-based rectangle allocator and an ad-hoc approach to the plane division. (The latter should be simple since no one ever wants a half-deep plane; it is either 1-bit or all-bits.) Quadtree allocation is analagous to a buddy-system linear memory allocator; Knuth has shown that such an allocator typically wastes 25 to 40 percent (if I remember aright) of the available memory, and it is intuitively obvious (though maybe not correct) that the proportion of waste will go up rapidly with the number of axes. I am not sure whether the use fraction will be high enough using quadtree-based allocation. Anyway, comp.graphics seemed like a reasonable place to ask. Please send mail if you have any suggestions (other than `forget it' :-) ). (For the curious: the hardware is DEC's QDSS; the idea is to cache X11R3 fonts, backing store, and save-unders.) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris