< Summary

Class:GDX.Collections.FreeList
Assembly:GDX
File(s):./Packages/com.dotbunny.gdx/GDX/Collections/FreeList.cs
Covered lines:79
Uncovered lines:0
Coverable lines:79
Total lines:174
Line coverage:100% (79 of 79)
Covered branches:0
Total branches:0
Covered methods:7
Total methods:7
Method coverage:100% (7 of 7)

Coverage History

Metrics

MethodBranch coverage Crap Score Cyclomatic complexity NPath complexity Sequence coverage
FreeList(...)0%220100%
Clear()0%220100%
AddWithExpandCheck(...)0%330100%
AddWithExpandCheck(...)0%330100%
AddUnchecked(...)0%110100%
RemoveAt(...)0%110100%
GetAndRemoveAt(...)0%110100%

File(s)

./Packages/com.dotbunny.gdx/GDX/Collections/FreeList.cs

#LineLine coverage
 1// Copyright (c) 2020-2024 dotBunny Inc.
 2// dotBunny licenses this file to you under the BSL-1.0 license.
 3// See the LICENSE file in the project root for more information.
 4
 5using System;
 6
 7namespace GDX.Collections
 8{
 9    /// <summary>
 10    ///     An array where indices are allocated from and stored in an in-place linked list.
 11    ///     Allocating or deallocating a single int from this array is very fast, as is single datum lookup,
 12    ///     but neither the allocated indices nor the free indices can be reliably iterated without an external data str
 13    ///     This structure can be adapted to an arbitrary of external, parallel arrays.
 14    /// </summary>
 15    public struct FreeList
 16    {
 17        /// <summary>
 18        ///     Data storage for allocated indices as well as the in-place free-list.
 19        /// </summary>
 20        public int[] Indices;
 21
 22        /// <summary>
 23        ///     The next available index of the free-list.
 24        /// </summary>
 25        public int CurrentFreeIndex;
 26
 27        /// <summary>
 28        ///     The total number of currently-allocated indices.
 29        /// </summary>
 30        public int Count;
 31
 32        /// <summary>
 33        /// </summary>
 34        /// <param name="initialCapacity">The initial capacity of the array.</param>
 35        public FreeList(int initialCapacity)
 836        {
 837            Indices = new int[initialCapacity];
 838            CurrentFreeIndex = 0;
 839            Count = 0;
 40
 4841            for (int i = 0; i < initialCapacity; i++)
 1642            {
 1643                Indices[i] = i + 1;
 1644            }
 845        }
 46
 47        /// <summary>
 48        ///     Removes all allocated data and rebuilds the free-list.
 49        /// </summary>
 50        public void Clear()
 151        {
 152            int length = Indices.Length;
 653            for (int i = 0; i < length; i++)
 254            {
 255                Indices[i] = i + 1;
 256            }
 57
 158            Count = 0;
 159            CurrentFreeIndex = 0;
 160        }
 61
 62        /// <summary>
 63        ///     Allocates an index from the free-list and stores an integer there, expanding the array if necessary.
 64        /// </summary>
 65        /// <param name="data">The integer value to store at the allocated index.</param>
 66        /// <param name="allocatedIndex">The index allocated from the free-list.</param>
 67        /// <param name="expandBy">How much the array should expand by when out of space.</param>
 68        /// <returns>True if the array expanded.</returns>
 69        public bool AddWithExpandCheck(int data, out int allocatedIndex, int expandBy)
 170        {
 171            int currentIndex = CurrentFreeIndex;
 172            int oldLength = Indices.Length;
 173            int expandedLength = oldLength + expandBy;
 74
 175            bool needsExpansion = currentIndex >= oldLength;
 176            if (needsExpansion)
 177            {
 178                int[] newIndices = new int[expandedLength];
 179                Array.Copy(Indices, 0, newIndices, 0, oldLength);
 180                Indices = newIndices;
 81
 2282                for (int i = oldLength; i < expandedLength; i++)
 1083                {
 1084                    Indices[i] = i + 1;
 1085                }
 186            }
 87
 188            CurrentFreeIndex = Indices[currentIndex];
 189            Indices[currentIndex] = data;
 190            ++Count;
 91
 192            allocatedIndex = currentIndex;
 93
 194            return needsExpansion;
 195        }
 96
 97        /// <summary>
 98        ///     Allocates an index from the free-list and stores an integer there, expanding the array by twice the curr
 99        ///     necessary.
 100        /// </summary>
 101        /// <param name="data">The integer value to store at the allocated index.</param>
 102        /// <param name="allocatedIndex">The index allocated from the free-list.</param>
 103        /// <returns>True if the array expanded.</returns>
 104        public bool AddWithExpandCheck(int data, out int allocatedIndex)
 5105        {
 5106            int currentIndex = CurrentFreeIndex;
 5107            int oldLength = Indices.Length;
 5108            int expandedLength = oldLength * 2;
 109
 5110            bool needsExpansion = currentIndex >= oldLength;
 5111            if (needsExpansion)
 2112            {
 2113                int[] newIndices = new int[expandedLength];
 2114                Array.Copy(Indices, 0, newIndices, 0, oldLength);
 2115                Indices = newIndices;
 116
 8117                for (int i = oldLength; i < expandedLength; i++)
 2118                {
 2119                    Indices[i] = i + 1;
 2120                }
 2121            }
 122
 5123            CurrentFreeIndex = Indices[currentIndex];
 5124            Indices[currentIndex] = data;
 5125            ++Count;
 126
 5127            allocatedIndex = currentIndex;
 128
 5129            return needsExpansion;
 5130        }
 131
 132        /// <summary>
 133        ///     Allocates an index from the free-list and stores an integer there, without checking for expansion.
 134        /// </summary>
 135        /// <param name="data">The integer value to store at the allocated index.</param>
 136        /// <returns>The index allocated from the free-list.</returns>
 137        public int AddUnchecked(int data)
 10138        {
 10139            int currentIndex = CurrentFreeIndex;
 140
 10141            CurrentFreeIndex = Indices[currentIndex];
 9142            Indices[currentIndex] = data;
 9143            ++Count;
 144
 9145            return currentIndex;
 9146        }
 147
 148        /// <summary>
 149        ///     Deallocates the given index and adds it to the free-list.
 150        /// </summary>
 151        /// <param name="index">The index to add to the free-list.</param>
 152        public void RemoveAt(int index)
 1153        {
 1154            Indices[index] = CurrentFreeIndex;
 1155            CurrentFreeIndex = index;
 1156            --Count;
 1157        }
 158
 159        /// <summary>
 160        ///     Retrieves the value stored at the given index and deallocates the index, adding it to the free-list.
 161        /// </summary>
 162        /// <param name="index">The index to add to the free-list.</param>
 163        /// <returns>The value stored at the given index.</returns>
 164        public int GetAndRemoveAt(int index)
 1165        {
 1166            int data = Indices[index];
 1167            Indices[index] = CurrentFreeIndex;
 1168            CurrentFreeIndex = index;
 1169            --Count;
 170
 1171            return data;
 1172        }
 173    }
 174}

Coverage by test methods









Methods/Properties

FreeList(System.Int32)
Clear()
AddWithExpandCheck(System.Int32, System.Int32&, System.Int32)
AddWithExpandCheck(System.Int32, System.Int32&)
AddUnchecked(System.Int32)
RemoveAt(System.Int32)
GetAndRemoveAt(System.Int32)