sam-t2/sam/system/blaze/prioque.cc

// ========== Copyright Header Begin ==========================================
//
// OpenSPARC T2 Processor File: prioque.cc
// Copyright (c) 2006 Sun Microsystems, Inc.  All Rights Reserved.
// DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
//
// The above named program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License version 2 as published by the Free Software Foundation.
//
// The above named program is distributed in the hope that it will be
// useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public
// License along with this work; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
//
// ========== Copyright Header End ============================================
/*
 * Copyright (C) 2004 Sun Microsystems, Inc.
 * All rights reserved.
 */
#pragma ident "@(#)1.2  04/08/13        prioque.cc"


/*
 *
 */


extern long SYSTEM_get_time (int whence = 0);

#include "prioque.h"


/*static*/ int EventQue::debug = 0;
/*static*/ volatile int EventQue::event_id = 1;


#define PQ_PARENT(x) ((x)>>1)
#define PQ_LEFT(x) ((x)<<1)
#define PQ_RIGHT(x) (((x)<<1)+1)


EventQue::EventQue () {
  _size = 0;
  _limit = 63;
  _heap = (Event_t*) malloc ((_limit+1) * sizeof (Event_t));
  mutex_init (&_lock, 0, 0);    // other options include recursive locks, ...
}

void
EventQue::_grow () {
  _limit = 2 * _limit + 1;
  _heap = (Event_t*) realloc (_heap, (_limit+1) * sizeof (Event_t));
}

EventQue::~EventQue () {
  free (_heap);
  _heap = NULL;
  _size = _limit = 0;
  mutex_destroy (&_lock);
}


static int ulog2 (uint32_t x) {int i; for (i=-1;x>0;i++) x>>=1; return i;}
static void indent (int x) { for (int i = 0; i < x; i++) printf ("  "); }

void EventQue::internaldebug (int x) {
  if (x == 1) printf ("size=%d\n", _size);
  if (PQ_RIGHT(x) <= _size)
    internaldebug (PQ_RIGHT(x));
  // identify violations of the heap-invariant (top down sorted property)
  if (x>1 && _heap[x].pq_priority < _heap[PQ_PARENT(x)].pq_priority)
    printf ("*");
  indent (ulog2 (x)); printf ("%d: %lld\n", x, _heap[x].pq_priority);
  if (PQ_LEFT(x) <= _size)
    internaldebug (PQ_LEFT(x));
}


void
EventQue::_topdown_update (int index)      // aka. MIN-HEAPIFY in "Intro to Algs",
                 // but should have been called MIN-INCREASE-KEY for symmetry!
{
   // Top down restoration of the heap invariant starting at index,
   // assuming that only the node at index has been modified and that
   // only that node potentially fails the invariant. It might have to
   // percolate downwards if its priority is too high (too far in the future).

    uint64_t min  = _heap[index].pq_priority;
    int      imin = index;

  tailrecurse:

    /* see if a child has lower priority (earlier time) than index's */
    if (PQ_LEFT(index) <= _size && _heap[PQ_LEFT(index)].pq_priority < min) {
        min = _heap[PQ_LEFT(index)].pq_priority;
        imin = PQ_LEFT(index);
    }
    if (PQ_RIGHT(index) <= _size && _heap[PQ_RIGHT(index)].pq_priority < min) {
        min = _heap[PQ_RIGHT(index)].pq_priority;
        imin = PQ_RIGHT(index);
    }

    /* if so swap it up into index's place, then descend... */
    if (imin != index) {
        Event_t temp = _heap[index];    // copy semantics, ugh...
        _heap[index] = _heap[imin];     // ugh...
        _heap[imin] = temp;             // ugh...

        // fix parameters and loop, instead of recursing
        index = imin;
        min = _heap[index].pq_priority; // loop invar, but comp wont figure it
        goto tailrecurse;
    } else
        return;
}


void
EventQue::_bottomup_update (int index) // aka. MIN-DECREASE-KEY in "Intro to Algs"
{
   // Bottom up restoration of the heap invariant starting at index,
   // assuming that only the node at index has been modified and that
   // only that node potentially fails the invariant. If might have to
   // percolate updwards if its priority is too low (too near in the future).

    uint64_t min  = _heap[index].pq_priority;
    int      imin = index;

tailrecurse:

    /* see if index has a lower priority (earlier time) than its parent */
    if (index > 1 && min < _heap[PQ_PARENT(index)].pq_priority) {
        imin = PQ_PARENT(index);
        /* oops, dont do this!: min = _heap[imin].pq_priority; */
    } else
        return;

    /* if so swap it up into its parent's place, then ascend... */
    if (imin != index) {
        Event_t temp = _heap[index];    // copy semantics, ugh...
        _heap[index] = _heap[imin];     // ugh...
        _heap[imin] = temp;             // ugh...

        // fix parameters and loop, instead of recursing
        index = imin;
        goto tailrecurse;
    }
}


void
EventQue::_insert (Event_t * object)
{
    if (_size == _limit)
        _grow();
    _heap[_size+1] = *object;           // copy semantics...
    _bottomup_update (_size+1);
    _size = _size+1;
}


void
EventQue::_delete (Event_t * object)
{
    if (object != NULL) *object = _heap[1];     // copy semantics...
    if (_size > 1) {
        _heap[1] = _heap[_size];
        _size = _size-1;
        _topdown_update (1);
    } else
        _size = 0;
}


#if 0 /* SELFTEST */

/* Stateless random number generator, 31-bit integer result. */
int rand31 (int prev)
{
  int hi, lo, next;

/* See "Random Number Generators: Good Ones Are Hard To Find", */
/*     Park & Miller, CACM 31#10 October 1988 pages 1192-1201. */
#define _A_MULTIPLIER  16807
#define _M_MODULUS     2147483647  /* (2**31)-1 */
#define _Q_QUOTIENT    127773      /* 2147483647 / 16807 */
#define _R_REMAINDER   2836        /* 2147483647 % 16807 */

    hi = prev / _Q_QUOTIENT;
    lo = prev % _Q_QUOTIENT;
    next = _A_MULTIPLIER * lo - _R_REMAINDER * hi;
    if (next > 0) {
        return next;
    } else {
        return next + _M_MODULUS;
    }
}


int main (int argc, char * argv[])
{
    int i, RN = 0x12345678;
    uint64_t dummy_data[8];
    EventQue pq;
    EventQue::Event_t temp;

    if (argc == 2 && strcmp (argv[1], "-rand") == 0) {
      for (i=0; i<100; i++) {
        RN = rand31(RN);
        printf ("%4d\n", RN%1000);
      }
      exit (0);
    } else if (argc == 2) {
      printf ("usage:\n");
      printf ("\ta.out > prioque.out;\n");
      printf ("\ta.out -rand | sort > sort.out;\n");
      printf ("\tdiff prioque.out sort.out;   # should be equal...\n");
    }


    for (i=0; i<100; i++) {                             // insert 100 items
        RN = rand31(RN);
        pq.insert_mondo ((uint64_t)RN%1000, (uint64_t)RN%1000, &dummy_data[0]);
        /*printf ("--- after insert ---\n");pq.debug ();*/
    }
    if (pq.size () != 100)
        printf ("1) size=%d, expecting 10\n", pq.size ());

#if 0
    for (i=0; i<900; i++) {                             // insert and delete 900
        pq.get_top (&temp);
        if (temp.pq_kind == EventQue::PQ_MONDO) {
            printf ("%4d\n", (int)temp.pq_ctrl);
        } else
            printf ("2.a) kind=%d, expecting %d\n", temp.pq_kind, EventQue::PQ_MONDO);

        RN = rand31(RN);
        pq.insert_mondo ((uint64_t)RN%1000, (uint64_t)RN%1000, &dummy_data[0]);
    }
    if (pq.size () != 100)
        printf ("2) size=%d, expecting 10\n", pq.size ());
#endif


    for (i=0; i<100; i++) {                             // delete 100 items
        pq.get_top (&temp);
        if (temp.pq_kind == EventQue::PQ_MONDO) {
            printf ("%4d\n", (int)temp.pq_ctrl);
        } else
            printf ("3.a) kind=%d, expecting %d\n", temp.pq_kind, EventQue::PQ_MONDO);
        /*printf ("--- after delete ---\n");pq.debug ();*/
    }
    if (!pq.empty () || pq.size () != 0)
        printf ("3) size=%d, expecting 0\n", pq.size ());

    return 0;
}

#endif