zilutils/zilasm/symtable.c

/*
 * symtable.c -- part of ZilUtils/ZilAsm
 *
 * Copyright (C) 2016 Jason Self <j@jxself.org>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>
 *
 * SPDX-License-Identifier: AGPL-3.0-or-later
 */

#include <string.h>
#include <stdlib.h>
#include <assert.h>

#include "symtable.h"

#define FIELD_SIZE(Typ,Field)  (sizeof(((Typ*)0)->Field))

Symtable* symtable_create(unsigned elems_count, unsigned name_size, unsigned elem_size)
{
	size_t n = elems_count * (name_size + elem_size) + sizeof(Symtable) - FIELD_SIZE(Symtable, contents);
	Symtable *p = malloc(n);
	assert(p);
	bzero(p, n);
	p->elems_count = elems_count;
	p->name_size   = name_size;
	p->elem_size   = elem_size;
	return p;
}

void symtable_destroy(Symtable *p)
{
	assert(p);
	free(p);
}

static unsigned name2pos(const Symtable *p, const char *name, unsigned namelen)
{
	assert(p);
	unsigned key = 0;
	while(namelen--)
		key = ((key << 1) | (*name++));
	return key % p->elems_count;
}

static char *getsym(const Symtable *p, unsigned pos)
{
	//assert(p);   //already checked by caller
	//assert(pos < p->elems_count);
	return ((char*)p) + sizeof(Symtable) - FIELD_SIZE(Symtable, contents) + (pos * p->elem_size);
}

void* symtable_lookup2(const Symtable *p, const char *name, unsigned namelen)
{
	assert(p);
	assert(name);
	assert(namelen > 0);
	assert(namelen < p->name_size);

	unsigned start = name2pos(p, name, namelen);
	unsigned pos = start;

	do {
		char *s = getsym(p, pos);
		if (!*s)
			return NULL;
		if (!memcmp(name, s, namelen))
			return s + p->name_size;
		if (++pos >= p->elems_count)
			pos = 0;
	} while(pos != start);

	return NULL;
}

void* symtable_lookup(const Symtable *p, const char *name)
{
	assert(name);
	return symtable_lookup2(p, name, strlen(name));
}

void* symtable_add(Symtable *p, const char *name, void *contents)
{
	assert(name);
	return symtable_add2(p, name, strlen(name), contents);
}

void* symtable_add2(Symtable *p, const char *name, unsigned namelen, void *contents)
{
	assert(p);
	assert(name);
	assert(namelen > 0 && namelen < p->name_size);
	assert(contents);

	unsigned start = name2pos(p, name, namelen);
	unsigned pos = start;

	do {
		char *s = getsym(p, pos);
		if (!*s) {
			memcpy(s, name, namelen + 1);
			s[namelen] = '\0';
			memcpy(s + p->name_size, contents, p->elem_size);
			return s + p->name_size;
		}
		if (!memcmp(name, s, namelen) && s[namelen] == '\0') {
			/* TODO!! report error */
			return NULL;  /* ..already added */
		}
		if (++pos >= p->elems_count)
			pos = 0;
	} while(pos != start);

	/* TODO!! report overflow */
	return NULL;
	/* TODO!!! */
}

static int sortfunc(const void *a, const void *b)
{
	const char *s1 = a;
	const char *s2 = b;
	if (!*s1 && !*s2) return  0;
	if (!*s1)         return  1;
	if (!*s2)         return -1;
	return strcmp(s1, s2);
}

void symtable_sort(Symtable *p)
{
	assert(p);
	qsort(getsym(p, 0), p->elems_count, p->elem_size + p->name_size, sortfunc);
}

/* END */