keyarray.c

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