← Back to branch summary

~ubuntu-branches/ubuntu/wily/dovecot/wily

« back to all changes in this revision

Viewing changes to src/lib/hash.c

  • Committer: Bazaar Package Importer
  • Author(s): CHuck Short, Chuck Short
  • Date: 2009-11-06 00:47:29 UTC
  • mfrom: (4.1.9 squeeze)
  • Revision ID: james.westby@ubuntu.com-20091106004729-i39n7v9e7d4h51f6
Tags: 1:1.2.6-1ubuntu1
https://launchpad.net/bugs/164837
https://launchpad.net/bugs/329878
https://launchpad.net/bugs/254721
* Merge from debian testing, remaining changes:
  Add new binary pkg dovecot-postfix that integrates postfix and dovecot
  automatically: (LP: #164837)
  + debian/control:
    - add new binary with short description
    - set Architecture all for dovecot-postfix (LP: #329878)
  + debian/dovecot-postfix.postinst:
    - create initial certificate symlinks to snakeoil.
    - set up postfix with postconf to:
      - use Maildir/ as the default mailbox.
      - use dovecot as the sasl authentication server.
      - use dovecot LDA (deliver).
      - use tls for smtp{d} services.
    - fix certificates paths in postfix' main.cf
    - add reject_unauth_destination to postfix' recipient restrictions
    - add reject_unknown_sender_domain to postfix' sender restrictions
    - rename configuration name on remove, delete on purge
    - restart dovecot after linking certificates
    - handle use case when postfix is unconfigurated
   + debian/dovecot-postfix.dirs: create backup directory for postfix's configuration
   + restart postfix and dovecot.
   + debian/dovecot-postfix.postrm:
     - remove all dovecot related configuration from postfix.
     - restart postfix and dovecot.
   + debian/dovecot-common.init:
     - check if /etc/dovecot/dovecot-postfix.conf exists and use it
       as the configuration file if so.
   + debian/patches/warning-ubuntu-postfix.dpatch
     - add warning about dovecot-postfix.conf in dovecot default 
       configuration file
   + debian/patches/dovecot-postfix.conf.diff:
     - Ubuntu server custom changes to the default dovecot configuration for
       better interfation with postfix
     - enable sieve plugin
   + debian/patches/dovecot-postfix.conf.diff:
     + Ubuntu server custom changes to the default dovecot configuration for
       better integration with postfix:
       - enable imap, pop3, imaps, pop3s and managesieve by default.
       - enable dovecot LDA (deliver).
       - enable SASL auth socket in postfix private directory.
   + debian/rules:
     - copy, patch and install dovecot-postfix.conf in /etc/dovecot/.
     - build architecure independent packages too
   + Use Snakeoil SSL certificates by default.
     - debian/control: Depend on ssl-cert.
     - debian/patches/ssl-cert-snakeoil.dpatch: Change default SSL cert
       paths to snakeoil.
     - debian/dovecot-common.postinst: Relax grep for SSL_* a bit.
   + Add autopkgtest to debian/tests/*.
   + Fast TearDown: Update the lsb init header to not stop in level 6.
   + Add ufw integration:
     - Created debian/dovecot-common.ufw.profile.
     - debian/rules:
       + install profile
     - debian/control:
       + Suggest ufw
   + debian/{control,rules}: enable PIE hardening.
   + dovecot-imapd, dovecot-pop3: Replaces dovecot-common (<< 1:1.1). LP: #254721
   + debian/control:
     - Update Vcs-* headers.
   + debian/rules:
     - Create emtpy stamp.h.in files in dovecot-sieve/ and dovecot-managesieve/
       if they're not there since empty files are not included in the diff.gz 
       file.
   + Add SMTP-AUTH support for Outlook (login auth mechanism)
   + Dropped:
     - debian/patches/security-CVE-2009-3235: Applied upstream.
     - debian/patches/fix-pop3-assertion.dpatch: Applied upstream.
     - dovecot-sieve and dovecot-managesieve: Use the debian patches instead.

  [Chuck Short]
  - Updated dovecot-sieve to 0.1.13.
  - Updated dovecot-managesieve to 0.11.9.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/lib/hash.c
8
8
 
9
9
#include <ctype.h>
10
10
 
11
 
#define HASH_TABLE_MIN_SIZE 109
 
11
#define HASH_TABLE_MIN_SIZE 131
12
12
 
13
13
struct hash_node {
14
14
        struct hash_node *next;
36
36
        unsigned int pos;
37
37
};
38
38
 
39
 
static bool hash_resize(struct hash_table *table, bool grow);
 
39
static bool hash_table_resize(struct hash_table *table, bool grow);
40
40
 
41
41
static int direct_cmp(const void *p1, const void *p2)
42
42
{
50
50
}
51
51
 
52
52
struct hash_table *
53
 
hash_create(pool_t table_pool, pool_t node_pool, unsigned int initial_size,
54
 
            hash_callback_t *hash_cb, hash_cmp_callback_t *key_compare_cb)
 
53
hash_table_create(pool_t table_pool, pool_t node_pool, unsigned int initial_size,
 
54
                  hash_callback_t *hash_cb, hash_cmp_callback_t *key_compare_cb)
55
55
{
56
56
        struct hash_table *table;
57
57
 
91
91
        }
92
92
}
93
93
 
94
 
static void hash_destroy_nodes(struct hash_table *table)
 
94
static void hash_table_destroy_nodes(struct hash_table *table)
95
95
{
96
96
        unsigned int i;
97
97
 
101
101
        }
102
102
}
103
103
 
104
 
void hash_destroy(struct hash_table **_table)
 
104
void hash_table_destroy(struct hash_table **_table)
105
105
{
106
106
        struct hash_table *table = *_table;
107
107
 
108
108
        *_table = NULL;
109
109
 
110
110
        if (!table->node_pool->alloconly_pool) {
111
 
                hash_destroy_nodes(table);
 
111
                hash_table_destroy_nodes(table);
112
112
                destroy_node_list(table, table->free_nodes);
113
113
        }
114
114
 
116
116
        p_free(table->table_pool, table);
117
117
}
118
118
 
119
 
void hash_clear(struct hash_table *table, bool free_nodes)
 
119
void hash_table_clear(struct hash_table *table, bool free_nodes)
120
120
{
121
121
        if (!table->node_pool->alloconly_pool)
122
 
                hash_destroy_nodes(table);
 
122
                hash_table_destroy_nodes(table);
123
123
 
124
124
        if (free_nodes) {
125
125
                if (!table->node_pool->alloconly_pool)
134
134
}
135
135
 
136
136
static struct hash_node *
137
 
hash_lookup_node(const struct hash_table *table,
138
 
                 const void *key, unsigned int hash)
 
137
hash_table_lookup_node(const struct hash_table *table,
 
138
                       const void *key, unsigned int hash)
139
139
{
140
140
        struct hash_node *node;
141
141
 
152
152
        return NULL;
153
153
}
154
154
 
155
 
void *hash_lookup(const struct hash_table *table, const void *key)
 
155
void *hash_table_lookup(const struct hash_table *table, const void *key)
156
156
{
157
157
        struct hash_node *node;
158
158
 
159
 
        node = hash_lookup_node(table, key, table->hash_cb(key));
 
159
        node = hash_table_lookup_node(table, key, table->hash_cb(key));
160
160
        return node != NULL ? node->value : NULL;
161
161
}
162
162
 
163
 
bool hash_lookup_full(const struct hash_table *table, const void *lookup_key,
164
 
                      void **orig_key, void **value)
 
163
bool hash_table_lookup_full(const struct hash_table *table,
 
164
                            const void *lookup_key,
 
165
                            void **orig_key, void **value)
165
166
{
166
167
        struct hash_node *node;
167
168
 
168
 
        node = hash_lookup_node(table, lookup_key,
169
 
                                table->hash_cb(lookup_key));
 
169
        node = hash_table_lookup_node(table, lookup_key,
 
170
                                      table->hash_cb(lookup_key));
170
171
        if (node == NULL)
171
172
                return FALSE;
172
173
 
178
179
}
179
180
 
180
181
static struct hash_node *
181
 
hash_insert_node(struct hash_table *table, void *key, void *value,
182
 
                 bool check_existing)
 
182
hash_table_insert_node(struct hash_table *table, void *key, void *value,
 
183
                       bool check_existing)
183
184
{
184
185
        struct hash_node *node, *prev;
185
186
        unsigned int hash;
190
191
 
191
192
        if (check_existing && table->removed_count > 0) {
192
193
                /* there may be holes, have to check everything */
193
 
                node = hash_lookup_node(table, key, hash);
 
194
                node = hash_table_lookup_node(table, key, hash);
194
195
                if (node != NULL) {
195
196
                        node->value = value;
196
197
                        return node;
234
235
        }
235
236
 
236
237
        if (node == NULL) {
237
 
                if (table->frozen == 0 && hash_resize(table, TRUE)) {
 
238
                if (table->frozen == 0 && hash_table_resize(table, TRUE)) {
238
239
                        /* resized table, try again */
239
 
                        return hash_insert_node(table, key, value, FALSE);
 
240
                        return hash_table_insert_node(table, key, value, FALSE);
240
241
                }
241
242
 
242
243
                if (table->free_nodes == NULL)
250
251
        }
251
252
 
252
253
        node->key = key;
253
 
        node->value = value;;
 
254
        node->value = value;
254
255
 
255
256
        table->nodes_count++;
256
257
        return node;
257
258
}
258
259
 
259
 
void hash_insert(struct hash_table *table, void *key, void *value)
 
260
void hash_table_insert(struct hash_table *table, void *key, void *value)
260
261
{
261
262
        struct hash_node *node;
262
263
 
263
 
        node = hash_insert_node(table, key, value, TRUE);
 
264
        node = hash_table_insert_node(table, key, value, TRUE);
264
265
        node->key = key;
265
266
}
266
267
 
267
 
void hash_update(struct hash_table *table, void *key, void *value)
 
268
void hash_table_update(struct hash_table *table, void *key, void *value)
268
269
{
269
 
        (void)hash_insert_node(table, key, value, TRUE);
 
270
        (void)hash_table_insert_node(table, key, value, TRUE);
270
271
}
271
272
 
272
 
static void hash_compress(struct hash_table *table, struct hash_node *root)
 
273
static void
 
274
hash_table_compress(struct hash_table *table, struct hash_node *root)
273
275
{
274
276
        struct hash_node *node, *next;
275
277
 
293
295
        }
294
296
}
295
297
 
296
 
static void hash_compress_removed(struct hash_table *table)
 
298
static void hash_table_compress_removed(struct hash_table *table)
297
299
{
298
300
        unsigned int i;
299
301
 
300
302
        for (i = 0; i < table->size; i++)
301
 
                hash_compress(table, &table->nodes[i]);
 
303
                hash_table_compress(table, &table->nodes[i]);
302
304
 
303
305
        table->removed_count = 0;
304
306
}
305
307
 
306
 
void hash_remove(struct hash_table *table, const void *key)
 
308
void hash_table_remove(struct hash_table *table, const void *key)
307
309
{
308
310
        struct hash_node *node;
309
311
        unsigned int hash;
310
312
 
311
313
        hash = table->hash_cb(key);
312
314
 
313
 
        node = hash_lookup_node(table, key, hash);
 
315
        node = hash_table_lookup_node(table, key, hash);
314
316
        if (unlikely(node == NULL))
315
317
                i_panic("key not found from hash");
316
318
 
319
321
 
320
322
        if (table->frozen != 0)
321
323
                table->removed_count++;
322
 
        else if (!hash_resize(table, FALSE))
323
 
                hash_compress(table, &table->nodes[hash % table->size]);
 
324
        else if (!hash_table_resize(table, FALSE))
 
325
                hash_table_compress(table, &table->nodes[hash % table->size]);
324
326
}
325
327
 
326
 
unsigned int hash_count(const struct hash_table *table)
 
328
unsigned int hash_table_count(const struct hash_table *table)
327
329
{
328
330
        return table->nodes_count;
329
331
}
330
332
 
331
 
struct hash_iterate_context *hash_iterate_init(struct hash_table *table)
 
333
struct hash_iterate_context *hash_table_iterate_init(struct hash_table *table)
332
334
{
333
335
        struct hash_iterate_context *ctx;
334
336
 
335
 
        hash_freeze(table);
 
337
        hash_table_freeze(table);
336
338
 
337
339
        ctx = i_new(struct hash_iterate_context, 1);
338
340
        ctx->table = table;
340
342
        return ctx;
341
343
}
342
344
 
343
 
static struct hash_node *hash_iterate_next(struct hash_iterate_context *ctx,
344
 
                                           struct hash_node *node)
 
345
static struct hash_node *
 
346
hash_table_iterate_next(struct hash_iterate_context *ctx,
 
347
                        struct hash_node *node)
345
348
{
346
349
        do {
347
350
                node = node->next;
357
360
        return node;
358
361
}
359
362
 
360
 
bool hash_iterate(struct hash_iterate_context *ctx,
361
 
                  void **key_r, void **value_r)
 
363
bool hash_table_iterate(struct hash_iterate_context *ctx,
 
364
                        void **key_r, void **value_r)
362
365
{
363
366
        struct hash_node *node;
364
367
 
365
368
        node = ctx->next;
366
369
        if (node != NULL && node->key == NULL)
367
 
                node = hash_iterate_next(ctx, node);
 
370
                node = hash_table_iterate_next(ctx, node);
368
371
        if (node == NULL) {
369
372
                *key_r = *value_r = NULL;
370
373
                return FALSE;
372
375
        *key_r = node->key;
373
376
        *value_r = node->value;
374
377
 
375
 
        ctx->next = hash_iterate_next(ctx, node);
 
378
        ctx->next = hash_table_iterate_next(ctx, node);
376
379
        return TRUE;
377
380
}
378
381
 
379
 
void hash_iterate_deinit(struct hash_iterate_context **_ctx)
 
382
void hash_table_iterate_deinit(struct hash_iterate_context **_ctx)
380
383
{
381
384
        struct hash_iterate_context *ctx = *_ctx;
382
385
 
383
386
        *_ctx = NULL;
384
 
        hash_thaw(ctx->table);
 
387
        hash_table_thaw(ctx->table);
385
388
        i_free(ctx);
386
389
}
387
390
 
388
 
void hash_freeze(struct hash_table *table)
 
391
void hash_table_freeze(struct hash_table *table)
389
392
{
390
393
        table->frozen++;
391
394
}
392
395
 
393
 
void hash_thaw(struct hash_table *table)
 
396
void hash_table_thaw(struct hash_table *table)
394
397
{
395
398
        i_assert(table->frozen > 0);
396
399
 
398
401
                return;
399
402
 
400
403
        if (table->removed_count > 0) {
401
 
                if (!hash_resize(table, FALSE))
402
 
                        hash_compress_removed(table);
 
404
                if (!hash_table_resize(table, FALSE))
 
405
                        hash_table_compress_removed(table);
403
406
        }
404
407
}
405
408
 
406
 
static bool hash_resize(struct hash_table *table, bool grow)
 
409
static bool hash_table_resize(struct hash_table *table, bool grow)
407
410
{
408
411
        struct hash_node *old_nodes, *node, *next;
409
412
        unsigned int next_size, old_size, i;
436
439
        /* move the data */
437
440
        for (i = 0; i < old_size; i++) {
438
441
                node = &old_nodes[i];
439
 
                if (node->key != NULL)
440
 
                        hash_insert_node(table, node->key, node->value, FALSE);
 
442
                if (node->key != NULL) {
 
443
                        hash_table_insert_node(table, node->key,
 
444
                                               node->value, FALSE);
 
445
                }
441
446
 
442
447
                for (node = node->next; node != NULL; node = next) {
443
448
                        next = node->next;
444
449
 
445
450
                        if (node->key != NULL) {
446
 
                                hash_insert_node(table, node->key,
447
 
                                                 node->value, FALSE);
 
451
                                hash_table_insert_node(table, node->key,
 
452
                                                       node->value, FALSE);
448
453
                        }
449
454
                        free_node(table, node);
450
455
                }
456
461
        return TRUE;
457
462
}
458
463
 
459
 
void hash_copy(struct hash_table *dest, struct hash_table *src)
 
464
void hash_table_copy(struct hash_table *dest, struct hash_table *src)
460
465
{
461
466
        struct hash_iterate_context *iter;
462
467
        void *key, *value;
463
468
 
464
 
        hash_freeze(dest);
465
 
 
466
 
        iter = hash_iterate_init(src);
467
 
        while (hash_iterate(iter, &key, &value))
468
 
                hash_insert(dest, key, value);
469
 
        hash_iterate_deinit(&iter);
470
 
 
471
 
        hash_thaw(dest);
 
469
        hash_table_freeze(dest);
 
470
 
 
471
        iter = hash_table_iterate_init(src);
 
472
        while (hash_table_iterate(iter, &key, &value))
 
473
                hash_table_insert(dest, key, value);
 
474
        hash_table_iterate_deinit(&iter);
 
475
 
 
476
        hash_table_thaw(dest);
472
477
}
473
478
 
474
479
/* a char* hash function from ASU -- from glib */