Chameleon

Chameleon Svn Source Tree

Root/branches/cparm/i386/modules/include/utstring.h

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

Archive Download this file

Revision: 2182