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, see <https://www.gnu.org/licenses/>.
  17  */
  18
  19 #include <stdbool.h>
  20 #include <stdint.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24
  25 #include "keyarray.h"
  26 #include "keystructs.h"
  27
  28 int fingerprint_cmp(struct openpgp_fingerprint *a,
  29                 struct openpgp_fingerprint *b)
  30 {
  31         if (a->length < b->length) {
  32                 return -1;
  33         } else if (a->length > b->length) {
  34                 return 1;
  35         } else {
  36                 return memcmp(a->fp, b->fp, a->length);
  37         }
  38 }
  39
  40 bool array_find(struct keyarray *array, struct openpgp_fingerprint *fp)
  41 {
  42         bool found;
  43         int  top = 0;
  44         int  bottom = 0;
  45         int  curpos;
  46
  47         found = false;
  48         if (array->keys != NULL && array->count > 0) {
  49                 bottom = -1;
  50                 top = array->count - 1;
  51                 while ((top - bottom) > 1) {
  52                         curpos = (top + bottom) / 2;
  53                         if (fingerprint_cmp(fp, &array->keys[curpos]) > 0) {
  54                                 bottom = curpos;
  55                         } else {
  56                                 top = curpos;
  57                         }
  58                 }
  59                 found = (fingerprint_cmp(fp, &array->keys[top]) == 0);
  60         }
  61
  62         return found;
  63 }
  64
  65 bool array_add(struct keyarray *array, struct openpgp_fingerprint *fp)
  66 {
  67         bool found;
  68         int  top = 0;
  69         int  bottom = 0;
  70         int  curpos = 0;
  71
  72         found = false;
  73         if (array->size != 0 && array->count > 0) {
  74                 bottom = -1;
  75                 top = array->count - 1;
  76                 while ((top - bottom) > 1) {
  77                         curpos = (top + bottom) / 2;
  78                         if (fingerprint_cmp(fp, &array->keys[curpos]) > 0) {
  79                                 bottom = curpos;
  80                         } else {
  81                                 top = curpos;
  82                         }
  83                 }
  84                 found = (fingerprint_cmp(fp, &array->keys[top]) == 0);
  85
  86                 if (fingerprint_cmp(fp, &array->keys[top]) > 0) {
  87                         curpos = top + 1;
  88                 } else {
  89                         curpos = top;
  90                 }
  91         }
  92
  93         if (!found) {
  94                 if (array->size == 0) {
  95                         array->keys = malloc(16 *
  96                                 sizeof(struct openpgp_fingerprint));
  97                         array->size = 16;
  98                         array->count = 1;
  99                         array->keys[0] = *fp;
 100                 } else {
 101                         if (array->count >= array->size) {
 102                                 array->size *= 2;
 103                                 array->keys = realloc(array->keys,
 104                                         array->size *
 105                                         sizeof(struct openpgp_fingerprint));
 106                         }
 107                         if (curpos < array->count) {
 108                                 memmove(&array->keys[curpos+1],
 109                                         &array->keys[curpos],
 110                                         sizeof(struct openpgp_fingerprint) *
 111                                                 (array->count - curpos));
 112                         }
 113                         array->keys[curpos] = *fp;
 114                         array->count++;
 115                 }
 116         }
 117
 118         return !found;
 119 }
 120
 121 void array_free(struct keyarray *array)
 122 {
 123         if (array->keys) {
 124                 free(array->keys);
 125                 array->keys = NULL;
 126         }
 127         array->count = array->size = 0;
 128
 129         return;
 130 }