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