Improved Box-Allocation Method for Off-Screen Video Memory

Improved Box-Allocation Method for Off-Screen Video Memory

      Disclosed is a program for allocating rectangular memory spaces
more efficiently than a traditional quad-tree method.  The improved
method here is to make one of the four boundaries movable that were
fixed in a traditional way.

      In personal computer video system, off-screen video memory is
often used for bitmap cache buffers.  As those buffers are
two-dimensional rectangular spaces, allocation algorithm should be
carefully selected to minimize fragmentation involved in the process.
Fig. 1 shows a traditional quad-tree linked-list structure.  Each
leaf-nodes indicate allocated rectangular spaces and have a flag of
"Used" or "Unused".  When a new rectangular space is requested to be
allocated, "Unused" leaf-nodes are scanned to check if it is large
enough to allocate the requested space.  If it is large enough, the
node will be divided into 4 rectangles again so that one of them may
be the requested rectangular size.  Once a node is divided, the four
resulted rectangles will not change their sizes.  So, it is known
that fragmentation problem is severe when allocating rectangles are
being bigger like Fig. 2.  The improved method introduced here is to
allow two consecutive "Unused" rectangles change their sizes by
moving a boundary between them if the enlarged rectangle can be large
enough to allocate a requested rectangular space.  In Fig. 3, (2) and
(3) shows re-sized rectangles from (1). ...