/* Copyright 1989, 1990 by James Aspnes, David Applegate, and Bennet Yee */ /* See the file COPYING for distribution information */ #include "os.h" #include "alist.h" #define alist_space_needed(size) (sizeof(datum) * 2 * (size + 1)) #define shrink_threshold(size) ((size) >> 3) /* below this you shrink */ #define grow_threshold(size) (3 * ((size) >> 2)) /* above this you grow */ #define resize_leeway(count) ((count) << 1) /* how much space to guarantee */ /* we don't worry about running off the end of this */ /* because malloc would blow out long before */ static unsigned long nice_primes[] = { 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, 1073741789, 2147483647, 4294967291 }; #define HASH(a, key) hash_range(alist_size(a), (key)) #define NEXT(a, key) next_probe(alist_size(a), key) #define BETWEEN(lb, c, ub) \ (((lb) <= (ub)) ? ((lb) <= (c) && (c) <= (ub)) \ : ((c) >= (lb) || (c) <= (ub))) int assoc (alist a, datum key, datum * value) { unsigned long p; if (a == 0) return 0; for (p = HASH (a, key); alist_key (a, p) != NOTHING && alist_key (a, p) != key; p = NEXT (a, p)); if (alist_key (a, p)) { if (value) *value = alist_value (a, p); return 1; } else { return 0; } } /* this just shoves it in without checking the count */ static void add_assoc1 (alist a, datum key, datum value) { unsigned long p; /* find an empty slot */ for (p = HASH (a, key); alist_key (a, p) != NOTHING; p = NEXT (a, p)); alist_key (a, p) = key; alist_value (a, p) = value; alist_count (a)++; } /* resizes an alist to fit */ static alist resize_alist (alist a) { unsigned long i; alist a1; if (a) { for (i = 0; nice_primes[i] <= (unsigned long)resize_leeway (alist_count (a)); i++); } else { i = 0; } /* nice_primes[i] is the new size */ a1 = (alist) malloc (alist_space_needed (nice_primes[i])); alist_size (a1) = nice_primes[i]; alist_count (a1) = 0; /* clear it out */ for (i = 0; i < (unsigned long)alist_size (a1); i++) { alist_key (a1, i) = NOTHING; } /* throw in everything from the old one */ if (a) { for (i = 0; i < (unsigned long)alist_size (a); i++) { if (alist_key (a, i) != NOTHING) { add_assoc1 (a1, alist_key (a, i), alist_value (a, i)); } } free ((void *) a); } return a1; } /* adds an element to an alist */ alist add_assoc (alist a, datum key, datum value) { if (a == 0 || alist_count (a) >= grow_threshold (alist_size (a))) { a = resize_alist (a); } add_assoc1 (a, key, value); return a; } /* deletes an element from an alist */ /* Don't ask me how it works, read Knuth vol. 2 p. 527 (Algorithm R) */ alist del_assoc (alist a, datum key, datum value) { unsigned long p; unsigned long ub; /* skip until we get it */ for (p = HASH (a, key); alist_key (a, p) != NOTHING && (alist_key (a, p) != key || alist_value (a, p) != value); p = NEXT (a, p)); if (alist_key (a, p) == NOTHING) { return a; /* not found */ } else if (--alist_count (a) == 0) { /* completely empty, nuke it */ free ((void *) a); return 0; } else { /* scan for a replacement */ for (;;) { alist_key (a, p) = NOTHING; /* nuke this place */ /* otherwise, look for something we can move up into p */ ub = p; for (;;) { p = NEXT (a, p); if (alist_key (a, p) == NOTHING) { /* hit the end of the block */ /* check for shrinkage */ if (alist_count (a) <= shrink_threshold (alist_size (a))) { a = resize_alist (a); } return a; } else if (!BETWEEN (p, HASH (a, alist_key (a, p)), NEXT (a, ub))) { /* we've got something we can move up */ alist_key (a, ub) = alist_key (a, p); alist_value (a, ub) = alist_value (a, p); break; /* have to fill this slot now */ } } } } } /* delete all occurences of key */ alist del_assocs (alist a, datum key) { datum value; /* we'll be stupid about it, since a smart version would be painful */ while (assoc (a, key, &value)) a = del_assoc (a, key, value); return a; } /* sets first instance of key to point to value */ /* or adds (key, value) if key isn't there already */ alist set_assoc (alist a, datum key, datum value) { unsigned long p; if (a) { for (p = HASH (a, key); alist_key (a, p) != NOTHING; p = NEXT (a, p)) { if (alist_key (a, p) == key) { /* got it */ alist_value (a, p) = value; return a; } } } /* not there */ return add_assoc (a, key, value); } alist copy_alist (alist a) { alist a1; if (a == 0) return 0; /* empty */ a1 = (alist) malloc (alist_space_needed (alist_size (a))); bcopy ((void *) a, (void *) a1, alist_space_needed (alist_size (a))); return a1; } datum alist_next (alist a, alist_iterator * i, datum * value) { datum key; if (a) { for (i->pos++; i->pos < alist_size (a); i->pos++) { if ((key = alist_key (a, i->pos)) != NOTHING) { if (value) *value = alist_value (a, i->pos); return key; } } } if (value) *value = NOTHING; return NOTHING; } datum alist_first (alist a, alist_iterator * i, datum * value) { i->pos = -1; return alist_next (a, i, value); } int alist_next_match (alist a, alist_iterator * i, datum * value) { datum oldpos; datum key; if (a) { while ((key = alist_key (a, i->pos)) != NOTHING) { oldpos = i->pos; i->pos = next_probe (alist_size (a), i->pos); if (key == i->key) { if (value) *value = alist_value (a, oldpos); return 1; } /* else continue */ } } return 0; } int alist_first_match (alist a, alist_iterator * i, datum * value, datum key) { if (a) { i->key = key; i->pos = hash_range (alist_size (a), key); return alist_next_match (a, i, value); } return 0; } int alist_member (alist a, datum key, datum value) { datum v; FOREACH_MATCH (a, key, v) { if (v == value) return 1; } END_FOREACH; return 0; }