Chameleon

Chameleon Svn Source Tree

Root/branches/cparm/i386/libsaio/utstring.h

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

Archive Download this file

Revision: 2182