Guillotiere

https://docs.rs/guillotiere/
Admin
Guillotiere is a dynamic texture atlas allocator in Rust that uses the guillotine algorithm to...
Tokens:22,979
Snippets:135
Trust Score:9.1
Update:1 month ago
Show doc for...
Tokens:
Raw
### Grid Layout Example

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html

A visual example of a grid layout that could be generated by different split sequences.

```text
+---------+------+
|    A    |  B   |
|         |      |
+---------+------+
|    C    |  D   |
|         |      |
+---------+------+
```

--------------------------------

### ASCII Tree Coalescing Example

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Visual representation of how deallocating a rectangle can lead to node lifting in the tree structure.

```ascii
+-----------+   AB  C                 +-----------+    ABC
```

--------------------------------

### Get atlas size

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Returns the total size of the atlas.

```rust
pub fn size(&self) -> Size {
        self.size
    }
```

--------------------------------

### Grow Atlas and Allocate in Large Bucket

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Demonstrates growing an atlas past the large threshold and verifying that a subsequent allocation successfully searches the large bucket.

```rust
// Atlas is a single free root node in SMALL_BUCKET (20 < 32).
// Grow it past the large threshold.
atlas2.grow(size2(512, 512));

// Allocate something that searches LARGE_BUCKET.
assert!(
    atlas2.allocate(size2(500, 500)).is_some(),
    "Single-root grow should update the free list bucket"
);
}
```

--------------------------------

### AtlasAllocator Initialization

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Methods for creating a new AtlasAllocator instance with default or custom options.

```rust
impl AtlasAllocator {
    /// Create an atlas allocator.
    pub fn new(size: Size) -> Self {
        AtlasAllocator::with_options(size, &DEFAULT_OPTIONS)
    }

    /// Create an atlas allocator with the provided options.
    pub fn with_options(size: Size, options: &AllocatorOptions) -> Self {
        assert!(options.alignment.width > 0);
        assert!(options.alignment.height > 0);
        assert!(size.width > 0);
        assert!(size.height > 0);
        assert!(options.large_size_threshold >= options.small_size_threshold);

        let mut free_lists = [Vec::new(), Vec::new(), Vec::new()];
        let bucket = free_list_for_size(
            options.small_size_threshold,
            options.large_size_threshold,
            &size,
        );
        free_lists[bucket].push(AllocIndex(0));

        AtlasAllocator {
            nodes: vec![Node {
                parent: AllocIndex::NONE,
                next_sibling: AllocIndex::NONE,
                prev_sibling: AllocIndex::NONE,
                rect: size.into(),
                kind: NodeKind::Free,
                orientation: Orientation::Vertical,
            }],
            free_lists,
            generations: vec![Wrapping(0)],
            unused_nodes: AllocIndex::NONE,
            alignment: options.alignment,
            small_size_threshold: options.small_size_threshold,
            large_size_threshold: options.large_size_threshold,
            size,
            root_node: AllocIndex(0),
        }
    }
```

--------------------------------

### Node Allocation and Deallocation Methods

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Methods for creating new nodes, marking nodes as unused, and managing free lists.

```rust
    fn new_node(&mut self) -> AllocIndex {
        let idx = self.unused_nodes;
        if idx.index() < self.nodes.len() {
            self.unused_nodes = self.nodes[idx.index()].next_sibling;
            self.generations[idx.index()] += Wrapping(1);
            debug_assert_eq!(self.nodes[idx.index()].kind, NodeKind::Unused);
            return idx;
        }

        self.nodes.push(Node {
            parent: AllocIndex::NONE,
            next_sibling: AllocIndex::NONE,
            prev_sibling: AllocIndex::NONE,
            rect: Rectangle::zero(),
            kind: NodeKind::Unused,
            orientation: Orientation::Horizontal,
        });

        self.generations.push(Wrapping(0));

        AllocIndex(self.nodes.len() as u32 - 1)
    }

    fn mark_node_unused(&mut self, id: AllocIndex) {
        debug_assert!(self.nodes[id.index()].kind != NodeKind::Unused);
        self.nodes[id.index()].kind = NodeKind::Unused;
        self.nodes[id.index()].next_sibling = self.unused_nodes;
        self.unused_nodes = id;
    }
```

```rust
    fn add_free_rect(&mut self, id: AllocIndex, size: &Size) {
        debug_assert_eq!(self.nodes[id.index()].kind, NodeKind::Free);
        let bucket = free_list_for_size(self.small_size_threshold, self.large_size_threshold, size);
        self.free_lists[bucket].push(id);
    }
```

--------------------------------

### Tree Structure Comparison for Grid Layouts

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html

Comparison of tree structures resulting from vertical versus horizontal split sequences for the same layout.

```text
 Tree            | Layout             Tree            | Layout
-----------------+------------       -----------------+------------
        #        |                           #        |
        |        |                           |        |
    +---+---+ . .|. Vertical             +---+---+ . .|. Horizontal
    |       |    |                       |       |    |
    #       #    |               or      #       #    |
    |       |    |                       |       |    |
  +-+-+ . +-+-+ .|. Horizontal         +-+-+ . +-+-+ .|. Vertical
  |   |   |   |  |                     |   |   |   |  |
  A   B   C   D  |                     A   C   B   D  |
```

--------------------------------

### SimpleAtlasAllocator

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.SimpleAtlasAllocator.html

Documentation for the SimpleAtlasAllocator struct and its public methods.

```APIDOC
## SimpleAtlasAllocator

### Description
A simpler atlas allocator implementation that can allocate rectangles but not deallocate them.

### Methods

#### new

##### Description
Create a simple atlas allocator with default options.

##### Signature
```rust
pub fn new(size: Size) -> Self
```

##### Parameters
- **size** (Size) - Required - The size of the atlas.

#### with_options

##### Description
Create a simple atlas allocator with the provided options.

##### Signature
```rust
pub fn with_options(size: Size, options: &AllocatorOptions) -> Self
```

##### Parameters
- **size** (Size) - Required - The size of the atlas.
- **options** (&AllocatorOptions) - Required - The allocator options.

#### clear

##### Description
Drop all rectangles, clearing the atlas to its initial state.

##### Signature
```rust
pub fn clear(&mut self)
```

#### reset

##### Description
Clear the allocator and reset its size and options.

##### Signature
```rust
pub fn reset(&mut self, size: Size, options: &AllocatorOptions)
```

##### Parameters
- **size** (Size) - Required - The new size of the atlas.
- **options** (&AllocatorOptions) - Required - The new allocator options.

#### is_empty

##### Description
Returns whether the atlas is empty.

##### Signature
```rust
pub fn is_empty(&self) -> bool
```

#### size

##### Description
The total size of the atlas.

##### Signature
```rust
pub fn size(&self) -> Size
```

#### allocate

##### Description
Allocate a rectangle in the atlas.

##### Signature
```rust
pub fn allocate(&mut self, requested_size: Size) -> Option<Rectangle>
```

##### Parameters
- **requested_size** (Size) - Required - The size of the rectangle to allocate.

##### Returns
- **Option<Rectangle>** - The allocated rectangle, or `None` if allocation fails.

#### grow

##### Description
Resize the atlas without changing the allocations. This method is not allowed to shrink the width or height of the atlas.

##### Signature
```rust
pub fn grow(&mut self, new_size: Size)
```

##### Parameters
- **new_size** (Size) - Required - The new size of the atlas.

#### init_from_allocator

##### Description
Initialize this simple allocator with the content of an atlas allocator.

##### Signature
```rust
pub fn init_from_allocator(&mut self, src: &AtlasAllocator)
```

##### Parameters
- **src** (&AtlasAllocator) - Required - The source atlas allocator.

```

--------------------------------

### Initialize from another allocator

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Initializes the current allocator state using data from an existing AtlasAllocator.

```rust
pub fn init_from_allocator(&mut self, src: &AtlasAllocator) {
        self.size = src.size;
        self.alignment = src.alignment;
        self.small_size_threshold = src.small_size_threshold;
        self.large_size_threshold = src.large_size_threshold;

        for bucket in 0..NUM_BUCKETS {
            self.free_rects[bucket].clear();

            for id in src.free_lists[bucket].iter() {
                // During tree simplification we don't remove merged nodes from the free list, so we have
                // to handle it here.
                // This is a tad awkward, but lets us avoid having to maintain a doubly linked list for
                // the free list (which would be needed to remove nodes during tree simplification).
                if src.nodes[id.index()].kind != NodeKind::Free {
                    continue;
                }

                self.free_rects[bucket].push(src.nodes[id.index()].rect);
            }
        }
    }
```

--------------------------------

### ChangeList::empty

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.ChangeList.html

Creates an empty ChangeList instance. This is a public constructor method for the ChangeList struct.

```APIDOC
## ChangeList::empty

### Description
Creates a new empty ChangeList.

### Method
pub fn empty() -> Self

### Parameters
None

### Returns
- **Self** - A new ChangeList instance with empty changes and failures vectors.

### Example
```rust
let change_list = ChangeList::empty();
```
```

--------------------------------

### grow method

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Expands the atlas dimensions without moving existing allocations. It requires that the new dimensions are not smaller than the current ones and handles free space expansion or addition.

```rust
pub fn grow(&mut self, new_size: Size) {
        assert!(new_size.width >= self.size.width);
        assert!(new_size.height >= self.size.height);

        let old_size = self.size;
        self.size = new_size;

        let dx = new_size.width - old_size.width;
        let dy = new_size.height - old_size.height;

        // If there is only one node and it is free, just grow it.
        let root = &mut self.nodes[self.root_node.index()];
        if root.kind == NodeKind::Free && root.rect.size() == old_size {
            root.rect.max = root.rect.min + new_size.to_vector();
            // The node's size changed, move it to the correct free list bucket.
            self.update_free_list_bucket(self.root_node);
            return;
        }

        let root_orientation = root.orientation;
        let grows_in_root_orientation = match root_orientation {
            Orientation::Horizontal => dx > 0,
            Orientation::Vertical => dy > 0,
        };

        // If growing along the orientation of the root node, find the right-or-bottom-most sibling
        // and either grow it (if it is free) or append a free node next.
        if grows_in_root_orientation {
            let mut sibling = self.root_node;
            while self.nodes[sibling.index()].next_sibling != AllocIndex::NONE {
                sibling = self.nodes[sibling.index()].next_sibling;
            }
            let node = &mut self.nodes[sibling.index()];
            if node.kind == NodeKind::Free {
                node.rect.max += match root_orientation {
                    Orientation::Horizontal => vec2(dx, 0),
                    Orientation::Vertical => vec2(0, dy),
                };
                // The node's size changed, move it to the correct free list bucket.
                self.update_free_list_bucket(sibling);
            } else {
                let rect = match root_orientation {
                    Orientation::Horizontal => {
                        let min = point2(node.rect.max.x, node.rect.min.y);
                        let max = min + vec2(dx, node.rect.height());
                        Rectangle { min, max }
                    }
                    Orientation::Vertical => {
                        let min = point2(node.rect.min.x, node.rect.max.y);
                        let max = min + vec2(node.rect.width(), dy);
                        Rectangle { min, max }
                    }
                };

                let next = self.new_node();
                self.nodes[sibling.index()].next_sibling = next;
                self.nodes[next.index()] = Node {
                    kind: NodeKind::Free,
                    rect,
                    prev_sibling: sibling,
                    next_sibling: AllocIndex::NONE,
                    parent: AllocIndex::NONE,
                    orientation: root_orientation,
                };

                self.add_free_rect(next, &rect.size());
            }
        }

        let grows_in_opposite_orientation = match root_orientation {
            Orientation::Horizontal => dy > 0,
            Orientation::Vertical => dx > 0,
        };

        if grows_in_opposite_orientation {
            let free_node = self.new_node();
            let new_root = self.new_node();

            let old_root = self.root_node;
            self.root_node = new_root;
```

--------------------------------

### Subdivision layout visualization

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html

A visual representation of a rectangle subdivision layout.

```text
+-----------+----------+---+---+--+---------+---+
|           |          | C | D |E | F       | G |
|           |          +---+---+--+---------+---+
|     A     |    B     |                        |
|           |          |           H            |
|           |          |                        |
+------+----+----------+-+----------------------+
|      |        J        |                      |
|  I   +-----------------+          L           |
|      |        K        |                      |
+------+-----------------+----------------------+
```

--------------------------------

### atlas_basic test

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

A basic unit test verifying allocation and deallocation sequences in the AtlasAllocator.

```rust
#[test]
fn atlas_basic() {
    let mut atlas = AtlasAllocator::new(size2(1000, 1000));

    let full = atlas.allocate(size2(1000, 1000)).unwrap().id;
    assert!(atlas.allocate(size2(1, 1)).is_none());

    atlas.deallocate(full);

    let a = atlas.allocate(size2(100, 1000)).unwrap().id;
    let b = atlas.allocate(size2(900, 200)).unwrap().id;
    let c = atlas.allocate(size2(300, 200)).unwrap().id;
    let d = atlas.allocate(size2(200, 300)).unwrap().id;
    let e = atlas.allocate(size2(100, 300)).unwrap().id;
    let f = atlas.allocate(size2(100, 300)).unwrap().id;
    let g = atlas.allocate(size2(100, 300)).unwrap().id;

    atlas.deallocate(b);
    atlas.deallocate(f);
    atlas.deallocate(c);
    atlas.deallocate(e);
    let h = atlas.allocate(size2(500, 200)).unwrap().id;
    atlas.deallocate(a);
    let i = atlas.allocate(size2(500, 200)).unwrap().id;
    atlas.deallocate(g);
    atlas.deallocate(h);
    atlas.deallocate(d);
    atlas.deallocate(i);

    let full = atlas.allocate(size2(1000, 1000)).unwrap().id;
    assert!(atlas.allocate(size2(1, 1)).is_none());
    atlas.deallocate(full);
}
```

--------------------------------

### resize_and_rearrange method

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Rearranges existing allocations to fit within a new atlas size. It sorts allocations by area, clears the current state, and attempts to reallocate them into the new dimensions.

```rust
pub fn resize_and_rearrange(&mut self, new_size: Size) -> ChangeList {
        let mut allocs = Vec::with_capacity(self.nodes.len());
        for (i, node) in self.nodes.iter().enumerate() {
            if node.kind != NodeKind::Alloc {
                continue;
            }
            let id = self.alloc_id(AllocIndex(i as u32));
            allocs.push(Allocation {
                id,
                rectangle: node.rect,
            });
        }

        allocs.sort_by_key(|alloc| safe_area(&alloc.rectangle));
        allocs.reverse();

        self.size = new_size;
        self.clear();

        let mut changes = Vec::new();
        let mut failures = Vec::new();

        for old in allocs {
            let size = old.rectangle.size();
            if let Some(new) = self.allocate(size) {
                changes.push(Change { old, new });
            } else {
                failures.push(old);
            }
        }

        ChangeList { changes, failures }
    }
```

--------------------------------

### Allocator Implementation Source

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

The core implementation of the guillotine allocator, including bucket definitions, allocation indices, node structures, and configuration options.

```rust
1#[cfg(test)]
2extern crate std;
3
4use alloc::vec;
5use alloc::vec::Vec;
6use crate::{Rectangle, Size};
7use euclid::{vec2, point2, size2};
8
9use core::num::Wrapping;
10
11const LARGE_BUCKET: usize = 2;
12const MEDIUM_BUCKET: usize = 1;
13const SMALL_BUCKET: usize = 0;
14const NUM_BUCKETS: usize = 3;
15
16fn free_list_for_size(small_threshold: i32, large_threshold: i32, size: &Size) -> usize {
17    if size.width >= large_threshold || size.height >= large_threshold {
18        LARGE_BUCKET
19    } else if size.width >= small_threshold || size.height >= small_threshold {
20        MEDIUM_BUCKET
21    } else {
22        SMALL_BUCKET
23    }
24}
25
26#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
27#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
28struct AllocIndex(u32);
29impl AllocIndex {
30    const NONE: AllocIndex = AllocIndex(u32::MAX);
31
32    fn index(self) -> usize {
33        self.0 as usize
34    }
35
36    fn is_none(self) -> bool {
37        self == AllocIndex::NONE
38    }
39
40    fn is_some(self) -> bool {
41        self != AllocIndex::NONE
42    }
43}
44
45/// ID referring to an allocated rectangle.
46#[repr(C)]
47#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
48#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
49pub struct AllocId(pub(crate) u32);
50
51impl AllocId {
52    pub fn serialize(&self) -> u32 {
53        self.0
54    }
55
56    pub fn deserialize(bytes: u32) -> Self {
57        AllocId(bytes)
58    }
59}
60
61const GEN_MASK: u32 = 0xFF000000;
62const IDX_MASK: u32 = 0x00FFFFFF;
63
64#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
65#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
66enum Orientation {
67    Vertical,
68    Horizontal,
69}
70
71impl Orientation {
72    fn flipped(self) -> Self {
73        match self {
74            Orientation::Vertical => Orientation::Horizontal,
75            Orientation::Horizontal => Orientation::Vertical,
76        }
77    }
78}
79
80#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
81#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
82pub enum NodeKind {
83    Container,
84    Alloc,
85    Free,
86    Unused,
87}
88
89#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
90#[derive(Clone, Debug)]
91struct Node {
92    parent: AllocIndex,
93    next_sibling: AllocIndex,
94    prev_sibling: AllocIndex,
95    kind: NodeKind,
96    orientation: Orientation,
97    rect: Rectangle,
98}
99
100/// Options to tweak the behavior of the atlas allocator.
101#[repr(C)]
102#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
103#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
104pub struct AllocatorOptions {
105    /// Round the rectangle sizes up to a multiple of this value.
106    ///
107    /// Width and height alignments must be superior to zero.
108    ///
109    /// Default value: (1, 1),
110    pub alignment: Size,
111
112    /// Value below which a size is considered small.
113    ///
114    /// This is value is used to speed up the storage and lookup of free rectangles.
115    /// This value must be inferior or equal to `large_size_threshold`
116    ///
117    /// Default value: 32,
118    pub small_size_threshold: i32,
119
120    /// Value above which a size is considered large.
121    ///
122    /// This is value is used to speed up the storage and lookup of free rectangles.
123    /// This value must be inferior or equal to `large_size_threshold`
124    ///
125    /// Default value: 256,
126    pub large_size_threshold: i32,
127}
128
129pub const DEFAULT_OPTIONS: AllocatorOptions = AllocatorOptions {
130    alignment: size2(1,  1),
131    large_size_threshold: 256,
132    small_size_threshold: 32,
133};
134
135impl Default for AllocatorOptions {
136    fn default() -> Self {
137        DEFAULT_OPTIONS
138    }
139}
```

--------------------------------

### Deallocation and Tree Merging Visualization

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html

Visual representation of how deallocating a node allows it to merge with siblings and potentially lift up the tree structure.

```text
+-------+---+         #               +-----------+         #                 #
|       |   |         |               |           |         |                 |
| AB    | C |     +---+---+           | ABC       |     +---+---+         +---+---+
|       |   |     |       |           |           |     |       |         |       |
+-------+---+     #       D           +-----------+     #       D        ABC      D
| D         |     |            ->     | D         |     |           ->
|           |   +-+-+                 |           |     +
|           |   |   |                 |           |     |
+-----------+   AB  C                 +-----------+    ABC
```

--------------------------------

### Finding a Suitable Rectangle

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Searches for a suitable rectangle in the free lists based on the requested size, using either best-fit or worst-fit strategies.

```rust
fn find_suitable_rect(&mut self, requested_size: &Size) -> AllocIndex {
        let ideal_bucket = free_list_for_size(
            self.small_size_threshold,
            self.large_size_threshold,
            requested_size,
        );

        let use_worst_fit = ideal_bucket == LARGE_BUCKET;
        for bucket in ideal_bucket..NUM_BUCKETS {
            let mut candidate_score = if use_worst_fit { 0 } else { i32::MAX };
            let mut candidate = None;

            let mut freelist_idx = 0;
            while freelist_idx < self.free_lists[bucket].len() {
                let id = self.free_lists[bucket][freelist_idx];

                // During tree simplification we don't remove merged nodes from the free list, so we have
                // to handle it here.
                // This is a tad awkward, but lets us avoid having to maintain a doubly linked list for
                // the free list (which would be needed to remove nodes during tree simplification).
                if self.nodes[id.index()].kind != NodeKind::Free {
                    // remove the element from the free list
                    self.free_lists[bucket].swap_remove(freelist_idx);
                    continue;
                }

                let size = self.nodes[id.index()].rect.size();
                let dx = size.width - requested_size.width;
                let dy = size.height - requested_size.height;

                if dx >= 0 && dy >= 0 {
                    if dx == 0 || dy == 0 {
                        // Perfect fit!
                        candidate = Some((id, freelist_idx));
                        break;
                    }

                    // Favor the largest minimum dimension, except for small
                    // allocations.
                    let score = i32::min(dx, dy);
                    if (use_worst_fit && score > candidate_score)
                        || (!use_worst_fit && score < candidate_score)
                    {
                        candidate_score = score;
```

--------------------------------

### AllocatorOptions

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Options to tweak the behavior of the atlas allocator.

```APIDOC
## AllocatorOptions

### Description
Options to tweak the behavior of the atlas allocator.

### Fields
- **alignment** (Size) - Round the rectangle sizes up to a multiple of this value. Width and height alignments must be superior to zero. Default value: (1, 1).
- **small_size_threshold** (i32) - Value below which a size is considered small. Used to speed up storage and lookup of free rectangles. Must be inferior or equal to large_size_threshold. Default value: 32.
- **large_size_threshold** (i32) - Value above which a size is considered large. Used to speed up storage and lookup of free rectangles. Must be inferior or equal to large_size_threshold. Default value: 256.

### Default
- **DEFAULT_OPTIONS**: AllocatorOptions with alignment (1, 1), large_size_threshold 256, small_size_threshold 32.

```

--------------------------------

### Reset the allocator with new size and options

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Updates alignment, size thresholds, and size, then calls clear to reset the allocator state.

```rust
    /// Clear the allocator and reset its size and options.
    pub fn reset(&mut self, size: Size, options: &AllocatorOptions) {
        self.alignment = options.alignment;
        self.small_size_threshold = options.small_size_threshold;
        self.large_size_threshold = options.large_size_threshold;
        self.size = size;

        self.clear();
    }
```

--------------------------------

### Test grow_free_list_bucket

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Regression test ensuring that growing a free node in-place correctly updates its bucket, allowing subsequent large allocations to succeed.

```rust
#[test]
fn grow_free_list_bucket() {
    // Regression test: growing a free node in-place must move it to the correct
    // free list bucket, otherwise allocations searching a higher bucket won't find it.

    let mut atlas = AtlasAllocator::with_options(
        size2(100, 100),
        &AllocatorOptions {
            small_size_threshold: 32,
            large_size_threshold: 256,
            ..DEFAULT_OPTIONS
        },
    );

    // Allocate most of the atlas, leaving a thin free strip along the bottom.
    // The strip's min dimension (10) is below small_size_threshold (32), so it
    // lands in the SMALL_BUCKET.
    let a = atlas.allocate(size2(100, 90)).unwrap().id;

    // Grow the atlas so that the free strip extends from 10 to 1010 pixels tall.
    // Its min dimension is now 100 (>= small_threshold), so it should move out of
    // SMALL_BUCKET. Before the fix it stayed in SMALL_BUCKET and large allocations
    // could not find it.
    atlas.grow(size2(100, 1100));

    // This allocation needs a rect of 100x500. The ideal bucket is LARGE_BUCKET
    // (500 >= 256). Without the bucket fix the 100x1010 free strip would still be
    // in SMALL_BUCKET and this allocation would fail.
    assert!(
        atlas.allocate(size2(100, 500)).is_some(),
        "Should find the grown free strip in the correct bucket"
    );

    atlas.deallocate(a);

    // Also test the single-root early-return path in grow().
    let mut atlas2 = AtlasAllocator::with_options(
        size2(20, 20),
        &AllocatorOptions {
            small_size_threshold: 32,
            large_size_threshold: 256,
            ..DEFAULT_OPTIONS
        },
    );
}
```

--------------------------------

### Allocation and Change Structures

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Data structures representing allocations, changes, and lists of changes within the allocator.

```rust
#[repr(C)]
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct Allocation {
    pub id: AllocId,
    pub rectangle: Rectangle,
}

#[repr(C)]
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct Change {
    pub old: Allocation,
    pub new: Allocation,
}

#[derive(Clone, Debug, PartialEq)]
pub struct ChangeList {
    pub changes: Vec<Change>,
    pub failures: Vec<Allocation>,
}

impl ChangeList {
    pub fn empty() -> Self {
        ChangeList {
            changes: Vec::new(),
            failures: Vec::new(),
        }
    }
}
```

--------------------------------

### size2

Source: https://docs.rs/guillotiere/latest/guillotiere/fn.size2.html

Creates a Size2D value using the provided width and height. This is a convenience function equivalent to Size2D::new(w, h).

```APIDOC
## size2

### Description
Creates a `Size2D` value with the given width and height. This is a shorthand for `Size2D::new(w, h)`.

### Function Signature
```rust
pub const fn size2<T, U>(w: T, h: T) -> Size2D<T, U>
```

### Parameters
- `w` (T) - The width component of the size.
- `h` (T) - The height component of the size.

### Returns
- `Size2D<T, U>` - A new `Size2D` instance with the specified width and height.

### Example
```rust
let size = size2(10, 20);
```
```

--------------------------------

### Node Splitting and Allocation Logic

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Handles the logic for splitting nodes and updating the allocator tree structure when allocating space, accounting for orientation changes and leftover rectangles.

```rust
let leftover_id;

if orientation == current_orientation {
    if !split_rect.is_empty() {
        let next_sibling = chosen_node.next_sibling;

        split_id = self.new_node();
        self.nodes[split_id.index()] = Node {
            parent: chosen_node.parent,
            next_sibling,
            prev_sibling: chosen_id,
            rect: split_rect,
            kind: NodeKind::Free,
            orientation: current_orientation,
        };

        self.nodes[chosen_id.index()].next_sibling = split_id;
        if next_sibling.is_some() {
            self.nodes[next_sibling.index()].prev_sibling = split_id;
        }
    } else {
        split_id = AllocIndex::NONE;
    }

    if !leftover_rect.is_empty() {
        self.nodes[chosen_id.index()].kind = NodeKind::Container;

        allocated_id = self.new_node();
        leftover_id = self.new_node();

        self.nodes[allocated_id.index()] = Node {
            parent: chosen_id,
            next_sibling: leftover_id,
            prev_sibling: AllocIndex::NONE,
            rect: allocated_rect,
            kind: NodeKind::Alloc,
            orientation: current_orientation.flipped(),
        };

        self.nodes[leftover_id.index()] = Node {
            parent: chosen_id,
            next_sibling: AllocIndex::NONE,
            prev_sibling: allocated_id,
            rect: leftover_rect,
            kind: NodeKind::Free,
            orientation: current_orientation.flipped(),
        };
    } else {
        // No need to split for the leftover area, we can allocate directly in the chosen node.
        allocated_id = chosen_id;
        let node = &mut self.nodes[chosen_id.index()];
        node.kind = NodeKind::Alloc;
        node.rect = allocated_rect;

        leftover_id = AllocIndex::NONE
    }
} else {
    self.nodes[chosen_id.index()].kind = NodeKind::Container;

    if !split_rect.is_empty() {
        split_id = self.new_node();
        self.nodes[split_id.index()] = Node {
            parent: chosen_id,
            next_sibling: AllocIndex::NONE,
            prev_sibling: AllocIndex::NONE,
            rect: split_rect,
            kind: NodeKind::Free,
            orientation: current_orientation.flipped(),
        };
    } else {
        split_id = AllocIndex::NONE;
    }

    if !leftover_rect.is_empty() {
        let container_id = self.new_node();
        self.nodes[container_id.index()] = Node {
            parent: chosen_id,
            next_sibling: split_id,
            prev_sibling: AllocIndex::NONE,
            rect: Rectangle::zero(),
            kind: NodeKind::Container,
            orientation: current_orientation.flipped(),
        };

        self.nodes[split_id.index()].prev_sibling = container_id;

        allocated_id = self.new_node();
        leftover_id = self.new_node();

        self.nodes[allocated_id.index()] = Node {
            parent: container_id,
            next_sibling: leftover_id,
            prev_sibling: AllocIndex::NONE,
            rect: allocated_rect,
            kind: NodeKind::Alloc,
            orientation: current_orientation,
        };

        self.nodes[leftover_id.index()] = Node {
            parent: container_id,
            next_sibling: AllocIndex::NONE,
            prev_sibling: allocated_id,
            rect: leftover_rect,
            kind: NodeKind::Free,
            orientation: current_orientation,
        };
    } else {
        allocated_id = self.new_node();
        self.nodes[allocated_id.index()] = Node {
            parent: chosen_id,
            next_sibling: split_id,
            prev_sibling: AllocIndex::NONE,
            rect: allocated_rect,
            kind: NodeKind::Alloc,
            orientation: current_orientation.flipped(),
        };

        self.nodes[split_id.index()].prev_sibling = allocated_id;
    }
```

--------------------------------

### Allocator

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

A dynamic texture atlas allocator using the guillotine algorithm. The guillotine algorithm is assisted by a data structure that keeps track of neighboring rectangles to provide fast deallocation and coalescing.

```APIDOC
## Allocator

### Description
A dynamic texture atlas allocator using the guillotine algorithm. The guillotine algorithm is assisted by a data structure that keeps track of neighboring rectangles to provide fast deallocation and coalescing.

### Goals
- Coalescing free rectangles can be expensive under real-time constraints; this implementation provides fast (constant time) search for merge candidates at the expense of some bookkeeping overhead.
- The subdivision scheme uses the worst fit variant of the guillotine algorithm for simplicity and CPU efficiency.

```

--------------------------------

### Iteration over Free Rectangles

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Invokes a callback for each free rectangle currently in the atlas.

```rust
/// Invoke a callback for each free rectangle in the atlas.
    pub fn for_each_free_rectangle<F>(&self, mut callback: F)
    where
        F: FnMut(&Rectangle),
    {
        for node in &self.nodes {
            if node.kind == NodeKind::Free {
                callback(&node.rect);
            }
        }
    }
```

--------------------------------

### Rearrange the atlas to reduce fragmentation

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Calls resize_and_rearrange with the current size, returning a ChangeList. Previous ids and rectangles become invalid after this operation.

```rust
    /// Recompute the allocations in the atlas and returns a list of the changes.
    ///
    /// Previous ids and rectangles are not valid anymore after this operation as each id/rectangle
    /// pair is assigned to new values which are communicated in the returned change list.
    /// Rearranging the atlas can help reduce fragmentation.
    pub fn rearrange(&mut self) -> ChangeList {
        let size = self.size;
        self.resize_and_rearrange(size)
    }
```

--------------------------------

### test_grow test

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Verifies that the atlas can be grown to a larger size.

```rust
#[test]
fn test_grow() {
    let mut atlas = AtlasAllocator::new(size2(1000, 1000));

    atlas.grow(size2(2000, 2000));

    let full = atlas.allocate(size2(2000, 2000)).unwrap().id;
```

--------------------------------

### Allocate a rectangle

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Allocates a rectangle of the requested size in the atlas, using bucket-based selection and splitting logic.

```rust
pub fn allocate(&mut self, mut requested_size: Size) -> Option<Rectangle> {
        if requested_size.is_empty() {
            return None;
        }

        adjust_size(self.alignment.width, &mut requested_size.width);
        adjust_size(self.alignment.height, &mut requested_size.height);

        let ideal_bucket = free_list_for_size(
            self.small_size_threshold,
            self.large_size_threshold,
            &requested_size,
        );

        let use_worst_fit = ideal_bucket == LARGE_BUCKET;

        let mut chosen_rect = None;
        for bucket in ideal_bucket..NUM_BUCKETS {
            let mut candidate_score = if use_worst_fit { 0 } else { i32::MAX };
            let mut candidate = None;

            for (index, rect) in self.free_rects[bucket].iter().enumerate() {
                let dx = rect.width() - requested_size.width;
                let dy = rect.height() - requested_size.height;

                if dx >= 0 && dy >= 0 {
                    if dx == 0 || dy == 0 {
                        // Perfect fit!
                        candidate = Some(index);
                        break;
                    }

                    let score = i32::min(dx, dy);
                    if (use_worst_fit && score > candidate_score)
                        || (!use_worst_fit && score < candidate_score)
                    {
                        candidate_score = score;
                        candidate = Some(index);
                    }
                }
            }

            if let Some(index) = candidate {
                let rect = self.free_rects[bucket].remove(index);
                chosen_rect = Some(rect);
                break;
            }
        }

        if let Some(rect) = chosen_rect {
            let (split_rect, leftover_rect, _) =
                guillotine_rect(&rect, requested_size, Orientation::Vertical);
            self.add_free_rect(&split_rect);
            self.add_free_rect(&leftover_rect);

            return Some(Rectangle {
                min: rect.min,
                max: rect.min + requested_size.to_vector(),
            });
        }

        None
    }
```

--------------------------------

### AllocId::serialize

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AllocId.html

Serializes the AllocId into a u32 value.

```APIDOC
## AllocId::serialize

### Description
Serializes the AllocId into a u32 value.

### Method
pub fn serialize(&self) -> u32

### Parameters
None.

### Returns
u32 - The serialized representation of the AllocId.

```

--------------------------------

### AllocatorOptions Struct Definition

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AllocatorOptions.html

The AllocatorOptions struct definition with its public fields and their descriptions.

```APIDOC
## Struct AllocatorOptions

### Description
Options to tweak the behavior of the atlas allocator.

### Definition
```rust
#[repr(C)]
pub struct AllocatorOptions {
    pub alignment: Size,
    pub small_size_threshold: i32,
    pub large_size_threshold: i32,
}
```

### Fields
- **alignment** (Size) - Round the rectangle sizes up to a multiple of this value. Width and height alignments must be superior to zero. Default value: (1, 1).
- **small_size_threshold** (i32) - Value below which a size is considered small. This value is used to speed up the storage and lookup of free rectangles. This value must be inferior or equal to `large_size_threshold`. Default value: 32.
- **large_size_threshold** (i32) - Value above which a size is considered large. This value is used to speed up the storage and lookup of free rectangles. This value must be inferior or equal to `large_size_threshold`. Default value: 256.

### Trait Implementations
- **Clone** - Provides `clone` and `clone_from` methods.
- **Copy** - Marker trait for types that can be copied.
- **Debug** - Provides `fmt` for formatting.
- **Default** - Provides `default` method returning the default value.
- **Eq** - Marker trait for equality.
- **Hash** - Provides `hash` and `hash_slice` methods.
- **PartialEq** - Provides `eq` and `ne` methods.
- **StructuralPartialEq** - Marker trait for structural equality.

### Auto Trait Implementations
- Freeze
- RefUnwindSafe
- Send
- Sync
- Unpin
- UnsafeUnpin
- UnwindSafe

### Blanket Implementations
- Any, Borrow, BorrowMut, CloneToUninit, From, Into, ToOwned, TryFrom, TryInto

```

--------------------------------

### AtlasAllocator Size Query

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Retrieves the total size of the atlas.

```rust
    /// The total size of the atlas.
    pub fn size(&self) -> Size {
        self.size
    }
```

--------------------------------

### Guillotine Splitting Logic

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Determines how to split a chosen rectangle into allocated, split, and leftover regions based on requested size.

```rust
fn guillotine_rect(
    chosen_rect: &Rectangle,
    requested_size: Size,
    default_orientation: Orientation,
) -> (Rectangle, Rectangle, Orientation) {
    let candidate_leftover_rect_to_right = Rectangle {
        min: chosen_rect.min + vec2(requested_size.width, 0),
        max: point2(chosen_rect.max.x, chosen_rect.min.y + requested_size.height),
    };
    let candidate_leftover_rect_to_bottom = Rectangle {
        min: chosen_rect.min + vec2(0, requested_size.height),
        max: point2(chosen_rect.min.x + requested_size.width, chosen_rect.max.y),
    };

    let split_rect;
    let leftover_rect;
    let orientation;
    if requested_size == chosen_rect.size() {
        orientation = default_orientation;
        split_rect = Rectangle::zero();
        leftover_rect = Rectangle::zero();
    } else if safe_area(&candidate_leftover_rect_to_right) > safe_area(&candidate_leftover_rect_to_bottom) {
        leftover_rect = candidate_leftover_rect_to_bottom;
        split_rect = Rectangle {
            min: candidate_leftover_rect_to_right.min,
            max: point2(candidate_leftover_rect_to_right.max.x, chosen_rect.max.y),
        };
        orientation = Orientation::Horizontal;
    } else {
        leftover_rect = candidate_leftover_rect_to_right;
        split_rect = Rectangle {
            min: candidate_leftover_rect_to_bottom.min,
            max: point2(chosen_rect.max.x, candidate_leftover_rect_to_bottom.max.y),
        };
        orientation = Orientation::Vertical;
    }

    (split_rect, leftover_rect, orientation)
}
```

--------------------------------

### Merging siblings visualization

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html

Visual representation of the tree update process when deallocating a rectangle and merging siblings.

```text
+---+---+---+         #               +-------+---+         #
|   |   |///|         |               |       |///|         |
| A | B |/C/|     +---+---+           | AB    |/C/|     +---+---+
|   |   |///|     |       |           |       |///|     |       |
+---+---+---+     #       D           +-------+---+     #       D
| D         |     |            ->     | D         |     |
|           |   +-+-+                 |           |   +-+-+
|           |   | | |                 |           |   |   |
+-----------+   A B C                 +-----------+   AB  C
```

--------------------------------

### Test simple_atlas

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Tests basic allocation functionality in SimpleAtlasAllocator and ensures that allocated rectangles do not intersect.

```rust
#[test]
fn simple_atlas() {
    let mut atlas = SimpleAtlasAllocator::new(size2(1000, 1000));

    assert!(atlas.allocate(size2(1, 1001)).is_none());
    assert!(atlas.allocate(size2(1001, 1)).is_none());

    let mut rectangles = Vec::new();
    rectangles.push(atlas.allocate(size2(100, 1000)).unwrap());
    rectangles.push(atlas.allocate(size2(900, 200)).unwrap());
    rectangles.push(atlas.allocate(size2(300, 200)).unwrap());
    rectangles.push(atlas.allocate(size2(200, 300)).unwrap());
    rectangles.push(atlas.allocate(size2(100, 300)).unwrap());
    rectangles.push(atlas.allocate(size2(100, 300)).unwrap());
    rectangles.push(atlas.allocate(size2(100, 300)).unwrap());
    assert!(atlas.allocate(size2(800, 800)).is_none());

    for i in 0..rectangles.len() {
        for j in 0..rectangles.len() {
            if i == j {
                continue;
            }

            assert!(!rectangles[i].intersects(&rectangles[j]));
        }
    }
}
```

--------------------------------

### Test allocate_negative

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Verifies that negative dimensions in allocation requests are rejected by the allocator.

```rust
#[test]
fn allocate_negative() {
    let mut atlas = SimpleAtlasAllocator::new(size2(1000, 1000));

    assert!(atlas.allocate(size2(-1, 1)).is_none());
    assert!(atlas.allocate(size2(1, -1)).is_none());
    assert!(atlas.allocate(size2(-1, -1)).is_none());

    assert!(atlas.allocate(size2(-167114179, -718142)).is_none());
}
```

--------------------------------

### dump_into_svg function

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Dumps a visual representation of the atlas in SVG format. If a rectangle is provided, the output is translated and scaled to fit it.

```rust
pub fn dump_into_svg(atlas: &AtlasAllocator, rect: Option<&Rectangle>, output: &mut dyn std::io::Write) -> std::io::Result<()> {
    use svg_fmt::*;

    let (sx, sy, tx, ty) = if let Some(rect) = rect {
        (
            rect.width() as f32 / atlas.size.width as f32,
            rect.height() as f32 / atlas.size.height as f32,
            rect.min.x as f32,
            rect.min.y as f32,
        )
    } else {
        (1.0, 1.0, 0.0, 0.0)
    };

    for node in &atlas.nodes {
        let color = match node.kind {
            NodeKind::Free => rgb(50, 50, 50),
            NodeKind::Alloc => rgb(70, 70, 180),
            _ => {
                continue;
            }
        };

        let (x, y) = node.rect.min.to_f32().to_tuple();
        let (w, h) = node.rect.size().to_f32().to_tuple();

        writeln!(
            output,
            r#"    {}"#,
            rectangle(tx + x * sx, ty + y * sy, w * sx, h * sy)
                .fill(color)
                .stroke(Stroke::Color(black(), 1.0))
        )?;
    }

    Ok(())
}
```

--------------------------------

### Iteration over Allocated Rectangles

Source: https://docs.rs/guillotiere/latest/src/guillotiere/allocator.rs.html

Invokes a callback for each allocated rectangle in the atlas, providing the allocation ID and the rectangle.

```rust
/// Invoke a callback for each allocated rectangle in the atlas.
    pub fn for_each_allocated_rectangle<F>(&self, mut callback: F)
    where
        F: FnMut(AllocId, &Rectangle),
    {
        for (i, node) in self.nodes.iter().enumerate() {
            if node.kind != NodeKind::Alloc {
                continue;
            }

            let id = self.alloc_id(AllocIndex(i as u32));

            callback(id, &node.rect);
        }
    }
```

--------------------------------

### AtlasAllocator struct definition

Source: https://docs.rs/guillotiere/latest/guillotiere/struct.AtlasAllocator.html

The primary structure definition for the AtlasAllocator.

```rust
pub struct AtlasAllocator { /* private fields */ }
```
Tokens:
Raw