Branch data Line data Source code
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 : 588 : _UNUSED_ static void utstring_printf_va(UT_string *s, const char *fmt, va_list ap) {
124 : : int n;
125 : : va_list cp;
126 : 588 : while (1) {
127 : : #ifdef _WIN32
128 : : cp = ap;
129 : : #else
130 : 588 : va_copy(cp, ap);
131 : : #endif
132 : 588 : n = vsnprintf (&s->d[s->i], s->n-s->i, fmt, cp);
133 : 588 : va_end(cp);
134 : :
135 [ + - - + ]: 588 : if ((n > -1) && (n < (int)(s->n-s->i))) {
136 : 588 : s->i += n;
137 : 588 : return;
138 : : }
139 : :
140 : : /* Else try again with more space. */
141 [ # # # # : 0 : if (n > -1) utstring_reserve(s,n+1); /* exact */
# # # # ]
142 [ # # # # : 0 : 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 : 588 : _UNUSED_ static void utstring_printf(UT_string *s, const char *fmt, ...) {
151 : : va_list ap;
152 : 588 : va_start(ap,fmt);
153 : 588 : utstring_printf_va(s,fmt,ap);
154 : 588 : va_end(ap);
155 : 588 : }
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 */
|
