← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

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

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

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
}