"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))