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