_timer_heapify.c

Go to the documentation of this file.

/*
** Copyright (C) 2005 by Kevin L. Mitchell <klmitch@mit.edu>
**
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
**
** This 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 program; if not, write to the Free Software
** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
**
** @(#)$Id: _timer_heapify.c,v 1.7 2005/12/18 00:15:10 klmitch Exp $
*/
#include "event_int.h"

RCSTAG("@(#)$Id: _timer_heapify.c,v 1.7 2005/12/18 00:15:10 klmitch Exp $");

static ev_err_t
node_swap(ev_ctx_t *ctx, ev_tim_t *tim)
{
  ev_tim_t *parent = tim->ti_node.tn_parent;
  _ev_timnode_t swap;

  ev_trace();

  /* First, let's swap the node pointer values */
  swap = parent->ti_node;
  parent->ti_node = tim->ti_node;
  tim->ti_node = swap;

  /* one or the other of these must be true... */
  ev_assert(tim->ti_node.tn_left == tim || tim->ti_node.tn_right == tim);

  /* Fix up the timer for its new position... */
  if (tim->ti_node.tn_left == tim)
    tim->ti_node.tn_left = parent;
  else
    tim->ti_node.tn_right = parent;

  /* make sure parent was linked... */
  ev_assert((!tim->ti_node.tn_parent && ctx->ec_timtree.tt_root == parent) ||
            tim->ti_node.tn_parent->ti_node.tn_left == parent ||
            tim->ti_node.tn_parent->ti_node.tn_right == parent);

  /* fix up timer's parent for the new position */
  if (!tim->ti_node.tn_parent) /* no parent, must be the root of the tree */
    ctx->ec_timtree.tt_root = tim;
  else if (tim->ti_node.tn_parent->ti_node.tn_left == parent)
    tim->ti_node.tn_parent->ti_node.tn_left = tim;
  else
    tim->ti_node.tn_parent->ti_node.tn_right = tim;

  /* Now fix up the linked list... */
  if (tim->ti_node.tn_next == tim)
    tim->ti_node.tn_next = parent;
  if (tim->ti_node.tn_prev == tim)
    tim->ti_node.tn_prev = parent;
  if (parent->ti_node.tn_next == parent)
    parent->ti_node.tn_next = tim;
  if (parent->ti_node.tn_prev == parent)
    parent->ti_node.tn_prev = tim;

  /* make sure everyone else is pointing at the right place... */
  tt_node_fix(parent);
  tt_node_fix(tim);

  /* finally, update the insertion cursor */
  if (ctx->ec_timtree.tt_insert == parent)
    ctx->ec_timtree.tt_insert = tim;
  else if (ctx->ec_timtree.tt_insert == tim)
    ctx->ec_timtree.tt_insert = parent;

  ev_return(0);
}

ev_err_t
_timer_heapify_up(ev_ctx_t *ctx, ev_tim_t *tim)
{
  ev_err_t err;

  ev_trace();

  /* bubble earlier timeouts upwards */
  while (tim->ti_node.tn_parent &&
         tv_comp(&tim->ti_expire, &tim->ti_node.tn_parent->ti_expire) < 0)
    if ((err = node_swap(ctx, tim)))
      ev_return(err); /* handle any assertion failures that cropped up */

  ev_return(0);
}

ev_err_t
_timer_heapify_down(ev_ctx_t *ctx, ev_tim_t *tim)
{
  ev_err_t err = 0;
  int left, right;

  ev_trace();

  /* bubble later timeouts downwards */
  while (1) { /* first, calculate the delta with the children */
    left  = (!tim->ti_node.tn_left  ? 0 :
             tv_comp(&tim->ti_expire, &tim->ti_node.tn_left->ti_expire));
    right = (!tim->ti_node.tn_right ? 0 :
             tv_comp(&tim->ti_expire, &tim->ti_node.tn_right->ti_expire));

    if (left <= 0 && right <= 0) /* in order?  stop heapifying... */
      break;

    if (left > right) /* check which node to swap with... */
      err = node_swap(ctx, tim->ti_node.tn_left);
    else
      err = node_swap(ctx, tim->ti_node.tn_right);

    if (err) /* handle any assertion failures that cropped up */
      ev_return(err);
  }

  ev_return(0);
}

---