xorp

heap.hh

00001 // -*- c-basic-offset: 4; tab-width: 8; indent-tabs-mode: t -*-
00002 // vim:set sts=4 ts=8:
00003 
00004 // Copyright (c) 2001-2011 XORP, Inc and Others
00005 //
00006 // This program is free software; you can redistribute it and/or modify
00007 // it under the terms of the GNU Lesser General Public License, Version
00008 // 2.1, June 1999 as published by the Free Software Foundation.
00009 // Redistribution and/or modification of this program under the terms of
00010 // any other version of the GNU Lesser General Public License is not
00011 // permitted.
00012 // 
00013 // This program is distributed in the hope that it will be useful, but
00014 // WITHOUT ANY WARRANTY; without even the implied warranty of
00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. For more details,
00016 // see the GNU Lesser General Public License, Version 2.1, a copy of
00017 // which can be found in the XORP LICENSE.lgpl file.
00018 // 
00019 // XORP, Inc, 2953 Bunker Hill Lane, Suite 204, Santa Clara, CA 95054, USA;
00020 // http://xorp.net
00021 
00022 // Portions of this code originally derived from:
00023 //  FreeBSD dummynet code, (C) 2001 Luigi Rizzo.
00024 
00025 
00026 #ifndef __LIBXORP_HEAP_HH__
00027 #define __LIBXORP_HEAP_HH__
00028 
00029 
00030 #include <stdio.h>
00031 #ifdef HAVE_STDLIB_H
00032 #include <stdlib.h>
00033 #endif
00034 #include <assert.h>
00035 
00036 #ifdef HAVE_SYS_TIME_H
00037 #include <sys/time.h>
00038 #endif
00039 
00040 #include "timeval.hh"
00041 #include "bug_catcher.hh"
00042 
00053 const int NOT_IN_HEAP = -1 ;
00054 
00059 class HeapBase {
00060  public:
00061     HeapBase() : _pos_in_heap(NOT_IN_HEAP) {}
00062     virtual ~HeapBase() {}
00063 
00064     int     _pos_in_heap;   // position of this object in the heap
00065 };
00066 
00067 class Heap /*: public BugCatcher*/ {
00068     friend class TimerList;
00069 protected:
00070 typedef TimeVal Heap_Key ;
00071     struct heap_entry {
00072     Heap_Key key;   /* sorting key. Topmost element is smallest one */
00073     HeapBase *object;      /* object pointer */
00074     } ;
00075 public:
00080     Heap();
00081     
00092     explicit Heap(bool); // heap supporting removal from the middle
00093     
00097     virtual ~Heap();
00098 
00105     void push(Heap_Key k, HeapBase *p) { push(k, p, 0); }
00106 
00114     void push(int i) { push( Heap_Key(0, 0) /* anything */, NULL, i); }
00115 
00123     void move(Heap_Key new_key, HeapBase *object);
00124 
00132     struct heap_entry *top() const {
00133     return  (_p == 0 || _elements == 0) ? 0 :  &(_p[0]) ;
00134     }
00135 
00141     size_t size() const { return _elements; }
00142 
00146     void pop() { pop_obj(0); }
00147 
00156     void pop_obj(HeapBase *p);
00157 
00161     void heapify();
00162 
00163 #ifdef _TEST_HEAP_CODE
00164     void print();
00165     void print_all(int);
00166 #endif
00167     
00168 private:
00169     void push(Heap_Key key, HeapBase *p, int son);
00170     int resize(int new_size);
00171     void verify();
00172     
00173     int _size;
00174     int _elements ;
00175     bool _intrude ; // True if the object holds the heap position
00176     struct heap_entry *_p ;   // really an array of "size" entries
00177 };
00178 
00179 #endif // __LIBXORP_HEAP_HH__
 All Classes Namespaces Functions Variables Typedefs Enumerations