1// This is an open source non-commercial project. Dear PVS-Studio, please check
2// it. PVS-Studio Static Code Analyzer for C, C++ and C#: http://www.viva64.com
3
4/// @file garray.c
5///
6/// Functions for handling growing arrays.
7
8#include <string.h>
9#include <inttypes.h>
10
11#include "nvim/vim.h"
12#include "nvim/ascii.h"
13#include "nvim/log.h"
14#include "nvim/memory.h"
15#include "nvim/path.h"
16#include "nvim/garray.h"
17#include "nvim/strings.h"
18
19// #include "nvim/globals.h"
20#include "nvim/memline.h"
21
22#ifdef INCLUDE_GENERATED_DECLARATIONS
23# include "garray.c.generated.h"
24#endif
25
26/// Clear an allocated growing array.
27void ga_clear(garray_T *gap)
28{
29 xfree(gap->ga_data);
30
31 // Initialize growing array without resetting itemsize or growsize
32 gap->ga_data = NULL;
33 gap->ga_maxlen = 0;
34 gap->ga_len = 0;
35}
36
37/// Clear a growing array that contains a list of strings.
38///
39/// @param gap
40void ga_clear_strings(garray_T *gap)
41{
42 GA_DEEP_CLEAR_PTR(gap);
43}
44
45/// Initialize a growing array.
46///
47/// @param gap
48/// @param itemsize
49/// @param growsize
50void ga_init(garray_T *gap, int itemsize, int growsize)
51{
52 gap->ga_data = NULL;
53 gap->ga_maxlen = 0;
54 gap->ga_len = 0;
55 gap->ga_itemsize = itemsize;
56 ga_set_growsize(gap, growsize);
57}
58
59/// A setter for the growsize that guarantees it will be at least 1.
60///
61/// @param gap
62/// @param growsize
63void ga_set_growsize(garray_T *gap, int growsize)
64{
65 if (growsize < 1) {
66 WLOG("trying to set an invalid ga_growsize: %d", growsize);
67 gap->ga_growsize = 1;
68 } else {
69 gap->ga_growsize = growsize;
70 }
71}
72
73/// Make room in growing array "gap" for at least "n" items.
74///
75/// @param gap
76/// @param n
77void ga_grow(garray_T *gap, int n)
78{
79 if (gap->ga_maxlen - gap->ga_len >= n) {
80 // the garray still has enough space, do nothing
81 return;
82 }
83
84 if (gap->ga_growsize < 1) {
85 WLOG("ga_growsize(%d) is less than 1", gap->ga_growsize);
86 }
87
88 // the garray grows by at least growsize
89 if (n < gap->ga_growsize) {
90 n = gap->ga_growsize;
91 }
92
93 // A linear growth is very inefficient when the array grows big. This
94 // is a compromise between allocating memory that won't be used and too
95 // many copy operations. A factor of 1.5 seems reasonable.
96 if (n < gap->ga_len / 2) {
97 n = gap->ga_len / 2;
98 }
99
100 int new_maxlen = gap->ga_len + n;
101
102 size_t new_size = (size_t)gap->ga_itemsize * (size_t)new_maxlen;
103 size_t old_size = (size_t)gap->ga_itemsize * (size_t)gap->ga_maxlen;
104
105 // reallocate and clear the new memory
106 char *pp = xrealloc(gap->ga_data, new_size);
107 memset(pp + old_size, 0, new_size - old_size);
108
109 gap->ga_maxlen = new_maxlen;
110 gap->ga_data = pp;
111}
112
113/// Sort "gap" and remove duplicate entries. "gap" is expected to contain a
114/// list of file names in allocated memory.
115///
116/// @param gap
117void ga_remove_duplicate_strings(garray_T *gap)
118{
119 char_u **fnames = gap->ga_data;
120
121 // sort the growing array, which puts duplicates next to each other
122 sort_strings(fnames, gap->ga_len);
123
124 // loop over the growing array in reverse
125 for (int i = gap->ga_len - 1; i > 0; i--) {
126 if (fnamecmp(fnames[i - 1], fnames[i]) == 0) {
127 xfree(fnames[i]);
128
129 // close the gap (move all strings one slot lower)
130 for (int j = i + 1; j < gap->ga_len; j++) {
131 fnames[j - 1] = fnames[j];
132 }
133
134 --gap->ga_len;
135 }
136 }
137}
138
139/// For a growing array that contains a list of strings: concatenate all the
140/// strings with sep as separator.
141///
142/// @param gap
143/// @param sep
144///
145/// @returns the concatenated strings
146char_u *ga_concat_strings_sep(const garray_T *gap, const char *sep)
147 FUNC_ATTR_NONNULL_RET
148{
149 const size_t nelem = (size_t) gap->ga_len;
150 const char **strings = gap->ga_data;
151
152 if (nelem == 0) {
153 return (char_u *) xstrdup("");
154 }
155
156 size_t len = 0;
157 for (size_t i = 0; i < nelem; i++) {
158 len += strlen(strings[i]);
159 }
160
161 // add some space for the (num - 1) separators
162 len += (nelem - 1) * strlen(sep);
163 char *const ret = xmallocz(len);
164
165 char *s = ret;
166 for (size_t i = 0; i < nelem - 1; i++) {
167 s = xstpcpy(s, strings[i]);
168 s = xstpcpy(s, sep);
169 }
170 strcpy(s, strings[nelem - 1]);
171
172 return (char_u *) ret;
173}
174
175/// For a growing array that contains a list of strings: concatenate all the
176/// strings with a separating comma.
177///
178/// @param gap
179///
180/// @returns the concatenated strings
181char_u* ga_concat_strings(const garray_T *gap) FUNC_ATTR_NONNULL_RET
182{
183 return ga_concat_strings_sep(gap, ",");
184}
185
186/// Concatenate a string to a growarray which contains characters.
187/// When "s" is NULL does not do anything.
188///
189/// WARNING:
190/// - Does NOT copy the NUL at the end!
191/// - The parameter may not overlap with the growing array
192///
193/// @param gap
194/// @param s
195void ga_concat(garray_T *gap, const char_u *restrict s)
196{
197 if (s == NULL) {
198 return;
199 }
200
201 ga_concat_len(gap, (const char *restrict) s, strlen((char *) s));
202}
203
204/// Concatenate a string to a growarray which contains characters
205///
206/// @param[out] gap Growarray to modify.
207/// @param[in] s String to concatenate.
208/// @param[in] len String length.
209void ga_concat_len(garray_T *const gap, const char *restrict s,
210 const size_t len)
211 FUNC_ATTR_NONNULL_ALL
212{
213 if (len) {
214 ga_grow(gap, (int) len);
215 char *data = gap->ga_data;
216 memcpy(data + gap->ga_len, s, len);
217 gap->ga_len += (int) len;
218 }
219}
220
221/// Append one byte to a growarray which contains bytes.
222///
223/// @param gap
224/// @param c
225void ga_append(garray_T *gap, char c)
226{
227 GA_APPEND(char, gap, c);
228}
229