dmd.backend.barray source code

1 /**
2  * Compiler implementation of the
3  * $(LINK2 http://www.dlang.org, D programming language).
4  *
5  * Copyright:   Copyright (C) 2018-2020 by The D Language Foundation, All Rights Reserved
6  * Authors:     $(LINK2 http://www.digitalmars.com, Walter Bright)
7  * License:     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
8  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/backend/barrayf.d, backend/barray.d)
9  * Documentation: https://dlang.org/phobos/dmd_backend_barray.html
10  */
11 
12 module dmd.backend.barray;
13 
14 import core.stdc.stdio;
15 import core.stdc.stdlib;
16 import core.stdc.string;
17 
18 nothrow:
19 
20 extern (C++): void err_nomem();
21 
22 /*************************************
23  * A reusable array that ratchets up in capacity.
24  */
25 struct Barray(T)
26 {
27     /**********************
28      * Set useable length of array.
29      * Params:
30      *  length = minimum number of elements in array
31      */
32     void setLength(size_t length)
33     {
34         static void enlarge(ref Barray barray, size_t length)
35         {
36             pragma(inline, false);
37             auto newcap = (barray.capacity == 0) ? length : length + (length >> 1);
38             barray.capacity = (newcap + 15) & ~15;
39             T* p = cast(T*)realloc(barray.array.ptr, barray.capacity * T.sizeof);
40             if (length && !p)
41             {
42                 version (unittest)
43                     assert(0);
44                 else
45                     err_nomem();
46             }
47             barray.array = p[0 .. length];
48         }
49 
50         if (length <= capacity)
51             array = array.ptr[0 .. length];     // the fast path
52         else
53             enlarge(this, length);              // the slow path
54     }
55 
56 
57     /*******************
58      * Append element t to array.
59      * Params:
60      *  t = element to append
61      */
62     void push(T t)
63     {
64         const i = length;
65         setLength(i + 1);
66         array[i] = t;
67     }
68 
69     /**********************
70      * Move the last element from the array into [i].
71      * Reduce the array length by one.
72      * Params:
73      *  i = index of element to remove
74      */
75     void remove(size_t i)
76     {
77         const len = length - 1;
78         if (i != len)
79         {
80             array[i] = array[len];
81         }
82         setLength(len);
83     }
84 
85     /******************
86      * Release all memory used.
87      */
88     ~this()
89     {
90         free(array.ptr);
91         array = null;
92         capacity = 0;
93     }
94 
95     alias array this;
96     T[] array;
97 
98   private:
99     size_t capacity;
100 }
101 
102 unittest
103 {
104     Barray!int a;
105     a.setLength(10);
106     assert(a.length == 10);
107     a.setLength(4);
108     assert(a.length == 4);
109     foreach (i, ref v; a[])
110         v = cast(int) i * 2;
111     foreach (i, ref const v; a[])
112         assert(v == i * 2);
113     a.remove(3);
114     assert(a.length == 3);
115     a.push(50);
116     a.remove(1);
117     assert(a[1] == 50);
118 }