keyarray.c

   1 /*
   2  * keyarray.c - routines to maintain a sorted array of keyids.
   3  *
   4  * Copyright 2004 Jonathan McDowell <noodles@earth.li>
   5  *
   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.
   9  *
  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
  13  * more details.
  14  *
  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.
  18  */
  19
  20 #include <stdbool.h>
  21 #include <stdint.h>
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25
  26 #include "keyarray.h"
  27
  28 bool array_find(struct keyarray *array, uint64_t key)
  29 {
  30         bool found;
  31         int  top = 0;
  32         int  bottom = 0;
  33         int  curpos;
  34
  35         found = false;
  36         if (array->keys != NULL && array->count > 0) {
  37                 bottom = -1;
  38                 top = array->count - 1;
  39                 while ((top - bottom) > 1) {
  40                         curpos = (top + bottom) / 2;
  41                         if (key > array->keys[curpos]) {
  42                                 bottom = curpos;
  43                         } else {
  44                                 top = curpos;
  45                         }
  46                 }
  47                 found = (array->keys[top] == key);
  48         }
  49
  50         return found;
  51 }
  52
  53 bool array_add(struct keyarray *array, uint64_t key)
  54 {
  55         bool found;
  56         int  top = 0;
  57         int  bottom = 0;
  58         int  curpos = 0;
  59
  60         found = false;
  61         if (array->keys != NULL && array->count > 0) {
  62                 bottom = -1;
  63                 top = array->count - 1;
  64                 while ((top - bottom) > 1) {
  65                         curpos = (top + bottom) / 2;
  66                         if (key > array->keys[curpos]) {
  67                                 bottom = curpos;
  68                         } else {
  69                                 top = curpos;
  70                         }
  71                 }
  72                 found = (array->keys[top] == key);
  73
  74                 if (key > array->keys[top]) {
  75                         curpos = top + 1;
  76                 } else {
  77                         curpos = top;
  78                 }
  79         }
  80
  81         if (!found) {
  82                 if (array->size == 0) {
  83                         array->keys = malloc(16 * sizeof(uint64_t));
  84                         array->size = 16;
  85                         array->count = 1;
  86                         array->keys[0] = key;
  87                 } else {
  88                         if (array->count >= array->size) {
  89                                 array->size *= 2;
  90                                 array->keys = realloc(array->keys,
  91                                                 array->size * sizeof(uint64_t));
  92                         }
  93                         if (curpos < array->count) {
  94                                 memmove(&array->keys[curpos+1],
  95                                         &array->keys[curpos],
  96                                         sizeof(uint64_t) *
  97                                                 (array->count - curpos));
  98                         }
  99                         array->keys[curpos] = key;
 100                         array->count++;
 101                 }
 102         }
 103
 104         return !found;
 105 }
 106
 107 void array_free(struct keyarray *array)
 108 {
 109         if (array->keys) {
 110                 free(array->keys);
 111                 array->keys = NULL;
 112         }
 113         array->count = array->size = 0;
 114
 115         return;
 116 }