← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/innobase/include/ut0rnd.ic

Merged in latest plugin-slot-reorg.

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/innobase/include/ut0rnd.ic
1
 
/******************************************************************
2
 
Random numbers and hashing
3
 
 
4
 
(c) 1994, 1995 Innobase Oy
5
 
 
6
 
Created 5/30/1994 Heikki Tuuri
7
 
*******************************************************************/
8
 
 
9
 
#define UT_HASH_RANDOM_MASK     1463735687
10
 
#define UT_HASH_RANDOM_MASK2    1653893711
11
 
#define UT_RND1                 151117737
12
 
#define UT_RND2                 119785373
13
 
#define UT_RND3                  85689495
14
 
#define UT_RND4                  76595339
15
 
#define UT_SUM_RND2              98781234
16
 
#define UT_SUM_RND3             126792457
17
 
#define UT_SUM_RND4              63498502
18
 
#define UT_XOR_RND1             187678878
19
 
#define UT_XOR_RND2             143537923
20
 
 
21
 
extern  ulint    ut_rnd_ulint_counter;
22
 
 
23
 
/************************************************************
24
 
This is used to set the random number seed. */
25
 
UNIV_INLINE
26
 
void
27
 
ut_rnd_set_seed(
28
 
/*============*/
29
 
        ulint    seed)           /* in: seed */
30
 
{
31
 
        ut_rnd_ulint_counter = seed;
32
 
}
33
 
 
34
 
/************************************************************
35
 
The following function generates a series of 'random' ulint integers. */
36
 
UNIV_INLINE
37
 
ulint
38
 
ut_rnd_gen_next_ulint(
39
 
/*==================*/
40
 
                        /* out: the next 'random' number */
41
 
        ulint   rnd)    /* in: the previous random number value */
42
 
{
43
 
        ulint   n_bits;
44
 
 
45
 
        n_bits = 8 * sizeof(ulint);
46
 
 
47
 
        rnd = UT_RND2 * rnd + UT_SUM_RND3;
48
 
        rnd = UT_XOR_RND1 ^ rnd;
49
 
        rnd = (rnd << 20) + (rnd >> (n_bits - 20));
50
 
        rnd = UT_RND3 * rnd + UT_SUM_RND4;
51
 
        rnd = UT_XOR_RND2 ^ rnd;
52
 
        rnd = (rnd << 20) + (rnd >> (n_bits - 20));
53
 
        rnd = UT_RND1 * rnd + UT_SUM_RND2;
54
 
 
55
 
        return(rnd);
56
 
}
57
 
 
58
 
/************************************************************
59
 
The following function generates 'random' ulint integers which
60
 
enumerate the value space of ulint integers in a pseudo random
61
 
fashion. Note that the same integer is repeated always after
62
 
2 to power 32 calls to the generator (if ulint is 32-bit). */
63
 
UNIV_INLINE
64
 
ulint
65
 
ut_rnd_gen_ulint(void)
66
 
/*==================*/
67
 
                        /* out: the 'random' number */
68
 
{
69
 
        ulint   rnd;
70
 
        ulint   n_bits;
71
 
 
72
 
        n_bits = 8 * sizeof(ulint);
73
 
 
74
 
        ut_rnd_ulint_counter = UT_RND1 * ut_rnd_ulint_counter + UT_RND2;
75
 
 
76
 
        rnd = ut_rnd_gen_next_ulint(ut_rnd_ulint_counter);
77
 
 
78
 
        return(rnd);
79
 
}
80
 
 
81
 
/************************************************************
82
 
Generates a random integer from a given interval. */
83
 
UNIV_INLINE
84
 
ulint
85
 
ut_rnd_interval(
86
 
/*============*/
87
 
                        /* out: the 'random' number */
88
 
        ulint   low,    /* in: low limit; can generate also this value */
89
 
        ulint   high)   /* in: high limit; can generate also this value */
90
 
{
91
 
        ulint   rnd;
92
 
 
93
 
        ut_ad(high >= low);
94
 
 
95
 
        if (low == high) {
96
 
 
97
 
                return(low);
98
 
        }
99
 
 
100
 
        rnd = ut_rnd_gen_ulint();
101
 
 
102
 
        return(low + (rnd % (high - low + 1)));
103
 
}
104
 
 
105
 
/*************************************************************
106
 
Generates a random iboolean value. */
107
 
UNIV_INLINE
108
 
ibool
109
 
ut_rnd_gen_ibool(void)
110
 
/*=================*/
111
 
                        /* out: the random value */
112
 
{
113
 
        ulint    x;
114
 
 
115
 
        x = ut_rnd_gen_ulint();
116
 
 
117
 
        if (((x >> 20) + (x >> 15)) & 1) {
118
 
 
119
 
                return(TRUE);
120
 
        }
121
 
 
122
 
        return(FALSE);
123
 
}
124
 
 
125
 
/***********************************************************
126
 
The following function generates a hash value for a ulint integer
127
 
to a hash table of size table_size, which should be a prime
128
 
or some random number for the hash table to work reliably. */
129
 
UNIV_INLINE
130
 
ulint
131
 
ut_hash_ulint(
132
 
/*==========*/
133
 
                                /* out: hash value */
134
 
        ulint    key,           /* in: value to be hashed */
135
 
        ulint    table_size)    /* in: hash table size */
136
 
{
137
 
        key = key ^ UT_HASH_RANDOM_MASK2;
138
 
 
139
 
        return(key % table_size);
140
 
}
141
 
 
142
 
/*****************************************************************
143
 
Folds a pair of ulints. */
144
 
UNIV_INLINE
145
 
ulint
146
 
ut_fold_ulint_pair(
147
 
/*===============*/
148
 
                        /* out: folded value */
149
 
        ulint   n1,     /* in: ulint */
150
 
        ulint   n2)     /* in: ulint */
151
 
{
152
 
        return(((((n1 ^ n2 ^ UT_HASH_RANDOM_MASK2) << 8) + n1)
153
 
                ^ UT_HASH_RANDOM_MASK) + n2);
154
 
}
155
 
 
156
 
/*****************************************************************
157
 
Folds a dulint. */
158
 
UNIV_INLINE
159
 
ulint
160
 
ut_fold_dulint(
161
 
/*===========*/
162
 
                        /* out: folded value */
163
 
        dulint  d)      /* in: dulint */
164
 
{
165
 
        return(ut_fold_ulint_pair(ut_dulint_get_low(d),
166
 
                                  ut_dulint_get_high(d)));
167
 
}
168
 
 
169
 
/*****************************************************************
170
 
Folds a character string ending in the null character. */
171
 
UNIV_INLINE
172
 
ulint
173
 
ut_fold_string(
174
 
/*===========*/
175
 
                                /* out: folded value */
176
 
        const char*     str)    /* in: null-terminated string */
177
 
{
178
 
#ifdef UNIV_DEBUG
179
 
        ulint   i = 0;
180
 
#endif
181
 
        ulint   fold = 0;
182
 
 
183
 
        ut_ad(str);
184
 
 
185
 
        while (*str != '\0') {
186
 
 
187
 
#ifdef UNIV_DEBUG
188
 
                i++;
189
 
                ut_a(i < 100);
190
 
#endif
191
 
 
192
 
                fold = ut_fold_ulint_pair(fold, (ulint)(*str));
193
 
                str++;
194
 
        }
195
 
 
196
 
        return(fold);
197
 
}
198
 
 
199
 
/*****************************************************************
200
 
Folds a binary string. */
201
 
UNIV_INLINE
202
 
ulint
203
 
ut_fold_binary(
204
 
/*===========*/
205
 
                                /* out: folded value */
206
 
        const byte*     str,    /* in: string of bytes */
207
 
        ulint           len)    /* in: length */
208
 
{
209
 
        const byte*     str_end = str + len;
210
 
        ulint           fold = 0;
211
 
 
212
 
        ut_ad(str);
213
 
 
214
 
        while (str < str_end) {
215
 
                fold = ut_fold_ulint_pair(fold, (ulint)(*str));
216
 
 
217
 
                str++;
218
 
        }
219
 
 
220
 
        return(fold);
221
 
}