/*
 * 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.
 */

#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;
        }
}