2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
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)
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
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
24 * $XConsortium: heap.cc /main/4 1996/07/18 14:29:27 drk $
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
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
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.
44 * HAL COMPUTER SYSTEMS INTERNATIONAL, LTD.
51 #include "dstr/heap.h"
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)
56 // the 0th element is never used.
61 buffer::put(z, sizeof(voidPtr));
68 voidPtr *heap_space = (voidPtr*)buffer::get_base();
72 for ( int i=1; i<=ct; i++ )
80 // the 0th element is excluded
81 return buffer::content_sz() / sizeof(voidPtr) - 1;
85 Boolean heap::insert(voidPtr elm)
87 if ( buf_sz() < (int)(content_sz() + 2*sizeof(voidPtr)) )
88 buffer::expand_chunk(2*buf_sz()) ;
98 Boolean heap::insert_heapify(voidPtr elm)
102 int j = count(); int i = j/2;
104 voidPtr *heap_space = (voidPtr*)buffer::get_base();
106 while ( i > 0 && (*f_cmp_func_ls)(heap_space[i], elm) == true ) {
107 heap_space[j] = heap_space[i];
115 void heap::adjust(int i, call_back_func_ptr_t call_back)
117 voidPtr *heap_space = (voidPtr*)buffer::get_base();
120 voidPtr item = heap_space[i];
122 while ( j <= count() ) {
124 (*f_cmp_func_ls)(heap_space[j], heap_space[j+1]) == true
128 if ( (*f_cmp_func_ls)(item, heap_space[j]) == false )
131 heap_space[j/2] = heap_space[j];
132 if ( call_back != 0 )
133 (*call_back)(j/2, heap_space[j/2]);
139 heap_space[j/2] = item;
141 if ( call_back != 0 )
142 (*call_back)(j/2, item);
145 voidPtr heap::max_elm()
147 voidPtr *heap_space = (voidPtr*)buffer::get_base();
150 return heap_space[1];
155 void heap::adjust_max_to(voidPtr new_max_item)
157 voidPtr *heap_space = (voidPtr*)buffer::get_base();
159 heap_space[1] = new_max_item;
166 //for ( int i = (int)floor(double(count())/2); i>=1; adjust(i--) );
168 for ( int i = count()/2; i>=1; adjust(i--) );
174 buffer::put((unsigned int)0);
178 void heap::delete_max(call_back_func_ptr_t call_back)
180 //MESSAGE(cerr, "delete max");
181 voidPtr *heap_space = (voidPtr*)buffer::get_base();
185 heap_space[1] = heap_space[ct];
186 set_content_sz(content_sz() - sizeof(voidPtr));
190 adjust(1, call_back);
193 void heap::_delete_max(int i, voidPtr* heap_array)
195 int target = ( heap_array[i+1] == 0 ) ? 2*i : 2*i+1;
197 voidPtr tmp = heap_array[i];
198 heap_array[i] = heap_array[target] ;
199 heap_array[target] = tmp;
201 if ( heap_array[target] != 0 )
202 _delete_max(target, heap_array);
209 return ( count() >= 1 ) ? 1 : 0;
212 void heap::next(int& ind)
214 ind = ( ind < count() ) ? (ind+1) : 0;
217 voidPtr heap::operator()(int ind)
219 if ( INRANGE(ind, 1, count()) ) {
220 voidPtr *heap_space = (voidPtr*)buffer::get_base();
221 return heap_space[ind];