Systems and methods for display list management

Abstract

Systems and methods consistent with some embodiments of the present invention provide data structures and methods for the automatic storing, manipulating and processing of a intermediate printable data generated from a first printable data are presented. In some embodiments, the first printable data may take the form of a PDL description of a document and the intermediate printable data may take the form of a display list of objects generated from the PDL description. In some embodiments, a data structure for storing a intermediate printable data generated from a first printable data may comprise at least one memory pool, which may further comprise a plurality of uniformly sized segments to store the intermediate printable data; at least one global structure for storing information related to the one or more memory pools; and buffers for performing operations on the first printable data and the intermediate printable data.

1 - 22 . (canceled) 
   
   
       23 . A method for managing display lists in a memory pool, wherein the memory pool comprises a plurality of uniformly sized segments with at least one control data structure the method comprising:
 adding a display list object to a block that was most recently associated with the control data structure, if sufficient unused memory is available within the block to hold the display list object;   adding the display list object to a new block associated with the control data structure and created by using an additional segment, if the size of the display list object exceeds the size of unused memory within the block that was most recently associated with the control data structure;   adding the display list object to a new block associated with the control data structure and created from two or more unused contiguous segments, if the size of the display list object exceeds the size of a segment; and   adding the display list object to a new block associated with the control data structure and created by applying at least one of a plurality of memory recovery strategies, if the combination of unused contiguous segments is insufficient to hold the display list object.   
   
   
       24 . The method of  claim 23 , wherein the plurality of memory recovery strategies comprise of:
 waiting for memory blocks to be freed;   adding additional available free memory to the memory pool;   compacting blocks associated with the control data structure for the memory pool;   freeing blocks associated with control data structures in the memory pool that are also stored at an alternate location;   compressing display list objects in blocks associated with control data structures in memory; and   storing previously existing display list objects in secondary storage.   
   
   
       25 . The method of  claim 23 , wherein the size of the segments can be chosen from one of several pre-determined sizes. 
   
   
       26 . The method of  claim 23 , wherein adding the display list object to a new block associated with the control data structure and created by combining a two or more unused contiguous segments comprises:
 determining the number of contiguous segments needed to hold the display list object;   associating a new block comprising the combined unused contiguous segments with the control data structure; and   adding the display list object to the new block.   
   
   
       27 . The method of  claim 24 , wherein waiting for memory blocks to be freed comprises one of:
 waiting until an adequate number of memory blocks sufficient to hold the display list object have been freed; and   terminating the wait if the size of the display list object exceeds currently available memory including any freed memory blocks and it is unlikely that any further memory blocks will be freed.   
   
   
       28 . The method of  claim 24 , wherein waiting for memory blocks to be freed comprises associating a new block comprising of one or more memory segments resulting from freed memory blocks with the control data structure, wherein the memory blocks are freed during the waiting period. 
   
   
       29 . The method of  claim 24 , wherein adding additional available free memory to the memory pool comprises:
 allocating additional available free memory not currently within the memory pool to increase the size of the memory pool; and   associating a new block comprising of one or more memory segments resulting from the additionally available memory with the control data structure.   
   
   
       30 . The method of  claim 29 , further comprising deallocating the additional allocated memory after use. 
   
   
       31 . The method of  claim 29 , wherein the allocation of the additional available free memory to the memory pool is dynamic and occurs at execution time. 
   
   
       32 . The method of  claim 24 , wherein compacting blocks associated with the control data structure in the memory pool comprises:
 rearranging memory blocks to form a set of contiguous segments; and   associating a new block comprising of one or more of the contiguous memory segments resulting from the rearrangement of memory blocks with the control data structure.   
   
   
       33 . The method of  claim 24 , wherein freeing blocks associated with control data structures in the memory pool that are also stored at an alternate location comprises:
 deleting blocks with duplicated display list objects;   freeing blocks that held the display list objects; and   associating a new block comprising of one or more memory segments resulting from freed memory blocks with the control data structure.   
   
   
       34 . The method of  claim 24 , wherein compressing display list objects in blocks associated with control data structures in memory comprises one or more of the steps of:
 compressing display list objects in blocks associated with the control data structure;   storing each compressed display list object in a compression band;   storing information pertaining to the compression bands at locations in the control data structure associated with the blocks that held display list objects corresponding to the compression bands;   freeing blocks that held the display list objects; and   associating a new block comprising of one or more memory segments resulting from freed memory blocks with the control data structure.   
   
   
       35 . The method of  claim 34 , wherein compressing display list objects in blocks associated with the control data structure comprises one or more of the steps of:
 compressing data in blocks associated with the control data structure; and   compressing image data in blocks associated with the control data structure.   
   
   
       36 . The method of  claim 35 , wherein data is compressed using one of ZLIB compression, GZIP compression, or any other lossless data compression algorithm. 
   
   
       37 . The method of  claim 35 , wherein image data is compressed using JPEG compression, with a specified Q-factor. 
   
   
       38 . The method of  claim 23 , wherein the memory pool is resident on a printing device. 
   
   
       39 . The method of  claim 24 , wherein storing previously existing display list objects in secondary storage comprises:
 storing one or more display list objects at locations on a secondary storage device;   storing address information for the stored display list objects at locations in the control data structure associated with the blocks that held the stored display list objects;   freeing blocks that held the stored display list objects; and   associating a new block comprising of one or more memory segments resulting from freed memory blocks with the control data structure.   
   
   
       40 . A computer-readable medium that stores instructions, which when executed by a processor perform a method for managing display lists in a memory pool, wherein the memory pool comprises a plurality of uniformly sized segments with at least one control data structure the method comprising:
 adding a display list object to a block that was most recently associated with the control data structure, if sufficient unused memory is available within the block to hold the display list object;   adding the display list object by using an additional segment, if the size of the display list object exceeds the size of unused memory within the block that was most recently associated with the control data structure;   adding the display list object by combining a two or more unused contiguous segments, if the size of the display list object exceeds the size of a segment; and   adding the display list object to a new block associated with the control data structure and created by applying at least one of a plurality of memory recovery strategies, if the combination of unused contiguous segments is insufficient to hold the display list object.   
   
   
       41 . The method of  claim 40 , wherein the plurality of memory recovery strategies comprise of:
 waiting for memory blocks to be freed;   adding additional available free memory to the memory pool;   compacting blocks associated with the control data structure for the memory pool;   freeing blocks associated with control data structures in the memory pool that are also stored at an alternate location;   compressing display list objects in blocks associated with control data structures in memory; and   storing previously existing display list objects in secondary storage.   
   
   
       42 . A computer readable memory containing instructions for controlling a processor to perform a method of managing display lists in a memory pool, wherein the memory pool comprises a plurality of uniformly sized segments with at least one control data structure the method comprising:
 adding a display list object to a block that was most recently associated with the control data structure, if sufficient unused memory is available within the block to hold the display list object;   adding the display list object by using an additional segment, if the size of the display list object exceeds the size of unused memory within the block that was most recently associated with the control data structure;   adding the display list object by combining a two or more unused contiguous segments, if the size of the display list object exceeds the size of a segment; and   adding the display list object to a new block associated with the control data structure and created by applying at least one of a plurality of memory recovery strategies, if the combination of unused contiguous segments is insufficient to hold the display list object.   
   
   
       43 . The method of  claim 42 , wherein the plurality of memory recovery strategies comprise of:
 waiting for memory blocks to be freed;   adding additional available free memory to the memory pool;   compacting blocks associated with the control data structure for the memory pool;   freeing blocks associated with control data structures in the memory pool that are also stored at an alternate location;   compressing display list objects in blocks associated with control data structures in memory; and   storing previously existing display list objects in secondary storage.