libdtrace/common/dt_pq.c

e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal/*
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * CDDL HEADER START
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal *
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * This file and its contents are supplied under the terms of the
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * Common Development and Distribution License ("CDDL"), version 1.0.
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * You may only use this file in accordance with the terms of version
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * 1.0 of the CDDL.
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal *
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * A full copy of the text of the CDDL should have accompanied this
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * source.  A copy of the CDDL is also available via the Internet at
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * http://www.illumos.org/license/CDDL.
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal *
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * CDDL HEADER END
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal */
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal/*
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * Copyright (c) 2012 by Delphix. All rights reserved.
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal */
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal#include <dtrace.h>
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal#include <dt_impl.h>
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal#include <dt_pq.h>
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal#include <assert.h>
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal/*
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * Create a new priority queue.
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal *
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * size is the maximum number of items that will be stored in the priority
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * queue at one time.
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal */
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhaldt_pq_t *
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhaldt_pq_init(dtrace_hdl_t *dtp, uint_t size, dt_pq_value_f value_cb, void *cb_arg)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal{
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    dt_pq_t *p;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    assert(size > 1);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    if ((p = dt_zalloc(dtp, sizeof (dt_pq_t))) == NULL)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        return (NULL);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_items = dt_zalloc(dtp, size * sizeof (p->dtpq_items[0]));
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    if (p->dtpq_items == NULL) {
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        dt_free(dtp, p);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        return (NULL);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    }
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_hdl = dtp;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_size = size;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_last = 1;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_value = value_cb;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_arg = cb_arg;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    return (p);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal}
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhalvoid
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhaldt_pq_fini(dt_pq_t *p)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal{
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    dtrace_hdl_t *dtp = p->dtpq_hdl;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    dt_free(dtp, p->dtpq_items);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    dt_free(dtp, p);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal}
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhalstatic uint64_t
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhaldt_pq_getvalue(dt_pq_t *p, uint_t index)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal{
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    void *item = p->dtpq_items[index];
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    return (p->dtpq_value(item, p->dtpq_arg));
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal}
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhalvoid
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhaldt_pq_insert(dt_pq_t *p, void *item)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal{
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    uint_t i;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    assert(p->dtpq_last < p->dtpq_size);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    i = p->dtpq_last++;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_items[i] = item;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    while (i > 1 && dt_pq_getvalue(p, i) < dt_pq_getvalue(p, i / 2)) {
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        void *tmp = p->dtpq_items[i];
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        p->dtpq_items[i] = p->dtpq_items[i / 2];
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        p->dtpq_items[i / 2] = tmp;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        i /= 2;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    }
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal}
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal/*
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * Return elements from the priority queue.  *cookie should be zero when first
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal * called.  Returns NULL when there are no more elements.
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal */
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhalvoid *
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhaldt_pq_walk(dt_pq_t *p, uint_t *cookie)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal{
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    (*cookie)++;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    if (*cookie >= p->dtpq_last)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        return (NULL);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    return (p->dtpq_items[*cookie]);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal}
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhalvoid *
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhaldt_pq_pop(dt_pq_t *p)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal{
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    uint_t i = 1;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    void *ret;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    assert(p->dtpq_last > 0);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    if (p->dtpq_last == 1)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        return (NULL);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    ret = p->dtpq_items[1];
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_last--;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_items[1] = p->dtpq_items[p->dtpq_last];
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    p->dtpq_items[p->dtpq_last] = NULL;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    for (;;) {
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        uint_t lc = i * 2;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        uint_t rc = i * 2 + 1;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        uint_t c;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        uint64_t v;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        void *tmp;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        if (lc >= p->dtpq_last)
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal            break;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        if (rc >= p->dtpq_last) {
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal            c = lc;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal            v = dt_pq_getvalue(p, lc);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        } else {
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal            uint64_t lv = dt_pq_getvalue(p, lc);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal            uint64_t rv = dt_pq_getvalue(p, rc);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal            if (lv < rv) {
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal                c = lc;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal                v = lv;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal            } else {
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal                c = rc;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal                v = rv;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal            }
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        }
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        if (v >= dt_pq_getvalue(p, i))
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal            break;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        tmp = p->dtpq_items[i];
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        p->dtpq_items[i] = p->dtpq_items[c];
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        p->dtpq_items[c] = tmp;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal        i = c;
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    }
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal    return (ret);
e5803b76927480e8f9b67b22201c484ccf4c2bcfAdam H. Leventhal}