| /* | |
| 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); } |