← Back to branch summary

~ubuntu-branches/ubuntu/trusty/ocamlnet/trusty

« back to all changes in this revision

Viewing changes to src/netsys/netsys_c_htab.c

  • Committer: Bazaar Package Importer
  • Author(s): Stéphane Glondu
  • Date: 2011-09-02 14:12:33 UTC
  • mfrom: (18.2.3 sid)
  • Revision ID: james.westby@ubuntu.com-20110902141233-zbj0ygxb92u6gy4z
Tags: 3.4-1
http://bugs.debian.org/637147
* New upstream release
  - add a new NetcgiRequire directive to ease dependency management
    (Closes: #637147)
  - remove patches that were applied upstream:
    + Added-missing-shebang-lines-in-example-shell-scripts
    + Try-also-ocamlc-for-POSIX-threads

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/netsys/netsys_c_htab.c
 
1
/* $Id: netsys_c_htab.c 1497 2010-11-28 22:13:46Z gerd $ */
 
2
 
 
3
#include "netsys_c_htab.h"
 
4
#include <stdlib.h>
 
5
#include <errno.h>
 
6
#include <string.h>
 
7
 
 
8
/* Define an FNV-1 hash function
 
9
   (see http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash)
 
10
 
 
11
   All artithmetic is unsigned!
 
12
*/
 
13
#ifdef ARCH_SIXTYFOUR
 
14
/* 64 bit */
 
15
#define P 1099511628211
 
16
#define S 0xcbf29ce484222325
 
17
#define H(x,n) \
 
18
  ((((((((((((((((S * P) ^ ((x >> 56) & 0xff)) * \
 
19
  P) ^ ((x >> 48) & 0xff)) * \
 
20
  P) ^ ((x >> 40) & 0xff)) * \
 
21
  P) ^ ((x >> 32) & 0xff)) * \
 
22
  P) ^ ((x >> 24) & 0xff)) * \
 
23
  P) ^ ((x >> 16) & 0xff)) * \
 
24
  P) ^ ((x >> 8) & 0xff)) * \
 
25
  P) ^ (x & 0xff)) % n
 
26
#else
 
27
/* 32 bit */
 
28
#define S 0x811c9dc5
 
29
#define P 16777619
 
30
#define H(x,n) \
 
31
  ((((((((S * P) ^ ((x >> 24) & 0xff)) * P) ^ ((x >> 16) & 0xff)) * \
 
32
  P) ^ ((x >> 8) & 0xff)) * P) ^ (x & 0xff)) % n
 
33
#endif
 
34
 
 
35
 
 
36
static void netsys_htab_add_1(struct htab *t, void *a1, void *a2)
 
37
{
 
38
    unsigned long i1, h1, size;
 
39
    struct htab_cell *table;
 
40
 
 
41
    table = t->table;
 
42
    size = t->table_size;
 
43
    i1 = (unsigned long) a1;
 
44
    h1 = H(i1, size);
 
45
    while (table[h1].orig_addr != NULL) {
 
46
        h1++;
 
47
        if (h1 == size) h1 = 0;
 
48
    }
 
49
    table[h1].orig_addr = a1;
 
50
    table[h1].relo_addr = a2;
 
51
    t->table_used++;
 
52
}
 
53
 
 
54
 
 
55
static int netsys_htab_grow(struct htab *t, unsigned long n)
 
56
{
 
57
    struct htab_cell *old_table;
 
58
    struct htab_cell *new_table;
 
59
    unsigned long k, old_size;
 
60
 
 
61
    if (n < t->table_size) return (-2);
 
62
 
 
63
    old_table = t->table;
 
64
    old_size = t->table_size;
 
65
 
 
66
    new_table = (struct htab_cell *) malloc(n * sizeof(struct htab_cell));
 
67
    if (new_table == NULL) {
 
68
        errno = ENOMEM;
 
69
        return (-1);
 
70
    } 
 
71
 
 
72
    for (k=0; k<n; k++) {
 
73
        new_table[k].orig_addr = NULL;
 
74
        new_table[k].relo_addr = NULL;
 
75
    }
 
76
 
 
77
    t->table = new_table;
 
78
    t->table_size = n;
 
79
    t->table_used = 0;
 
80
 
 
81
    if (old_table != NULL) {
 
82
        for (k=0; k<old_size; k++) {
 
83
            if (old_table[k].orig_addr != NULL) {
 
84
                netsys_htab_add_1(t, 
 
85
                                  old_table[k].orig_addr, 
 
86
                                  old_table[k].relo_addr);
 
87
            }
 
88
        }
 
89
 
 
90
        free(old_table);
 
91
    };
 
92
 
 
93
    return 0;
 
94
}
 
95
 
 
96
 
 
97
int netsys_htab_init(struct htab *t, unsigned long n)
 
98
{
 
99
    t->table = NULL;
 
100
    t->table_size = 0;
 
101
    t->table_used = 0;
 
102
    return netsys_htab_grow(t, n);
 
103
}
 
104
 
 
105
 
 
106
void netsys_htab_clear(struct htab *t) 
 
107
{
 
108
    unsigned long k, size;
 
109
    struct htab_cell *table;
 
110
 
 
111
    size = t->table_size;
 
112
    table = t->table;
 
113
    memset(table, 0, size * sizeof(struct htab_cell));
 
114
    t->table_used = 0;
 
115
}
 
116
 
 
117
 
 
118
int netsys_htab_add(struct htab *t, void *a1, void *a2)
 
119
{
 
120
    int code;
 
121
 
 
122
    if (a1 == NULL || a2 == NULL) return (-2);
 
123
 
 
124
    if (2 * t->table_used > t->table_size) {
 
125
        code = netsys_htab_grow(t, 2 * t->table_size);
 
126
        if (code < 0) return code;
 
127
    }
 
128
 
 
129
    netsys_htab_add_1(t, a1, a2);
 
130
    return 0;
 
131
}
 
132
 
 
133
 
 
134
int netsys_htab_lookup(struct htab *t, 
 
135
                       void *a1, void **a2p)
 
136
{
 
137
    unsigned long i1, h1, size;
 
138
    struct htab_cell *table;
 
139
 
 
140
    table = t->table;
 
141
    size = t->table_size;
 
142
    i1 = (unsigned long) a1;
 
143
    h1 = H(i1, size);
 
144
    while (table[h1].orig_addr != NULL && table[h1].orig_addr != a1) {
 
145
        h1++;
 
146
        if (h1 == size) h1 = 0;
 
147
    }
 
148
    if (table[h1].orig_addr == NULL)
 
149
        *a2p = NULL;
 
150
    else
 
151
        *a2p = table[h1].relo_addr;
 
152
 
 
153
    return 0;
 
154
}
 
155
 
 
156
 
 
157
void netsys_htab_free(struct htab *t)
 
158
{
 
159
    free(t->table);
 
160
    t->table = NULL;
 
161
}
 
162