| /* |
| Copyright 2002-2003 John Plevyak, All Rights Reserved |
| */ |
| |
| #include "d.h" |
| |
| uint prime2[] = { |
| 1, 3, 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, |
| 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 2097143, |
| 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, |
| 268435399, 536870909 |
| }; |
| |
| int verbose_level = 0; |
| int debug_level = 0; |
| int test_level = 0; |
| |
| char * |
| d_dup_pathname_str(char *s) { |
| char *e = s; |
| if (!s) |
| return strdup(""); |
| if (*e == '"') { |
| e++; while (*e && *e != '"') e++; |
| return dup_str(s + 1, e); |
| } else |
| return dup_str(s, s+strlen(s)); |
| } |
| |
| char * |
| dup_str(char *s, char *e) { |
| int l = e-s; |
| char *ss = (char*)MALLOC(l+1); |
| memcpy(ss, s, l); |
| ss[l] = 0; |
| return ss; |
| } |
| |
| uint |
| strhashl(char *s, int l) { |
| uint h = 0, g; |
| int i = 0; |
| |
| for (;i < l;i++,s++) { |
| h = (h << 4) + *s; |
| if ((g = h & 0xf0000000)) |
| h = (h ^ (g >> 24)) ^ g; |
| } |
| return h; |
| } |
| |
| int |
| buf_read(char *pathname, char **buf, int *len) { |
| struct stat sb; |
| int fd; |
| |
| *buf = 0; |
| *len = 0; |
| fd = open(pathname, O_RDONLY); |
| if (fd <= 0) |
| return -1; |
| memset(&sb, 0, sizeof(sb)); |
| fstat(fd, &sb); |
| *len = sb.st_size; |
| *buf = (char*)MALLOC(*len + 2); |
| (*buf)[*len] = 0; /* terminator */ |
| (*buf)[*len + 1] = 0; /* sentinal */ |
| read(fd, *buf, *len); |
| close(fd); |
| return *len; |
| } |
| |
| char * |
| sbuf_read(char *pathname) { |
| char *buf; |
| int len; |
| |
| if (buf_read(pathname, &buf, &len) < 0) |
| return NULL; |
| return buf; |
| } |
| |
| void |
| d_fail(char *str, ...) { |
| char nstr[256]; |
| va_list ap; |
| va_start(ap, str); |
| snprintf(nstr, 255, "fail: %s\n", str); |
| vfprintf(stderr, nstr, ap); |
| va_end(ap); |
| exit(1); |
| } |
| |
| void |
| vec_add_internal(void *v, void *elem) { |
| AbstractVec *av = (AbstractVec*)v; |
| if (!av->n) { |
| av->v = av->e; |
| } else if (av->v == av->e) { |
| av->v = (void**)MALLOC(INITIAL_VEC_SIZE * sizeof(void *)); |
| memcpy(av->v, av->e, av->n * sizeof(void *)); |
| } else |
| if ((av->n & (INITIAL_VEC_SIZE - 1)) == 0) { |
| int l = av->n, nl = (1 + INITIAL_VEC_SHIFT); |
| l = l >> INITIAL_VEC_SHIFT; |
| while (!(l&1)) { l = l >> 1; nl++; } |
| l = l >> 1; |
| if (!av->n || !l) { |
| nl = 1 << nl; |
| av->v = (void**)REALLOC(av->v, nl * sizeof(void *)); |
| } |
| } |
| av->v[av->n++] = elem; |
| } |
| |
| int |
| vec_eq(void *v, void *vv) { |
| AbstractVec *av = (AbstractVec*)v; |
| AbstractVec *avv = (AbstractVec*)vv; |
| uint i; |
| |
| if (av->n != avv->n) |
| return 0; |
| for (i = 0; i < av->n; i++) |
| if (av->v[i] != avv->v[i]) |
| return 0; |
| return 1; |
| } |
| |
| void * |
| stack_push_internal(AbstractStack *s, void *elem) { |
| int n = s->cur - s->start; |
| if (s->start == s->initial) { |
| s->cur = (void**)MALLOC(n * 2 * sizeof(void*)); |
| memcpy(s->cur, s->start, n * sizeof(void*)); |
| } else |
| s->cur = (void**)REALLOC(s->start, n * 2 * sizeof(void*)); |
| s->end = s->start = s->cur; |
| s->cur += n; |
| s->end += n * 2; |
| *s->cur++ = elem; |
| return elem; |
| } |
| |
| int |
| set_add(void *av, void *t) { |
| AbstractVec *v = (AbstractVec*)av, vv; |
| int j, n = v->n; |
| uint i; |
| if (n) { |
| ulong h = ((ulong)t); |
| h = h % n; |
| for (i = h, j = 0; |
| i < v->n && j < SET_MAX_SEQUENTIAL; |
| i = ((i + 1) % n), j++) |
| { |
| if (!v->v[i]) { |
| v->v[i] = t; |
| return 1; |
| } else if (v->v[i] == t) |
| return 0; |
| } |
| } |
| if (!n) { |
| vv.v = NULL; |
| v->i = INITIAL_SET_SIZE_INDEX; |
| } else { |
| vv.v = v->v; |
| vv.n = v->n; |
| v->i = v->i + 1; |
| } |
| v->n = prime2[v->i]; |
| v->v = (void**)MALLOC(v->n * sizeof(void *)); |
| memset(v->v, 0, v->n * sizeof(void *)); |
| if (vv.v) { |
| set_union(av, &vv); |
| FREE(vv.v); |
| } |
| return set_add(v, t); |
| } |
| |
| void * |
| set_add_fn(void *av, void *t, hash_fns_t *fns) { |
| AbstractVec *v = (AbstractVec*)av, vv; |
| uint32 tt = fns->hash_fn(t, fns); |
| int j, n = v->n; |
| uint i; |
| if (n) { |
| uint h = tt % n; |
| for (i = h, j = 0; |
| i < v->n && j < SET_MAX_SEQUENTIAL; |
| i = ((i + 1) % n), j++) |
| { |
| if (!v->v[i]) { |
| v->v[i] = t; |
| return t; |
| } else { |
| if (!fns->cmp_fn(v->v[i], t, fns)) |
| return v->v[i]; |
| } |
| } |
| } |
| if (!n) { |
| vv.v = NULL; |
| v->i = INITIAL_SET_SIZE_INDEX; |
| } else { |
| vv.v = v->v; |
| vv.n = v->n; |
| v->i = v->i + 1; |
| } |
| v->n = prime2[v->i]; |
| v->v = (void**)MALLOC(v->n * sizeof(void *)); |
| memset(v->v, 0, v->n * sizeof(void *)); |
| if (vv.v) { |
| set_union_fn(av, &vv, fns); |
| FREE(vv.v); |
| } |
| return set_add_fn(v, t, fns); |
| } |
| |
| int |
| set_union(void *av, void *avv) { |
| AbstractVec *vv = (AbstractVec*)avv; |
| uint i, changed = 0; |
| |
| for (i = 0; i < vv->n; i++) |
| if (vv->v[i]) |
| changed = set_add(av, vv->v[i]) || changed; |
| return changed; |
| } |
| |
| void |
| set_union_fn(void *av, void *avv, hash_fns_t *fns) { |
| AbstractVec *vv = (AbstractVec*)avv; |
| uint i; |
| |
| for (i = 0; i < vv->n; i++) |
| if (vv->v[i]) |
| set_add_fn(av, vv->v[i], fns); |
| } |
| |
| void |
| set_to_vec(void *av) { |
| AbstractVec *v = (AbstractVec*)av, vv; |
| uint i; |
| |
| vv.n = v->n; |
| vv.v = v->v; |
| if (v->v == v->e) { |
| memcpy(vv.e, v->e, sizeof(v->e)); |
| vv.v = vv.e; |
| } |
| v->n = 0; |
| v->v = 0; |
| for (i = 0; i < vv.n; i++) |
| if (vv.v[i]) |
| vec_add_internal(v, vv.v[i]); |
| FREE(vv.v); |
| } |
| |
| void |
| int_list_diff(int *a, int *b, int *c) { |
| while (1) { |
| if (*b < 0) |
| break; |
| Lagainc: |
| if (*c < 0) { |
| while (*b >= 0) |
| *a++ = *b++; |
| break; |
| } |
| Lagainb: |
| if (*b == *c) { |
| b++; |
| c++; |
| continue; |
| } |
| if (*b < *c) { |
| *a++ = *b++; |
| if (*b < 0) |
| break; |
| goto Lagainb; |
| } |
| if (*c < *b) { |
| c++; |
| goto Lagainc; |
| } |
| } |
| *a++ = -1; |
| } |
| |
| void |
| int_list_intersect(int *a, int *b, int *c) { |
| while (1) { |
| if (*b < 0) |
| break; |
| Lagainc: |
| if (*c < 0) |
| break; |
| Lagainb: |
| if (*b == *c) { |
| *a++ = *b++; |
| c++; |
| continue; |
| } |
| if (*b < *c) { |
| b++; |
| if (*b < 0) |
| break; |
| goto Lagainb; |
| } |
| if (*c < *b) { |
| c++; |
| goto Lagainc; |
| } |
| } |
| *a++ = -1; |
| } |
| |
| int * |
| int_list_dup(int *aa) { |
| int *a = aa, *b, *bb; |
| while (*a != -1) { a++; } |
| bb = b = (int*)MALLOC((a - aa + 1) * sizeof(int)); |
| a = aa; |
| while (*a != -1) { *b++ = *a++; } |
| *b++ = -1; |
| return bb; |
| } |
| |
| #define ESC(_c) *ss++ = '\\'; *ss++ = _c; break; |
| char * |
| escape_string(char *s) { |
| char *ss = (char*)MALLOC((strlen(s) + 1) * 4), *sss = ss; |
| for (; *s; s++) { |
| switch (*s) { |
| case '\b': ESC('b'); |
| case '\f': ESC('f'); |
| case '\n': ESC('n'); |
| case '\r': ESC('r'); |
| case '\t': ESC('t'); |
| case '\v': ESC('v'); |
| case '\a': ESC('a'); |
| case '\\': |
| case '\"': |
| *ss++ = '\\'; |
| *ss++ = *s; break; |
| |
| default: |
| if (isprint(*s)) { |
| *ss++ = *s; |
| } else { |
| *ss++ = '\\'; |
| *ss++ = 'x'; |
| *ss++ = tohex2(*s); |
| *ss++ = tohex1(*s); |
| } |
| break; |
| } |
| } |
| *ss = 0; |
| return sss; |
| } |
| |
| void d_free(void *x) { FREE(x); } |