1 /*
2 * data.c -- basic data structures and functions to manipulate them
3 *
4 * Copyright (C) 1998 by Massimiliano Ghilardi
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 */
12
13 #include <stdio.h>
14 #include <stdlib.h>
15 #include <string.h>
16 #include <errno.h>
17 #include <time.h>
18 #include <sys/time.h>
19
20 #include "defines.h"
21 #include "main.h"
22 #include "utils.h"
23 #include "eval.h"
24
25 /*
26 * create a new, empty ptr.
27 * return NULL if max == 0
28 */
__P1(int,max)29 ptr ptrnew __P1 (int,max)
30 {
31 ptr p = (ptr)0;
32
33 if (max == 0)
34 ;
35 else if (limit_mem && max > limit_mem)
36 error = MEM_LIMIT_ERROR;
37 else if (max < 0 || max + sizeofptr < max) /* overflow! */
38 error = NO_MEM_ERROR;
39 else if ((p = (ptr)malloc(max + sizeofptr))) {
40 p->signature = PTR_SIG;
41 p->max = max;
42 ptrdata(p)[p->len = 0] = '\0';
43 } else
44 error = NO_MEM_ERROR;
45 return p;
46 }
47
48 /*
49 * create a new ptr giving an initial contents,
50 * which gets duplicated.
51 *
52 * warning: newmax could be so small that we must truncate the copied data!
53 */
__P2(ptr,src,int,newmax)54 ptr ptrdup2 __P2 (ptr,src, int,newmax)
55 {
56 ptr p = (ptr)0;
57
58 if (newmax == 0)
59 ;
60 else if (newmax < 0 || newmax + sizeofptr < newmax)
61 error = NO_MEM_ERROR;
62 else if (limit_mem && newmax > limit_mem)
63 error = MEM_LIMIT_ERROR;
64 else if (!src)
65 p = ptrnew(newmax);
66 else if ((p = malloc(newmax + sizeofptr))) {
67 p->signature = PTR_SIG;
68 p->max = newmax;
69 if (newmax > ptrlen(src))
70 newmax = ptrlen(src);
71 memmove(ptrdata(p), ptrdata(src), p->len = newmax);
72 ptrdata(p)[newmax] = '\0';
73 } else
74 error = NO_MEM_ERROR;
75 return p;
76 }
77
__P1(ptr,src)78 ptr ptrdup __P1 (ptr,src)
79 {
80 if (!src)
81 return src;
82 return ptrdup2(src, ptrlen(src));
83 }
84
85 /* delete (free) a ptr */
__P1(ptr,p)86 void _ptrdel __P1 (ptr,p)
87 {
88 if (p && p->signature == PTR_SIG)
89 free((void *)p);
90 //else
91 //fprintf( stderr, "Tried to free non ptr @%x\n", p );
92 }
93
94 /* clear a ptr */
__P1(ptr,p)95 void ptrzero __P1 (ptr,p)
96 {
97 if (p) {
98 p->len = 0;
99 ptrdata(p)[0] = '\0';
100 }
101 }
102
103 /* truncate a ptr to len chars */
__P2(ptr,p,int,len)104 void ptrtrunc __P2 (ptr,p, int,len)
105 {
106 if (p) {
107 if (len < 0 || len > ptrlen(p))
108 return;
109 ptrdata(p)[p->len = len] = '\0';
110 }
111 }
112
113 /* shrink a ptr by len chars */
__P2(ptr,p,int,len)114 void ptrshrink __P2 (ptr,p, int,len)
115 {
116 if (p) {
117 if (len < 0 || len > ptrlen(p))
118 return;
119 ptrdata(p)[p->len -= len] = '\0';
120 }
121 }
122
123 /*
124 * concatenate two ptr (ptrcat) or a ptr and a char* (ptrmcat)
125 * result may be a _newly_allocated_ ptr if original one
126 * is too small or if it is soooo big that we are wasting tons of memory.
127 * In both cases, the original one may get deleted (freed)
128 * You have been warned! Don't use any statically created ptr for
129 * write operations, and you will be fine.
130 */
__P4(ptr,dst,char *,src,int,len,int,shrink)131 ptr __ptrmcat __P4 (ptr,dst, char *,src, int,len, int,shrink)
132 {
133 int newmax, failmax, overlap;
134 char mustalloc;
135
136 if (!src || len <= 0)
137 return dst;
138 if (len + sizeofptr < 0) {
139 /* overflow! */
140 error = NO_MEM_ERROR;
141 return dst;
142 }
143
144 if (!dst) {
145 failmax = len;
146 mustalloc = 1;
147 } else {
148 failmax = ptrlen(dst) + len;
149 mustalloc = ptrmax(dst) < ptrlen(dst) + len;
150
151 if (shrink && ptrmax(dst) > PARAMLEN
152 && ptrmax(dst)/4 > ptrlen(dst) + len)
153 /* we're wasting space, shrink dst */
154 mustalloc = 1;
155 }
156
157 if (failmax + sizeofptr < 0) {
158 /* overflow! */
159 error = NO_MEM_ERROR;
160 return dst;
161 }
162
163 if (mustalloc) {
164 /* dst must be (re)allocated */
165 ptr p;
166
167 /* ugly but working: check for overlapping dst and src */
168 if (dst && src >= ptrdata(dst) && src < ptrdata(dst) + ptrmax(dst))
169 overlap = 1;
170 else
171 overlap = 0;
172
173 /* find a suitable new size */
174 if (limit_mem && failmax > limit_mem) {
175 error = MEM_LIMIT_ERROR;
176 return dst;
177 }
178 if (failmax < PARAMLEN / 2)
179 newmax = PARAMLEN;
180 else if (failmax / 1024 < PARAMLEN && failmax + PARAMLEN + sizeofptr > 0)
181 newmax = failmax + PARAMLEN;
182 else
183 newmax = failmax;
184 if (limit_mem && newmax > limit_mem) {
185 if (len + (dst ? ptrlen(dst) : 0) > limit_mem)
186 len = limit_mem - (dst ? ptrlen(dst) : 0);
187 if (len < 0)
188 len = 0;
189 newmax = limit_mem;
190 }
191 if ((p = (ptr)realloc((void *)dst, newmax + sizeofptr))) {
192 if (dst == NULL)
193 p->signature = PTR_SIG;
194 if (overlap)
195 src = ptrdata(p) + (src - ptrdata(dst));
196 if (!dst)
197 p->len = 0;
198 p->max = newmax;
199 dst = p;
200 } else if ((p = ptrdup2(dst, newmax))) {
201 if (overlap)
202 src = ptrdata(p) + (src - ptrdata(dst));
203 ptrdel(dst);
204 dst = p;
205 } else {
206 error = NO_MEM_ERROR;
207 return dst;
208 }
209 }
210 if (ptrdata(dst) + ptrlen(dst) != src)
211 memmove(ptrdata(dst) + ptrlen(dst), src, len);
212 dst->len += len;
213 ptrdata(dst)[ptrlen(dst)] = '\0';
214 return dst;
215 }
216
__P3(ptr,dst,char *,src,int,len)217 ptr ptrmcat __P3 (ptr,dst, char *,src, int,len)
218 {
219 return __ptrmcat(dst, src, len, 1);
220 }
221
__P2(ptr,dst,ptr,src)222 ptr ptrcat __P2 (ptr,dst, ptr,src)
223 {
224 if (src)
225 return __ptrmcat(dst, ptrdata(src), ptrlen(src), 1);
226 return dst;
227 }
228
229 /*
230 * copy a ptr into another (ptrcpy), or a char* into a ptr (ptrmcpy);
231 * same warning as above if dst is too small or way too big.
232 */
__P4(ptr,dst,char *,src,int,len,int,shrink)233 ptr __ptrmcpy __P4(ptr,dst, char *,src, int,len, int,shrink)
234 {
235 int newmax, failmax = len, overlap;
236 char mustalloc;
237
238 if (!src || len<=0) {
239 if (len>=0)
240 ptrzero(dst);
241 return dst;
242 }
243 if (failmax + sizeofptr < 0) {
244 /* overflow! */
245 error = NO_MEM_ERROR;
246 return dst;
247 }
248
249 if (!dst) {
250 mustalloc = 1;
251 } else {
252 mustalloc = ptrmax(dst) < len;
253
254 if (shrink && ptrmax(dst) > PARAMLEN && ptrmax(dst)/4 > len)
255 /* we're wasting space, shrink dst */
256 mustalloc = 1;
257 }
258
259 if (mustalloc) {
260 /* dst must be (re)allocated */
261 ptr p;
262
263 /* ugly but working: check for overlapping dst and src */
264 if (dst && src >= ptrdata(dst) && src < ptrdata(dst) + ptrmax(dst))
265 overlap = 1;
266 else
267 overlap = 0;
268
269 /* find a suitable new size */
270 if (limit_mem && failmax > limit_mem) {
271 error = MEM_LIMIT_ERROR;
272 return dst;
273 }
274 if (failmax < PARAMLEN / 2)
275 newmax = PARAMLEN;
276 else if (failmax / 1024 < PARAMLEN && failmax + PARAMLEN + sizeofptr > 0)
277 newmax = failmax + PARAMLEN;
278 else
279 newmax = failmax;
280 if (limit_mem && newmax > limit_mem) {
281 if (len > limit_mem)
282 len = limit_mem;
283 newmax = limit_mem;
284 }
285
286 if ((p = (ptr)realloc((void *)dst, newmax + sizeofptr))) {
287 if (dst == NULL)
288 p->signature = PTR_SIG;
289 if (overlap)
290 src = ptrdata(p) + (src - ptrdata(dst));
291 if (!dst)
292 p->len = 0;
293 p->max = newmax;
294 dst = p;
295 } else if ((p = ptrdup2(dst, newmax))) {
296 if (overlap)
297 src = ptrdata(p) + (src - ptrdata(dst));
298 ptrdel(dst);
299 dst = p;
300 } else {
301 error = NO_MEM_ERROR;
302 return dst;
303 }
304 }
305 if (ptrdata(dst) != src)
306 memmove(ptrdata(dst), src, len);
307 dst->len = len;
308 ptrdata(dst)[ptrlen(dst)] = '\0';
309 return dst;
310 }
311
__P3(ptr,dst,char *,src,int,len)312 ptr ptrmcpy __P3 (ptr,dst, char *,src, int,len)
313 {
314 return __ptrmcpy(dst, src, len, 1);
315 }
316
__P2(ptr,dst,ptr,src)317 ptr ptrcpy __P2 (ptr,dst, ptr,src)
318 {
319 if (src)
320 return __ptrmcpy(dst, ptrdata(src), ptrlen(src), 1);
321 ptrzero(dst);
322 return dst;
323 }
324
325 /* enlarge a ptr by len chars. create new if needed */
__P2(ptr,p,int,len)326 ptr ptrpad __P2 (ptr,p, int,len)
327 {
328 if (!p) {
329 if (len<=0)
330 return p;
331 else
332 return ptrnew(len);
333 }
334 if (len > ptrmax(p) - ptrlen(p)) {
335 /* must realloc the ptr */
336 len += ptrlen(p);
337 if (len < 0) {
338 /* overflow! */
339 error = NO_MEM_ERROR;
340 return p;
341 }
342 /*
343 * cheat: we use ptrmcpy with src==dst
344 * and do an out-of-boud read of src.
345 * works since dst (==src) gets enlarged
346 * before doing the copy.
347 */
348 p = ptrmcpy(p, ptrdata(p), len);
349 } else {
350 p->len += len;
351 ptrdata(p)[ptrlen(p)] = '\0';
352 }
353 return p;
354 }
355
356 /* set a ptr to be len chars at minimum. create new if needed */
__P2(ptr,p,int,len)357 ptr ptrsetlen __P2 (ptr,p, int,len)
358 {
359 if (!p) {
360 if (len<=0)
361 return p;
362 else {
363 if ((p = ptrnew(len)))
364 ptrdata(p)[p->len = len] = '\0';
365 return p;
366 }
367 }
368 return ptrpad(p, len - ptrlen(p));
369 }
370
371 /*
372 * compare two ptr (ptrcmp) or a ptr and a char* (ptrmcmp)
373 * if one is a truncated copy of the other, the shorter is considered smaller
374 */
__P3(ptr,p,char *,q,int,lenq)375 int ptrmcmp __P3 (ptr,p, char *,q, int,lenq)
376 {
377 int res;
378 if (!p || !ptrlen(p)) {
379 if (!q || lenq<=0)
380 /* both empty */
381 res = 0;
382 else
383 res = -1;
384 } else if (!q || lenq<=0)
385 res = 1;
386 else if ((res = memcmp(ptrdata(p), q, MIN2(ptrlen(p), lenq))))
387 ;
388 else if (ptrlen(p) < lenq)
389 res = -1;
390 else if (ptrlen(p) > lenq)
391 res = 1;
392 else
393 res = 0;
394 return res;
395 }
396
__P2(ptr,p,ptr,q)397 int ptrcmp __P2 (ptr,p, ptr,q)
398 {
399 if (q)
400 return ptrmcmp(p, ptrdata(q), ptrlen(q));
401 else if (p)
402 return 1;
403 else
404 return 0;
405 }
406
407 /*
408 * find first occurrence of c in p
409 * return NULL if none found.
410 */
__P2(ptr,p,char,c)411 char *ptrchr __P2 (ptr,p, char,c)
412 {
413 if (p)
414 return (char *)memchr(ptrdata(p), c, ptrlen(p));
415 return (char*)p; /* shortcut for NULL */
416 }
417
418 #ifdef _GNU_SOURCE
419 /*
420 * find last occurrence of c in p
421 * return NULL if none found.
422 */
__P3(char *,p,int,lenp,char,c)423 char *memrchr __P3 (char *,p, int,lenp, char,c)
424 {
425 char *v, *s = p;
426
427 if (!p || lenp<=0)
428 return NULL;
429
430 v = s + lenp - 1;
431 while (v != s && *v != c) {
432 v--;
433 }
434 if (v != s)
435 return v;
436 else
437 return NULL;
438 }
439 #endif
440
__P2(ptr,p,char,c)441 char *ptrrchr __P2 (ptr,p, char,c)
442 {
443 if (p)
444 return memrchr(ptrdata(p), ptrlen(p), c);
445 return (char*)p; /* shortcut for NULL */
446 }
447
448 #ifndef _GNU_SOURCE
449 /*
450 * find first occurrence of needle in hay
451 *
452 * GNU libc has memmem(), for others we do by hand.
453 */
__P4(char *,hay,int,haylen,char *,needle,int,needlelen)454 char *memfind __P4 (char *,hay, int,haylen, char *,needle, int,needlelen)
455 {
456 char *tmp;
457
458 if (!hay || haylen<=0 || needlelen<0)
459 return NULL;
460 if (!needle || !needlelen)
461 return hay;
462
463 while (haylen >= needlelen) {
464 /* find a matching first char */
465 if ((tmp = memchr(hay, *needle, haylen))) {
466 if ((haylen -= (tmp-hay)) < needlelen)
467 return NULL;
468 hay = tmp;
469 } else
470 return NULL;
471
472 /* got a matching first char,
473 * check the rest */
474 if (!memcmp(needle, tmp, needlelen))
475 return tmp;
476
477 hay++, haylen --;
478 }
479
480 return NULL;
481 }
482 #endif /* !_GNU_SOURCE */
483
484 /*
485 * find first occurrence of q in p,
486 * return NULL if none found.
487 */
__P3(ptr,p,char *,q,int,lenq)488 char *ptrmfind __P3 (ptr,p, char *,q, int,lenq)
489 {
490 if (p) {
491 if (q && lenq>0)
492 return (char *)memfind(ptrdata(p), ptrlen(p), q, lenq);
493 return ptrdata(p);
494 }
495 return (char*)p; /* shortcut for NULL */
496 }
497
__P2(ptr,p,ptr,q)498 char *ptrfind __P2 (ptr,p, ptr,q)
499 {
500 if (p) {
501 if (q)
502 return (char *)memfind(ptrdata(p), ptrlen(p), ptrdata(q), ptrlen(q));
503 return ptrdata(p);
504 }
505 return (char*)p; /* shortcut for NULL */
506 }
507
508
509 /*
510 * Scan p for the first occurrence of one of the characters in q,
511 * return NULL if none of them is found.
512 */
__P4(char *,p,int,lenp,char *,q,int,lenq)513 char *memchrs __P4 (char *,p, int,lenp, char *,q, int,lenq)
514 {
515 char *endp;
516
517 if (!q || lenq<=0)
518 return p;
519 if (!p || lenp<=0)
520 return NULL;
521
522 endp = p + lenp;
523
524 while (p < endp && !memchr(q, *p, lenq))
525 p++;
526
527 if (p == endp)
528 return NULL;
529 return p;
530 }
531
__P3(ptr,p,char *,q,int,lenq)532 char *ptrmchrs __P3 (ptr,p, char *,q, int,lenq)
533 {
534 if (p)
535 return memchrs(ptrdata(p), ptrlen(p), q, lenq);
536 return (char*)p; /* shortcut for NULL */
537 }
538
__P2(ptr,p,ptr,q)539 char *ptrchrs __P2 (ptr,p, ptr,q)
540 {
541 if (p) {
542 if (q)
543 return memchrs(ptrdata(p), ptrlen(p), ptrdata(q), ptrlen(q));
544 return ptrdata(p);
545 }
546 return (char*)p; /* shortcut for NULL */
547 }
548
549
550 /*
551 * Scan p for the last occurrence of one of the characters in q,
552 * return NULL if none of them is found.
553 */
__P4(char *,p,int,lenp,char *,q,int,lenq)554 char *memrchrs __P4 (char *,p, int,lenp, char *,q, int,lenq)
555 {
556 if (!p || lenp<=0) {
557 if (!q || lenq<=0)
558 return p;
559 else
560 return NULL;
561 }
562
563 p += lenp;
564 if (!q || lenq<=0)
565 return p;
566 do {
567 lenp--, p--;
568 } while (lenp >= 0 && !memchr(q, *p, lenq));
569
570 if (lenp < 0)
571 return NULL;
572 return p;
573 }
574
__P3(ptr,p,char *,q,int,lenq)575 char *ptrmrchrs __P3 (ptr,p, char *,q, int,lenq)
576 {
577 if (p)
578 return memrchrs(ptrdata(p), ptrlen(p), q, lenq);
579 return (char*)p; /* shortcut for NULL */
580 }
581
__P2(ptr,p,ptr,q)582 char *ptrrchrs __P2 (ptr,p, ptr,q)
583 {
584 if (p && q)
585 return memrchrs(ptrdata(p), ptrlen(p), ptrdata(q), ptrlen(q));
586 return p ? ptrdata(p) + ptrlen(p) : (char*)p; /* shortcut for NULL */
587 }
588
589