The Tor Browser / file comparison

comparison: layout/doc/DD-SpaceManager.html

layout/doc/DD-SpaceManager.html

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:488093bfb2c1
1 <!-- This Source Code Form is subject to the terms of the Mozilla Public
2 - License, v. 2.0. If a copy of the MPL was not distributed with this
3 - file, You can obtain one at http://mozilla.org/MPL/2.0/. -->
4
5 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
6 <html>
7 <head>
8
9 <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
10 <title>Detailed Design Template</title>
11 </head>
12 <body>
13
14 <h1><font color="#cc0000">Gecko Layout Detailed Design Document</font></h1>
15
16 <h1>Space Manager Detailed Design</h1>
17
18 <h2>Overview</h2>
19 <p>
20 The Space Manager and related classes and structures are an important of
21 the Gecko Layout system, specifically Block Layout. &nbsp;See the High Level
22 Design document for an overview of the Space Manager, and as an introduction
23 to the classes, structures and algorithms container in this, the Detailed
24 Design Document.
25 </p>
26
27
28
29 <hr width="100%" size="2">
30 <h2>nsSpaceManager</h2>
31 <p>
32 The Space Manager is the central class is a group of classes that manage
33 the occupied and available space that exists in horizontal bands across
34 a canvas. &nbsp;The primary goal of the Space Manager is to provide information
35 about those bands of space to support the CSS notion of floated elements.
36 </p>
37
38 <p>
39 There are three important parts to the Space Manager API: the parts that
40 deal with the coordinate space of the Space Manager, the parts that deal with
41 the regions managed by the Space Manager, and the parts that manage float
42 impact intervals.
43 </p>
44
45 <p>
46 The class nsSpaceManager is declared in the file <a href="http://lxr.mozilla.org/seamonkey/source/layout/base/src/nsSpaceManager.h">
47 nsSpaceManger.h</a>
48 . &nbsp;The class is only used in the layout module and cannot be exported
49 outside of that module (nor does it need to be). &nbsp;It is not a general
50 purpose class, and is not intended to be subclasses<font color="#cc0000">
51 .</font>
52 </p>
53
54 <p>
55 Here is the class declaration, taken from the source file as of 01.08.02
56 </p>
57
58
59
60 <pre>/**
61 * Class for dealing with bands of available space. The space manager
62 * defines a coordinate space with an origin at (0, 0) that grows down
63 * and to the right.
64 */
65 class nsSpaceManager {
66 public:
67 nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
68 ~nsSpaceManager();
69
70 void* operator new(size_t aSize);
71 void operator delete(void* aPtr, size_t aSize);
72
73 static void Shutdown();
74
75 /*
76 * Get the frame that's associated with the space manager. This frame
77 * created the space manager, and the world coordinate space is
78 * relative to this frame.
79 *
80 * You can use QueryInterface() on this frame to get any additional
81 * interfaces.
82 */
83 nsIFrame* GetFrame() const { return mFrame; }
84
85 /**
86 * Translate the current origin by the specified (dx, dy). This
87 * creates a new local coordinate space relative to the current
88 * coordinate space.
89 */
90 void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
91
92 /**
93 * Returns the current translation from local coordinate space to
94 * world coordinate space. This represents the accumulated calls to
95 * Translate().
96 */
97 void GetTranslation(nscoord&amp; aX, nscoord&amp; aY) const { aX = mX; aY = mY; }
98
99 /**
100 * Returns the y-most of the bottommost band or 0 if there are no bands.
101 *
102 * @return PR_TRUE if there are bands and PR_FALSE if there are no bands
103 */
104 PRBool YMost(nscoord&amp; aYMost) const;
105
106 /**
107 * Returns a band starting at the specified y-offset. The band data
108 * indicates which parts of the band are available, and which parts
109 * are unavailable
110 *
111 * The band data that is returned is in the coordinate space of the
112 * local coordinate system.
113 *
114 * The local coordinate space origin, the y-offset, and the max size
115 * describe a rectangle that's used to clip the underlying band of
116 * available space, i.e.
117 * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
118 * coordinate space
119 *
120 * @param aYOffset the y-offset of where the band begins. The coordinate is
121 * relative to the upper-left corner of the local coordinate space
122 * @param aMaxSize the size to use to constrain the band data
123 * @param aBandData [in,out] used to return the list of trapezoids that
124 * describe the available space and the unavailable space
125 * @return NS_OK if successful and NS_ERROR_FAILURE if the band data is not
126 * not large enough. The 'count' member of the band data struct
127 * indicates how large the array of trapezoids needs to be
128 */
129 nsresult GetBandData(nscoord aYOffset,
130 const nsSize&amp; aMaxSize,
131 nsBandData&amp; aBandData) const;
132
133 /**
134 * Add a rectangular region of unavailable space. The space is
135 * relative to the local coordinate system.
136 *
137 * The region is tagged with a frame
138 *
139 * @param aFrame the frame used to identify the region. Must not be NULL
140 * @param aUnavailableSpace the bounding rect of the unavailable space
141 * @return NS_OK if successful
142 * NS_ERROR_FAILURE if there is already a region tagged with aFrame
143 */
144 nsresult AddRectRegion(nsIFrame* aFrame,
145 const nsRect&amp; aUnavailableSpace);
146
147 /**
148 * Resize the rectangular region associated with aFrame by the specified
149 * deltas. The height change always applies to the bottom edge or the existing
150 * rect. You specify whether the width change applies to the left or right edge
151 *
152 * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
153 * tagged with aFrame
154 */
155 enum AffectedEdge {LeftEdge, RightEdge};
156 nsresult ResizeRectRegion(nsIFrame* aFrame,
157 nscoord aDeltaWidth,
158 nscoord aDeltaHeight,
159 AffectedEdge aEdge = RightEdge);
160
161 /**
162 * Offset the region associated with aFrame by the specified amount.
163 *
164 * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
165 * tagged with aFrame
166 */
167 nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
168
169 /**
170 * Remove the region associated with aFrane.
171 *
172 * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
173 * tagged with aFrame
174 */
175 nsresult RemoveRegion(nsIFrame* aFrame);
176
177 /**
178 * Clears the list of regions representing the unavailable space.
179 */
180 void ClearRegions();
181
182 /**
183 * Methods for dealing with the propagation of float damage during
184 * reflow.
185 */
186 PRBool HasFloatDamage()
187 {
188 return !mFloatDamage.IsEmpty();
189 }
190
191 void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
192 {
193 mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
194 }
195
196 PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
197 {
198 return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
199 }
200
201 #ifdef DEBUG
202 /**
203 * Dump the state of the spacemanager out to a file
204 */
205 nsresult List(FILE* out);
206
207 void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
208 #endif
209
210 private:
211 // Structure that maintains information about the region associated
212 // with a particular frame
213 struct FrameInfo {
214 nsIFrame* const mFrame;
215 nsRect mRect; // rectangular region
216 FrameInfo* mNext;
217
218 FrameInfo(nsIFrame* aFrame, const nsRect&amp; aRect);
219 #ifdef NS_BUILD_REFCNT_LOGGING
220 ~FrameInfo();
221 #endif
222 };
223
224 // Doubly linked list of band rects
225 struct BandRect : PRCListStr {
226 nscoord mLeft, mTop;
227 nscoord mRight, mBottom;
228 int32_t mNumFrames; // number of frames occupying this rect
229 union {
230 nsIFrame* mFrame; // single frame occupying the space
231 nsVoidArray* mFrames; // list of frames occupying the space
232 };
233
234 BandRect(nscoord aLeft, nscoord aTop,
235 nscoord aRight, nscoord aBottom,
236 nsIFrame*);
237 BandRect(nscoord aLeft, nscoord aTop,
238 nscoord aRight, nscoord aBottom,
239 nsVoidArray*);
240 ~BandRect();
241
242 // List operations
243 BandRect* Next() const {return (BandRect*)PR_NEXT_LINK(this);}
244 BandRect* Prev() const {return (BandRect*)PR_PREV_LINK(this);}
245 void InsertBefore(BandRect* aBandRect) {PR_INSERT_BEFORE(aBandRect, this);}
246 void InsertAfter(BandRect* aBandRect) {PR_INSERT_AFTER(aBandRect, this);}
247 void Remove() {PR_REMOVE_LINK(this);}
248
249 // Split the band rect into two vertically, with this band rect becoming
250 // the top part, and a new band rect being allocated and returned for the
251 // bottom part
252 //
253 // Does not insert the new band rect into the linked list
254 BandRect* SplitVertically(nscoord aBottom);
255
256 // Split the band rect into two horizontally, with this band rect becoming
257 // the left part, and a new band rect being allocated and returned for the
258 // right part
259 //
260 // Does not insert the new band rect into the linked list
261 BandRect* SplitHorizontally(nscoord aRight);
262
263 // Accessor functions
264 PRBool IsOccupiedBy(const nsIFrame*) const;
265 void AddFrame(const nsIFrame*);
266 void RemoveFrame(const nsIFrame*);
267 PRBool HasSameFrameList(const BandRect* aBandRect) const;
268 int32_t Length() const;
269 };
270
271 // Circular linked list of band rects
272 struct BandList : BandRect {
273 BandList();
274
275 // Accessors
276 PRBool IsEmpty() const {return PR_CLIST_IS_EMPTY((PRCListStr*)this);}
277 BandRect* Head() const {return (BandRect*)PR_LIST_HEAD(this);}
278 BandRect* Tail() const {return (BandRect*)PR_LIST_TAIL(this);}
279
280 // Operations
281 void Append(BandRect* aBandRect) {PR_APPEND_LINK(aBandRect, this);}
282
283 // Remove and delete all the band rects in the list
284 void Clear();
285 };
286
287
288 FrameInfo* GetFrameInfoFor(nsIFrame* aFrame);
289 FrameInfo* CreateFrameInfo(nsIFrame* aFrame, const nsRect&amp; aRect);
290 void DestroyFrameInfo(FrameInfo*);
291
292 void ClearFrameInfo();
293 void ClearBandRects();
294
295 BandRect* GetNextBand(const BandRect* aBandRect) const;
296 void DivideBand(BandRect* aBand, nscoord aBottom);
297 PRBool CanJoinBands(BandRect* aBand, BandRect* aPrevBand);
298 PRBool JoinBands(BandRect* aBand, BandRect* aPrevBand);
299 void AddRectToBand(BandRect* aBand, BandRect* aBandRect);
300 void InsertBandRect(BandRect* aBandRect);
301
302 nsresult GetBandAvailableSpace(const BandRect* aBand,
303 nscoord aY,
304 const nsSize&amp; aMaxSize,
305 nsBandData&amp; aAvailableSpace) const;
306
307 nsIFrame* const mFrame; // frame associated with the space manager
308 nscoord mX, mY; // translation from local to global coordinate space
309 BandList mBandList; // header/sentinel for circular linked list of band rects
310 FrameInfo* mFrameInfoMap;
311 nsIntervalSet mFloatDamage;
312
313 static int32_t sCachedSpaceManagerCount;
314 static void* sCachedSpaceManagers[NS_SPACE_MANAGER_CACHE_SIZE];
315
316 nsSpaceManager(const nsSpaceManager&amp;); // no implementation
317 void operator=(const nsSpaceManager&amp;); // no implementation
318 };
319
320 </pre>
321
322 <h3>Public API</h3>
323
324 <h4>Life Cycle:</h4>
325 <p>
326 The Constructor requires a Presentation Shell, used for arena allocations
327 mostly, and a frame that this Space Manager is rooted on. &nbsp;The coordinate
328 space of this Space Manager is relative to the frame passed in to the constructor.
329 </p>
330
331 <pre> nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
332 ~nsSpaceManager();
333 </pre>
334 <p>
335 Operators 'new' and 'delete' are overridden to support a recycler. &nbsp;Space
336 Manager instances come and go pretty frequently, and this recycler prevents
337 excessive heap allocations and the performance penalties associated with
338 it. The #define NS_SPACE_MANAGER_CACHE_SIZE is used to control the number
339 of Space Manager instances that can be present in the recycler, currently
340 4. &nbsp;If more than NS_SPACE_MANAGER_CACHE_SIZE are allocated at a time,
341 then standard allocation is used.
342 </p>
343
344 <pre>
345 void* operator new(size_t aSize);
346 void operator delete(void* aPtr, size_t aSize);
347
348 </pre>
349 <p>
350 A Static method is used to shutdown the Space Manager recycling. &nbsp;This
351 method deletes all of the Space Mangers inthe recycler,and prevents further
352 recycling. &nbsp;It is meant to be called only when the layout module is being
353 terminated.
354 </p>
355
356 <pre> static void Shutdown();
357
358 </pre>
359
360 <h4>Origin / Coordinate Space Translation</h4>
361
362 <pre> /**
363 * Translate the current origin by the specified (dx, dy). This
364 * creates a new local coordinate space relative to the current
365 * coordinate space.
366 */
367 void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
368
369 /**
370 * Returns the current translation from local coordinate space to
371 * world coordinate space. This represents the accumulated calls to
372 * Translate().
373 */
374 void GetTranslation(nscoord&amp; aX, nscoord&amp; aY) const { aX = mX; aY = mY; }
375
376 /**
377 * Returns the y-most of the bottommost band or 0 if there are no bands.
378 *
379 * @return PR_TRUE if there are bands and PR_FALSE if there are no bands
380 */
381 PRBool YMost(nscoord&amp; aYMost) const;
382 </pre>
383
384 <h4>Region Management</h4>
385
386 <pre> /**
387 * Returns a band starting at the specified y-offset. The band data
388 * indicates which parts of the band are available, and which parts
389 * are unavailable
390 *
391 * The band data that is returned is in the coordinate space of the
392 * local coordinate system.
393 *
394 * The local coordinate space origin, the y-offset, and the max size
395 * describe a rectangle that's used to clip the underlying band of
396 * available space, i.e.
397 * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
398 * coordinate space
399 *
400 * @param aYOffset the y-offset of where the band begins. The coordinate is
401 * relative to the upper-left corner of the local coordinate space
402 * @param aMaxSize the size to use to constrain the band data
403 * @param aBandData [in,out] used to return the list of trapezoids that
404 * describe the available space and the unavailable space
405 * @return NS_OK if successful and NS_ERROR_FAILURE if the band data is not
406 * not large enough. The 'count' member of the band data struct
407 * indicates how large the array of trapezoids needs to be
408 */
409 nsresult GetBandData(nscoord aYOffset,
410 const nsSize&amp; aMaxSize,
411 nsBandData&amp; aBandData) const;
412
413 /**
414 * Add a rectangular region of unavailable space. The space is
415 * relative to the local coordinate system.
416 *
417 * The region is tagged with a frame
418 *
419 * @param aFrame the frame used to identify the region. Must not be NULL
420 * @param aUnavailableSpace the bounding rect of the unavailable space
421 * @return NS_OK if successful
422 * NS_ERROR_FAILURE if there is already a region tagged with aFrame
423 */
424 nsresult AddRectRegion(nsIFrame* aFrame,
425 const nsRect&amp; aUnavailableSpace);
426
427 /**
428 * Resize the rectangular region associated with aFrame by the specified
429 * deltas. The height change always applies to the bottom edge or the existing
430 * rect. You specify whether the width change applies to the left or right edge
431 *
432 * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
433 * tagged with aFrame
434 */
435 enum AffectedEdge {LeftEdge, RightEdge};
436 nsresult ResizeRectRegion(nsIFrame* aFrame,
437 nscoord aDeltaWidth,
438 nscoord aDeltaHeight,
439 AffectedEdge aEdge = RightEdge);
440
441 /**
442 * Offset the region associated with aFrame by the specified amount.
443 *
444 * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
445 * tagged with aFrame
446 */
447 nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
448
449 /**
450 * Remove the region associated with aFrane.
451 *
452 * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
453 * tagged with aFrame
454 */
455 nsresult RemoveRegion(nsIFrame* aFrame);
456
457 /**
458 * Clears the list of regions representing the unavailable space.
459 */
460 void ClearRegions();
461 </pre>
462
463 <h4>Float Impact</h4>
464
465 <pre> /**
466 * Methods for dealing with the propagation of float damage during
467 * reflow.
468 */
469 PRBool HasFloatDamage()
470 {
471 return !mFloatDamage.IsEmpty();
472 }
473
474 void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
475 {
476 mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
477 }
478
479 PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
480 {
481 return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
482 }
483 </pre>
484
485 <h4>Debug Only Methods</h4>
486
487 <pre> /**
488 * Dump the state of the spacemanager out to a file
489 */
490 nsresult List(FILE* out);
491
492 void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
493
494 </pre>
495
496 <h4>Unused / Obsolete Methods</h4>
497
498 <pre> /*
499 * Get the frame that's associated with the space manager. This frame
500 * created the space manager, and the world coordinate space is
501 * relative to this frame.
502 *
503 * You can use QueryInterface() on this frame to get any additional
504 * interfaces.
505 */
506 nsIFrame* GetFrame() const { return mFrame; }
507
508 </pre>
509
510 <h3>Implementation Notes</h3>
511
512 <h4></h4>
513
514 <h4>Algorithm 1: GetBandData</h4>
515 <p>
516 GetBandData is used to provide information to clients about what space if
517 available and unavailable in a band of space. &nbsp;The client provides a
518 vertical offset, the yOffset, that corresponds to the band that is of interest.
519 &nbsp;This will be the y offset of the frame that is being reflowed. &nbsp;The
520 caller also provides a collection of BandData objects (an array) and the
521 number of items that the collection can handle. &nbsp;If the collection is
522 too small, then an error is returned and the count is updated to indicate
523 the size required.
524 </p>
525
526 <p>
527 The algorithm to provide the band data is as follows:
528 </p>
529 <ul>
530 <li>Get a &nbsp;vertical offset in world coordinates (instead of frame-relative
531 coordinates) by adding the y-origin of the SpaceManager to the y offset passed
532 in</li>
533 <li>If the (adjusted) y value passed in is greater than the greatest band
534 being managed, then all space is available so a single trapezoid is returned,
535 marked as available and sized to the maximum size value (passed in).</li>
536 <li>If the (adjusted) y offset intersects a band, then gather the band
537 data:</li>
538 <ul>
539 <li>walk the internal bandData list from head to tail</li>
540 <li>for each band data entry, see if the top of the band is greater than
541 the (adjusted) y offset requested</li>
542 <li>if it is, then band is below the offset requested, so the area between
543 the band and the y offset is available - create a trapezoid with that region
544 and return it.</li>
545 <li>if the (adjusted) y offset is between the band top and bottom, then
546 get the available space for the band by calling GetBandAvailableSpace</li>
547 <li>otherwise, move to the next band</li>
548 </ul>
549 </ul>
550 <h5>GetBandAvailableSpace:</h5>
551 This method is called from GetBandData only. It walks all of the bands in
552 the space manager and determines which bands intersect with the band passed
553 in, and if within those bands there are regions that are available or occupied.
554
555 <ul>
556 <li>First, walk all of the bands until a band that is to the right of the
557 desired offset is located</li>
558 <li>Starting at that band, &nbsp;walk the remaining bands:</li>
559 <ul>
560 <li>if the current band is to the right of the requested band, then there
561 is available space.&nbsp;</li>
562 <ul>
563 <li>if there is more room in the bandData collection, then add a trapezoid
564 to the bandData collection such that it is marked as available and has a
565 rect that represents the space between the reference band tna dht band being
566 examined</li>
567 <li>if there is no more room in the BandData collection, estimate the
568 number of entries requires as the current count + twice the number of bands
569 below the reference band, plus two. &nbsp;Return an error code so the caller
570 can reallocate the collection and try again.</li>
571 </ul>
572 <li>check the size of the collection again, if there is no room left
573 then estimate the number of items requires as the current count + twice the
574 number of bands below the band in question plus one.&nbsp;</li>
575 <li>create a new trapezoid in the band collection that has a region corresponding
576 to the reference band rect, marked as occupied by either a single or multiple
577 frames.</li>
578 <li>move to the next band</li>
579 </ul>
580 <li>after walking all of the band data, se if we have reached the right
581 edge of the band.&nbsp;</li>
582 <ul>
583 <li>If not, then check for space in the band collection</li>
584 <ul>
585 <li>if there is no room left, then set the count to the current count
586 plus 1 and return an error.</li>
587 <li>otherwise, create another entry in the band collection, marked
588 as available, and with a rect corresponding to the area remainin in the band
589 (eg. from the right edge of the last band rect to the right edge of the band).</li>
590 </ul>
591 </ul>
592 </ul>
593
594 <h4>Algorithm 2: AddRectRegion</h4>
595 Clients call into this method to notify the Space Manager that a new frame
596 is occupying some space.
597
598 <ul>
599 <li>First, try to get frame info for the frame. If it is found, return
600 an error since the frame is already associated with a region in the Space
601 Manager.</li>
602 <li>Next, create a rect from the occupied space passed in by the caller,
603 transforming it first to world-coordinates by adding the Space Manager's
604 offset to the occupied space rect passed in.</li>
605 <li>Create a new Frame Info instance for the frame and rect, returning
606 an error if allocation fails.</li>
607 <li>Check if the occupied space rect (adjusted) is empty, if so, return
608 an error &nbsp;(<font color="#cc0000">NOTE: this could be done earlier, or
609 prevented by the caller</font>)</li>
610 <li>Allocate a new BandRect instance with the rect and frame as constructor
611 arguments, and insert it into the collection via InsertBandRect</li>
612 </ul>
613 <h5>InsertBandRect:</h5>
614 Internal method to insert a band rect into the BandList in the correct location.
615 There are several cases it has to handle, as specified in the source file
616 comments:
617
618 <pre>// When comparing a rect to a band there are seven cases to consider.
619 // 'R' is the rect and 'B' is the band.
620 //
621 // Case 1 Case 2 Case 3 Case 4
622 // ------ ------ ------ ------
623 // +-----+ +-----+ +-----+ +-----+
624 // | R | | R | +-----+ +-----+ | | | |
625 // +-----+ +-----+ | | | R | | B | | B |
626 // +-----+ | B | +-----+ | | +-----+ | |
627 // | | | | +-----+ | R | +-----+
628 // | B | +-----+ +-----+
629 // | |
630 // +-----+
631 //
632 //
633 //
634 // Case 5 Case 6 Case 7
635 // ------ ------ ------
636 // +-----+ +-----+ +-----+ +-----+
637 // | | | R | | B | | | +-----+
638 // | B | +-----+ +-----+ | R | | B |
639 // | | | | +-----+
640 // +-----+ +-----+
641 // +-----+
642 // | R |
643 // +-----+
644 //
645 </pre>
646 <ul>
647 <li>First, check for the easiest case, where there are no existing band
648 rects, or the band rect passed in is below the bottommost rect. In this case,
649 just append the band rect and return.</li>
650 <li>Starting at the head of the list of bandRects, check for intersection
651 with the rect passed in:</li>
652 <ul>
653 <li>case #1: the rect is totally above the current band rect, so insert
654 a new band rect before the current bandRect</li>
655 <li>cases #2 and #7: the rect is partially above the band rect, so it
656 is divided into two bandRects, one entirely above the band, and one containing
657 the remainder of the rect. &nbsp;Insert the part that is totally above the
658 bandRect before the current bandRect, as in case #1 above, and adjust the
659 other band rect to exclude the part already added.</li>
660 <li>case #5: the rect is totally below the current bandRect, so just
661 skip to the next band</li>
662 <li>case #3 and #4: rect is at least partially intersection with the
663 bandRect, so divide the current band into two parts, where the top part is
664 above the current rect. &nbsp;Move to the new band just created, which is
665 the next band.</li>
666 <li>case #6: the rect shares the bottom and height with the bandRect,
667 so just add the rect to the band.</li>
668 <li>case #4 and #7: create a new rect for the part that overlaps the
669 bandRect, and add it to the current bandRect (similar to case #6) and then
670 move on to the next band, removing that part from the rect passed in. &nbsp;If
671 no more bands, append the rect passed in to the end of the bandRect list.</li>
672 </ul>
673 </ul>
674 <i>This algorithm is pretty confusing - basically what needs to happen is
675 that rects and bands need to be divided up so that complicated cases like
676 #2, #4, and #7, are reduced to simpler cases where the rects is totally above,
677 below, or between a band rect. &nbsp;From the current implementation, it
678 might be worth verifying that the final result of the inserts is a correctly
679 ordered liest of bandRects (debug mode only).</i>
680
681
682 <h4>Algorithm 3: RemoveRegion</h4>
683 When a float is removed, the Space Manager is notified by a call to RemoveRegion,
684 passing in the frame that is being removed.
685
686 <ul>
687 <li>Get the FrameInfo for the frame passed in. If not found, an error is
688 returned.</li>
689 <li>If the rect for the frame is not empty, then visit each band in the
690 bandList:</li>
691 <ul>
692 <li>for each rect in the band:
693
694 </li>
695 </ul>
696 <ul>
697 <ul>
698 <li>if the bandRect is occupied by the frame, either remove the frame
699 from the bandRect (if there are other frames sharing it) and remember that
700 it was shared</li>
701 <li>otherwise simply remove the bandRect (no other frames share it).</li>
702 <li>if the bandRect was shared, then try to coalesce adjacent bandRects</li>
703 <ul>
704 <li>if the previous bandRect is directly next to the current bandRect,
705 and they have the same frame list, then make the current bandRect cover the
706 previous bandRect's full region (adjust the left edge to be that of the previous
707 bandRect) and remove the previous bandRect.</li>
708 </ul>
709 </ul>
710 </ul>
711 <ul>
712 <li>if the current band or prior band had a rect occupied byu the frame,
713 then try to join the two bands via JoinBands</li>
714 </ul>
715 <li>Finally, destroy the frameInfo for the frame.
716
717 </li>
718 </ul>
719
720 <br>
721
722 <hr width="100%" size="2">
723 <h2>Cross-Component Algorithms</h2>
724
725 <br>
726
727
728
729 <hr width="100%" size="2">
730 <h2>Tech Notes</h2>
731 <ul>
732 <li>
733
734 </li>
735
736 </ul>
737
738
739
740
741
742 </body>
743 </html>

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial