Method and apparatus for allocating off-screen display memory

• US 5,291,188 A
• Filed: 06/17/1991
• Issued: 03/01/1994
• Est. Priority Date: 06/17/1991
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Priem, Curtis, McIntyre, Bruce, Rocchetti, Robert
• Primary Examiner(s): Hjerpe, Richard
• Assistant Examiner(s): SARAS, STEVEN J
• Application Number:
  US07/716,671
• Time in Patent Office: 988 Days
• Field of Search: 340/799, 340/798, 340/747, 395/164, 395/165, 395/166
• US Class Current: 345/543
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G09G 5/39 Control of the bit-mapped memory

Abstract

A method of allocating space in a frame buffer memory which is not used for storing pixels to be displayed currently including the steps of selecting a portion of the memory to be allocated for off-screen memory; determining the size of an area to be allocated; comparing the size of the area to be allocated with portions of the memory available to be allocated for off-screen memory using a memory allocation technique in which the least area considered is at least as great in either its horizontal or its vertical dimension as the greater dimension of the area to be allocated, the comparison being conducted in a pattern which consistently checks first a minimum area followed by three other minimum areas in an area having a size which is the next power of two larger in each dimension than the minimum area, then four more minimum areas in an adjacent area having a size which is the next power of two larger in each dimension than the minimum area than the minimum area in the pattern, the area selected for the second adjacent area being selected in the same pattern as are the minimum areas; continuing the pattern through areas which increase on the basis of the next power of two larger in each dimension of the last largest area, the search using the pattern used for selection in the minimum areas; and allocating the first area found of sufficient space to provide the memory area sought.

Claims

1. In a computer system comprising a frame buffer memory, a method for allocating space in a selected portion of a frame buffer memory to store off-screen information, said method comprising the steps of:

dividing said selected portion of frame buffer memory into a matrix of blocks, each block having equal width and equal height, said block width and block height being equal to a power of two;

adjusting a requested memory size comprising a requested width and a requested height, rounding said requested width and requested height to the next power of two larger than the larger of said requested width and height;

searching said selected portion of said frame buffer memory for a free area to allocate, said free area being equal to said adjusted requested size comprising an integral multiple of said frame buffer memory blocks, said search being systematically conducted in an initial corner area and a series of three adjacent area sets until said free area is found, said initial corner area and each of the three adjacent areas of the first three adjacent area set being equal in size to said free area being sought, each of the three adjacent areas of the n^th three adjacent area set being four times in size of each of the three adjacent areas of the n-1^th three adjacent area set and two of the three adjacent areas of the n^th three adjacent area set being adjacent to two of the three adjacent areas of the n-1^th three adjacent area set, each of the three adjacent areas of the n^th three adjacent area set being searched in the same manner as said initial corner area and n-1 three adjacent area sets were searched;

allocating said memory blocks within said free area found by said search.

2. The method of allocating space as set forth in claim 1, wherein said search comprises searching a bit map in which each of said frame buffer memory blocks is represented by a single bit of data.

3. The method of allocating space as set forth in claim 2, wherein said bitmap search comprises searching successive groups of bits of said bitmap corresponding to said initial corner area and subsequent adjacent areas.

4. The method of allocating space as set forth in claim 3, wherein if a selected one of said requested width and said requested height is less than one-half of one dimension of said free area being sought, then an additional test is made in each of said searches to determine if half of each of said areas being searched is free to be allocated.

5. In a computer system comprising a frame buffer memory, an apparatus for allocating space in a selected portion of a frame buffer memory to store off-screen information, said apparatus comprising:

division means coupled to said frame buffer memory for dividing said selected portion of frame buffer memory into a matrix of blocks, each block having equal width and equal height, said block width and block height being equal to a power of two;

adjustment means for adjusting a requested memory size comprising a requested width and a requested height, rounding said requested width and requested height to the next power of two larger than the larger of said requested width and height;

search means coupled to said adjustment means and said frame buffer memory for searching said selected portion of said frame buffer memory for a free area to allocate, said free area being equal to said adjusted requested size comprising an integral multiple of said frame buffer memory blocks, said search being systematically conducted in an initial corner area and a series of three adjacent area sets until said free area is found, said initial corner area and each of the three adjacent areas of the first three adjacent area set being equal in size to said free area being sought, each of the three adjacent areas of the n^th three adjacent area set being four times in size of each of the three adjacent areas of the n-1^th three adjacent area set and two of the three adjacent areas of the n^th three adjacent area set being adjacent to two of the three adjacent areas of the n-1^th three adjacent area set, each of the three adjacent areas of the n^th three adjacent area set being searched in the same manner as said initial corner area and n-1 three adjacent area sets were searched;

allocation means coupled to said search means for allocating said memory blocks within said free area found by said search.

6. The apparatus as set forth in claim 5, wherein said search means performs said searches by searching a bit map in which each of said frame buffer memory blocks is represented by a single bit of data.

7. The apparatus as set forth in claim 6, wherein said search means performs said bitmap search by searching successive groups of bits of said bitmap corresponding to said initial corner area and subsequent adjacent areas.

8. The apparatus as set forth in claim 7, wherein said search means further tests if a selected one of said requested width and said requested height is less than one-half of one dimension of said free area being sought, if so then said search means conducts an additional test in each of said searches to determine if half of each of said areas being searched is free to be allocated.