"Fossies" - the Fresh Open Source Software Archive

Member "dmelt/python/packages/sympy/thirdparty/pyglet/pyglet/graphics/allocation.py" (22 Jun 2022, 14077 Bytes) of package /linux/misc/dmelt-2.8.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 # ----------------------------------------------------------------------------
    2 # pyglet
    3 # Copyright (c) 2006-2008 Alex Holkner
    4 # All rights reserved.
    5 # 
    6 # Redistribution and use in source and binary forms, with or without
    7 # modification, are permitted provided that the following conditions 
    8 # are met:
    9 #
   10 #  * Redistributions of source code must retain the above copyright
   11 #    notice, this list of conditions and the following disclaimer.
   12 #  * Redistributions in binary form must reproduce the above copyright 
   13 #    notice, this list of conditions and the following disclaimer in
   14 #    the documentation and/or other materials provided with the
   15 #    distribution.
   16 #  * Neither the name of pyglet nor the names of its
   17 #    contributors may be used to endorse or promote products
   18 #    derived from this software without specific prior written
   19 #    permission.
   20 #
   21 # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   22 # "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   23 # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   24 # FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   25 # COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   26 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   27 # BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   28 # LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   29 # CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   30 # LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   31 # ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   32 # POSSIBILITY OF SUCH DAMAGE.
   33 # ----------------------------------------------------------------------------
   34 # $Id:$
   35 
   36 '''Memory allocation algorithm for vertex arrays and buffers.
   37 
   38 The region allocator is used to allocate vertex indices within a vertex
   39 domain's  multiple buffers.  ("Buffer" refers to any abstract buffer presented
   40 by `pyglet.graphics.vertexbuffer`.
   41  
   42 The allocator will at times request more space from the buffers. The current
   43 policy is to double the buffer size when there is not enough room to fulfil an
   44 allocation.  The buffer is never resized smaller.
   45 
   46 The allocator maintains references to free space only; it is the caller's
   47 responsibility to mantain the allocated regions.
   48 '''
   49 
   50 __docformat__ = 'restructuredtext'
   51 __version__ = '$Id: $'
   52  
   53 # Common cases:
   54 # -regions will be the same size (instances of same object, e.g. sprites)
   55 # -regions will not usually be resized (only exception is text)
   56 # -alignment of 4 vertices (glyphs, sprites, images, ...)
   57 #
   58 # Optimise for:
   59 # -keeping regions adjacent, reduce the number of entries in glMultiDrawArrays
   60 # -finding large blocks of allocated regions quickly (for drawing)
   61 # -finding block of unallocated space is the _uncommon_ case!
   62 #
   63 # Decisions:
   64 # -don't over-allocate regions to any alignment -- this would require more
   65 #  work in finding the allocated spaces (for drawing) and would result in
   66 #  more entries in glMultiDrawArrays
   67 # -don't move blocks when they truncate themselves.  try not to allocate the
   68 #  space they freed too soon (they will likely need grow back into it later,
   69 #  and growing will usually require a reallocation).
   70 # -allocator does not track individual allocated regions.  Trusts caller
   71 #  to provide accurate (start, size) tuple, which completely describes
   72 #  a region from the allocator's point of view.
   73 # -this means that compacting is probably not feasible, or would be hideously
   74 #  expensive
   75 
   76 class AllocatorMemoryException(Exception):
   77     '''The buffer is not large enough to fulfil an allocation.
   78 
   79     Raised by `Allocator` methods when the operation failed due to lack of
   80     buffer space.  The buffer should be increased to at least
   81     requested_capacity and then the operation retried (guaranteed to
   82     pass second time).
   83     '''
   84 
   85     def __init__(self, requested_capacity):
   86         self.requested_capacity = requested_capacity
   87 
   88 class Allocator(object):
   89     '''Buffer space allocation implementation.'''
   90     def __init__(self, capacity):
   91         '''Create an allocator for a buffer of the specified capacity.
   92 
   93         :Parameters:
   94             `capacity` : int
   95                 Maximum size of the buffer.
   96 
   97         '''
   98         self.capacity = capacity
   99 
  100         # Allocated blocks.  Start index and size in parallel lists.
  101         #
  102         # # = allocated, - = free
  103         #
  104         #  0  3 5        15   20  24                    40
  105         # |###--##########-----####----------------------|
  106         #
  107         # starts = [0, 5, 20]
  108         # sizes = [3, 10, 4]
  109         #
  110         # To calculate free blocks:
  111         # for i in range(0, len(starts)):
  112         #   free_start[i] = starts[i] + sizes[i]
  113         #   free_size[i] =  starts[i+1] - free_start[i]
  114         # free_size[i+1] = self.capacity - free_start[-1]
  115 
  116         self.starts = []
  117         self.sizes = []
  118 
  119     def set_capacity(self, size):
  120         '''Resize the maximum buffer size.
  121         
  122         The capaity cannot be reduced.
  123 
  124         :Parameters:
  125             `size` : int
  126                 New maximum size of the buffer.
  127 
  128         '''
  129         assert size > self.capacity
  130         self.capacity = size
  131 
  132     def alloc(self, size):
  133         '''Allocate memory in the buffer.
  134 
  135         Raises `AllocatorMemoryException` if the allocation cannot be
  136         fulfilled.
  137 
  138         :Parameters:
  139             `size` : int
  140                 Size of region to allocate.
  141                
  142         :rtype: int
  143         :return: Starting index of the allocated region.
  144         '''
  145         assert size > 0
  146 
  147         # return start
  148         # or raise AllocatorMemoryException
  149 
  150         if not self.starts:
  151             if size <= self.capacity:
  152                 self.starts.append(0)
  153                 self.sizes.append(size)
  154                 return 0
  155             else:
  156                 raise AllocatorMemoryException(size)
  157 
  158         # Allocate in a free space
  159         free_start = self.starts[0] + self.sizes[0]
  160         for i, (alloc_start, alloc_size) in \
  161                 enumerate(zip(self.starts[1:], self.sizes[1:])):
  162             # Danger!  
  163             # i is actually index - 1 because of slicing above...
  164             # starts[i]   points to the block before this free space
  165             # starts[i+1] points to the block after this free space, and is
  166             #             always valid.
  167             free_size = alloc_start - free_start
  168             if free_size == size:
  169                 # Merge previous block with this one (removing this free space)
  170                 self.sizes[i] += free_size + alloc_size
  171                 del self.starts[i+1]
  172                 del self.sizes[i+1]
  173                 return free_start
  174             elif free_size > size:
  175                 # Increase size of previous block to intrude into this free
  176                 # space.
  177                 self.sizes[i] += size
  178                 return free_start
  179             free_start = alloc_start + alloc_size
  180         
  181         # Allocate at end of capacity
  182         free_size = self.capacity - free_start
  183         if free_size >= size:
  184             self.sizes[-1] += size
  185             return free_start
  186         
  187         raise AllocatorMemoryException(self.capacity + size - free_size)
  188 
  189     def realloc(self, start, size, new_size):
  190         '''Reallocate a region of the buffer.
  191 
  192         This is more efficient than separate `dealloc` and `alloc` calls, as
  193         the region can often be resized in-place.
  194 
  195         Raises `AllocatorMemoryException` if the allocation cannot be
  196         fulfilled.
  197 
  198         :Parameters:
  199             `start` : int
  200                 Current starting index of the region.
  201             `size` : int
  202                 Current size of the region.
  203             `new_size` : int
  204                 New size of the region.
  205 
  206         '''
  207         assert size > 0 and new_size > 0
  208         
  209         # return start
  210         # or raise AllocatorMemoryException
  211 
  212         # Truncation is the same as deallocating the tail cruft
  213         if new_size < size:
  214             self.dealloc(start + new_size, size - new_size)
  215             return start
  216             
  217         # Find which block it lives in
  218         for i, (alloc_start, alloc_size) in \
  219                 enumerate(zip(*(self.starts, self.sizes))):
  220             p = start - alloc_start
  221             if p >= 0 and size <= alloc_size - p:
  222                 break
  223         if not (p >= 0 and size <= alloc_size - p):
  224             print zip(self.starts, self.sizes)
  225             print start, size, new_size
  226             print p, alloc_start, alloc_size
  227         assert p >= 0 and size <= alloc_size - p, 'Region not allocated'
  228 
  229         if size == alloc_size - p:
  230             # Region is at end of block.  Find how much free space is after
  231             # it.
  232             is_final_block = i == len(self.starts) - 1
  233             if not is_final_block:
  234                 free_size = self.starts[i + 1] - (start + size)
  235             else:
  236                 free_size = self.capacity - (start + size)
  237 
  238             # TODO If region is an entire block being an island in free space, 
  239             # can possibly extend in both directions.
  240 
  241             if free_size == new_size - size and not is_final_block:
  242                 # Merge block with next (region is expanded in place to
  243                 # exactly fill the free space)
  244                 self.sizes[i] += free_size + self.sizes[i + 1]
  245                 del self.starts[i + 1]
  246                 del self.sizes[i + 1]
  247                 return start
  248             elif free_size > new_size - size:
  249                 # Expand region in place
  250                 self.sizes[i] += new_size - size
  251                 return start
  252 
  253         # The block must be repositioned.  Dealloc then alloc.
  254         
  255         # But don't do this!  If alloc fails, we've already silently dealloc'd
  256         # the original block.
  257         #   self.dealloc(start, size)
  258         #   return self.alloc(new_size)
  259 
  260         # It must be alloc'd first.  We're not missing an optimisation 
  261         # here, because if freeing the block would've allowed for the block to 
  262         # be placed in the resulting free space, one of the above in-place
  263         # checks would've found it.
  264         result = self.alloc(new_size)
  265         self.dealloc(start, size)
  266         return result
  267 
  268     def dealloc(self, start, size):
  269         '''Free a region of the buffer.
  270 
  271         :Parameters:
  272             `start` : int
  273                 Starting index of the region.
  274             `size` : int
  275                 Size of the region.
  276 
  277         '''
  278         assert size > 0
  279         assert self.starts
  280         
  281         # Find which block needs to be split
  282         for i, (alloc_start, alloc_size) in \
  283                 enumerate(zip(*(self.starts, self.sizes))):
  284             p = start - alloc_start
  285             if p >= 0 and size <= alloc_size - p:
  286                 break
  287         
  288         # Assert we left via the break
  289         assert p >= 0 and size <= alloc_size - p, 'Region not allocated'
  290 
  291         if p == 0 and size == alloc_size:
  292             # Remove entire block
  293             del self.starts[i]
  294             del self.sizes[i]
  295         elif p == 0:
  296             # Truncate beginning of block
  297             self.starts[i] += size
  298             self.sizes[i] -= size
  299         elif size == alloc_size - p:
  300             # Truncate end of block
  301             self.sizes[i] -= size
  302         else:
  303             # Reduce size of left side, insert block at right side
  304             #   $ = dealloc'd block, # = alloc'd region from same block
  305             #
  306             #   <------8------>
  307             #   <-5-><-6-><-7->
  308             #   1    2    3    4
  309             #   #####$$$$$#####
  310             #
  311             #   1 = alloc_start
  312             #   2 = start
  313             #   3 = start + size
  314             #   4 = alloc_start + alloc_size
  315             #   5 = start - alloc_start = p
  316             #   6 = size
  317             #   7 = {8} - ({5} + {6}) = alloc_size - (p + size)
  318             #   8 = alloc_size
  319             #
  320             self.sizes[i] = p
  321             self.starts.insert(i + 1, start + size)
  322             self.sizes.insert(i + 1, alloc_size - (p + size))
  323 
  324     def get_allocated_regions(self):
  325         '''Get a list of (aggregate) allocated regions.
  326 
  327         The result of this method is ``(starts, sizes)``, where ``starts`` is
  328         a list of starting indices of the regions and ``sizes`` their
  329         corresponding lengths.
  330 
  331         :rtype: (list, list)
  332         '''
  333         # return (starts, sizes); len(starts) == len(sizes)
  334         return (self.starts, self.sizes)
  335 
  336     def get_fragmented_free_size(self):
  337         '''Returns the amount of space unused, not including the final
  338         free block.
  339 
  340         :rtype: int
  341         '''
  342         if not self.starts:
  343             return 0
  344 
  345         # Variation of search for free block.
  346         total_free = 0
  347         free_start = self.starts[0] + self.sizes[0]
  348         for i, (alloc_start, alloc_size) in \
  349                 enumerate(zip(self.starts[1:], self.sizes[1:])):
  350             total_free += alloc_start - free_start
  351             free_start = alloc_start + alloc_size
  352 
  353         return total_free
  354 
  355     def get_free_size(self):
  356         '''Return the amount of space unused.
  357         
  358         :rtype: int
  359         '''
  360         if not self.starts:
  361             return self.capacity
  362 
  363         free_end = self.capacity - (self.starts[-1] + self.sizes[-1])
  364         return self.get_fragmented_free_size() + free_end
  365 
  366     def get_usage(self):
  367         '''Return fraction of capacity currently allocated.
  368         
  369         :rtype: float
  370         '''
  371         return 1. - self.get_free_size() / float(self.capacity)
  372 
  373     def get_fragmentation(self):
  374         '''Return fraction of free space that is not expandable.
  375         
  376         :rtype: float
  377         '''
  378         free_size = self.get_free_size()
  379         if free_size == 0:
  380             return 0.
  381         return self.get_fragmented_free_size() / float(self.get_free_size())
  382 
  383     def _is_empty(self):
  384         return not self.starts
  385 
  386     def __str__(self):
  387         return 'allocs=' + repr(zip(self.starts, self.sizes))
  388 
  389     def __repr__(self):
  390         return '<%s %s>' % (self.__class__.__name__, str(self))