cde/programs/dtinfo/DtMmdb/dstr/heap.C

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*
  24  * $XConsortium: heap.cc /main/4 1996/07/18 14:29:27 drk $
  25  *
  26  * Copyright (c) 1993 HAL Computer Systems International, Ltd.
  27  * All rights reserved.  Unpublished -- rights reserved under
  28  * the Copyright Laws of the United States.  USE OF A COPYRIGHT
  29  * NOTICE IS PRECAUTIONARY ONLY AND DOES NOT IMPLY PUBLICATION
  30  * OR DISCLOSURE.
  31  *
  32  * THIS SOFTWARE CONTAINS CONFIDENTIAL INFORMATION AND TRADE
  33  * SECRETS OF HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.  USE,
  34  * DISCLOSURE, OR REPRODUCTION IS PROHIBITED WITHOUT THE
  35  * PRIOR EXPRESS WRITTEN PERMISSION OF HAL COMPUTER SYSTEMS
  36  * INTERNATIONAL, LTD.
  37  *
  38  *                         RESTRICTED RIGHTS LEGEND
  39  * Use, duplication, or disclosure by the Government is subject
  40  * to the restrictions as set forth in subparagraph (c)(l)(ii)
  41  * of the Rights in Technical Data and Computer Software clause
  42  * at DFARS 252.227-7013.
  43  *
  44  *          HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.
  45  *                  1315 Dell Avenue
  46  *                  Campbell, CA  95008
  47  *
  48  */
  49
  50
  51 #include "dstr/heap.h"
  52
  53 heap::heap(cmp_func_ptr_t eq,    cmp_func_ptr_t ls, int max) :
  54 buffer(MAX(1, max)*sizeof(voidPtr)), f_cmp_func_eq(eq), f_cmp_func_ls(ls)
  55 {
  56 // the 0th element is never used.
  57    char z[16];
  58
  59    memset(z, 0, 16);
  60
  61    buffer::put(z, sizeof(voidPtr));
  62    v_updated = false;
  63 }
  64
  65 heap::~heap()
  66 {
  67 /*
  68    voidPtr *heap_space = (voidPtr*)buffer::get_base();
  69
  70    int ct = count();
  71
  72    for ( int i=1; i<=ct; i++ )
  73       delete heap_space[i];
  74 */
  75 }
  76
  77 /*
  78 int heap::count()
  79 {
  80 // the 0th element is excluded
  81    return buffer::content_sz() / sizeof(voidPtr) - 1;
  82 }
  83 */
  84
  85 Boolean heap::insert(voidPtr elm)
  86 {
  87    if ( buf_sz() < (int)(content_sz() + 2*sizeof(voidPtr)) )
  88       buffer::expand_chunk(2*buf_sz()) ;
  89
  90    long x = long(elm);
  91    buffer::put(x);
  92
  93    v_updated = true;
  94
  95    return true;
  96 }
  97
  98 Boolean heap::insert_heapify(voidPtr elm)
  99 {
 100    insert(elm);
 101
 102    int j = count(); int i = j/2;
 103
 104    voidPtr *heap_space = (voidPtr*)buffer::get_base();
 105
 106    while ( i > 0 && (*f_cmp_func_ls)(heap_space[i], elm) == true ) {
 107       heap_space[j] = heap_space[i];
 108       j = i; i /= 2;
 109    }
 110    heap_space[j] = elm;
 111
 112    return true;
 113 }
 114
 115 void heap::adjust(int i, call_back_func_ptr_t call_back)
 116 {
 117    voidPtr *heap_space = (voidPtr*)buffer::get_base();
 118
 119    int j = 2*i;
 120    voidPtr item = heap_space[i];
 121
 122    while ( j <= count() ) {
 123        if ( j < count() &&
 124             (*f_cmp_func_ls)(heap_space[j], heap_space[j+1]) == true
 125           ) {
 126           j++;
 127        }
 128        if ( (*f_cmp_func_ls)(item, heap_space[j]) == false )
 129           break;
 130        else {
 131           heap_space[j/2] = heap_space[j];
 132           if ( call_back != 0 )
 133              (*call_back)(j/2, heap_space[j/2]);
 134        }
 135
 136        j *= 2;
 137    }
 138
 139    heap_space[j/2] = item;
 140
 141    if ( call_back != 0 )
 142       (*call_back)(j/2, item);
 143 }
 144
 145 voidPtr heap::max_elm()
 146 {
 147    voidPtr *heap_space = (voidPtr*)buffer::get_base();
 148
 149    if ( count() > 0 )
 150       return heap_space[1];
 151    else
 152       return 0;
 153 }
 154
 155 void heap::adjust_max_to(voidPtr new_max_item)
 156 {
 157    voidPtr *heap_space = (voidPtr*)buffer::get_base();
 158
 159    heap_space[1] = new_max_item;
 160    adjust(1);
 161    v_updated = true;
 162 }
 163
 164 void heap::heapify()
 165 {
 166    //for ( int i = (int)floor(double(count())/2); i>=1; adjust(i--) );
 167
 168    for ( int i = count()/2; i>=1; adjust(i--) );
 169 }
 170
 171 void heap::remove()
 172 {
 173    set_content_sz(0);
 174    buffer::put((unsigned int)0);
 175    v_updated = false;
 176 }
 177
 178 void heap::delete_max(call_back_func_ptr_t call_back)
 179 {
 180 //MESSAGE(cerr, "delete max");
 181    voidPtr *heap_space = (voidPtr*)buffer::get_base();
 182
 183    int ct = count();
 184
 185    heap_space[1] = heap_space[ct];
 186    set_content_sz(content_sz() - sizeof(voidPtr));
 187
 188    ct--;
 189
 190    adjust(1, call_back);
 191 }
 192
 193 void heap::_delete_max(int i, voidPtr* heap_array)
 194 {
 195    int target = ( heap_array[i+1] == 0 ) ? 2*i : 2*i+1;
 196
 197    voidPtr tmp = heap_array[i];
 198    heap_array[i] = heap_array[target] ;
 199    heap_array[target] = tmp;
 200
 201    if ( heap_array[target] != 0 )
 202       _delete_max(target, heap_array);
 203
 204    return;
 205 }
 206
 207 int heap::first()
 208 {
 209    return ( count() >= 1 ) ? 1 : 0;
 210 }
 211
 212 void heap::next(int& ind)
 213 {
 214    ind = ( ind < count() ) ? (ind+1) : 0;
 215 }
 216
 217 voidPtr heap::operator()(int ind)
 218 {
 219    if ( INRANGE(ind, 1, count()) ) {
 220       voidPtr *heap_space = (voidPtr*)buffer::get_base();
 221       return heap_space[ind];
 222    } else
 223       return 0;
 224 }
 225