1 |
/* |
2 |
The Malete project - the Z39.2/Z39.50 database framework of OpenIsis. |
3 |
Version 0.9.x (patchlevel see file Version) |
4 |
Copyright (C) 2001-2003 by Erik Grziwotz, erik@openisis.org |
5 |
|
6 |
This library is free software; you can redistribute it and/or |
7 |
modify it under the terms of the GNU Lesser General Public |
8 |
License as published by the Free Software Foundation; either |
9 |
version 2.1 of the License, or (at your option) any later version. |
10 |
|
11 |
This library is distributed in the hope that it will be useful, |
12 |
but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. |
14 |
See the GNU Lesser General Public License for more details. |
15 |
|
16 |
You should have received a copy of the GNU Lesser General Public |
17 |
License along with this library; if not, write to the Free Software |
18 |
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
19 |
|
20 |
see README for more information |
21 |
EOH */ |
22 |
|
23 |
/* |
24 |
$Id: uti.c,v 1.25 2004/11/11 13:13:01 kripke Exp $ |
25 |
utilities |
26 |
*/ |
27 |
|
28 |
#include <string.h> /* strlen */ |
29 |
#include <stdarg.h> |
30 |
|
31 |
|
32 |
#include "../core/core.h" |
33 |
|
34 |
/* ************************************************************ |
35 |
data |
36 |
*/ |
37 |
const char b36dig[36] = { |
38 |
'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','g','h', |
39 |
'i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z' |
40 |
}; |
41 |
|
42 |
const char b36val[256] = { |
43 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
44 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
45 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
46 |
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,36,36,36,36,36,36, |
47 |
36,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24, |
48 |
25,26,27,28,29,30,31,32,33,34,35,36,36,36,36,36, |
49 |
36,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24, |
50 |
25,26,27,28,29,30,31,32,33,34,35,36,36,36,36,36, |
51 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
52 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
53 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
54 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
55 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
56 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
57 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36, |
58 |
36,36,36,36,36,36,36,36,36,36,36,36,36,36,36,36 |
59 |
}; |
60 |
|
61 |
const unsigned char lat1up[256] = { |
62 |
0,' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ', |
63 |
' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ', |
64 |
' ','!','"','#','$','%','&','\'','(',')','*','+',',','-','.','/', |
65 |
'0','1','2','3','4','5','6','7','8','9',':',';','<','=','>','?', |
66 |
'@','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O', |
67 |
'P','Q','R','S','T','U','V','W','X','Y','Z','[','\\',']','^','_', |
68 |
'`','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O', |
69 |
'P','Q','R','S','T','U','V','W','X','Y','Z','{','|','}','~',' ', |
70 |
' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ', |
71 |
' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ',' ', |
72 |
' ',161,162,163,164,165,166,167,168,169,170,171,172,173,174,175, |
73 |
176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191, |
74 |
'A','A','A','A','A','A','A','C','E','E','E','E','I','I','I','I', |
75 |
'T','N','O','O','O','O','O',215,'O','U','U','U','U','Y','T','S', |
76 |
'A','A','A','A','A','A','A','C','E','E','E','E','I','I','I','I', |
77 |
'T','N','O','O','O','O','O',247,'O','U','U','U','U','Y','T','Y' |
78 |
}; |
79 |
|
80 |
const unsigned char lat1ct[256] = { |
81 |
/* NUL STX SOT ETX EOT ENQ ACK BEL */ |
82 |
CT_W,CT_W,CT_W,CT_W,CT_W,CT_W,CT_W,CT_W, |
83 |
/* BS HT LF VT FF CR SO SI */ |
84 |
CT_W,CT_W,CT_W,CT_W,CT_W,CT_W,CT_W,CT_W, |
85 |
/* DLE DC1 DC2 DC3 DC4 NAK SYN ETB */ |
86 |
CT_W,CT_W,CT_W,CT_W,CT_W,CT_W,CT_W,CT_W, |
87 |
/* CAN EM SUB ESC FS GS RS US */ |
88 |
CT_W,CT_W,CT_W,CT_W,CT_W,CT_W,CT_W,CT_W, |
89 |
/*blank ! " # $ % & ' */ |
90 |
CT_W,CT_S,CT_S,CT_S,CT_S,CT_S,CT_S,CT_S, |
91 |
/* ( ) * + , - . / */ |
92 |
CT_S,CT_S,CT_S,CT_S,CT_S,CT_S,CT_S,CT_S, |
93 |
/* 0 1 2 3 4 5 6 7 */ |
94 |
CT_D,CT_D,CT_D,CT_D,CT_D,CT_D,CT_D,CT_D, |
95 |
/* 8 9 : ; < = > ? */ |
96 |
CT_D,CT_D,CT_S,CT_S,CT_S,CT_S,CT_S,CT_S, |
97 |
/* @ A B C D E F G */ |
98 |
CT_S,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A, |
99 |
CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A, /* H-O */ |
100 |
CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A, /* P-W */ |
101 |
/* X Y Z [ \ ] ^ _ */ |
102 |
CT_A,CT_A,CT_A,CT_S,CT_S,CT_S,CT_S,CT_I, |
103 |
/* ` a b c d e f g */ |
104 |
CT_S,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A, |
105 |
CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A, |
106 |
CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A,CT_A, |
107 |
/* x y z { | } ~ DEL */ |
108 |
CT_A,CT_A,CT_A,CT_S,CT_S,CT_S,CT_S,CT_S, |
109 |
/* 32 C1 controls */ |
110 |
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , |
111 |
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , |
112 |
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , |
113 |
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , |
114 |
/* 32 mostly symbols */ |
115 |
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , |
116 |
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , |
117 |
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , |
118 |
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , |
119 |
/* 64 Latin alphas including 2 symbols */ |
120 |
CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L, |
121 |
CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L, |
122 |
CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L, 0 , |
123 |
CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L, |
124 |
CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L, |
125 |
CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L, |
126 |
CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L, 0 , |
127 |
CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L,CT_L |
128 |
}; |
129 |
|
130 |
/* ************************************************************ |
131 |
general utilities |
132 |
*/ |
133 |
|
134 |
|
135 |
int a2il ( const char *p, int l, int *res ) |
136 |
{ |
137 |
const char *s = p; |
138 |
const char *e; |
139 |
char op = 0; |
140 |
int d, ret = 0; |
141 |
if ( 0 > l ) { /* 0 terminated */ |
142 |
while ( ' ' >= (unsigned char)*p ) |
143 |
if ( !*p++ ) |
144 |
return p - s -1; |
145 |
e = p+11; /* max useful, we bail out on 0 byte */ |
146 |
} else |
147 |
for ( e = p+l; p < e && ' ' >= (unsigned char)*p; ) /* skip white */ |
148 |
p++; |
149 |
if ( p < e ) |
150 |
switch ( *p ) { |
151 |
case '-': |
152 |
if ( p+1 == e ) ret = 1; /* so sole '-' is -1 */ |
153 |
case '~': /* sole ~ is ~0 */ |
154 |
case '+': |
155 |
op = *p++; |
156 |
} |
157 |
if ( p < e && '0' == *p && ++p < e && 'x' == *p ) |
158 |
while ( ++p < e && 16 > (d = b36val[(unsigned char)*p]) ) |
159 |
ret = (ret<<4) + d; |
160 |
else |
161 |
for ( ;p < e && 10 > (d = b36val[(unsigned char)*p]); p++ ) |
162 |
ret = 10*ret + d; |
163 |
if (0 != res) |
164 |
switch (op) { |
165 |
case '-': *res = -ret; break; |
166 |
case '~': *res = ~ret; break; |
167 |
default: *res = ret; |
168 |
} |
169 |
return p - s; |
170 |
} /* a2il */ |
171 |
|
172 |
int a2i ( const char *p, int l ) { |
173 |
int res; |
174 |
a2il (p, l, &res); |
175 |
return res; |
176 |
} |
177 |
|
178 |
int a2id ( const char *p, int l, int dflt ) { |
179 |
int res; |
180 |
if (0 > l) { |
181 |
l = (int) strlen (p); |
182 |
} |
183 |
if (l != a2il (p, l, &res)) { |
184 |
return dflt; |
185 |
} |
186 |
return res; |
187 |
} |
188 |
|
189 |
|
190 |
int i2a ( char *p, int i ) |
191 |
{ |
192 |
if ( i ) { |
193 |
int min, dig = 0, j; |
194 |
if ( 0 < i ) |
195 |
min = 0; |
196 |
else { |
197 |
min = 1; |
198 |
*p++ = '-'; |
199 |
i = -i; |
200 |
} |
201 |
for ( j=i; j; j/=10 ) |
202 |
dig++; |
203 |
for ( *(p+=dig)=0; i; i/=10 ) |
204 |
*--p = '0' + (i % 10); |
205 |
return min+dig; |
206 |
} |
207 |
*p = '0'; |
208 |
return 1; |
209 |
} /* i2a */ |
210 |
|
211 |
|
212 |
int u2a ( char *p, unsigned u ) |
213 |
{ |
214 |
if ( u ) { |
215 |
char *d = p+10; |
216 |
for ( ; u; u/=10 ) |
217 |
*--d = '0' + (u % 10); |
218 |
if ( p < d ) { |
219 |
char *e = p+10, *q = p; |
220 |
while ( d < e ) |
221 |
*q++ = *d++; |
222 |
return q-p; |
223 |
} |
224 |
return 10; |
225 |
} |
226 |
*p = '0'; |
227 |
return 1; |
228 |
} /* u2a */ |
229 |
|
230 |
|
231 |
|
232 |
|
233 |
/* ************************************************************ |
234 |
field functions |
235 |
*/ |
236 |
|
237 |
int vGet ( Fld *dst, const Fld *src, const char *opt ) |
238 |
{ |
239 |
char *p, *e = src->val + src->len; |
240 |
const char *q; |
241 |
|
242 |
if ( !dst->val || (p = dst->val+dst->len) < src->val || dst->val > e ) { |
243 |
/* initial */ |
244 |
p = src->val; |
245 |
if ( (!opt || '*' == *opt) && (!src->len || TAB == *p) ) { |
246 |
dst->tag = 0; |
247 |
dst->val = p; /* catch empty primary */ |
248 |
return 1 + (dst->len = 0); |
249 |
} |
250 |
} else if ( p >= e ) |
251 |
goto notfound; |
252 |
if ( p == src->val && (!opt || '*' == *opt) && TAB != *p ) |
253 |
dst->tag = 0; |
254 |
else { |
255 |
for (;;) { |
256 |
if ( e == p ) |
257 |
goto notfound; |
258 |
if ( TAB != *p++ ) |
259 |
continue; |
260 |
if ( e == p ) /* bad trailing tab */ |
261 |
goto notfound; |
262 |
/* p is on valid subfield indicator */ |
263 |
if ( !opt ) /* take any */ |
264 |
break; |
265 |
for (q=opt; *q; ) |
266 |
if (*p == *q++) |
267 |
goto takeit; /* break 2 */ |
268 |
} |
269 |
takeit: |
270 |
dst->tag = *p++; |
271 |
} |
272 |
dst->val = p; |
273 |
while ( e > p && TAB != *p ) |
274 |
p++; |
275 |
return 1 + (dst->len = p - dst->val); |
276 |
notfound: |
277 |
dst->val = 0; |
278 |
dst->len = 0; |
279 |
return 0; |
280 |
} /* vGet */ |
281 |
|
282 |
|
283 |
int vCmp ( const Fld *a, const Fld *b ) |
284 |
{ |
285 |
unsigned l = a->len; |
286 |
int cmp; |
287 |
|
288 |
if ( l > b->len ) l = b->len; |
289 |
return (l && (cmp = memcmp(a->val, b->val, l))) |
290 |
? cmp : (int)a->len - (int)b->len; |
291 |
} |
292 |
|
293 |
|
294 |
int vGt ( const Fld *a, const Fld *b ) |
295 |
{ |
296 |
unsigned l = a->len; |
297 |
int cmp = 0; |
298 |
|
299 |
if ( l > b->len ) l = b->len; |
300 |
return (l && 0 < (cmp = memcmp(a->val, b->val, l))) ? 1 |
301 |
: !cmp && a->len > b->len; |
302 |
} |
303 |
|
304 |
|
305 |
|
306 |
/* ************************************************************ |
307 |
record functions |
308 |
*/ |
309 |
|
310 |
unsigned rSiz ( const Fld *r ) |
311 |
{ |
312 |
unsigned ret = 0; |
313 |
const Fld *e = r + RLEN(r); |
314 |
|
315 |
while ( r < e ) |
316 |
ret += (r++)->len; |
317 |
return ret; |
318 |
} /* rSiz */ |
319 |
|
320 |
|
321 |
const Fld *rGet ( const Fld *r, int tag, int *pos ) |
322 |
{ |
323 |
const Fld *e = r + RLEN(r); |
324 |
const Fld *p = r + (pos ? *pos : 0); |
325 |
|
326 |
while ( ++p < e ) |
327 |
if ( tag == p->tag ) { |
328 |
if ( pos ) |
329 |
*pos = p-r; |
330 |
return p; |
331 |
} |
332 |
if ( pos ) |
333 |
*pos = e-r; |
334 |
return 0; |
335 |
} /* rGet */ |
336 |
|
337 |
|
338 |
const Fld *rKey ( const Fld *r, int tag, const char *key ) |
339 |
{ |
340 |
const Fld *e = r + RLEN(r); |
341 |
const Fld *d = 0; |
342 |
unsigned kl = strlen(key); |
343 |
|
344 |
while ( ++r < e ) |
345 |
if ( tag == r->tag ) { |
346 |
if ( VKEY(r, key, kl) ) |
347 |
return r; |
348 |
if ( !r->len || TAB == *r->val ) |
349 |
d = r; |
350 |
} |
351 |
return d; |
352 |
} /* rKey */ |
353 |
|
354 |
|
355 |
const Fld *rDup ( const Fld *src, unsigned siz ) |
356 |
{ |
357 |
int len = RLEN(src); |
358 |
const Fld *e = src + len; |
359 |
Fld *dst, *f; |
360 |
char *p; |
361 |
|
362 |
if ( !siz ) |
363 |
siz = rSiz( src ); |
364 |
f = dst = mAlloc( len*sizeof(Fld) + siz ); |
365 |
p = ((char*)dst) + len*sizeof(Fld); |
366 |
for ( ;src < e; src++, f++ ) { |
367 |
f->tag = src->tag; |
368 |
memcpy( f->val = p, src->val, f->len = src->len ); |
369 |
p += f->len; |
370 |
} |
371 |
return dst; |
372 |
} /* rDup */ |
373 |
|
374 |
|
375 |
int rSer ( char *buf, const Fld *f ) |
376 |
{ |
377 |
#if 0 |
378 |
static const char repl[4] = { 0, VT, TAB, ' ' }; |
379 |
const char *s, *e; |
380 |
#endif |
381 |
const Fld *fe = REND(f); |
382 |
char *p = buf; |
383 |
|
384 |
while ( ++f < fe ) { |
385 |
p += i2a( p, f->tag ); |
386 |
*p++ = TAB; |
387 |
memcpy(p, f->val, f->len); |
388 |
p += f->len; |
389 |
#if 0 |
390 |
e = (s = f->val) + f->len; |
391 |
for (;;) { |
392 |
while ( s<e && LF != (*p++ = *s++) ) /* tight */ |
393 |
; |
394 |
if ( s==e ) |
395 |
break; |
396 |
if ( opt ) |
397 |
p[-1] = repl[opt]; |
398 |
else |
399 |
*p++ = TAB; |
400 |
} |
401 |
#endif |
402 |
*p++ = LF; |
403 |
} |
404 |
*p++ = LF; |
405 |
return p - buf; |
406 |
} /* rSer */ |
407 |
|
408 |
|
409 |
#define REVBIT 0x80000000 /* highest bit on the length */ |
410 |
#define LENMSK 0x7fffffff /* will cut fields longer 2GB */ |
411 |
|
412 |
/* |
413 |
basic weak-heap-sort (Dutton 93) |
414 |
for faster variants see indexed-relaxed-weak-heap-sort (Edelkamp) |
415 |
or, for slightly better avg, quick-weak-heap-sort |
416 |
*/ |
417 |
void rSort ( Fld *r, VGt *gt ) |
418 |
{ |
419 |
Fld head, tmp; |
420 |
int l = -r->tag -1; |
421 |
int i; |
422 |
|
423 |
if ( 2 > l ) |
424 |
return; |
425 |
/* fields to sort are r[1]..r[l] |
426 |
we use r[0]..r[l-1], since whs puts biggest at 0 in first step |
427 |
and sorts the others at 1..l-1 |
428 |
*/ |
429 |
head = *r; |
430 |
*r = r[l]; |
431 |
/* weak-heap-forestify |
432 |
every node roots a weak heap AND is <= root |
433 |
(especially the leftist independent roots are <= root) |
434 |
*/ |
435 |
for ( i=l; --i; ) { |
436 |
int g = i; /* granma is 1st left i or root, if i is totally leftist ;) */ |
437 |
while (!(1&g)) /* we're left child */ |
438 |
g >>= 1; /* shift granma right :( */ |
439 |
g >>= 1; |
440 |
r[i].len &= LENMSK; |
441 |
/* merge: swap if g < i */ |
442 |
if ( !gt(r+i, r+g) ) |
443 |
continue; |
444 |
tmp = r[i]; r[i] = r[g]; r[g] = tmp; /* swap */ |
445 |
r[i].len |= REVBIT; |
446 |
} |
447 |
|
448 |
/* re-weak-heap-forestify */ |
449 |
for ( i=l; --i>1; ) { |
450 |
int j=1, left; |
451 |
r[i].len &= LENMSK; /* i's REVBIT no longer needed */ |
452 |
/* follow path of left childs (independent roots) */ |
453 |
while ( i > (left = (j<<1) + ((REVBIT & r[j].len)?1:0)) ) |
454 |
j = left; |
455 |
/* put max of them and i (new root) at i */ |
456 |
do { |
457 |
/* merge: swap if i < j */ |
458 |
/* clear all REVBITs, as gt will probably access .len */ |
459 |
int rj = REVBIT & r[j].len; |
460 |
r[j].len &= LENMSK; /* now i,j both are clean */ |
461 |
if ( !gt(r+j, r+i) ) { |
462 |
r[j].len |= rj; |
463 |
continue; |
464 |
} |
465 |
tmp = r[i]; r[i] = r[j]; r[j] = tmp; /* swap */ |
466 |
/* toggle original REVBIT at j, which now is at i */ |
467 |
if ( ! rj ) |
468 |
r[j].len |= REVBIT; |
469 |
} while (j >>= 1); |
470 |
} |
471 |
r[1].len &= LENMSK; /* 2... have been cleared */ |
472 |
/* initial root still untouched biggest (never had REVBIT) */ |
473 |
r[l] = *r; |
474 |
*r = head; |
475 |
} /* rSort */ |
476 |
|
477 |
|
478 |
void rSortTag ( Fld *r ) /* could use radixsort here ... */ |
479 |
{ |
480 |
Fld head, tmp; |
481 |
int l = -r->tag -1; |
482 |
int i; |
483 |
|
484 |
if ( 2 > l ) |
485 |
return; |
486 |
head = *r; |
487 |
*r = r[l]; |
488 |
for ( i=l; --i; ) { |
489 |
int g = i; |
490 |
while (!(1&g)) |
491 |
g >>= 1; |
492 |
g >>= 1; |
493 |
r[i].len &= LENMSK; |
494 |
if ( r[g].tag >= r[i].tag ) |
495 |
continue; |
496 |
tmp = r[i]; r[i] = r[g]; r[g] = tmp; /* swap */ |
497 |
r[i].len |= REVBIT; |
498 |
} |
499 |
|
500 |
for ( i=l; --i>1; ) { |
501 |
int j=1, left; |
502 |
while ( i > (left = (j<<1) + ((REVBIT & r[j].len)?1:0)) ) |
503 |
j = left; |
504 |
do { |
505 |
if ( r[i].tag >= r[j].tag ) |
506 |
continue; |
507 |
tmp = r[i]; r[i] = r[j]; r[j] = tmp; /* swap */ |
508 |
if ( REVBIT & r[i].len ) |
509 |
r[j].len &= LENMSK; |
510 |
else |
511 |
r[j].len |= REVBIT; |
512 |
} while (j >>= 1); |
513 |
} |
514 |
r[l] = *r; |
515 |
*r = head; |
516 |
while ( l-- ) /* clearing them later is significantly faster */ |
517 |
(++r)->len &= LENMSK; |
518 |
} /* rSortTag */ |
519 |
|
520 |
|
521 |
void rSortVal (Fld *r) |
522 |
{ |
523 |
Fld head, tmp; |
524 |
int l = -r->tag -1; |
525 |
unsigned cl; /* compare length */ |
526 |
int i, cmp; |
527 |
|
528 |
if ( 2 > l ) |
529 |
return; |
530 |
head = *r; |
531 |
*r = r[l]; |
532 |
for ( i=l; --i; ) { |
533 |
int g = i; |
534 |
while (!(1&g)) |
535 |
g >>= 1; |
536 |
g >>= 1; |
537 |
if ( (cl = r[g].len) > r[i].len ) |
538 |
cl = r[i].len; |
539 |
if ( !cl ? !r[i].len |
540 |
: (0 < (cmp = memcmp(r[g].val,r[i].val,cl)) |
541 |
|| (!cmp && r[i].len == cl)) |
542 |
) /* i <= g: ok */ |
543 |
continue; |
544 |
tmp = r[i]; r[i] = r[g]; r[g] = tmp; |
545 |
r[i].len |= REVBIT; |
546 |
} |
547 |
|
548 |
for ( i=l; --i>1; ) { |
549 |
int j=1, left; |
550 |
r[i].len &= LENMSK; |
551 |
while ( i > (left = (j<<1) + ((REVBIT & r[j].len)?1:0)) ) |
552 |
j = left; |
553 |
do { |
554 |
unsigned clj = LENMSK & r[j].len; |
555 |
if ( (cl = r[i].len) > clj ) |
556 |
cl = clj; |
557 |
if ( !cl ? !r[j].len |
558 |
: (0 < (cmp = memcmp(r[i].val,r[j].val,cl)) |
559 |
|| (!cmp && clj == cl)) |
560 |
) /* j <= i: ok */ |
561 |
continue; |
562 |
tmp = r[i]; r[i] = r[j]; r[j] = tmp; |
563 |
if ( REVBIT & r[i].len ) { /* toggle j's REVBIT */ |
564 |
r[i].len &= LENMSK; |
565 |
r[j].len &= LENMSK; |
566 |
} else |
567 |
r[j].len |= REVBIT; |
568 |
} while (j >>= 1); |
569 |
} |
570 |
r[1].len &= LENMSK; |
571 |
r[l] = *r; |
572 |
*r = head; |
573 |
} /* rSortVal */ |
574 |
|
575 |
|
576 |
|
577 |
/* ************************************************************ |
578 |
list functions |
579 |
*/ |
580 |
|
581 |
List *lInit ( List *l, const char *fmt, ... ) |
582 |
{ |
583 |
memset( l, 0, sizeof(*l) ); |
584 |
l->blk = &l->bl0; |
585 |
l->fld = l->fl0; |
586 |
l->fav = DEFFIELDS; |
587 |
l->bok = l->buf = l->bl0.byt; |
588 |
l->end = l->buf + DEFBLKLEN; |
589 |
l->siz = 0; |
590 |
if ( fmt ) { /* print header */ |
591 |
va_list ap; |
592 |
va_start( ap, fmt ); |
593 |
lOut( l, -1, 0, fmt, ap ); |
594 |
va_end( ap ); |
595 |
} |
596 |
return l; |
597 |
} /* lInit */ |
598 |
|
599 |
|
600 |
#define LBLK_FREE( l ) \ |
601 |
while ( (l)->blk != &(l)->bl0 ) { \ |
602 |
LBlk *__nxt = (l)->blk->nxt; \ |
603 |
mBlkFree( (l)->blk ); \ |
604 |
(l)->blk = __nxt; \ |
605 |
} |
606 |
|
607 |
|
608 |
List *lClr ( List *l ) |
609 |
{ |
610 |
l->fav -= l->fld->tag; |
611 |
l->fld->tag = 0; |
612 |
l->fld->val = l->bl0.byt; |
613 |
l->fld->len = 0; |
614 |
l->bok = l->buf = l->bl0.byt; |
615 |
l->end = l->buf + DEFBLKLEN; |
616 |
l->siz = 0; |
617 |
LBLK_FREE(l); |
618 |
return l; |
619 |
} /* lClr */ |
620 |
|
621 |
|
622 |
List *lReset ( List *l ) |
623 |
{ |
624 |
if ( l->fld->val != l->bl0.byt ) { /* header has moved */ |
625 |
if ( l->fld->len > DEFBLKLEN ) |
626 |
l->fld->len = DEFBLKLEN; /* truncate header !!! */ |
627 |
memmove( l->bl0.byt, l->fld->val, l->fld->len ); |
628 |
l->fld->val = l->bl0.byt; |
629 |
} |
630 |
l->fav += -1 - l->fld->tag; |
631 |
l->fld->tag = -1; |
632 |
l->bok = l->buf = l->bl0.byt + l->fld->len; |
633 |
l->end = l->buf + DEFBLKLEN; |
634 |
l->siz = l->fld->len; |
635 |
LBLK_FREE(l); |
636 |
return l; |
637 |
} /* lReset */ |
638 |
|
639 |
|
640 |
void OPT_STDCALL lFini ( List *l ) |
641 |
{ |
642 |
LBLK_FREE(l); |
643 |
if ( l->fld != l->fl0 ) |
644 |
mFldFree( l->fld ); |
645 |
} /* lFini */ |
646 |
|
647 |
|
648 |
int OPT_REGPARM lExtend ( List *l, unsigned need, int fields ) |
649 |
{ |
650 |
LBlk *nju; |
651 |
Fld *contig; |
652 |
|
653 |
if ( 0 <= fields ) |
654 |
contig = 0; |
655 |
else { |
656 |
contig = LLAST(l); |
657 |
fields = -fields -1; |
658 |
need += contig->len; |
659 |
} |
660 |
LOG_DBG(LOG_VERBOSE, "lExtend need %u avl %d fields %u fav %d ctg %d", |
661 |
need, LAVL(l), fields, l->fav, contig); |
662 |
|
663 |
if ( l->fav < (unsigned)fields ) { |
664 |
int had = - l->fld->tag; |
665 |
Fld *f; |
666 |
|
667 |
if ( fields < had>>2 ) /* grow 25% */ |
668 |
fields = had>>2; |
669 |
else if ( fields < DEFFIELDS ) |
670 |
fields = DEFFIELDS; |
671 |
f = mFldAlloc(fields + had); |
672 |
memcpy( f, l->fld, had*sizeof(Fld) ); |
673 |
if ( l->fld != l->fl0 ) |
674 |
mFldFree( l->fld ); |
675 |
l->fld = f; |
676 |
l->fav = (unsigned)fields; |
677 |
} |
678 |
|
679 |
if ( LAVL(l) >= need ) |
680 |
return 1; |
681 |
|
682 |
l->siz += l->buf - l->blk->byt; /* add to secondary size */ |
683 |
nju = mBlkAlloc(need + DEFBLKLEN/2); |
684 |
nju->nxt = l->blk; |
685 |
l->blk = nju; |
686 |
l->buf = nju->byt; |
687 |
l->end = l->buf + nju->siz; /* >= requested */ |
688 |
if ( contig ) { |
689 |
memcpy( l->buf, contig->val, contig->len ); |
690 |
contig->val = l->buf; |
691 |
l->buf += contig->len; |
692 |
} |
693 |
return 1; |
694 |
} /* lExtend */ |
695 |
|
696 |
static const char at[] = { TAB, '@' }; |
697 |
|
698 |
int lArgv ( List *l, int tag, int argc, const char **argv ) |
699 |
{ |
700 |
LNEWF( l, tag, 4000 ); |
701 |
if ( !argc ) |
702 |
return 0; |
703 |
if ( '-' != **argv ) { |
704 |
const char *a = *argv++; |
705 |
argc--; |
706 |
LAPPS( l, a ); |
707 |
} |
708 |
while ( argc-- ) { |
709 |
const char *a = *argv++; |
710 |
unsigned len = 1; |
711 |
if ( '-' == *a ) |
712 |
a++; |
713 |
else |
714 |
len = 2; |
715 |
LAPP( l, at, len ); |
716 |
LAPPS( l, a ); |
717 |
} |
718 |
return LLAST(l)->len; |
719 |
} /* lArgv */ |
720 |
|
721 |
|
722 |
List *lVar ( List *l, int argc, const char **argv ) |
723 |
{ |
724 |
static const char tab = TAB; |
725 |
LNEWF( l, -1, 4000 ); |
726 |
if ( !argc ) |
727 |
return l; |
728 |
if ( '-' != **argv ) { |
729 |
const char *a = *argv++; |
730 |
argc--; |
731 |
LAPPS( l, a ); |
732 |
} |
733 |
while ( argc-- ) { |
734 |
const char *a = *argv++; |
735 |
if ( '-' == *a ) { |
736 |
a++; |
737 |
LAPP( l, &tab, 1 ); |
738 |
} else { |
739 |
LNEWF( l, 1, 100 ); |
740 |
} |
741 |
LAPPS( l, a ); |
742 |
} |
743 |
return l; |
744 |
} /* lVar */ |
745 |
|
746 |
|
747 |
int lCpy ( List *l, const Fld *src, unsigned need ) |
748 |
{ |
749 |
int len = RLEN(src); |
750 |
const Fld *e = src + len; |
751 |
|
752 |
if ( !need ) |
753 |
need = rSiz( src ); |
754 |
if ( !lExtend(l, need, len) ) |
755 |
return 0; |
756 |
for ( ;src < e; src++ ) |
757 |
LADDF( l, src ); |
758 |
return len; |
759 |
} /* lCpy */ |
760 |
|
761 |
|
762 |
int lParse (List *l, const char *p, int s) |
763 |
{ |
764 |
int state = LPS_VAL&s, bits = (LPS_NEG|LPS_CR)&s; |
765 |
const char *e = p + (LPS_LEN&s), *lf; |
766 |
unsigned len; |
767 |
Fld *f = LLAST(l); |
768 |
|
769 |
for (;;) switch (state) { |
770 |
case LPS_SOR: |
771 |
case LPS_SOL: |
772 |
switch (*p) { |
773 |
case CR: |
774 |
if (e == p+1) goto done; /* ignore */ |
775 |
if (LF != p[1]) break; /* weird crap */ |
776 |
p++; |
777 |
case LF: /* got blank line */ |
778 |
return e - p - 1; |
779 |
} |
780 |
LNEWF(l, 0, 80); |
781 |
if ( (LPS_SOR==state) && (CT_IS(D,*p) || '-' == *p) ) { |
782 |
eRr(LOG_WARN, "no message name"); |
783 |
LNEWF(l, 0, 80); |
784 |
} |
785 |
f = LLAST(l); |
786 |
state = LPS_TAG; |
787 |
if ( '-' != *p ) |
788 |
bits &= ~LPS_NEG; |
789 |
else { |
790 |
bits |= LPS_NEG; |
791 |
if ( e == ++p ) goto done; |
792 |
} |
793 |
case LPS_TAG: |
794 |
while ( CT_IS(D,*p) ) { |
795 |
f->tag = f->tag*10 + b36val[(unsigned char)*p]; |
796 |
if ( e == ++p ) goto done; |
797 |
} |
798 |
if ( LPS_NEG & bits ) |
799 |
f->tag = -f->tag; |
800 |
LOG_DBG(LOG_DEBUG, "got tag %d", f->tag); |
801 |
state = LPS_VAL; |
802 |
if ( TAB == *p && e == ++p ) goto done; |
803 |
case LPS_VAL: |
804 |
lf = memchr(p, LF, e-p); |
805 |
if ( !lf ) |
806 |
len = e-p; |
807 |
else if ( (len = lf-p) && CR == lf[-1] ) { |
808 |
if ( LPS_CR & bits ) |
809 |
len--; |
810 |
else if ( f == l->fld ) { |
811 |
len--; |
812 |
bits |= LPS_CR; |
813 |
LOG_DBG(LOG_DEBUG, "detected crlf"); |
814 |
} |
815 |
} |
816 |
LAPP(l, p, len); |
817 |
if ( lf ) { |
818 |
state = LPS_SOL; |
819 |
/* if ( f == l->fld ) STRIP W\t ? */ |
820 |
if ( e > (p = lf+1) ) |
821 |
continue; |
822 |
} |
823 |
goto done; |
824 |
} // for switch |
825 |
done: |
826 |
return state|bits; |
827 |
} /* lParse */ |
828 |
|
829 |
|
830 |
int lOut ( List *l, int tag, const char *fmt, ... ) |
831 |
{ |
832 |
va_list ap; |
833 |
int indir = !fmt; |
834 |
int bav; |
835 |
int len=0, i; |
836 |
unsigned u; |
837 |
char *p, *q=0, c=0; |
838 |
const char *tok = 0; |
839 |
|
840 |
va_start( ap, fmt ); |
841 |
if ( indir ) { |
842 |
va_list ap2; |
843 |
fmt = va_arg(ap, const char*); |
844 |
ap2 = va_arg(ap, va_list); |
845 |
va_end( ap ); |
846 |
ap = ap2; |
847 |
} |
848 |
LNEWF( l, tag, 4000 ); |
849 |
bav = LAVL(l); |
850 |
p = l->buf; |
851 |
for (;;) { |
852 |
if ( !*fmt ) |
853 |
goto extend; |
854 |
if ('%' != *fmt) { |
855 |
tok = fmt+1; |
856 |
while (*tok && '%'!=*tok) |
857 |
tok++; |
858 |
if ( bav < (len = tok-fmt) ) |
859 |
goto extend; |
860 |
memcpy(p, fmt, len); |
861 |
p += len; |
862 |
bav -= len; |
863 |
if ( !*(fmt = tok) ) |
864 |
goto extend; |
865 |
} |
866 |
/* now '%' == *fmt */ |
867 |
switch (c = *++fmt) { |
868 |
case 0: /* bah -- trailing % */ |
869 |
goto extend; |
870 |
case '0': /* only in %0nx */ |
871 |
if ( fmt[1] < '1' || '8' < fmt[1] || 'x' != fmt[2] ) |
872 |
continue; |
873 |
c = fmt[1]; |
874 |
tok = fmt + 2; |
875 |
case '2': /* meaning %02x */ |
876 |
case '4': |
877 |
case '8': |
878 |
if ( 'x' == fmt[1] ) tok = fmt + 1; /* optional */ |
879 |
if (0) { |
880 |
case 'x': |
881 |
c = '4'; |
882 |
case 'd': |
883 |
case 'u': |
884 |
tok = fmt; |
885 |
} |
886 |
if ( bav < (len = 12) ) |
887 |
goto extend; |
888 |
u = va_arg(ap, unsigned); |
889 |
switch (c) { |
890 |
case 'd': len = i2a(p, (int)u); break; |
891 |
case 'u': len = u2a(p, u); break; |
892 |
default: |
893 |
i = len = c - '0'; |
894 |
while (i--) { |
895 |
p[i] = b36dig[u & 0xf]; |
896 |
u >>= 4; |
897 |
} |
898 |
} |
899 |
fmt = tok; |
900 |
break; /* the numbers */ |
901 |
case 'c': |
902 |
if ( bav < (len = 1) ) |
903 |
goto extend; |
904 |
*p = (char)va_arg(ap, int); |
905 |
break; |
906 |
default: |
907 |
case '%': |
908 |
if ( bav < (len = 1) ) |
909 |
goto extend; |
910 |
*p = c; |
911 |
break; |
912 |
case 'b': /* bytes -- eats 2 args len, q */ |
913 |
len = 2*va_arg(ap, int); |
914 |
q = va_arg(ap, char*); |
915 |
if ( bav < len ) |
916 |
goto extend; |
917 |
the_bytes_thing: |
918 |
for (i=0; i<len; ) { |
919 |
u = (unsigned char)*q++; |
920 |
p[i++] = b36dig[u>>4]; |
921 |
p[i++] = b36dig[u & 0xf]; |
922 |
} |
923 |
break; |
924 |
case '.': /* only used as .*s */ |
925 |
if ( '*' != *++fmt || 's' != *++fmt ) |
926 |
continue; /* prolly bad ... */ |
927 |
case '*': /* shorthand */ |
928 |
len = va_arg(ap, int); |
929 |
case 's': |
930 |
q = va_arg(ap, char*); |
931 |
if ( 's' == c ) |
932 |
len = strlen(q); |
933 |
if ( 0 ) { |
934 |
Fld *v; |
935 |
case 'v': |
936 |
v = va_arg(ap, Fld*); |
937 |
len = v->len; |
938 |
q = v->val; |
939 |
} |
940 |
if ( bav < len ) |
941 |
goto extend; |
942 |
the_string_thing: /* for eivind aarset */ |
943 |
/* since we need to shift args to check len and cannot unshift */ |
944 |
memcpy(p, q, len); |
945 |
} |
946 |
p += len; |
947 |
bav -= len; |
948 |
fmt++; |
949 |
continue; |
950 |
extend: |
951 |
LLAST( l )->len += p - l->buf; |
952 |
l->buf = p; |
953 |
if ( !*fmt ) |
954 |
break; |
955 |
/* need len */ |
956 |
lExtend(l, len, -1); |
957 |
bav = LAVL(l); |
958 |
p = l->buf; |
959 |
switch (c) { |
960 |
case '.': |
961 |
case '*': |
962 |
case 's': |
963 |
goto the_string_thing; |
964 |
case 'b': |
965 |
goto the_bytes_thing; |
966 |
} |
967 |
fmt--; /* simply start over */ |
968 |
} |
969 |
if ( !indir ) /* else it's not ours and caller should va_end */ |
970 |
va_end( ap ); |
971 |
return len; |
972 |
} /* lOut */ |