common/eversholt/iexpr.c

	iexpr.c revision 80ab886d233f514d54c2a6bdeb9fdfd951bd6881
/*
 * 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 2006 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 */
} *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 ((int)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 ((int)np->u.name.s);

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

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

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

    case T_NUM:
        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:
        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);
            return (cp->np);
        }

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

    stats_counter_bump(Niexpr);

    return (np);
}

/*
 * 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;
    }
}