Logo Search packages:      
Sourcecode: wackamole version File versions  Download package

abt.c

/*
 * The Wackamole Program.
 *     
 * The contents of this file are subject to the CNDS Open Source
 * License, Version 1.0 (the ``License''); you may not use
 * this file except in compliance with the License.  You may obtain a
 * copy of the License at:
 *
 * http://www.backhand.org/wackamole/license/
 *
 * or in the file ``license.txt'' found in this distribution.
 *
 * Software distributed under the License is distributed on an AS IS basis, 
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License 
 * for the specific language governing rights and limitations under the 
 * License.
 *
 * The Creators of Wackamole are:
 *  Yair Amir, Ryan Caudy, Aashima Munjal and Theo Schlossnagle.
 *
 *  Copyright (C) 2000-2001 The Johns Hopkins University
 *  All Rights Reserved.
 *
 *  This product uses the Spread toolkit, developed by Spread Concepts LLC.
 *  For more information about Spread see http://www.spread.org
 *
 *  Wackamole development was partially funded by a grant from the Defense
 *  Advanced Research Projects Agency (DARPA) to Johns Hopkins University. The 
 *  U.S. Government retains certain rights in this software.
 *
 */
#include "config.h"
#include "abt.h"

abt *new_abt() {
  abt *nh;
  nh = malloc(sizeof(abt));
  nh->size=0;
  nh->space=128;
  nh->data=malloc(sizeof(int)*nh->space);
  return nh;
}

void add_abt(abt *h, int toadd) {
  int p, c, l, move, tmp;
  if(chk_abt(h, toadd)) return;
  if(h->size == h->space) {
    h->space *= 2;
    h->data = realloc(h->data, h->space);
  }
  c = h->size++;
  h->data[c] = toadd;
  /* up phase */
  move = 1;
  while(c>0) {
    p = (c-1)/2;
    if(c == (2*p)+1) { /* lefty, swap if we aren't less */
      if(h->data[c] < h->data[p]) break;
    } else { /* righty */
      if(h->data[c] > h->data[p]) break;
    }
    tmp = h->data[p];
    h->data[p] = h->data[c];
    h->data[c] = tmp;
    c = p;
  }
  /* down phase */
  while((2*c+1) < h->size) { /* can potentially have a child */
    l = 2*c+1; /* default is to swap withour left child */
    if(h->data[c] > h->data[l]) {
      if(h->data[c]<h->data[l+1]) break;
      else l+=1; /* swap with right */
    }
    tmp = h->data[l];
    h->data[l] = h->data[c];
    h->data[c] = tmp;
    c = l;
  }
  /* Done */
  return;
}

int chk_abt(abt *h, int tofind) {
  int p=0;
  while(p<h->size) {
    if(h->data[p] == tofind) return 1;
    if(h->data[p] > tofind) p = 2*p+1;
    else p = 2*p+2;
  }
  return 0;
}

Generated by  Doxygen 1.6.0   Back to index