2 * keyarray.c - routines to maintain a sorted array of keyids.
4 * Copyright 2004 Jonathan McDowell <noodles@earth.li>
6 * This program is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License as published by the Free
8 * Software Foundation; version 2 of the License.
10 * This program is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
15 * You should have received a copy of the GNU General Public License along with
16 * this program; if not, write to the Free Software Foundation, Inc., 51
17 * Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
28 bool array_find(struct keyarray *array, uint64_t key)
36 if (array->keys != NULL && array->count > 0) {
38 top = array->count - 1;
39 while ((top - bottom) > 1) {
40 curpos = (top + bottom) / 2;
41 if (key > array->keys[curpos]) {
47 found = (array->keys[top] == key);
53 bool array_add(struct keyarray *array, uint64_t key)
61 if (array->keys != NULL && array->count > 0) {
63 top = array->count - 1;
64 while ((top - bottom) > 1) {
65 curpos = (top + bottom) / 2;
66 if (key > array->keys[curpos]) {
72 found = (array->keys[top] == key);
74 if (key > array->keys[top]) {
82 if (array->size == 0) {
83 array->keys = malloc(16 * sizeof(uint64_t));
88 if (array->count >= array->size) {
90 array->keys = realloc(array->keys,
91 array->size * sizeof(uint64_t));
93 if (curpos < array->count) {
94 memmove(&array->keys[curpos+1],
97 (array->count - curpos));
99 array->keys[curpos] = key;
107 void array_free(struct keyarray *array)
113 array->count = array->size = 0;