← Back to branch summary

~ubuntu-branches/ubuntu/saucy/openvpn/saucy-proposed

« back to all changes in this revision

Viewing changes to list.h

  • Committer: Package Import Robot
  • Author(s): Stéphane Graber
  • Date: 2013-05-24 17:42:45 UTC
  • mfrom: (1.1.19) (10.2.22 sid)
  • Revision ID: package-import@ubuntu.com-20130524174245-g9y6wlforycufqy5
Tags: 2.3.1-2ubuntu1
* Merge from Debian unstable. Remaining changes:
  - debian/openvpn.init.d:
    + Do not use start-stop-daemon and </dev/null to avoid blocking boot.
    + Show per-VPN result messages.
    + Add "--script-security 2" by default for backwards compatabliity.

Show diffs side-by-side

added added

removed removed

Lines of Context:
list.h
1
 
/*
2
 
 *  OpenVPN -- An application to securely tunnel IP networks
3
 
 *             over a single TCP/UDP port, with support for SSL/TLS-based
4
 
 *             session authentication and key exchange,
5
 
 *             packet encryption, packet authentication, and
6
 
 *             packet compression.
7
 
 *
8
 
 *  Copyright (C) 2002-2010 OpenVPN Technologies, Inc. <sales@openvpn.net>
9
 
 *
10
 
 *  This program is free software; you can redistribute it and/or modify
11
 
 *  it under the terms of the GNU General Public License version 2
12
 
 *  as published by the Free Software Foundation.
13
 
 *
14
 
 *  This program is distributed in the hope that it will be useful,
15
 
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
16
 
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17
 
 *  GNU General Public License for more details.
18
 
 *
19
 
 *  You should have received a copy of the GNU General Public License
20
 
 *  along with this program (see the file COPYING included with this
21
 
 *  distribution); if not, write to the Free Software Foundation, Inc.,
22
 
 *  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
23
 
 */
24
 
 
25
 
#ifndef LIST_H
26
 
#define LIST_H
27
 
 
28
 
/*
29
 
 * This code is a fairly straightforward hash
30
 
 * table implementation using Bob Jenkins'
31
 
 * hash function.
32
 
 *
33
 
 * Hash tables are used in OpenVPN to keep track of
34
 
 * client instances over various key spaces.
35
 
 */
36
 
 
37
 
#if P2MP_SERVER
38
 
 
39
 
/* define this to enable special list test mode */
40
 
/*#define LIST_TEST*/
41
 
 
42
 
#include "basic.h"
43
 
#include "buffer.h"
44
 
 
45
 
#define hashsize(n) ((uint32_t)1<<(n))
46
 
#define hashmask(n) (hashsize(n)-1)
47
 
 
48
 
struct hash_element
49
 
{
50
 
  void *value;
51
 
  const void *key;
52
 
  unsigned int hash_value;
53
 
  struct hash_element *next;
54
 
};
55
 
 
56
 
struct hash_bucket
57
 
{
58
 
  struct hash_element *list;
59
 
};
60
 
 
61
 
struct hash
62
 
{
63
 
  int n_buckets;
64
 
  int n_elements;
65
 
  int mask;
66
 
  uint32_t iv;
67
 
  uint32_t (*hash_function)(const void *key, uint32_t iv);
68
 
  bool (*compare_function)(const void *key1, const void *key2); /* return true if equal */
69
 
  struct hash_bucket *buckets;
70
 
};
71
 
 
72
 
struct hash *hash_init (const int n_buckets,
73
 
                        const uint32_t iv,
74
 
                        uint32_t (*hash_function)(const void *key, uint32_t iv),
75
 
                        bool (*compare_function)(const void *key1, const void *key2));
76
 
 
77
 
void hash_free (struct hash *hash);
78
 
 
79
 
bool hash_add (struct hash *hash, const void *key, void *value, bool replace);
80
 
 
81
 
struct hash_element *hash_lookup_fast (struct hash *hash,
82
 
                                       struct hash_bucket *bucket,
83
 
                                       const void *key,
84
 
                                       uint32_t hv);
85
 
 
86
 
bool hash_remove_fast (struct hash *hash,
87
 
                       struct hash_bucket *bucket,
88
 
                       const void *key,
89
 
                       uint32_t hv);
90
 
 
91
 
void hash_remove_by_value (struct hash *hash, void *value);
92
 
 
93
 
struct hash_iterator
94
 
{
95
 
  struct hash *hash;
96
 
  int bucket_index;
97
 
  struct hash_bucket *bucket;
98
 
  struct hash_element *elem;
99
 
  struct hash_element *last;
100
 
  bool bucket_marked;
101
 
  int bucket_index_start;
102
 
  int bucket_index_end;
103
 
};
104
 
 
105
 
void hash_iterator_init_range (struct hash *hash,
106
 
                               struct hash_iterator *hi,
107
 
                               int start_bucket,
108
 
                               int end_bucket);
109
 
 
110
 
void hash_iterator_init (struct hash *hash, struct hash_iterator *iter);
111
 
struct hash_element *hash_iterator_next (struct hash_iterator *hi);
112
 
void hash_iterator_delete_element (struct hash_iterator *hi);
113
 
void hash_iterator_free (struct hash_iterator *hi);
114
 
 
115
 
uint32_t hash_func (const uint8_t *k, uint32_t length, uint32_t initval);
116
 
 
117
 
uint32_t void_ptr_hash_function (const void *key, uint32_t iv);
118
 
bool void_ptr_compare_function (const void *key1, const void *key2);
119
 
 
120
 
#ifdef LIST_TEST
121
 
void list_test (void);
122
 
#endif
123
 
 
124
 
static inline uint32_t
125
 
hash_value (const struct hash *hash, const void *key)
126
 
{
127
 
  return (*hash->hash_function)(key, hash->iv);
128
 
}
129
 
 
130
 
static inline int
131
 
hash_n_elements (const struct hash *hash)
132
 
{
133
 
  return hash->n_elements;
134
 
}
135
 
 
136
 
static inline int
137
 
hash_n_buckets (const struct hash *hash)
138
 
{
139
 
  return hash->n_buckets;
140
 
}
141
 
 
142
 
static inline struct hash_bucket *
143
 
hash_bucket (struct hash *hash, uint32_t hv)
144
 
{
145
 
  return &hash->buckets[hv & hash->mask];
146
 
}
147
 
 
148
 
static inline void *
149
 
hash_lookup (struct hash *hash, const void *key)
150
 
{
151
 
  void *ret = NULL;
152
 
  struct hash_element *he;
153
 
  uint32_t hv = hash_value (hash, key);
154
 
  struct hash_bucket *bucket = &hash->buckets[hv & hash->mask];
155
 
 
156
 
  he = hash_lookup_fast (hash, bucket, key, hv);
157
 
  if (he)
158
 
    ret = he->value;
159
 
 
160
 
  return ret;
161
 
}
162
 
 
163
 
/* NOTE: assumes that key is not a duplicate */
164
 
static inline void
165
 
hash_add_fast (struct hash *hash,
166
 
               struct hash_bucket *bucket,
167
 
               const void *key,
168
 
               uint32_t hv,
169
 
               void *value)
170
 
{
171
 
  struct hash_element *he;
172
 
 
173
 
  ALLOC_OBJ (he, struct hash_element);
174
 
  he->value = value;
175
 
  he->key = key;
176
 
  he->hash_value = hv;
177
 
  he->next = bucket->list;
178
 
  bucket->list = he;
179
 
  ++hash->n_elements;
180
 
}
181
 
 
182
 
static inline bool
183
 
hash_remove (struct hash *hash, const void *key)
184
 
{
185
 
  uint32_t hv;
186
 
  struct hash_bucket *bucket;
187
 
  bool ret;
188
 
 
189
 
  hv = hash_value (hash, key);
190
 
  bucket = &hash->buckets[hv & hash->mask];
191
 
  ret = hash_remove_fast (hash, bucket, key, hv);
192
 
  return ret;
193
 
}
194
 
 
195
 
#endif /* P2MP_SERVER */
196
 
#endif /* LIST */