1 /* $NetBSD: str.h,v 1.15 2021/12/15 10:57:01 rillig Exp $ */
2
3 /*
4 Copyright (c) 2021 Roland Illig <rillig@NetBSD.org>
5 All rights reserved.
6
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions
9 are met:
10
11 1. Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
13 2. Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in the
15 documentation and/or other materials provided with the distribution.
16
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
19 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS
21 BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 POSSIBILITY OF SUCH DAMAGE.
28 */
29
30
31 /*
32 * Memory-efficient string handling.
33 */
34
35
36 /* A read-only string that may need to be freed after use. */
37 typedef struct FStr {
38 const char *str;
39 void *freeIt;
40 } FStr;
41
42 /* A read-only range of a character array, NOT null-terminated. */
43 typedef struct Substring {
44 const char *start;
45 const char *end;
46 } Substring;
47
48 /*
49 * Builds a string, only allocating memory if the string is different from the
50 * expected string.
51 */
52 typedef struct LazyBuf {
53 char *data;
54 size_t len;
55 size_t cap;
56 const char *expected;
57 } LazyBuf;
58
59 /* The result of splitting a string into words. */
60 typedef struct Words {
61 char **words;
62 size_t len;
63 void *freeIt;
64 } Words;
65
66 /* The result of splitting a string into words. */
67 typedef struct SubstringWords {
68 Substring *words;
69 size_t len;
70 void *freeIt;
71 } SubstringWords;
72
73
74 MAKE_INLINE FStr
FStr_Init(const char * str,void * freeIt)75 FStr_Init(const char *str, void *freeIt)
76 {
77 FStr fstr;
78 fstr.str = str;
79 fstr.freeIt = freeIt;
80 return fstr;
81 }
82
83 /* Return a string that is the sole owner of str. */
84 MAKE_INLINE FStr
FStr_InitOwn(char * str)85 FStr_InitOwn(char *str)
86 {
87 return FStr_Init(str, str);
88 }
89
90 /* Return a string that refers to the shared str. */
91 MAKE_INLINE FStr
FStr_InitRefer(const char * str)92 FStr_InitRefer(const char *str)
93 {
94 return FStr_Init(str, NULL);
95 }
96
97 MAKE_INLINE void
FStr_Done(FStr * fstr)98 FStr_Done(FStr *fstr)
99 {
100 free(fstr->freeIt);
101 #ifdef CLEANUP
102 fstr->str = NULL;
103 fstr->freeIt = NULL;
104 #endif
105 }
106
107
108 MAKE_STATIC Substring
Substring_Init(const char * start,const char * end)109 Substring_Init(const char *start, const char *end)
110 {
111 Substring sub;
112
113 sub.start = start;
114 sub.end = end;
115 return sub;
116 }
117
118 MAKE_INLINE Substring
Substring_InitStr(const char * str)119 Substring_InitStr(const char *str)
120 {
121 return Substring_Init(str, str + strlen(str));
122 }
123
124 MAKE_STATIC size_t
Substring_Length(Substring sub)125 Substring_Length(Substring sub)
126 {
127 return (size_t)(sub.end - sub.start);
128 }
129
130 MAKE_STATIC bool
Substring_IsEmpty(Substring sub)131 Substring_IsEmpty(Substring sub)
132 {
133 return sub.start == sub.end;
134 }
135
136 MAKE_INLINE bool
Substring_Equals(Substring sub,const char * str)137 Substring_Equals(Substring sub, const char *str)
138 {
139 size_t len = strlen(str);
140 return Substring_Length(sub) == len &&
141 memcmp(sub.start, str, len) == 0;
142 }
143
144 MAKE_INLINE bool
Substring_Eq(Substring sub,Substring str)145 Substring_Eq(Substring sub, Substring str)
146 {
147 size_t len = Substring_Length(sub);
148 return len == Substring_Length(str) &&
149 memcmp(sub.start, str.start, len) == 0;
150 }
151
152 MAKE_STATIC Substring
Substring_Sub(Substring sub,size_t start,size_t end)153 Substring_Sub(Substring sub, size_t start, size_t end)
154 {
155 assert(start <= Substring_Length(sub));
156 assert(end <= Substring_Length(sub));
157 return Substring_Init(sub.start + start, sub.start + end);
158 }
159
160 MAKE_STATIC bool
Substring_HasPrefix(Substring sub,Substring prefix)161 Substring_HasPrefix(Substring sub, Substring prefix)
162 {
163 return Substring_Length(sub) >= Substring_Length(prefix) &&
164 memcmp(sub.start, prefix.start, Substring_Length(prefix)) == 0;
165 }
166
167 MAKE_STATIC bool
Substring_HasSuffix(Substring sub,Substring suffix)168 Substring_HasSuffix(Substring sub, Substring suffix)
169 {
170 size_t suffixLen = Substring_Length(suffix);
171 return Substring_Length(sub) >= suffixLen &&
172 memcmp(sub.end - suffixLen, suffix.start, suffixLen) == 0;
173 }
174
175 /* Returns an independent, null-terminated copy of the substring. */
176 MAKE_STATIC FStr
Substring_Str(Substring sub)177 Substring_Str(Substring sub)
178 {
179 if (Substring_IsEmpty(sub))
180 return FStr_InitRefer("");
181 return FStr_InitOwn(bmake_strsedup(sub.start, sub.end));
182 }
183
184 MAKE_STATIC const char *
Substring_SkipFirst(Substring sub,char ch)185 Substring_SkipFirst(Substring sub, char ch)
186 {
187 const char *p;
188
189 for (p = sub.start; p != sub.end; p++)
190 if (*p == ch)
191 return p + 1;
192 return sub.start;
193 }
194
195 MAKE_STATIC const char *
Substring_LastIndex(Substring sub,char ch)196 Substring_LastIndex(Substring sub, char ch)
197 {
198 const char *p;
199
200 for (p = sub.end; p != sub.start; p--)
201 if (p[-1] == ch)
202 return p - 1;
203 return NULL;
204 }
205
206 MAKE_STATIC Substring
Substring_Dirname(Substring pathname)207 Substring_Dirname(Substring pathname)
208 {
209 const char *p;
210
211 for (p = pathname.end; p != pathname.start; p--)
212 if (p[-1] == '/')
213 return Substring_Init(pathname.start, p - 1);
214 return Substring_InitStr(".");
215 }
216
217 MAKE_STATIC Substring
Substring_Basename(Substring pathname)218 Substring_Basename(Substring pathname)
219 {
220 const char *p;
221
222 for (p = pathname.end; p != pathname.start; p--)
223 if (p[-1] == '/')
224 return Substring_Init(p, pathname.end);
225 return pathname;
226 }
227
228
229 MAKE_STATIC void
LazyBuf_Init(LazyBuf * buf,const char * expected)230 LazyBuf_Init(LazyBuf *buf, const char *expected)
231 {
232 buf->data = NULL;
233 buf->len = 0;
234 buf->cap = 0;
235 buf->expected = expected;
236 }
237
238 MAKE_INLINE void
LazyBuf_Done(LazyBuf * buf)239 LazyBuf_Done(LazyBuf *buf)
240 {
241 free(buf->data);
242 }
243
244 MAKE_STATIC void
LazyBuf_Add(LazyBuf * buf,char ch)245 LazyBuf_Add(LazyBuf *buf, char ch)
246 {
247
248 if (buf->data != NULL) {
249 if (buf->len == buf->cap) {
250 buf->cap *= 2;
251 buf->data = bmake_realloc(buf->data, buf->cap);
252 }
253 buf->data[buf->len++] = ch;
254
255 } else if (ch == buf->expected[buf->len]) {
256 buf->len++;
257 return;
258
259 } else {
260 buf->cap = buf->len + 16;
261 buf->data = bmake_malloc(buf->cap);
262 memcpy(buf->data, buf->expected, buf->len);
263 buf->data[buf->len++] = ch;
264 }
265 }
266
267 MAKE_STATIC void
LazyBuf_AddStr(LazyBuf * buf,const char * str)268 LazyBuf_AddStr(LazyBuf *buf, const char *str)
269 {
270 const char *p;
271
272 for (p = str; *p != '\0'; p++)
273 LazyBuf_Add(buf, *p);
274 }
275
276 MAKE_STATIC void
LazyBuf_AddBytesBetween(LazyBuf * buf,const char * start,const char * end)277 LazyBuf_AddBytesBetween(LazyBuf *buf, const char *start, const char *end)
278 {
279 const char *p;
280
281 for (p = start; p != end; p++)
282 LazyBuf_Add(buf, *p);
283 }
284
285 MAKE_INLINE void
LazyBuf_AddSubstring(LazyBuf * buf,Substring sub)286 LazyBuf_AddSubstring(LazyBuf *buf, Substring sub)
287 {
288 LazyBuf_AddBytesBetween(buf, sub.start, sub.end);
289 }
290
291 MAKE_STATIC Substring
LazyBuf_Get(const LazyBuf * buf)292 LazyBuf_Get(const LazyBuf *buf)
293 {
294 const char *start = buf->data != NULL ? buf->data : buf->expected;
295 return Substring_Init(start, start + buf->len);
296 }
297
298 /*
299 * Returns the content of the buffer as a newly allocated string.
300 *
301 * See LazyBuf_Get to avoid unnecessary memory allocations.
302 */
303 MAKE_STATIC FStr
LazyBuf_DoneGet(LazyBuf * buf)304 LazyBuf_DoneGet(LazyBuf *buf)
305 {
306 if (buf->data != NULL) {
307 LazyBuf_Add(buf, '\0');
308 return FStr_InitOwn(buf->data);
309 }
310 return Substring_Str(LazyBuf_Get(buf));
311 }
312
313
314 Words Str_Words(const char *, bool);
315
316 MAKE_INLINE void
Words_Free(Words w)317 Words_Free(Words w)
318 {
319 free(w.words);
320 free(w.freeIt);
321 }
322
323
324 SubstringWords Substring_Words(const char *, bool);
325
326 MAKE_INLINE void
SubstringWords_Init(SubstringWords * w)327 SubstringWords_Init(SubstringWords *w)
328 {
329 w->words = NULL;
330 w->len = 0;
331 w->freeIt = NULL;
332 }
333
334 MAKE_INLINE void
SubstringWords_Free(SubstringWords w)335 SubstringWords_Free(SubstringWords w)
336 {
337 free(w.words);
338 free(w.freeIt);
339 }
340
341
342 char *str_concat2(const char *, const char *);
343 char *str_concat3(const char *, const char *, const char *);
344
345 bool Str_Match(const char *, const char *);
346
347 void Str_Intern_Init(void);
348 void Str_Intern_End(void);
349 const char *Str_Intern(const char *);
350