utstring.h (12229B)
1 /* 2 Copyright (c) 2008-2022, Troy D. Hanson https://troydhanson.github.io/uthash/ 3 All rights reserved. 4 5 Redistribution and use in source and binary forms, with or without 6 modification, are permitted provided that the following conditions are met: 7 8 * Redistributions of source code must retain the above copyright 9 notice, this list of conditions and the following disclaimer. 10 11 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 12 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 13 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 14 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 15 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 16 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 17 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 18 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 19 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 20 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 21 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 22 */ 23 24 /* a dynamic string implementation using macros 25 */ 26 #ifndef UTSTRING_H 27 #define UTSTRING_H 28 29 #define UTSTRING_VERSION 2.3.0 30 31 #include <stdlib.h> 32 #include <string.h> 33 #include <stdio.h> 34 #include <stdarg.h> 35 36 #ifdef __GNUC__ 37 #define UTSTRING_UNUSED __attribute__((__unused__)) 38 #else 39 #define UTSTRING_UNUSED 40 #endif 41 42 #ifdef oom 43 #error "The name of macro 'oom' has been changed to 'utstring_oom'. Please update your code." 44 #define utstring_oom() oom() 45 #endif 46 47 #ifndef utstring_oom 48 #define utstring_oom() exit(-1) 49 #endif 50 51 typedef struct { 52 char *d; /* pointer to allocated buffer */ 53 size_t n; /* allocated capacity */ 54 size_t i; /* index of first unused byte */ 55 } UT_string; 56 57 #define utstring_reserve(s,amt) \ 58 do { \ 59 if (((s)->n - (s)->i) < (size_t)(amt)) { \ 60 char *utstring_tmp = (char*)realloc( \ 61 (s)->d, (s)->n + (amt)); \ 62 if (!utstring_tmp) { \ 63 utstring_oom(); \ 64 } \ 65 (s)->d = utstring_tmp; \ 66 (s)->n += (amt); \ 67 } \ 68 } while(0) 69 70 #define utstring_init(s) \ 71 do { \ 72 (s)->n = 0; (s)->i = 0; (s)->d = NULL; \ 73 utstring_reserve(s,100); \ 74 (s)->d[0] = '\0'; \ 75 } while(0) 76 77 #define utstring_done(s) \ 78 do { \ 79 if ((s)->d != NULL) free((s)->d); \ 80 (s)->n = 0; \ 81 } while(0) 82 83 #define utstring_free(s) \ 84 do { \ 85 utstring_done(s); \ 86 free(s); \ 87 } while(0) 88 89 #define utstring_new(s) \ 90 do { \ 91 (s) = (UT_string*)malloc(sizeof(UT_string)); \ 92 if (!(s)) { \ 93 utstring_oom(); \ 94 } \ 95 utstring_init(s); \ 96 } while(0) 97 98 #define utstring_renew(s) \ 99 do { \ 100 if (s) { \ 101 utstring_clear(s); \ 102 } else { \ 103 utstring_new(s); \ 104 } \ 105 } while(0) 106 107 #define utstring_clear(s) \ 108 do { \ 109 (s)->i = 0; \ 110 (s)->d[0] = '\0'; \ 111 } while(0) 112 113 #define utstring_bincpy(s,b,l) \ 114 do { \ 115 utstring_reserve((s),(l)+1); \ 116 if (l) memcpy(&(s)->d[(s)->i], b, l); \ 117 (s)->i += (l); \ 118 (s)->d[(s)->i]='\0'; \ 119 } while(0) 120 121 #define utstring_concat(dst,src) \ 122 do { \ 123 utstring_reserve((dst),((src)->i)+1); \ 124 if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \ 125 (dst)->i += (src)->i; \ 126 (dst)->d[(dst)->i]='\0'; \ 127 } while(0) 128 129 #define utstring_len(s) ((s)->i) 130 131 #define utstring_body(s) ((s)->d) 132 133 UTSTRING_UNUSED static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) { 134 int n; 135 va_list cp; 136 for (;;) { 137 #ifdef _WIN32 138 cp = ap; 139 #else 140 va_copy(cp, ap); 141 #endif 142 n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp); 143 va_end(cp); 144 145 if ((n > -1) && ((size_t) n < (s->n-s->i))) { 146 s->i += n; 147 return; 148 } 149 150 /* Else try again with more space. */ 151 if (n > -1) utstring_reserve(s,n+1); /* exact */ 152 else utstring_reserve(s,(s->n)*2); /* 2x */ 153 } 154 } 155 #ifdef __GNUC__ 156 /* support printf format checking (2=the format string, 3=start of varargs) */ 157 static void utstring_printf(UT_string *s, const char *fmt, ...) 158 __attribute__ (( format( printf, 2, 3) )); 159 #endif 160 UTSTRING_UNUSED static void utstring_printf(UT_string *s, const char *fmt, ...) { 161 va_list ap; 162 va_start(ap,fmt); 163 utstring_printf_va(s,fmt,ap); 164 va_end(ap); 165 } 166 167 /******************************************************************************* 168 * begin substring search functions * 169 ******************************************************************************/ 170 /* Build KMP table from left to right. */ 171 UTSTRING_UNUSED static void _utstring_BuildTable( 172 const char *P_Needle, 173 size_t P_NeedleLen, 174 long *P_KMP_Table) 175 { 176 long i, j; 177 178 i = 0; 179 j = i - 1; 180 P_KMP_Table[i] = j; 181 while (i < (long) P_NeedleLen) 182 { 183 while ( (j > -1) && (P_Needle[i] != P_Needle[j]) ) 184 { 185 j = P_KMP_Table[j]; 186 } 187 i++; 188 j++; 189 if (i < (long) P_NeedleLen) 190 { 191 if (P_Needle[i] == P_Needle[j]) 192 { 193 P_KMP_Table[i] = P_KMP_Table[j]; 194 } 195 else 196 { 197 P_KMP_Table[i] = j; 198 } 199 } 200 else 201 { 202 P_KMP_Table[i] = j; 203 } 204 } 205 206 return; 207 } 208 209 210 /* Build KMP table from right to left. */ 211 UTSTRING_UNUSED static void _utstring_BuildTableR( 212 const char *P_Needle, 213 size_t P_NeedleLen, 214 long *P_KMP_Table) 215 { 216 long i, j; 217 218 i = P_NeedleLen - 1; 219 j = i + 1; 220 P_KMP_Table[i + 1] = j; 221 while (i >= 0) 222 { 223 while ( (j < (long) P_NeedleLen) && (P_Needle[i] != P_Needle[j]) ) 224 { 225 j = P_KMP_Table[j + 1]; 226 } 227 i--; 228 j--; 229 if (i >= 0) 230 { 231 if (P_Needle[i] == P_Needle[j]) 232 { 233 P_KMP_Table[i + 1] = P_KMP_Table[j + 1]; 234 } 235 else 236 { 237 P_KMP_Table[i + 1] = j; 238 } 239 } 240 else 241 { 242 P_KMP_Table[i + 1] = j; 243 } 244 } 245 246 return; 247 } 248 249 250 /* Search data from left to right. ( Multiple search mode. ) */ 251 UTSTRING_UNUSED static long _utstring_find( 252 const char *P_Haystack, 253 size_t P_HaystackLen, 254 const char *P_Needle, 255 size_t P_NeedleLen, 256 long *P_KMP_Table) 257 { 258 long i, j; 259 long V_FindPosition = -1; 260 261 /* Search from left to right. */ 262 i = j = 0; 263 while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) ) 264 { 265 while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) ) 266 { 267 i = P_KMP_Table[i]; 268 } 269 i++; 270 j++; 271 if (i >= (int)P_NeedleLen) 272 { 273 /* Found. */ 274 V_FindPosition = j - i; 275 break; 276 } 277 } 278 279 return V_FindPosition; 280 } 281 282 283 /* Search data from right to left. ( Multiple search mode. ) */ 284 UTSTRING_UNUSED static long _utstring_findR( 285 const char *P_Haystack, 286 size_t P_HaystackLen, 287 const char *P_Needle, 288 size_t P_NeedleLen, 289 long *P_KMP_Table) 290 { 291 long i, j; 292 long V_FindPosition = -1; 293 294 /* Search from right to left. */ 295 j = (P_HaystackLen - 1); 296 i = (P_NeedleLen - 1); 297 while ( (j >= 0) && (j >= i) ) 298 { 299 while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) ) 300 { 301 i = P_KMP_Table[i + 1]; 302 } 303 i--; 304 j--; 305 if (i < 0) 306 { 307 /* Found. */ 308 V_FindPosition = j + 1; 309 break; 310 } 311 } 312 313 return V_FindPosition; 314 } 315 316 317 /* Search data from left to right. ( One time search mode. ) */ 318 UTSTRING_UNUSED static long utstring_find( 319 UT_string *s, 320 long P_StartPosition, /* Start from 0. -1 means last position. */ 321 const char *P_Needle, 322 size_t P_NeedleLen) 323 { 324 long V_StartPosition; 325 long V_HaystackLen; 326 long *V_KMP_Table; 327 long V_FindPosition = -1; 328 329 if (P_StartPosition < 0) 330 { 331 V_StartPosition = s->i + P_StartPosition; 332 } 333 else 334 { 335 V_StartPosition = P_StartPosition; 336 } 337 V_HaystackLen = s->i - V_StartPosition; 338 if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) ) 339 { 340 V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1)); 341 if (V_KMP_Table != NULL) 342 { 343 _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table); 344 345 V_FindPosition = _utstring_find(s->d + V_StartPosition, 346 V_HaystackLen, 347 P_Needle, 348 P_NeedleLen, 349 V_KMP_Table); 350 if (V_FindPosition >= 0) 351 { 352 V_FindPosition += V_StartPosition; 353 } 354 355 free(V_KMP_Table); 356 } 357 } 358 359 return V_FindPosition; 360 } 361 362 363 /* Search data from right to left. ( One time search mode. ) */ 364 UTSTRING_UNUSED static long utstring_findR( 365 UT_string *s, 366 long P_StartPosition, /* Start from 0. -1 means last position. */ 367 const char *P_Needle, 368 size_t P_NeedleLen) 369 { 370 long V_StartPosition; 371 long V_HaystackLen; 372 long *V_KMP_Table; 373 long V_FindPosition = -1; 374 375 if (P_StartPosition < 0) 376 { 377 V_StartPosition = s->i + P_StartPosition; 378 } 379 else 380 { 381 V_StartPosition = P_StartPosition; 382 } 383 V_HaystackLen = V_StartPosition + 1; 384 if ( (V_HaystackLen >= (long) P_NeedleLen) && (P_NeedleLen > 0) ) 385 { 386 V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1)); 387 if (V_KMP_Table != NULL) 388 { 389 _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table); 390 391 V_FindPosition = _utstring_findR(s->d, 392 V_HaystackLen, 393 P_Needle, 394 P_NeedleLen, 395 V_KMP_Table); 396 397 free(V_KMP_Table); 398 } 399 } 400 401 return V_FindPosition; 402 } 403 /******************************************************************************* 404 * end substring search functions * 405 ******************************************************************************/ 406 407 #endif /* UTSTRING_H */