/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 *
 * iexpr.c -- instanced expression cache module
 *
 * this module provides a cache of fully instantized expressions.
 */

#pragma ident	"%Z%%M%	%I%	%E% SMI"

#include <stdio.h>
#include <string.h>
#include "alloc.h"
#include "out.h"
#include "lut.h"
#include "tree.h"
#include "ptree.h"
#include "itree.h"
#include "ipath.h"
#include "iexpr.h"
#include "stats.h"
#include "eval.h"
#include "config.h"

#define	IEXPRSZ	1024	/* hash table size */

static struct stats *Niexpr;

/* the cache is a hash table of these structs */
static struct iexpr {
	struct node *np;
	struct iexpr *next;	/* next entry in hash bucket */
	int count;
} *Cache[IEXPRSZ];

/*
 * iexpr_init -- initialize the iexpr module
 */
void
iexpr_init(void)
{
	Niexpr = stats_new_counter("iexpr.niexpr", "iexpr cache entries", 1);
}

/*
 * iexpr_hash -- produce a simple hash from an instanced expression tree
 */
static unsigned
iexpr_hash(struct node *np)
{
	if (np == NULL)
		return (1);

	switch (np->t) {
	case T_GLOBID:
		return ((uintptr_t)np->u.globid.s);

	case T_ASSIGN:
	case T_CONDIF:
	case T_CONDELSE:
	case T_NE:
	case T_EQ:
	case T_LT:
	case T_LE:
	case T_GT:
	case T_GE:
	case T_BITAND:
	case T_BITOR:
	case T_BITXOR:
	case T_BITNOT:
	case T_LSHIFT:
	case T_RSHIFT:
	case T_LIST:
	case T_AND:
	case T_OR:
	case T_NOT:
	case T_ADD:
	case T_SUB:
	case T_MUL:
	case T_DIV:
	case T_MOD:
		return ((int)np->t *
		    (iexpr_hash(np->u.expr.left) +
		    iexpr_hash(np->u.expr.right)));

	case T_NAME:
		return ((uintptr_t)np->u.name.s);

	case T_EVENT:
		return (iexpr_hash(np->u.event.ename) +
		    iexpr_hash(np->u.event.epname));

	case T_FUNC:
		return ((uintptr_t)np->u.func.s +
		    iexpr_hash(np->u.func.arglist));

	case T_QUOTE:
		return ((uintptr_t)np->u.quote.s);

	case T_NUM:
	case T_TIMEVAL:
		return ((int)np->u.ull);

	default:
		outfl(O_DIE, np->file, np->line,
		    "iexpr_hash: unexpected node type: %s",
		    ptree_nodetype2str(np->t));
	}
	/*NOTREACHED*/
	return (1);
}

/*
 * iexpr_cmp -- compare two instanced expression trees
 */
static int
iexpr_cmp(struct node *np1, struct node *np2)
{
	int diff;

	if (np1 == np2)
		return (0);

	if (np1 == NULL)
		return (1);

	if (np2 == NULL)
		return (-1);

	if (np1->t != np2->t)
		return (np2->t - np1->t);

	/* types match, need to see additional info matches */
	switch (np1->t) {
	case T_GLOBID:
		return (np2->u.globid.s - np1->u.globid.s);

	case T_ASSIGN:
	case T_CONDIF:
	case T_CONDELSE:
	case T_NE:
	case T_EQ:
	case T_LT:
	case T_LE:
	case T_GT:
	case T_GE:
	case T_BITAND:
	case T_BITOR:
	case T_BITXOR:
	case T_BITNOT:
	case T_LSHIFT:
	case T_RSHIFT:
	case T_LIST:
	case T_AND:
	case T_OR:
	case T_NOT:
	case T_ADD:
	case T_SUB:
	case T_MUL:
	case T_DIV:
	case T_MOD:
		diff = iexpr_cmp(np1->u.expr.left, np2->u.expr.left);
		if (diff != 0)
			return (diff);
		return (iexpr_cmp(np1->u.expr.right, np2->u.expr.right));

	case T_NAME:
		if (np2->u.name.s != np1->u.name.s)
			return (np2->u.name.s - np1->u.name.s);
		diff = iexpr_cmp(np1->u.name.child, np2->u.name.child);
		if (diff != 0)
			return (diff);
		return (iexpr_cmp(np1->u.name.next, np2->u.name.next));

	case T_EVENT:
		diff = iexpr_cmp(np1->u.event.ename, np2->u.event.ename);
		if (diff != 0)
			return (diff);
		return (iexpr_cmp(np1->u.event.epname, np2->u.event.epname));

	case T_FUNC:
		if (np1->u.func.s != np2->u.func.s)
			return (np2->u.func.s - np1->u.func.s);
		return (iexpr_cmp(np1->u.func.arglist, np2->u.func.arglist));

	case T_QUOTE:
		return (np2->u.quote.s - np1->u.quote.s);

	case T_NUM:
	case T_TIMEVAL:
		if (np2->u.ull > np1->u.ull)
			return (1);
		else if (np1->u.ull > np2->u.ull)
			return (-1);
		else
			return (0);

	default:
		outfl(O_DIE, np1->file, np1->line,
		    "iexpr_cmp: unexpected node type: %s",
		    ptree_nodetype2str(np1->t));
	}
	/*NOTREACHED*/
	return (0);
}

/*
 * iexpr -- find instanced expr in cache, or add it if necessary
 */
struct node *
iexpr(struct node *np)
{
	unsigned idx = iexpr_hash(np) % IEXPRSZ;
	struct iexpr *bucketp = Cache[idx];
	struct iexpr *cp;

	/* search cache */
	for (cp = bucketp; cp != NULL; cp = cp->next)
		if (iexpr_cmp(cp->np, np) == 0) {
			/* found it */
			tree_free(np);
			cp->count++;
			return (cp->np);
		}

	/* allocate new cache entry */
	cp = MALLOC(sizeof (*cp));
	cp->np = np;
	cp->next = bucketp;
	cp->count = 1;
	Cache[idx] = cp;

	stats_counter_bump(Niexpr);

	return (np);
}

void
iexpr_free(struct node *np)
{
	unsigned idx = iexpr_hash(np) % IEXPRSZ;
	struct iexpr *cp;
	struct iexpr *prevcp = NULL;

	/* search cache */
	for (cp = Cache[idx]; cp != NULL; cp = cp->next) {
		if (iexpr_cmp(cp->np, np) == 0) {
			/* found it */
			cp->count--;
			if (cp->count == 0) {
				tree_free(cp->np);
				if (prevcp == NULL)
					Cache[idx] = cp->next;
				else
					prevcp->next = cp->next;
				FREE(cp);
			}
			return;
		}
		prevcp = cp;
	}
}

/*
 * iexpr_cached -- return true if np is in the iexpr cache
 */
int
iexpr_cached(struct node *np)
{
	struct iexpr *cp = Cache[iexpr_hash(np) % IEXPRSZ];

	/* search cache */
	for (; cp != NULL; cp = cp->next)
		if (iexpr_cmp(cp->np, np) == 0) {
			/* found it */
			return (1);
		}

	return (0);
}

/*
 * iexpr_fini -- free the iexpr cache
 */
void
iexpr_fini(void)
{
	int i;

	for (i = 0; i < IEXPRSZ; i++) {
		struct iexpr *cp;
		struct iexpr *ncp;

		for (cp = Cache[i]; cp != NULL; cp = ncp) {
			tree_free(cp->np);
			ncp = cp->next;
			FREE(cp);
		}
		Cache[i] = NULL;
	}
}