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