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