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