(bug 19441) Updated date formatting for Lithuanian
[mediawiki.git] / includes / Cdb_PHP.php
blobf2a044c55bd1a235b05f3f2a3c4faa7c6dc2196e
1 <?php
3 /**
4 * This is a port of D.J. Bernstein's CDB to PHP. It's based on the copy that
5 * appears in PHP 5.3. Changes are:
6 * * Error returns replaced with exceptions
7 * * Exception thrown if sizes or offsets are between 2GB and 4GB
8 * * Some variables renamed
9 */
11 /**
12 * Common functions for readers and writers
14 class CdbFunctions {
15 /**
16 * Take a modulo of a signed integer as if it were an unsigned integer.
17 * $b must be less than 0x40000000 and greater than 0
19 public static function unsignedMod( $a, $b ) {
20 if ( $a < 0 ) {
21 $m = ( $a & 0x7fffffff ) % $b + 2 * ( 0x40000000 % $b );
22 return $m % $b;
23 } else {
24 return $a % $b;
28 /**
29 * Shift a signed integer right as if it were unsigned
31 public static function unsignedShiftRight( $a, $b ) {
32 if ( $b == 0 ) {
33 return $a;
35 if ( $a < 0 ) {
36 return ( ( $a & 0x7fffffff ) >> $b ) | ( 0x40000000 >> ( $b - 1 ) );
37 } else {
38 return $a >> $b;
42 /**
43 * The CDB hash function.
45 public static function hash( $s ) {
46 $h = 5381;
47 for ( $i = 0; $i < strlen( $s ); $i++ ) {
48 $h5 = $h << 5;
49 // Do a 32-bit sum
50 // Inlined here for speed
51 $sum = ($h & 0x3fffffff) + ($h5 & 0x3fffffff);
52 $h =
54 ( $sum & 0x40000000 ? 1 : 0 )
55 + ( $h < 0 ? 2 : 0 )
56 + ( $h & 0x40000000 ? 1 : 0 )
57 + ( $h5 < 0 ? 2 : 0 )
58 + ( $h5 & 0x40000000 ? 1 : 0 )
59 ) << 30
60 | ( $sum & 0x3fffffff );
61 $h ^= ord( $s[$i] );
63 return $h;
67 /**
68 * CDB reader class
70 class CdbReader_PHP extends CdbReader {
71 /** The file handle */
72 var $handle;
74 /* number of hash slots searched under this key */
75 var $loop;
77 /* initialized if loop is nonzero */
78 var $khash;
80 /* initialized if loop is nonzero */
81 var $kpos;
83 /* initialized if loop is nonzero */
84 var $hpos;
86 /* initialized if loop is nonzero */
87 var $hslots;
89 /* initialized if findNext() returns true */
90 var $dpos;
92 /* initialized if cdb_findnext() returns 1 */
93 var $dlen;
95 function __construct( $fileName ) {
96 $this->handle = fopen( $fileName, 'rb' );
97 if ( !$this->handle ) {
98 throw new MWException( 'Unable to open DB file "' . $fileName . '"' );
100 $this->findStart();
103 function close() {
104 fclose( $this->handle );
105 unset( $this->handle );
108 public function get( $key ) {
109 // strval is required
110 if ( $this->find( strval( $key ) ) ) {
111 return $this->read( $this->dlen, $this->dpos );
112 } else {
113 return false;
117 protected function match( $key, $pos ) {
118 $buf = $this->read( strlen( $key ), $pos );
119 return $buf === $key;
122 protected function findStart() {
123 $this->loop = 0;
126 protected function read( $length, $pos ) {
127 if ( fseek( $this->handle, $pos ) == -1 ) {
128 // This can easily happen if the internal pointers are incorrect
129 throw new MWException( __METHOD__.': seek failed, file may be corrupted.' );
132 if ( $length == 0 ) {
133 return '';
136 $buf = fread( $this->handle, $length );
137 if ( $buf === false || strlen( $buf ) !== $length ) {
138 throw new MWException( __METHOD__.': read from cdb file failed, file may be corrupted' );
140 return $buf;
144 * Unpack an unsigned integer and throw an exception if it needs more than 31 bits
146 protected function unpack31( $s ) {
147 $data = unpack( 'V', $s );
148 if ( $data[1] > 0x7fffffff ) {
149 throw new MWException( __METHOD__.': error in CDB file, integer too big' );
151 return $data[1];
155 * Unpack a 32-bit signed integer
157 protected function unpackSigned( $s ) {
158 $data = unpack( 'va/vb', $s );
159 return $data['a'] | ( $data['b'] << 16 );
162 protected function findNext( $key ) {
163 if ( !$this->loop ) {
164 $u = CdbFunctions::hash( $key );
165 $buf = $this->read( 8, ( $u << 3 ) & 2047 );
166 $this->hslots = $this->unpack31( substr( $buf, 4 ) );
167 if ( !$this->hslots ) {
168 return false;
170 $this->hpos = $this->unpack31( substr( $buf, 0, 4 ) );
171 $this->khash = $u;
172 $u = CdbFunctions::unsignedShiftRight( $u, 8 );
173 $u = CdbFunctions::unsignedMod( $u, $this->hslots );
174 $u <<= 3;
175 $this->kpos = $this->hpos + $u;
178 while ( $this->loop < $this->hslots ) {
179 $buf = $this->read( 8, $this->kpos );
180 $pos = $this->unpack31( substr( $buf, 4 ) );
181 if ( !$pos ) {
182 return false;
184 $this->loop += 1;
185 $this->kpos += 8;
186 if ( $this->kpos == $this->hpos + ( $this->hslots << 3 ) ) {
187 $this->kpos = $this->hpos;
189 $u = $this->unpackSigned( substr( $buf, 0, 4 ) );
190 if ( $u === $this->khash ) {
191 $buf = $this->read( 8, $pos );
192 $keyLen = $this->unpack31( substr( $buf, 0, 4 ) );
193 if ( $keyLen == strlen( $key ) && $this->match( $key, $pos + 8 ) ) {
194 // Found
195 $this->dlen = $this->unpack31( substr( $buf, 4 ) );
196 $this->dpos = $pos + 8 + $keyLen;
197 return true;
201 return false;
204 protected function find( $key ) {
205 $this->findStart();
206 return $this->findNext( $key );
211 * CDB writer class
213 class CdbWriter_PHP extends CdbWriter {
214 var $handle, $realFileName, $tmpFileName;
216 var $hplist;
217 var $numEntries, $pos;
219 function __construct( $fileName ) {
220 $this->realFileName = $fileName;
221 $this->tmpFileName = $fileName . '.tmp.' . mt_rand( 0, 0x7fffffff );
222 $this->handle = fopen( $this->tmpFileName, 'wb' );
223 if ( !$this->handle ) {
224 throw new MWException( 'Unable to open DB file for write "' . $fileName . '"' );
226 $this->hplist = array();
227 $this->numentries = 0;
228 $this->pos = 2048; // leaving space for the pointer array, 256 * 8
229 if ( fseek( $this->handle, $this->pos ) == -1 ) {
230 throw new MWException( __METHOD__.': fseek failed' );
234 function __destruct() {
235 if ( isset( $this->handle ) ) {
236 $this->close();
240 public function set( $key, $value ) {
241 if ( strval( $key ) === '' ) {
242 // DBA cross-check hack
243 return;
245 $this->addbegin( strlen( $key ), strlen( $value ) );
246 $this->write( $key );
247 $this->write( $value );
248 $this->addend( strlen( $key ), strlen( $value ), CdbFunctions::hash( $key ) );
251 public function close() {
252 $this->finish();
253 fclose( $this->handle );
254 if ( wfIsWindows() ) {
255 unlink( $this->realFileName );
257 if ( !rename( $this->tmpFileName, $this->realFileName ) ) {
258 throw new MWException( 'Unable to move the new CDB file into place.' );
260 unset( $this->handle );
263 protected function write( $buf ) {
264 $len = fwrite( $this->handle, $buf );
265 if ( $len !== strlen( $buf ) ) {
266 throw new MWException( 'Error writing to CDB file.' );
270 protected function posplus( $len ) {
271 $newpos = $this->pos + $len;
272 if ( $newpos > 0x7fffffff ) {
273 throw new MWException( 'A value in the CDB file is too large' );
275 $this->pos = $newpos;
278 protected function addend( $keylen, $datalen, $h ) {
279 $this->hplist[] = array(
280 'h' => $h,
281 'p' => $this->pos
284 $this->numentries++;
285 $this->posplus( 8 );
286 $this->posplus( $keylen );
287 $this->posplus( $datalen );
290 protected function addbegin( $keylen, $datalen ) {
291 if ( $keylen > 0x7fffffff ) {
292 throw new MWException( __METHOD__.': key length too long' );
294 if ( $datalen > 0x7fffffff ) {
295 throw new MWException( __METHOD__.': data length too long' );
297 $buf = pack( 'VV', $keylen, $datalen );
298 $this->write( $buf );
301 protected function finish() {
302 // Hack for DBA cross-check
303 $this->hplist = array_reverse( $this->hplist );
305 // Calculate the number of items that will be in each hashtable
306 $counts = array_fill( 0, 256, 0 );
307 foreach ( $this->hplist as $item ) {
308 ++ $counts[ 255 & $item['h'] ];
311 // Fill in $starts with the *end* indexes
312 $starts = array();
313 $pos = 0;
314 for ( $i = 0; $i < 256; ++$i ) {
315 $pos += $counts[$i];
316 $starts[$i] = $pos;
319 // Excessively clever and indulgent code to simultaneously fill $packedTables
320 // with the packed hashtables, and adjust the elements of $starts
321 // to actually point to the starts instead of the ends.
322 $packedTables = array_fill( 0, $this->numentries, false );
323 foreach ( $this->hplist as $item ) {
324 $packedTables[--$starts[255 & $item['h']]] = $item;
327 $final = '';
328 for ( $i = 0; $i < 256; ++$i ) {
329 $count = $counts[$i];
331 // The size of the hashtable will be double the item count.
332 // The rest of the slots will be empty.
333 $len = $count + $count;
334 $final .= pack( 'VV', $this->pos, $len );
336 $hashtable = array();
337 for ( $u = 0; $u < $len; ++$u ) {
338 $hashtable[$u] = array( 'h' => 0, 'p' => 0 );
341 // Fill the hashtable, using the next empty slot if the hashed slot
342 // is taken.
343 for ( $u = 0; $u < $count; ++$u ) {
344 $hp = $packedTables[$starts[$i] + $u];
345 $where = CdbFunctions::unsignedMod(
346 CdbFunctions::unsignedShiftRight( $hp['h'], 8 ), $len );
347 while ( $hashtable[$where]['p'] )
348 if ( ++$where == $len )
349 $where = 0;
350 $hashtable[$where] = $hp;
353 // Write the hashtable
354 for ( $u = 0; $u < $len; ++$u ) {
355 $buf = pack( 'vvV',
356 $hashtable[$u]['h'] & 0xffff,
357 CdbFunctions::unsignedShiftRight( $hashtable[$u]['h'], 16 ),
358 $hashtable[$u]['p'] );
359 $this->write( $buf );
360 $this->posplus( 8 );
364 // Write the pointer array at the start of the file
365 rewind( $this->handle );
366 if ( ftell( $this->handle ) != 0 ) {
367 throw new MWException( __METHOD__.': Error rewinding to start of file' );
369 $this->write( $final );