/*
 * Copyright (c) 2004 - 2007, Nils R. Weller 
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright 
 * notice, this list of conditions and the following disclaimer in the 
 * documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
/*
 * This module contains a primitive function to build a linked list for
 * symbols. Because every scope has its own symbol ``table'', speeding
 * this stuff up, e.g. by using a skip list, would probably buy very
 * little, maybe even make it slower. Implementing a unified lookup
 * mechanism for all symbols might be a reasonable future goal though
 */

#include "symlist.h"
#include <string.h>
#include "misc.h"
#include "decl.h"
#include "type.h"
#include "scope.h"
#include "debug.h"
#include "token.h"
#include "n_libc.h"

#define HASH_SYM_ENTRY	1

static int
hash_symbol(const char *name, int tabsize) {
	int	key = 0;

	for (; *name != 0; ++name) {
		key = (33 * key + *name) & (tabsize - 1);
	}
	return key;
}	


void
new_make_hash_table(struct sym_hash_table *tab, int size) {
	int	nbytes = size * sizeof *tab->hash_slots_head;

	tab->n_hash_slots = size;
	
	tab->hash_slots_head = n_xmalloc(nbytes);
	tab->hash_slots_tail = n_xmalloc(nbytes);
	memset(tab->hash_slots_head, 0, nbytes); 
	memset(tab->hash_slots_tail, 0, nbytes); 
	tab->used = 1;
}	


void
new_put_hash_table(struct sym_hash_table *htab, struct sym_entry *item) {
	int	key = hash_symbol(item->name, htab->n_hash_slots);

	if (htab->hash_slots_head[key] == NULL) {
		htab->hash_slots_head[key] = item;
		htab->hash_slots_tail[key] = item;
	} else {
		htab->hash_slots_tail[key]->next = item;
		htab->hash_slots_tail[key] = item;
	}
}

struct sym_entry *
new_lookup_hash(struct sym_hash_table *htab, const char *name, size_t len) {
	int		key = hash_symbol(name, htab->n_hash_slots);
	struct sym_entry	*hp;

	for (hp = htab->hash_slots_head[key]; hp != NULL; hp = hp->next) {
#if 0
		if (hp->item->namelen == len) {
#endif
		if (strcmp(hp->name, name) == 0) {
			return hp;
		}
	}
	return NULL;
}


#if 0
void
put_hash_table(
	struct hash_node **table,
	size_t nslots,
	struct sym_entry *item) {

	struct hash_node	*hn;
	struct hash_node	*newnode;
	int			idx;
	int			lastchar = 0;
	struct hash_node	*patchskip = NULL;
	char			*name = (char *)item->name;
	size_t			namelen = item->namelen;

	if (namelen >= nslots) {
		idx = nslots;
	} else {
		idx = namelen - 1;
	}
	newnode = n_xmalloc(sizeof *newnode);
	newnode->item = item;
	newnode->skip = NULL;
	if (table[idx] != NULL) {
		/* Collision */
		for (hn = table[idx];;) {
			char	*curname;
			struct sym_entry	*se = hn->item;

			curname = (char *)se->name;
			if (curname[0] == name[0]) {
				newnode->next = hn->next;
				hn->next = newnode;
				break;
			} else if (lastchar != curname[0]) {
				lastchar = curname[0];
				patchskip = hn;
			}

			if (hn->next == NULL) {
				newnode->next = NULL;
				hn->next = newnode;
				patchskip->skip = newnode;
				break;
			} else {
				hn = hn->next;
			}
		}
	} else {
		table[idx] = newnode;
		newnode->next = NULL;
	}
}
#endif

struct sym_entry *
make_sym_entry(struct decl *dec) {
	struct sym_entry	*s;

	s = n_xmalloc(sizeof *s);
	s->name = dec->dtype->name;
	if (s->name != NULL) {
		s->namelen = strlen(dec->dtype->name);
	} else {
		s->namelen = 0;
	}	
	s->dec = dec;
	s->next = NULL;
	return s;
}	

void
append_symlist(
	struct scope *scope,	
	struct sym_entry **head,
	struct sym_entry **tail,
	struct decl *dec) {

	struct sym_entry	*s;

	s = make_sym_entry(dec);
	if (scope != NULL && scope->type != SCOPE_STRUCT) {
		/* XXX this stuff does not belong here! it should go to
		 * new_scope() or something
		 */
		if (!scope->sym_hash.used) {
			if (scope == &global_scope) {
#if 0
		scope->sym_hash = n_xmalloc(64 * sizeof *scope->sym_hash);
		scope->n_hash_slots = 63;
		memset(scope->sym_hash, 0, 64 * sizeof *scope->sym_hash);
#endif
				new_make_hash_table(&scope->sym_hash,
					SYM_HTAB_GLOBAL_SCOPE);
#if 0
			} else if (scope->parent == NULL
				|| scope->parent->parent == NULL) {	
				new_make_hash_table(&scope->sym_hash,
					SYM_HTAB_FUNC_TOP_BLOCK);
#endif
			}
		}
	}

	if (scope && scope->sym_hash.used) {
		if (s->name != NULL) {
#if 0
			put_hash_table(scope->sym_hash, scope->n_hash_slots, s);
#endif
			new_put_hash_table(&scope->sym_hash, s);
		}	
	} else {
		if (*head == NULL) {
			*head = *tail = s;
		} else {
			(*tail)->next = s;
			s->prev = *tail;
			*tail = s;
		}
	}
}

#if 0
struct sym_entry *
lookup_hash(struct hash_node **tab, size_t nslots,
	const char *name, size_t len) {

	struct hash_node        *hn;
	struct sym_entry        *se;

	if (len >= nslots) {
		hn = tab[nslots];
	} else {
		hn = tab[len - 1];
	}
	
	if (hn == NULL) {
		return NULL;
	}
	for (;;) {
		se = hn->item;
		if (se->name[0] != name[0]) {
			hn = hn->skip;
		} else if (strcmp(se->name, name) != 0) {
			hn = hn->next;
		} else {
			/* Found */
			return se;
		}
		if (hn == NULL) {
			break;
		}
	}
	/* NOTREACHED */
	return NULL;
}
#endif