/* Copyright 1989, 1990 by James Aspnes, David Applegate, and Bennet Yee */
/* See the file COPYING for distribution information */
#ifndef _ASSOC_H
#define _ASSOC_H

#include "config.h"

typedef datum *alist;    

#define empty_alist() (0)
#define isempty(a) ((a) == 0)
#define free_alist(x) (free((void *) x))

#define NOTHING (0)

/* returns 1 if key is found, 0 otherwise */
/* If key is found, the value is stored in *value unless value = NULL */
extern int assoc(alist, datum key, datum *value /* RETVAL */);

/* searches for particular key, value pair */
extern int alist_member(alist, datum key, datum value);

extern alist add_assoc(alist, datum key, datum value);
extern alist del_assoc(alist, datum key, datum value);
extern alist del_assocs(alist, datum key);
extern alist set_assoc(alist, datum key, datum value);
extern alist copy_alist(alist);

#define hash_range(range, key) ((unsigned long) 3 * (key) % (range))
#define next_probe(range, p) (((p) ? (p) : (range)) - 1)

/* these are not safe if the alist is empty */
#define alist_size(a) ((a)[0])
#define alist_count(a) ((a)[1])
#define alist_key(a, i) ((a)[((i) << 1) + 2])
#define alist_value(a, i) ((a)[((i) << 1) + 3])

#define FOREACH(alist, keyvar, valvar) \
{ \
    unsigned long _FOREACH_p; \
    if(alist) \
	for(_FOREACH_p = 0; _FOREACH_p < alist_size(alist); _FOREACH_p++) { \
	    if((keyvar = alist_key(alist, _FOREACH_p)) != NOTHING) { \
		valvar = alist_value(alist, _FOREACH_p);

#define FOREACH_MATCH(alist, key, valvar) \
{ \
    unsigned long _FOREACH_p;\
    if(alist) \
	for(_FOREACH_p = hash_range(alist_size(alist), (key)); \
	    alist_key(alist, _FOREACH_p) != NOTHING; \
	    _FOREACH_p = next_probe(alist_size(alist), _FOREACH_p)) { \
	    if(alist_key(alist, _FOREACH_p) == (key)) { \
		valvar = alist_value(alist, _FOREACH_p);
	    
#define END_FOREACH }}}

/* "re-entrant FOREACH" */
typedef struct {
    datum pos;
    datum key;
} alist_iterator;

extern datum alist_first(alist a, alist_iterator *iter, datum *value);
extern datum alist_next(alist a, alist_iterator *iter, datum *value);

/* return 1 if another match exists */
extern int alist_first_match(alist a, alist_iterator *iter, datum *value,
			     datum key);
extern int alist_next_match(alist a, alist_iterator *iter, datum *value);

#endif /* _ASSOC_H */