release/src/router/pptp-client/vector.c

   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
  21 struct vector_item {
  22     int key;
  23     PPTP_CALL *call;
  24 };
  25
  26 struct 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
  35 static struct vector_item *binary_search(VECTOR *v, int key);
  36
  37 /*** vector_create ************************************************************/
  38 VECTOR *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 ***********************************************************/
  56 void 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 **************************************************************/
  66 int 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  */
  76 int 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 ************************************************************/
 112 int  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 ************************************************************/
 124 int  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 **********************************************************/
 135 int  vector_contains(VECTOR *v, int key)
 136 {
 137     assert(v != NULL);
 138     return (binary_search(v, key) != NULL);
 139 }
 140
 141 /*** vector_item **************************************************************/
 142 static 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  */
 164 int 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 ***********************************************************/
 204 PPTP_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 }