1 /* 2 Copyright (c) 2008-2013, Troy D. Hanson http://troydhanson.github.com/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 1.9.8 30 31 #ifdef __GNUC__ 32 #define _UNUSED_ __attribute__ ((__unused__)) 33 #else 34 #define _UNUSED_ 35 #endif 36 37 #include <stdlib.h> 38 #include <string.h> 39 #include <stdarg.h> 40 41 #ifndef oom 42 #define oom abort 43 #endif 44 45 typedef struct { 46 char *d; 47 void **pd; 48 size_t n; /* allocd size */ 49 size_t i; /* index of first unused byte */ 50 } UT_string; 51 52 #define utstring_reserve(s,amt) \ 53 do { \ 54 if (((s)->n - (s)->i) < (size_t)(amt)) { \ 55 (s)->d = (char*)realloc((s)->d, (s)->n + amt); \ 56 if ((s)->d == NULL) oom(); \ 57 else {(s)->n += amt; \ 58 if ((s)->pd) *((s)->pd) = (s)->d;} \ 59 } \ 60 } while(0) 61 62 #define utstring_init(s) \ 63 do { \ 64 (s)->n = 0; (s)->i = 0; (s)->d = NULL; \ 65 utstring_reserve(s,128); \ 66 (s)->d[0] = '\0'; \ 67 } while(0) 68 69 #define utstring_done(s) \ 70 do { \ 71 if ((s)->d != NULL) free((s)->d); \ 72 (s)->n = 0; \ 73 } while(0) 74 75 #define utstring_free(s) \ 76 do { \ 77 utstring_done(s); \ 78 free(s); \ 79 } while(0) 80 81 #define utstring_new(s) \ 82 do { \ 83 s = (UT_string*)calloc(1, sizeof(UT_string)); \ 84 if (!s) oom(); \ 85 else utstring_init(s); \ 86 } while(0) 87 88 #define utstring_renew(s) \ 89 do { \ 90 if (s) { \ 91 utstring_clear(s); \ 92 } else { \ 93 utstring_new(s); \ 94 } \ 95 } while(0) 96 97 #define utstring_clear(s) \ 98 do { \ 99 (s)->i = 0; \ 100 (s)->d[0] = '\0'; \ 101 } while(0) 102 103 #define utstring_bincpy(s,b,l) \ 104 do { \ 105 utstring_reserve((s),(l)+1); \ 106 if (l) memcpy(&(s)->d[(s)->i], b, l); \ 107 (s)->i += l; \ 108 (s)->d[(s)->i]='\0'; \ 109 } while(0) 110 111 #define utstring_concat(dst,src) \ 112 do { \ 113 utstring_reserve((dst),((src)->i)+1); \ 114 if ((src)->i) memcpy(&(dst)->d[(dst)->i], (src)->d, (src)->i); \ 115 (dst)->i += (src)->i; \ 116 (dst)->d[(dst)->i]='\0'; \ 117 } while(0) 118 119 #define utstring_len(s) ((unsigned)((s)->i)) 120 121 #define utstring_body(s) ((s)->d) 122 123 _UNUSED_ static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) { 124 int n; 125 va_list cp; 126 while (1) { 127 #ifdef _WIN32 128 cp = ap; 129 #else 130 va_copy(cp, ap); 131 #endif 132 n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp); 133 va_end(cp); 134 135 if ((n > -1) && (n < (int)(s->n-s->i))) { 136 s->i += n; 137 return; 138 } 139 140 /* Else try again with more space. */ 141 if (n > -1) utstring_reserve(s,n+1); /* exact */ 142 else utstring_reserve(s,(s->n)*2); /* 2x */ 143 } 144 } 145 #ifdef __GNUC__ 146 /* support printf format checking (2=the format string, 3=start of varargs) */ 147 static void utstring_printf(UT_string *s, const char *fmt, ...) 148 __attribute__ (( format( printf, 2, 3) )); 149 #endif 150 _UNUSED_ static void utstring_printf(UT_string *s, const char *fmt, ...) { 151 va_list ap; 152 va_start(ap,fmt); 153 utstring_printf_va(s,fmt,ap); 154 va_end(ap); 155 } 156 157 #define utstring_append_len(dst, src, len) \ 158 do { \ 159 while ((dst)->n-(dst)->i <= (len)) utstring_reserve((dst),((dst)->n)*2); \ 160 memcpy(&(dst)->d[(dst)->i], (src), (len)); \ 161 (dst)->i+=(len); \ 162 (dst)->d[(dst)->i]='\0'; \ 163 } while(0) 164 165 #define utstring_append_c(dst, c) \ 166 do { \ 167 if ((dst)->n-(dst)->i < 2) utstring_reserve((dst),((dst)->n)*2); \ 168 (dst)->d[(dst)->i++] = (c); \ 169 (dst)->d[(dst)->i]='\0'; \ 170 } while(0) 171 172 /******************************************************************************* 173 * begin substring search functions * 174 ******************************************************************************/ 175 /* Build KMP table from left to right. */ 176 _UNUSED_ static void _utstring_BuildTable( 177 const char *P_Needle, 178 ssize_t P_NeedleLen, 179 long *P_KMP_Table) 180 { 181 long i, j; 182 183 i = 0; 184 j = i - 1; 185 P_KMP_Table[i] = j; 186 while (i < P_NeedleLen) 187 { 188 while ( (j > -1) && (P_Needle[i] != P_Needle[j]) ) 189 { 190 j = P_KMP_Table[j]; 191 } 192 i++; 193 j++; 194 if (i < P_NeedleLen) 195 { 196 if (P_Needle[i] == P_Needle[j]) 197 { 198 P_KMP_Table[i] = P_KMP_Table[j]; 199 } 200 else 201 { 202 P_KMP_Table[i] = j; 203 } 204 } 205 else 206 { 207 P_KMP_Table[i] = j; 208 } 209 } 210 211 return; 212 } 213 214 215 /* Build KMP table from right to left. */ 216 _UNUSED_ static void _utstring_BuildTableR( 217 const char *P_Needle, 218 ssize_t P_NeedleLen, 219 long *P_KMP_Table) 220 { 221 long i, j; 222 223 i = P_NeedleLen - 1; 224 j = i + 1; 225 P_KMP_Table[i + 1] = j; 226 while (i >= 0) 227 { 228 while ( (j < P_NeedleLen) && (P_Needle[i] != P_Needle[j]) ) 229 { 230 j = P_KMP_Table[j + 1]; 231 } 232 i--; 233 j--; 234 if (i >= 0) 235 { 236 if (P_Needle[i] == P_Needle[j]) 237 { 238 P_KMP_Table[i + 1] = P_KMP_Table[j + 1]; 239 } 240 else 241 { 242 P_KMP_Table[i + 1] = j; 243 } 244 } 245 else 246 { 247 P_KMP_Table[i + 1] = j; 248 } 249 } 250 251 return; 252 } 253 254 255 /* Search data from left to right. ( Multiple search mode. ) */ 256 _UNUSED_ static long _utstring_find( 257 const char *P_Haystack, 258 size_t P_HaystackLen, 259 const char *P_Needle, 260 size_t P_NeedleLen, 261 long *P_KMP_Table) 262 { 263 long i, j; 264 long V_FindPosition = -1; 265 266 /* Search from left to right. */ 267 i = j = 0; 268 while ( (j < (int)P_HaystackLen) && (((P_HaystackLen - j) + i) >= P_NeedleLen) ) 269 { 270 while ( (i > -1) && (P_Needle[i] != P_Haystack[j]) ) 271 { 272 i = P_KMP_Table[i]; 273 } 274 i++; 275 j++; 276 if (i >= (int)P_NeedleLen) 277 { 278 /* Found. */ 279 V_FindPosition = j - i; 280 break; 281 } 282 } 283 284 return V_FindPosition; 285 } 286 287 288 /* Search data from right to left. ( Multiple search mode. ) */ 289 _UNUSED_ static long _utstring_findR( 290 const char *P_Haystack, 291 size_t P_HaystackLen, 292 const char *P_Needle, 293 size_t P_NeedleLen, 294 long *P_KMP_Table) 295 { 296 long i, j; 297 long V_FindPosition = -1; 298 299 /* Search from right to left. */ 300 j = (P_HaystackLen - 1); 301 i = (P_NeedleLen - 1); 302 while ( (j >= 0) && (j >= i) ) 303 { 304 while ( (i < (int)P_NeedleLen) && (P_Needle[i] != P_Haystack[j]) ) 305 { 306 i = P_KMP_Table[i + 1]; 307 } 308 i--; 309 j--; 310 if (i < 0) 311 { 312 /* Found. */ 313 V_FindPosition = j + 1; 314 break; 315 } 316 } 317 318 return V_FindPosition; 319 } 320 321 322 /* Search data from left to right. ( One time search mode. ) */ 323 _UNUSED_ static long utstring_find( 324 UT_string *s, 325 long P_StartPosition, /* Start from 0. -1 means last position. */ 326 const char *P_Needle, 327 ssize_t P_NeedleLen) 328 { 329 long V_StartPosition; 330 long V_HaystackLen; 331 long *V_KMP_Table; 332 long V_FindPosition = -1; 333 334 if (P_StartPosition < 0) 335 { 336 V_StartPosition = s->i + P_StartPosition; 337 } 338 else 339 { 340 V_StartPosition = P_StartPosition; 341 } 342 V_HaystackLen = s->i - V_StartPosition; 343 if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) ) 344 { 345 V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1)); 346 if (V_KMP_Table != NULL) 347 { 348 _utstring_BuildTable(P_Needle, P_NeedleLen, V_KMP_Table); 349 350 V_FindPosition = _utstring_find(s->d + V_StartPosition, 351 V_HaystackLen, 352 P_Needle, 353 P_NeedleLen, 354 V_KMP_Table); 355 if (V_FindPosition >= 0) 356 { 357 V_FindPosition += V_StartPosition; 358 } 359 360 free(V_KMP_Table); 361 } 362 } 363 364 return V_FindPosition; 365 } 366 367 368 /* Search data from right to left. ( One time search mode. ) */ 369 _UNUSED_ static long utstring_findR( 370 UT_string *s, 371 long P_StartPosition, /* Start from 0. -1 means last position. */ 372 const char *P_Needle, 373 ssize_t P_NeedleLen) 374 { 375 long V_StartPosition; 376 long V_HaystackLen; 377 long *V_KMP_Table; 378 long V_FindPosition = -1; 379 380 if (P_StartPosition < 0) 381 { 382 V_StartPosition = s->i + P_StartPosition; 383 } 384 else 385 { 386 V_StartPosition = P_StartPosition; 387 } 388 V_HaystackLen = V_StartPosition + 1; 389 if ( (V_HaystackLen >= P_NeedleLen) && (P_NeedleLen > 0) ) 390 { 391 V_KMP_Table = (long *)malloc(sizeof(long) * (P_NeedleLen + 1)); 392 if (V_KMP_Table != NULL) 393 { 394 _utstring_BuildTableR(P_Needle, P_NeedleLen, V_KMP_Table); 395 396 V_FindPosition = _utstring_findR(s->d, 397 V_HaystackLen, 398 P_Needle, 399 P_NeedleLen, 400 V_KMP_Table); 401 402 free(V_KMP_Table); 403 } 404 } 405 406 return V_FindPosition; 407 } 408 /******************************************************************************* 409 * end substring search functions * 410 ******************************************************************************/ 411 412 #endif /* UTSTRING_H */ 413