3 * This is a port of D.J. Bernstein's CDB to PHP. It's based on the copy that
4 * appears in PHP 5.3. Changes are:
5 * * Error returns replaced with exceptions
6 * * Exception thrown if sizes or offsets are between 2GB and 4GB
7 * * Some variables renamed
9 * This program is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22 * http://www.gnu.org/copyleft/gpl.html
28 * Common functions for readers and writers
32 * Take a modulo of a signed integer as if it were an unsigned integer.
33 * $b must be less than 0x40000000 and greater than 0
40 public static function unsignedMod( $a, $b ) {
41 if ( $a & 0x80000000 ) {
42 $m = ( $a & 0x7fffffff ) %
$b +
2 * ( 0x40000000 %
$b );
51 * Shift a signed integer right as if it were unsigned
56 public static function unsignedShiftRight( $a, $b ) {
60 if ( $a & 0x80000000 ) {
61 return ( ( $a & 0x7fffffff ) >> $b ) |
( 0x40000000 >> ( $b - 1 ) );
68 * The CDB hash function.
74 public static function hash( $s ) {
77 for ( $i = 0; $i < $len; $i++
) {
78 $h5 = ( $h << 5 ) & 0xffffffff;
80 // Inlined here for speed
81 $sum = ( $h & 0x3fffffff ) +
( $h5 & 0x3fffffff );
84 ( $sum & 0x40000000 ?
1 : 0 )
85 +
( $h & 0x80000000 ?
2 : 0 )
86 +
( $h & 0x40000000 ?
1 : 0 )
87 +
( $h5 & 0x80000000 ?
2 : 0 )
88 +
( $h5 & 0x40000000 ?
1 : 0 )
90 |
( $sum & 0x3fffffff );
102 class CdbReaderPHP
extends CdbReader
{
106 /** The file handle */
109 /* number of hash slots searched under this key */
112 /* initialized if loop is nonzero */
115 /* initialized if loop is nonzero */
118 /* initialized if loop is nonzero */
121 /* initialized if loop is nonzero */
124 /* initialized if findNext() returns true */
127 /* initialized if cdb_findnext() returns 1 */
131 * @param $fileName string
132 * @throws MWException
134 function __construct( $fileName ) {
135 $this->fileName
= $fileName;
136 $this->handle
= fopen( $fileName, 'rb' );
137 if ( !$this->handle
) {
138 throw new MWException( 'Unable to open CDB file "' . $this->fileName
. '".' );
144 if ( isset( $this->handle
) ) {
145 fclose( $this->handle
);
147 unset( $this->handle
);
152 * @return bool|string
154 public function get( $key ) {
155 // strval is required
156 if ( $this->find( strval( $key ) ) ) {
157 return $this->read( $this->dlen
, $this->dpos
);
168 protected function match( $key, $pos ) {
169 $buf = $this->read( strlen( $key ), $pos );
171 return $buf === $key;
174 protected function findStart() {
179 * @throws MWException
184 protected function read( $length, $pos ) {
185 if ( fseek( $this->handle
, $pos ) == -1 ) {
186 // This can easily happen if the internal pointers are incorrect
187 throw new MWException(
188 'Seek failed, file "' . $this->fileName
. '" may be corrupted.' );
191 if ( $length == 0 ) {
195 $buf = fread( $this->handle
, $length );
196 if ( $buf === false ||
strlen( $buf ) !== $length ) {
197 throw new MWException(
198 'Read from CDB file failed, file "' . $this->fileName
. '" may be corrupted.' );
205 * Unpack an unsigned integer and throw an exception if it needs more than 31 bits
207 * @throws MWException
210 protected function unpack31( $s ) {
211 $data = unpack( 'V', $s );
212 if ( $data[1] > 0x7fffffff ) {
213 throw new MWException(
214 'Error in CDB file "' . $this->fileName
. '", integer too big.' );
221 * Unpack a 32-bit signed integer
225 protected function unpackSigned( $s ) {
226 $data = unpack( 'va/vb', $s );
228 return $data['a'] |
( $data['b'] << 16 );
235 protected function findNext( $key ) {
236 if ( !$this->loop
) {
237 $u = CdbFunctions
::hash( $key );
238 $buf = $this->read( 8, ( $u << 3 ) & 2047 );
239 $this->hslots
= $this->unpack31( substr( $buf, 4 ) );
240 if ( !$this->hslots
) {
243 $this->hpos
= $this->unpack31( substr( $buf, 0, 4 ) );
245 $u = CdbFunctions
::unsignedShiftRight( $u, 8 );
246 $u = CdbFunctions
::unsignedMod( $u, $this->hslots
);
248 $this->kpos
= $this->hpos +
$u;
251 while ( $this->loop
< $this->hslots
) {
252 $buf = $this->read( 8, $this->kpos
);
253 $pos = $this->unpack31( substr( $buf, 4 ) );
259 if ( $this->kpos
== $this->hpos +
( $this->hslots
<< 3 ) ) {
260 $this->kpos
= $this->hpos
;
262 $u = $this->unpackSigned( substr( $buf, 0, 4 ) );
263 if ( $u === $this->khash
) {
264 $buf = $this->read( 8, $pos );
265 $keyLen = $this->unpack31( substr( $buf, 0, 4 ) );
266 if ( $keyLen == strlen( $key ) && $this->match( $key, $pos +
8 ) ) {
268 $this->dlen
= $this->unpack31( substr( $buf, 4 ) );
269 $this->dpos
= $pos +
8 +
$keyLen;
283 protected function find( $key ) {
286 return $this->findNext( $key );
293 class CdbWriterPHP
extends CdbWriter
{
294 var $handle, $realFileName, $tmpFileName;
297 var $numentries, $pos;
300 * @param $fileName string
302 function __construct( $fileName ) {
303 $this->realFileName
= $fileName;
304 $this->tmpFileName
= $fileName . '.tmp.' . mt_rand( 0, 0x7fffffff );
305 $this->handle
= fopen( $this->tmpFileName
, 'wb' );
306 if ( !$this->handle
) {
307 $this->throwException(
308 'Unable to open CDB file "' . $this->tmpFileName
. '" for write.' );
310 $this->hplist
= array();
311 $this->numentries
= 0;
312 $this->pos
= 2048; // leaving space for the pointer array, 256 * 8
313 if ( fseek( $this->handle
, $this->pos
) == -1 ) {
314 $this->throwException( 'fseek failed in file "' . $this->tmpFileName
. '".' );
318 function __destruct() {
319 if ( isset( $this->handle
) ) {
329 public function set( $key, $value ) {
330 if ( strval( $key ) === '' ) {
331 // DBA cross-check hack
334 $this->addbegin( strlen( $key ), strlen( $value ) );
335 $this->write( $key );
336 $this->write( $value );
337 $this->addend( strlen( $key ), strlen( $value ), CdbFunctions
::hash( $key ) );
341 * @throws MWException
343 public function close() {
345 if ( isset( $this->handle
) ) {
346 fclose( $this->handle
);
348 if ( wfIsWindows() && file_exists( $this->realFileName
) ) {
349 unlink( $this->realFileName
);
351 if ( !rename( $this->tmpFileName
, $this->realFileName
) ) {
352 $this->throwException( 'Unable to move the new CDB file into place.' );
354 unset( $this->handle
);
358 * @throws MWException
361 protected function write( $buf ) {
362 $len = fwrite( $this->handle
, $buf );
363 if ( $len !== strlen( $buf ) ) {
364 $this->throwException( 'Error writing to CDB file "' . $this->tmpFileName
. '".' );
369 * @throws MWException
372 protected function posplus( $len ) {
373 $newpos = $this->pos +
$len;
374 if ( $newpos > 0x7fffffff ) {
375 $this->throwException(
376 'A value in the CDB file "' . $this->tmpFileName
. '" is too large.' );
378 $this->pos
= $newpos;
386 protected function addend( $keylen, $datalen, $h ) {
387 $this->hplist
[] = array(
394 $this->posplus( $keylen );
395 $this->posplus( $datalen );
399 * @throws MWException
403 protected function addbegin( $keylen, $datalen ) {
404 if ( $keylen > 0x7fffffff ) {
405 $this->throwException( 'Key length too long in file "' . $this->tmpFileName
. '".' );
407 if ( $datalen > 0x7fffffff ) {
408 $this->throwException( 'Data length too long in file "' . $this->tmpFileName
. '".' );
410 $buf = pack( 'VV', $keylen, $datalen );
411 $this->write( $buf );
415 * @throws MWException
417 protected function finish() {
418 // Hack for DBA cross-check
419 $this->hplist
= array_reverse( $this->hplist
);
421 // Calculate the number of items that will be in each hashtable
422 $counts = array_fill( 0, 256, 0 );
423 foreach ( $this->hplist
as $item ) {
424 ++
$counts[255 & $item['h']];
427 // Fill in $starts with the *end* indexes
430 for ( $i = 0; $i < 256; ++
$i ) {
435 // Excessively clever and indulgent code to simultaneously fill $packedTables
436 // with the packed hashtables, and adjust the elements of $starts
437 // to actually point to the starts instead of the ends.
438 $packedTables = array_fill( 0, $this->numentries
, false );
439 foreach ( $this->hplist
as $item ) {
440 $packedTables[--$starts[255 & $item['h']]] = $item;
444 for ( $i = 0; $i < 256; ++
$i ) {
445 $count = $counts[$i];
447 // The size of the hashtable will be double the item count.
448 // The rest of the slots will be empty.
449 $len = $count +
$count;
450 $final .= pack( 'VV', $this->pos
, $len );
452 $hashtable = array();
453 for ( $u = 0; $u < $len; ++
$u ) {
454 $hashtable[$u] = array( 'h' => 0, 'p' => 0 );
457 // Fill the hashtable, using the next empty slot if the hashed slot
459 for ( $u = 0; $u < $count; ++
$u ) {
460 $hp = $packedTables[$starts[$i] +
$u];
461 $where = CdbFunctions
::unsignedMod(
462 CdbFunctions
::unsignedShiftRight( $hp['h'], 8 ), $len );
463 while ( $hashtable[$where]['p'] ) {
464 if ( ++
$where == $len ) {
468 $hashtable[$where] = $hp;
471 // Write the hashtable
472 for ( $u = 0; $u < $len; ++
$u ) {
474 $hashtable[$u]['h'] & 0xffff,
475 CdbFunctions
::unsignedShiftRight( $hashtable[$u]['h'], 16 ),
476 $hashtable[$u]['p'] );
477 $this->write( $buf );
482 // Write the pointer array at the start of the file
483 rewind( $this->handle
);
484 if ( ftell( $this->handle
) != 0 ) {
485 $this->throwException( 'Error rewinding to start of file "' . $this->tmpFileName
. '".' );
487 $this->write( $final );
491 * Clean up the temp file and throw an exception
494 * @throws MWException
496 protected function throwException( $msg ) {
497 if ( $this->handle
) {
498 fclose( $this->handle
);
499 unlink( $this->tmpFileName
);
501 throw new MWException( $msg );