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 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 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 92 FStr_InitRefer(const char *str) 93 { 94 return FStr_Init(str, NULL); 95 } 96 97 MAKE_INLINE void 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 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 119 Substring_InitStr(const char *str) 120 { 121 return Substring_Init(str, str + strlen(str)); 122 } 123 124 MAKE_STATIC size_t 125 Substring_Length(Substring sub) 126 { 127 return (size_t)(sub.end - sub.start); 128 } 129 130 MAKE_STATIC bool 131 Substring_IsEmpty(Substring sub) 132 { 133 return sub.start == sub.end; 134 } 135 136 MAKE_INLINE bool 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 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 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 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 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 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 * 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 * 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 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 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 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 239 LazyBuf_Done(LazyBuf *buf) 240 { 241 free(buf->data); 242 } 243 244 MAKE_STATIC void 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 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 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 286 LazyBuf_AddSubstring(LazyBuf *buf, Substring sub) 287 { 288 LazyBuf_AddBytesBetween(buf, sub.start, sub.end); 289 } 290 291 MAKE_STATIC Substring 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 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 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 327 SubstringWords_Init(SubstringWords *w) 328 { 329 w->words = NULL; 330 w->len = 0; 331 w->freeIt = NULL; 332 } 333 334 MAKE_INLINE void 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