Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	src/air/heap.c	Lines:	0	161	0.0 %
Date:	2017-05-26	Branches:	0	138	0.0 %


/*
  Teem: Tools to process and visualize scientific data and images             .
  Copyright (C) 2010 Thomas Schultz

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public License
  (LGPL) as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.
  The terms of redistributing and/or modifying this software also
  include exceptions to the LGPL that facilitate static linking.

  This library 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
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public License
  along with this library; if not, write to Free Software Foundation, Inc.,
  51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
*/

#include "air.h"
#include <string.h>

/* internal helper routines */
/* restore heap property by pulling a single node up the tree */
static void upheap(airHeap *h, unsigned int i) {
  while (i) {
    unsigned int parent = (i-1)/2;
    if (h->key[h->idx[parent]] > h->key[h->idx[i]]) { /* swap */
      unsigned int tmp = h->idx[parent];
      h->idx[parent] = h->idx[i];
      h->idx[i] = tmp;
      h->invidx[h->idx[i]] = i;
      h->invidx[h->idx[parent]] = parent;
      i = parent;
    } else
      i = 0; /* break loop */
  }
}

/* restore heap property by pushing a single node down the tree */
static void downheap (airHeap *h, unsigned int i) {
  unsigned int len = h->key_a->len;
  while (1) {
    unsigned int left = 2*i+1;
    unsigned int right = 2*i+2;
    unsigned int minidx = 0;
    double minval = 0;
    if (left>=len)
      return;
    if ((right>=len) ||
        (h->key[h->idx[left]] < h->key[h->idx[right]])) {
      minidx = left;
      minval = h->key[h->idx[left]];
    } else {
      minidx = right;
      minval = h->key[h->idx[right]];
    }
    if (h->key[h->idx[i]] > minval) { /* swap */
      unsigned int tmp = h->idx[i];
      h->idx[i] = h->idx[minidx];
      h->idx[minidx] = tmp;
      h->invidx[h->idx[i]] = i;
      h->invidx[h->idx[minidx]] = minidx;
      i = minidx;
    } else
      return;
  }
}

/* Restore heap property "from scratch" (without any prior assumptions).
 * Works in a bottom-up manner, which is more efficient than top-down */
static void heapify (airHeap *h) {
  unsigned int len = h->key_a->len;
  int maxi = len/2-1, i; /* above maxi, downheap has no effect */
  for (i=maxi; i>=0; i--) {
    downheap(h, i);
  }
}

/* Tries to increase or decrease the length of h. returns 0 upon success. */
static int heapLenIncr (airHeap *h, int delta) {
  unsigned int oldlen=h->key_a->len;
  unsigned int newlen=oldlen+delta;
  if (delta==0)
    return 0;
  airArrayLenIncr(h->key_a, delta);
  if (h->data_a!=NULL) airArrayLenIncr(h->data_a, delta);
  airArrayLenIncr(h->idx_a, delta);
  airArrayLenIncr(h->invidx_a, delta);
  if (h->key_a->len<newlen || (h->data_a!=NULL && h->data_a->len<newlen) ||
      h->idx_a->len<newlen || h->invidx_a->len<newlen) {
    /* Error. Try to undo changes and return error code. */
    if (h->key_a->len>oldlen)    airArrayLenSet(h->key_a, oldlen);
    if (h->data_a!=NULL && h->data_a->len>oldlen)
      airArrayLenSet(h->data_a, oldlen);
    if (h->idx_a->len>oldlen)    airArrayLenSet(h->idx_a, oldlen);
    if (h->invidx_a->len>oldlen) airArrayLenSet(h->invidx_a, oldlen);
    return 1;
  }
  return 0;
}

/* Creates a new heap, returning NULL upon error.  If additional data
 * is to be stored with each node, dataUnit needs to be set to the
 * number of data bytes needed per element.  incr is used for dynamic
 * memory allocation (an additional number of incr elements are
 * allocated each time the heap grows past its current capacity).
 */
airHeap *airHeapNew(size_t dataUnit, unsigned int incr) {
  airHeap *h;
  airPtrPtrUnion appu;
  h = AIR_CALLOC(1, airHeap);
  if (h==NULL) {
    return NULL;
  }

  appu.d = &h->key;
  h->key_a = airArrayNew(appu.v, NULL, sizeof(double), incr);
  if (dataUnit>0) { /* data is optional */
    h->data_a = airArrayNew(&h->data, NULL, dataUnit, incr);
  }
  appu.ui = &h->idx;
  h->idx_a = airArrayNew(appu.v, NULL, sizeof(unsigned int), incr);
  appu.ui = &h->invidx;
  h->invidx_a = airArrayNew(appu.v, NULL, sizeof(unsigned int), incr);

  if (h->key_a==NULL || (dataUnit>0 && h->data_a==NULL) || h->idx_a==NULL ||
      h->invidx_a==NULL) { /* allocation failed (partly) */
    airHeapNix(h);
    return NULL;
  }
  return h;
}

/* Same as airHeapNew, but initializes the new heap with the keys from key
 * and the optional data from data. If data is non-NULL, it needs to
 * have the same length as key, or this function will fail. The incr
 * field of the heap is copied from key (rather than data).
 */
airHeap *airHeapFromArray(const airArray *key, const airArray *data) {
  airHeap *h;
  unsigned int i;
  if (key==NULL || (data!=NULL && data->len!=key->len))
    return NULL; /* unusable input */
  h = airHeapNew((data==NULL)?0:data->unit, key->incr);
  if (heapLenIncr (h, key->len)) { /* could not allocate memory */
    airHeapNix(h);
    return NULL;
  }
  memcpy(h->key, key->data, key->len*sizeof(double));
  if (h->data_a!=NULL) memcpy(h->data, data->data, data->len*data->unit);
  for (i=0; i<key->len; i++) { /* initialize indices to identity */
    h->idx[i]=i;
    h->invidx[i]=i;
  }
  heapify(h);
  return h;
}

/* Frees all memory associated with the heap and its data */
airHeap *airHeapNix(airHeap *h) {
  if (h!=NULL) {
    airArrayNuke(h->key_a);
    if (h->data_a!=NULL) airArrayNuke(h->data_a);
    airArrayNuke(h->idx_a);
    airArrayNuke(h->invidx_a);
    free(h);
  }
  return NULL;
}

/* Returns the number of elements that are currently in heap h
 * (or 0 if h==NULL) */
unsigned int airHeapLength(const airHeap *h) {
  if (h!=NULL) {
    return h->key_a->len;
  } else
    return 0;
}

/* Inserts a key into the heap. data is copied over (deep copy) when the
 * heap was initialized to hold additional data. Otherwise, it is ignored.
 *
 * Returns the new number of elements in h.
 * Upon error, this can be the same as the old length. */
unsigned int airHeapInsert(airHeap *h, double key, const void *data) {
  unsigned int oldlen;
  if (h==NULL) return 0;
  oldlen = h->key_a->len;
  /* make space for the new element */
  if (heapLenIncr(h, 1))
    return oldlen;
  h->key[oldlen]=key;
  if (h->data_a!=NULL && data!=NULL) {
    memcpy((char*)h->data_a->data+oldlen*h->data_a->unit, data,
           h->data_a->unit);
  }
  h->idx[oldlen]=oldlen;
  h->invidx[oldlen]=oldlen;
  upheap(h,oldlen); /* restore the heap property */
  return oldlen+1;
}

/* Merges the second heap into the first. Returns the new length of first,
 * or zero upon error. */
unsigned int airHeapMerge(airHeap *first, const airHeap *second) {
  unsigned int first_len, second_len, i;
  if (first==NULL || second==NULL)
    return 0;
  if ((first->data_a==NULL) ^ (second->data_a==NULL))
    return 0; /* incompatible data */
  if (first->data_a!=NULL &&
      (first->data_a->unit!=second->data_a->unit))
    return 0; /* incompatible data */
  /* make sufficient space in first */
  first_len = first->key_a->len;
  second_len = second->key_a->len;
  if (heapLenIncr(first, second_len))
    return 0;
  /* concatenate and heapify */
  memcpy(first->key+first_len, second->key, second_len*sizeof(double));
  if (first->data_a!=NULL)
    memcpy((char*)first->data_a->data+first_len*first->data_a->unit,
           second->data_a->data,second_len*second->data_a->unit);
  for (i=0; i<second_len; i++) {
    first->idx[first_len+i] = first_len+second->idx[i];
    first->invidx[first->idx[first_len+i]]=first_len+i;
  }
  heapify(first);
  return first_len+second_len;
}

/* Returns the key of the front element in the heap and optionally copies the
 * associated data to *data. Does not modify the heap. */
double airHeapFrontPeek(const airHeap *h, void *data) {
  if (h==NULL || h->key_a->len==0)
    return 0.0;
  if (data!=NULL && h->data_a!=NULL)
    memcpy(data, (char*)h->data_a->data+h->idx[0]*h->data_a->unit,
           h->data_a->unit);
  return h->key[h->idx[0]];
}

/* Same as airHeapFrontPeek, but additionally removes the front element. */
double airHeapFrontPop(airHeap *h, void *data) {
  double retval = airHeapFrontPeek(h, data);
  if (h!=NULL && h->key_a->len>0) {
    airHeapRemove(h, h->idx[0]);
  }
  return retval;
}

/* Assigns a new key (and optionally, new data) to the front element and
 * re-sorts the heap if necessary. */
int airHeapFrontUpdate(airHeap *h, double newKey, const void *newData) {
  if (h==NULL || h->key_a->len==0)
    return 1;
  if (newData!=NULL && h->data_a!=NULL)
    memcpy((char*)h->data_a->data+h->idx[0]*h->data_a->unit, newData,
           h->data_a->unit);
  h->key[h->idx[0]]=newKey;
  downheap(h, 0);
  return 0;
}

/* The following functions provide advanced functionality and should
 * not be required in most applications. */

/* airHeapFind returns 0 if an element is found whose data is bitwise
 * equal to the given data, and sets *ai to the index of this
 * element. If more than one element matches the data, an arbitrary
 * one of them is returned.  The index can be used with airHeapRemove
 * or airHeapUpdate, but will become invalid as soon as any element is
 * removed from the heap. */
int airHeapFind(const airHeap *h, unsigned int *ai, const void *data) {
  unsigned int i;
  if (h==NULL || ai==NULL || data==NULL || h->data_a==NULL)
    return 1;
  for (i=0; i<h->key_a->len; i++) {
    if (!memcmp((char*)h->data_a->data+i*h->data_a->unit, data,
                h->data_a->unit)) {
      *ai = i;
      return 0;
    }
  }
  return 1;
}

/* Removes element ai from the heap, returns 0 upon success. */
int airHeapRemove(airHeap *h, unsigned int ai) {
  unsigned int old_invidx_ai;
  if (h==NULL || h->key_a->len<=ai)
    return 1;
  /* in the tree, replace ai with last element */
  old_invidx_ai=h->invidx[ai];
  h->idx[h->invidx[ai]]=h->idx[h->key_a->len-1];
  h->invidx[h->idx[h->key_a->len-1]]=h->invidx[ai];
  /* remove ai - copy last element over, then drop it */
  if (ai!=h->key_a->len-1) {
    h->key[ai]=h->key[h->key_a->len-1];
    if (h->data_a!=NULL) {
      memcpy((char*)h->data_a->data+ai*h->data_a->unit,
             (char*)h->data_a->data+(h->key_a->len-1)*h->data_a->unit,
             h->data_a->unit);
    }
    h->idx[h->invidx[h->key_a->len-1]]=ai;
    h->invidx[ai]=h->invidx[h->key_a->len-1];
  }
  heapLenIncr(h, -1);
  /* push moved element downheap */
  if (old_invidx_ai<h->key_a->len)
    downheap(h, old_invidx_ai);
  return 0;
}

/* Changes the key (and optional data) of the element ai, re-sorting
 * the heap if necessary. Returns 0 upon success. */
int airHeapUpdate(airHeap *h, unsigned int ai, double newKey,
                  const void *newData) {
  double oldkey;
  if (h==NULL || h->key_a->len<=ai)
    return 1;
  oldkey = h->key[ai];
  /* replace key and data */
  h->key[ai] = newKey;
  if (h->data_a!=NULL && newData!=NULL) {
    memcpy((char*)h->data_a->data+ai*h->data_a->unit,
           newData, h->data_a->unit);
  }
  if (oldkey<newKey) downheap(h, h->invidx[ai]);
  else upheap(h, h->invidx[ai]);
  return 0;
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/*
2			Teem: Tools to process and visualize scientific data and images .
3			Copyright (C) 2010 Thomas Schultz
4
5			This library is free software; you can redistribute it and/or
6			modify it under the terms of the GNU Lesser General Public License
7			(LGPL) as published by the Free Software Foundation; either
8			version 2.1 of the License, or (at your option) any later version.
9			The terms of redistributing and/or modifying this software also
10			include exceptions to the LGPL that facilitate static linking.
11
12			This library is distributed in the hope that it will be useful,
13			but WITHOUT ANY WARRANTY; without even the implied warranty of
14			MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15			Lesser General Public License for more details.
16
17			You should have received a copy of the GNU Lesser General Public License
18			along with this library; if not, write to Free Software Foundation, Inc.,
19			51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20			*/
21
22			#include "air.h"
23			#include <string.h>
24
25			/* internal helper routines */
26			/* restore heap property by pulling a single node up the tree */
27			static void upheap(airHeap *h, unsigned int i) {
28			while (i) {
29			unsigned int parent = (i-1)/2;
30			if (h->key[h->idx[parent]] > h->key[h->idx[i]]) { /* swap */
31			unsigned int tmp = h->idx[parent];
32			h->idx[parent] = h->idx[i];
33			h->idx[i] = tmp;
34			h->invidx[h->idx[i]] = i;
35			h->invidx[h->idx[parent]] = parent;
36			i = parent;
37			} else
38			i = 0; /* break loop */
39			}
40			}
41
42			/* restore heap property by pushing a single node down the tree */
43			static void downheap (airHeap *h, unsigned int i) {
44			unsigned int len = h->key_a->len;
45			while (1) {
46			unsigned int left = 2*i+1;
47			unsigned int right = 2*i+2;
48			unsigned int minidx = 0;
49			double minval = 0;
50			if (left>=len)
51			return;
52			if ((right>=len) \|\|
53			(h->key[h->idx[left]] < h->key[h->idx[right]])) {
54			minidx = left;
55			minval = h->key[h->idx[left]];
56			} else {
57			minidx = right;
58			minval = h->key[h->idx[right]];
59			}
60			if (h->key[h->idx[i]] > minval) { /* swap */
61			unsigned int tmp = h->idx[i];
62			h->idx[i] = h->idx[minidx];
63			h->idx[minidx] = tmp;
64			h->invidx[h->idx[i]] = i;
65			h->invidx[h->idx[minidx]] = minidx;
66			i = minidx;
67			} else
68			return;
69			}
70			}
71
72			/* Restore heap property "from scratch" (without any prior assumptions).
73			* Works in a bottom-up manner, which is more efficient than top-down */
74			static void heapify (airHeap *h) {
75			unsigned int len = h->key_a->len;
76			int maxi = len/2-1, i; /* above maxi, downheap has no effect */
77			for (i=maxi; i>=0; i--) {
78			downheap(h, i);
79			}
80			}
81
82			/* Tries to increase or decrease the length of h. returns 0 upon success. */
83			static int heapLenIncr (airHeap *h, int delta) {
84			unsigned int oldlen=h->key_a->len;
85			unsigned int newlen=oldlen+delta;
86			if (delta==0)
87			return 0;
88			airArrayLenIncr(h->key_a, delta);
89			if (h->data_a!=NULL) airArrayLenIncr(h->data_a, delta);
90			airArrayLenIncr(h->idx_a, delta);
91			airArrayLenIncr(h->invidx_a, delta);
92			if (h->key_a->len<newlen \|\| (h->data_a!=NULL && h->data_a->len<newlen) \|\|
93			h->idx_a->len<newlen \|\| h->invidx_a->len<newlen) {
94			/* Error. Try to undo changes and return error code. */
95			if (h->key_a->len>oldlen) airArrayLenSet(h->key_a, oldlen);
96			if (h->data_a!=NULL && h->data_a->len>oldlen)
97			airArrayLenSet(h->data_a, oldlen);
98			if (h->idx_a->len>oldlen) airArrayLenSet(h->idx_a, oldlen);
99			if (h->invidx_a->len>oldlen) airArrayLenSet(h->invidx_a, oldlen);
100			return 1;
101			}
102			return 0;
103			}
104
105			/* Creates a new heap, returning NULL upon error. If additional data
106			* is to be stored with each node, dataUnit needs to be set to the
107			* number of data bytes needed per element. incr is used for dynamic
108			* memory allocation (an additional number of incr elements are
109			* allocated each time the heap grows past its current capacity).
110			*/
111			airHeap *airHeapNew(size_t dataUnit, unsigned int incr) {
112			airHeap *h;
113			airPtrPtrUnion appu;
114			h = AIR_CALLOC(1, airHeap);
115			if (h==NULL) {
116			return NULL;
117			}
118
119			appu.d = &h->key;
120			h->key_a = airArrayNew(appu.v, NULL, sizeof(double), incr);
121			if (dataUnit>0) { /* data is optional */
122			h->data_a = airArrayNew(&h->data, NULL, dataUnit, incr);
123			}
124			appu.ui = &h->idx;
125			h->idx_a = airArrayNew(appu.v, NULL, sizeof(unsigned int), incr);
126			appu.ui = &h->invidx;
127			h->invidx_a = airArrayNew(appu.v, NULL, sizeof(unsigned int), incr);
128
129			if (h->key_a==NULL \|\| (dataUnit>0 && h->data_a==NULL) \|\| h->idx_a==NULL \|\|
130			h->invidx_a==NULL) { /* allocation failed (partly) */
131			airHeapNix(h);
132			return NULL;
133			}
134			return h;
135			}
136
137			/* Same as airHeapNew, but initializes the new heap with the keys from key
138			* and the optional data from data. If data is non-NULL, it needs to
139			* have the same length as key, or this function will fail. The incr
140			* field of the heap is copied from key (rather than data).
141			*/
142			airHeap airHeapFromArray(const airArray key, const airArray *data) {
143			airHeap *h;
144			unsigned int i;
145			if (key==NULL \|\| (data!=NULL && data->len!=key->len))
146			return NULL; /* unusable input */
147			h = airHeapNew((data==NULL)?0:data->unit, key->incr);
148			if (heapLenIncr (h, key->len)) { /* could not allocate memory */
149			airHeapNix(h);
150			return NULL;
151			}
152			memcpy(h->key, key->data, key->len*sizeof(double));
153			if (h->data_a!=NULL) memcpy(h->data, data->data, data->len*data->unit);
154			for (i=0; i<key->len; i++) { /* initialize indices to identity */
155			h->idx[i]=i;
156			h->invidx[i]=i;
157			}
158			heapify(h);
159			return h;
160			}
161
162			/* Frees all memory associated with the heap and its data */
163			airHeap airHeapNix(airHeap h) {
164			if (h!=NULL) {
165			airArrayNuke(h->key_a);
166			if (h->data_a!=NULL) airArrayNuke(h->data_a);
167			airArrayNuke(h->idx_a);
168			airArrayNuke(h->invidx_a);
169			free(h);
170			}
171			return NULL;
172			}
173
174			/* Returns the number of elements that are currently in heap h
175			* (or 0 if h==NULL) */
176			unsigned int airHeapLength(const airHeap *h) {
177			if (h!=NULL) {
178			return h->key_a->len;
179			} else
180			return 0;
181			}
182
183			/* Inserts a key into the heap. data is copied over (deep copy) when the
184			* heap was initialized to hold additional data. Otherwise, it is ignored.
185			*
186			* Returns the new number of elements in h.
187			* Upon error, this can be the same as the old length. */
188			unsigned int airHeapInsert(airHeap h, double key, const void data) {
189			unsigned int oldlen;
190			if (h==NULL) return 0;
191			oldlen = h->key_a->len;
192			/* make space for the new element */
193			if (heapLenIncr(h, 1))
194			return oldlen;
195			h->key[oldlen]=key;
196			if (h->data_a!=NULL && data!=NULL) {
197			memcpy((char)h->data_a->data+oldlenh->data_a->unit, data,
198			h->data_a->unit);
199			}
200			h->idx[oldlen]=oldlen;
201			h->invidx[oldlen]=oldlen;
202			upheap(h,oldlen); /* restore the heap property */
203			return oldlen+1;
204			}
205
206			/* Merges the second heap into the first. Returns the new length of first,
207			* or zero upon error. */
208			unsigned int airHeapMerge(airHeap first, const airHeap second) {
209			unsigned int first_len, second_len, i;
210			if (first==NULL \|\| second==NULL)
211			return 0;
212			if ((first->data_a==NULL) ^ (second->data_a==NULL))
213			return 0; /* incompatible data */
214			if (first->data_a!=NULL &&
215			(first->data_a->unit!=second->data_a->unit))
216			return 0; /* incompatible data */
217			/* make sufficient space in first */
218			first_len = first->key_a->len;
219			second_len = second->key_a->len;
220			if (heapLenIncr(first, second_len))
221			return 0;
222			/* concatenate and heapify */
223			memcpy(first->key+first_len, second->key, second_len*sizeof(double));
224			if (first->data_a!=NULL)
225			memcpy((char)first->data_a->data+first_lenfirst->data_a->unit,
226			second->data_a->data,second_len*second->data_a->unit);
227			for (i=0; i<second_len; i++) {
228			first->idx[first_len+i] = first_len+second->idx[i];
229			first->invidx[first->idx[first_len+i]]=first_len+i;
230			}
231			heapify(first);
232			return first_len+second_len;
233			}
234
235			/* Returns the key of the front element in the heap and optionally copies the
236			* associated data to data. Does not modify the heap. /
237			double airHeapFrontPeek(const airHeap h, void data) {
238			if (h==NULL \|\| h->key_a->len==0)
239			return 0.0;
240			if (data!=NULL && h->data_a!=NULL)
241			memcpy(data, (char)h->data_a->data+h->idx[0]h->data_a->unit,
242			h->data_a->unit);
243			return h->key[h->idx[0]];
244			}
245
246			/* Same as airHeapFrontPeek, but additionally removes the front element. */
247			double airHeapFrontPop(airHeap h, void data) {
248			double retval = airHeapFrontPeek(h, data);
249			if (h!=NULL && h->key_a->len>0) {
250			airHeapRemove(h, h->idx[0]);
251			}
252			return retval;
253			}
254
255			/* Assigns a new key (and optionally, new data) to the front element and
256			* re-sorts the heap if necessary. */
257			int airHeapFrontUpdate(airHeap h, double newKey, const void newData) {
258			if (h==NULL \|\| h->key_a->len==0)
259			return 1;
260			if (newData!=NULL && h->data_a!=NULL)
261			memcpy((char)h->data_a->data+h->idx[0]h->data_a->unit, newData,
262			h->data_a->unit);
263			h->key[h->idx[0]]=newKey;
264			downheap(h, 0);
265			return 0;
266			}
267
268			/* The following functions provide advanced functionality and should
269			* not be required in most applications. */
270
271			/* airHeapFind returns 0 if an element is found whose data is bitwise
272			* equal to the given data, and sets *ai to the index of this
273			* element. If more than one element matches the data, an arbitrary
274			* one of them is returned. The index can be used with airHeapRemove
275			* or airHeapUpdate, but will become invalid as soon as any element is
276			* removed from the heap. */
277			int airHeapFind(const airHeap h, unsigned int ai, const void *data) {
278			unsigned int i;
279			if (h==NULL \|\| ai==NULL \|\| data==NULL \|\| h->data_a==NULL)
280			return 1;
281			for (i=0; i<h->key_a->len; i++) {
282			if (!memcmp((char)h->data_a->data+ih->data_a->unit, data,
283			h->data_a->unit)) {
284			*ai = i;
285			return 0;
286			}
287			}
288			return 1;
289			}
290
291			/* Removes element ai from the heap, returns 0 upon success. */
292			int airHeapRemove(airHeap *h, unsigned int ai) {
293			unsigned int old_invidx_ai;
294			if (h==NULL \|\| h->key_a->len<=ai)
295			return 1;
296			/* in the tree, replace ai with last element */
297			old_invidx_ai=h->invidx[ai];
298			h->idx[h->invidx[ai]]=h->idx[h->key_a->len-1];
299			h->invidx[h->idx[h->key_a->len-1]]=h->invidx[ai];
300			/* remove ai - copy last element over, then drop it */
301			if (ai!=h->key_a->len-1) {
302			h->key[ai]=h->key[h->key_a->len-1];
303			if (h->data_a!=NULL) {
304			memcpy((char)h->data_a->data+aih->data_a->unit,
305			(char)h->data_a->data+(h->key_a->len-1)h->data_a->unit,
306			h->data_a->unit);
307			}
308			h->idx[h->invidx[h->key_a->len-1]]=ai;
309			h->invidx[ai]=h->invidx[h->key_a->len-1];
310			}
311			heapLenIncr(h, -1);
312			/* push moved element downheap */
313			if (old_invidx_ai<h->key_a->len)
314			downheap(h, old_invidx_ai);
315			return 0;
316			}
317
318			/* Changes the key (and optional data) of the element ai, re-sorting
319			* the heap if necessary. Returns 0 upon success. */
320			int airHeapUpdate(airHeap *h, unsigned int ai, double newKey,
321			const void *newData) {
322			double oldkey;
323			if (h==NULL \|\| h->key_a->len<=ai)
324			return 1;
325			oldkey = h->key[ai];
326			/* replace key and data */
327			h->key[ai] = newKey;
328			if (h->data_a!=NULL && newData!=NULL) {
329			memcpy((char)h->data_a->data+aih->data_a->unit,
330			newData, h->data_a->unit);
331			}
332			if (oldkey<newKey) downheap(h, h->invidx[ai]);
333			else upheap(h, h->invidx[ai]);
334			return 0;
335			}