Initial commit of OpenSPARC T2 architecture model.

[OpenSPARC-T2-SAM] / hypervisor / src / support / aschk / ashash.c

/*
* ========== Copyright Header Begin ==========================================
*
* Hypervisor Software File: ashash.c
* 
* Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
* 
*  - Do no alter or remove copyright notices
* 
*  - Redistribution and use of this software in source and binary forms, with 
*    or without modification, are permitted provided that the following 
*    conditions are met: 
* 
*  - Redistribution of source code must retain the above copyright notice, 
*    this list of conditions and the following disclaimer.
* 
*  - Redistribution 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. 
* 
*    Neither the name of Sun Microsystems, Inc. or the names of contributors 
* may be used to endorse or promote products derived from this software 
* without specific prior written permission. 
* 
*     This software is provided "AS IS," without a warranty of any kind. 
* ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, 
* INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A 
* PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN 
* MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR 
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR 
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN 
* OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR 
* FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE 
* DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, 
* ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF 
* SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
* 
* You acknowledge that this software is not designed, licensed or
* intended for use in the design, construction, operation or maintenance of
* any nuclear facility. 
* 
* ========== Copyright Header End ============================================
*/
/*
 * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#pragma ident	"@(#)ashash.c	1.2	07/06/07 SMI"

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <string.h>

#include "basics.h"
#include "internal.h"
#include "parser.h"


static symbol_t *sym_listp, *sym_list_endp;

typedef struct {
	symbol_t	*firstp;
	int		len;
} hash_bucket_t;

#define	INVALID_HASH_KEY	((uint64_t)-1)

#define	HASH_SIZE_BITS	10
#define	HASH_SIZE	(1<<HASH_SIZE_BITS)
#define	HASH_SIZE_MASK	(HASH_SIZE -1)
static hash_bucket_t	*hashp;

static symbol_t *hash_find_key(int idx, uint64_t key, char *namep);
static void hash_key(char *nampep, uint64_t *keyp, int *idxp);



void
init_symbols(void)
{
	sym_listp = NULL;
	sym_list_endp = NULL;

	hashp = calloc(HASH_SIZE, sizeof (hash_bucket_t));
	if (hashp == NULL) {
		fprintf(stderr, "Failed allocating hash space : %s\n",
		    strerror(errno));
		exit(1);
	}
}


symbol_t *
new_sym(sym_flags_t flags, char *namep, int offset, int size)
{
	symbol_t *symp;
	char *namecopyp;

	symp = malloc(sizeof (symbol_t));
	if (symp == NULL) {
		fprintf(stderr, "Failed allocating symbol space : %s\n",
		    strerror(errno));
		exit(1);
	}
	namecopyp = strdup(namep);
	if (namecopyp == NULL) {
		fprintf(stderr, "Failed allocating symbol space : %s\n",
		    strerror(errno));
		exit(1);
	}

	symp->flags = flags;
	symp->namep = namecopyp;
	symp->size = size;
	symp->offset = offset;

	symp->name_key = INVALID_HASH_KEY;
	symp->hash_nextp = NULL;
	symp->nextp = sym_list_endp;
	if (sym_list_endp == NULL)
		sym_listp = symp;
	sym_list_endp = symp;

	return (symp);
}


/*
 * Returns false if failed to insert because
 * of existing duplicate
 */
bool_t
sym_hash_insert(symbol_t *symp)
{
	uint64_t key;
	int idx;
	symbol_t *otherp;

	hash_key(symp->namep, &key, &idx);

	otherp = hash_find_key(idx, key, symp->namep);
	if (otherp != NULL)
		return (false);

	/*
	 * Insert new entry
	 */
	symp->name_key = key;
	symp->hash_nextp = hashp[idx].firstp;
	hashp[idx].firstp = symp;
	hashp[idx].len ++;

	return (true);
}


symbol_t *
hash_find(char *namep)
{
	uint64_t key;
	int idx;

	hash_key(namep, &key, &idx);

	return (hash_find_key(idx, key, namep));
}


static symbol_t *
hash_find_key(int idx, uint64_t key, char *namep)
{
	symbol_t *p;

	for (p = hashp[idx].firstp; p != NULL; p = p->hash_nextp) {
		if (p->name_key == key && strcmp(p->namep, namep) == 0)
			return (p);
	}
	return (NULL);
}


/*
 * can use any old hash ... this is not a particualrly good one,
 * but OK for now.
 */

#define	KEY_SHIFT	5

static void
hash_key(char *namep, uint64_t *keyp, int *idxp)
{
	char *sp;
	uint64_t key;
	uint64_t ch;

	key = 0;
	for (sp = namep; (ch = *sp) != '\0'; sp++) {
		key = (key >> (64 - KEY_SHIFT)) ^ (key << KEY_SHIFT) ^ ch;
	}

	*keyp = key;
	*idxp = key & HASH_SIZE_MASK;
}