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