1/* vector.c ..... store a vector of PPTP_CALL information and search it 2 * efficiently. 3 * C. Scott Ananian <cananian@alumni.princeton.edu> 4 * 5 * $Id: vector.c,v 1.3 2003/06/17 10:12:55 reink Exp $ 6 */ 7 8#include <stdlib.h> 9#include <string.h> 10#include <assert.h> 11#include "pptp_ctrl.h" 12#include "vector.h" 13/* #define VECTOR_DEBUG */ 14#ifndef TRUE 15#define TRUE 1 16#endif 17#ifndef FALSE 18#define FALSE 0 19#endif 20 21struct vector_item { 22 int key; 23 PPTP_CALL *call; 24}; 25 26struct vector_struct { 27 struct vector_item *item; 28 int size; 29 int alloc; 30#ifdef VECTOR_DEBUG 31 int key_max; 32#endif 33}; 34 35static struct vector_item *binary_search(VECTOR *v, int key); 36 37/*** vector_create ************************************************************/ 38VECTOR *vector_create() 39{ 40 const int INITIAL_SIZE = 4; 41 42 VECTOR *v = malloc(sizeof(*v)); 43 if (v == NULL) return v; 44 45 v->size = 0; 46 v->alloc = INITIAL_SIZE; 47 v->item = malloc(sizeof(*(v->item)) * (v->alloc)); 48#ifdef VECTOR_DEBUG 49 v->key_max = -1; 50#endif 51 if (v->item == NULL) { free(v); return NULL; } 52 else return v; 53} 54 55/*** vector_destroy ***********************************************************/ 56void vector_destroy(VECTOR *v) 57{ 58 free(v->item); 59#ifdef VECTOR_DEBUG 60 v->item = NULL; 61#endif 62 free(v); 63} 64 65/*** vector_size **************************************************************/ 66int vector_size(VECTOR *v) 67{ 68 assert(v != NULL); 69 return v->size; 70} 71 72/*** vector_insert************************************************************* 73 * nice thing about file descriptors is that we are assured by POSIX 74 * that they are monotonically increasing. 75 */ 76int vector_insert(VECTOR *v, int key, PPTP_CALL * call) 77{ 78 int i; 79 assert(v != NULL && call != NULL); 80 assert(!vector_contains(v, key)); 81#ifdef VECTOR_DEBUG 82 assert(v->key_max < key); 83#endif 84 if (!(v->size < v->alloc)) { 85 void *tmp = realloc(v->item, sizeof(*(v->item)) * 2 * v->alloc); 86 if (tmp != NULL) { 87 v->alloc *= 2; 88 v->item = tmp; 89 } else return FALSE; /* failed to alloc memory. */ 90 } 91 assert(v->size < v->alloc); 92 /* for safety, we make this work in the general case; 93 * but this is optimized for adding call to the end of the vector. 94 */ 95 for(i = v->size - 1; i >= 0; i--) 96 if (v->item[i].key < key) 97 break; 98 /* insert after item i */ 99 memmove(&v->item[i + 2], &v->item[i + 1], 100 (v->size - i - 1) * sizeof(*(v->item))); 101 v->item[i + 1].key = key; 102 v->item[i + 1].call = call; 103 v->size++; 104#ifdef VECTOR_DEBUG 105 if (v->key_max < key) /* ie, always. */ 106 v->key_max = key; 107#endif 108 return TRUE; 109} 110 111/*** vector_remove ************************************************************/ 112int vector_remove(VECTOR *v, int key) 113{ 114 struct vector_item *tmp; 115 assert(v != NULL); 116 if ((tmp =binary_search(v,key)) == NULL) return FALSE; 117 assert(tmp >= v->item && tmp < v->item + v->size); 118 memmove(tmp, tmp + 1, (v->size - (v->item - tmp) - 1) * sizeof(*(v->item))); 119 v->size--; 120 return TRUE; 121} 122 123/*** vector_search ************************************************************/ 124int vector_search(VECTOR *v, int key, PPTP_CALL **call) 125{ 126 struct vector_item *tmp; 127 assert(v != NULL); 128 tmp = binary_search(v, key); 129 if (tmp ==NULL) return FALSE; 130 *call = tmp->call; 131 return TRUE; 132} 133 134/*** vector_contains **********************************************************/ 135int vector_contains(VECTOR *v, int key) 136{ 137 assert(v != NULL); 138 return (binary_search(v, key) != NULL); 139} 140 141/*** vector_item **************************************************************/ 142static struct vector_item *binary_search(VECTOR *v, int key) 143{ 144 int l,r,x; 145 l = 0; 146 r = v->size - 1; 147 while (r >= l) { 148 x = (l + r)/2; 149 if (key < v->item[x].key) r = x - 1; else l = x + 1; 150 if (key == v->item[x].key) return &(v->item[x]); 151 } 152 return NULL; 153} 154 155/*** vector_scan *************************************************************** 156 * Hmm. Let's be fancy and use a binary search for the first 157 * unused key, taking advantage of the list is stored sorted; ie 158 * we can look at pointers and keys at two different locations, 159 * and if (ptr1 - ptr2) = (key1 - key2) then all the slots 160 * between ptr1 and ptr2 are filled. Note that ptr1-ptr2 should 161 * never be greater than key1-key2 (no duplicate keys!)... we 162 * check for this. 163 */ 164int vector_scan(VECTOR *v, int lo, int hi, int *key) 165{ 166 int l,r,x; 167 assert(v != NULL); 168 assert(key != NULL); 169 if ((v->size<1) || (lo < v->item[0].key)) { *key = lo; return TRUE; } 170 /* our array bounds */ 171 l = 0; r = v->size - 1; 172 while (r > l) { 173 /* check for a free spot right after l */ 174 if (v->item[l].key + 1 < v->item[l + 1].key) { /* found it! */ 175 *key = v->item[l].key + 1; 176 return TRUE; 177 } 178 /* no dice. Let's see if the free spot is before or after the midpoint */ 179 x = (l + r)/2; 180 /* Okay, we have right (r), left (l) and the probe (x). */ 181 assert(x - l <= v->item[x].key - v->item[l].key); 182 assert(r - x <= v->item[r].key - v->item[x].key); 183 if (x - l < v->item[x].key - v->item[l].key) 184 /* room between l and x */ 185 r = x; 186 else /* no room between l and x */ 187 if (r - x < v->item[r].key - v->item[x].key) 188 /* room between x and r */ 189 l = x; 190 else /* no room between x and r, either */ 191 break; /* game over, man. */ 192 } 193 /* no room found in already allocated space. Check to see if 194 * there's free space above allocated entries. */ 195 if (v->item[v->size - 1].key < hi) { 196 *key = v->item[v->size - 1].key + 1; 197 return TRUE; 198 } 199 /* outta luck */ 200 return FALSE; 201} 202 203/*** vector_get_Nth ***********************************************************/ 204PPTP_CALL * vector_get_Nth(VECTOR *v, int n) 205{ 206 assert(v != NULL); 207 assert(0 <= n && n < vector_size(v)); 208 return v->item[n].call; 209} 210