lib/WikiDB/backend/dbaBase.php

   1 <?php rcs_id('$Id: dbaBase.php,v 1.22 2005-08-07 10:11:24 rurban Exp $');
   2
   3 require_once('lib/WikiDB/backend.php');
   4
   5 // FIXME:padding of data?  Is it needed?  dba_optimize() seems to do a good
   6 // job at packing 'gdbm' (and 'db2') databases.
   7
   8 /*
   9  * Tables:
  10  *
  11  *  page:
  12  *   Index: pagename
  13  *  Values: latestversion . ':' . flags . ':' serialized hash of page meta data
  14  *           Currently flags = 1 if latest version has empty content.
  15  *
  16  *  version
  17  *   Index: version:pagename
  18  *   Value: serialized hash of revision meta data, including:
  19  *          + quasi-meta-data %content
  20  *
  21  *  links
  22  *   index: 'o' . pagename
  23  *   value: serialized list of pages (names) which pagename links to.
  24  *   index: 'i' . pagename
  25  *   value: serialized list of pages which link to pagename
  26  *
  27  *  TODO:
  28  *  Don't keep tables locked the whole time
  29  *
  30  *  index table with:
  31  *   list of pagenames for get_all_pages
  32  *   mostpopular list?
  33  *   RecentChanges support:
  34  *     lists of most recent edits (major, minor, either).
  35  *
  36  *
  37  *  Separate hit table, so we don't have to update the whole page entry
  38  *  each time we get a hit.  (Maybe not so important though...).
  39  */
  40
  41 require_once('lib/DbaPartition.php');
  42
  43 class WikiDB_backend_dbaBase
  44 extends WikiDB_backend
  45 {
  46     function WikiDB_backend_dbaBase (&$dba) {
  47         $this->_db = &$dba;
  48         // TODO: page and version tables should be in their own files, probably.
  49         // We'll pack them all in one for now (testing).
  50         // 2004-07-09 10:07:30 rurban: It's fast enough this way.
  51         $this->_pagedb = new DbaPartition($dba, 'p');
  52         $this->_versiondb = new DbaPartition($dba, 'v');
  53         $linkdbpart = new DbaPartition($dba, 'l');
  54         $this->_linkdb = new WikiDB_backend_dbaBase_linktable($linkdbpart);
  55         $this->_dbdb = new DbaPartition($dba, 'd');
  56     }
  57
  58     function sortable_columns() {
  59         return array('pagename','mtime'/*,'author_id','author'*/);
  60     }
  61
  62     function close() {
  63         $this->_db->close();
  64     }
  65
  66     function optimize() {
  67         $this->_db->optimize();
  68     }
  69
  70     function sync() {
  71         $this->_db->sync();
  72     }
  73
  74     function rebuild() {
  75         $this->_linkdb->rebuild();
  76         $this->optimize();
  77     }
  78
  79     function check() {
  80         return $this->_linkdb->check();
  81     }
  82
  83     function get_pagedata($pagename) {
  84         $result = $this->_pagedb->get($pagename);
  85         if (!$result)
  86             return false;
  87         list(,,$packed) = explode(':', $result, 3);
  88         $data = unserialize($packed);
  89         return $data;
  90     }
  91
  92     function update_pagedata($pagename, $newdata) {
  93         $result = $this->_pagedb->get($pagename);
  94         if ($result) {
  95             list($latestversion,$flags,$data) = explode(':', $result, 3);
  96             $data = unserialize($data);
  97         }
  98         else {
  99             $latestversion = $flags = 0;
 100             $data = array();
 101         }
 102
 103         foreach ($newdata as $key => $val) {
 104             if (empty($val))
 105                 unset($data[$key]);
 106             else
 107                 $data[$key] = $val;
 108         }
 109         $this->_pagedb->set($pagename,
 110                             (int)$latestversion . ':'
 111                             . (int)$flags . ':'
 112                             . serialize($data));
 113     }
 114
 115     function get_latest_version($pagename) {
 116         return (int) $this->_pagedb->get($pagename);
 117     }
 118
 119     function get_previous_version($pagename, $version) {
 120         $versdb = &$this->_versiondb;
 121
 122         while (--$version > 0) {
 123             if ($versdb->exists($version . ":$pagename"))
 124                 return $version;
 125         }
 126         return false;
 127     }
 128
 129     //check $want_content
 130     function get_versiondata($pagename, $version, $want_content=false) {
 131         $data = $this->_versiondb->get((int)$version . ":$pagename");
 132         if (empty($data)) return false;
 133         else {
 134             $data = unserialize($data);
 135             if (!$want_content)
 136                 $data['%content'] = !empty($data['%content']);
 137             return $data;
 138         }
 139     }
 140
 141     /**
 142      * See ADODB for a better delete_page(), which can be undone and is seen in RecentChanges.
 143      * See backend.php
 144      */
 145     //function delete_page($pagename) { $this->purge_page($pagename);  }
 146
 147     /**
 148      * Completely delete page from the database.
 149      */
 150     function purge_page($pagename) {
 151         $pagedb = &$this->_pagedb;
 152         $versdb = &$this->_versiondb;
 153
 154         $version = $this->get_latest_version($pagename);
 155         while ($version > 0) {
 156             $versdb->set($version-- . ":$pagename", false);
 157         }
 158         $pagedb->set($pagename, false);
 159
 160         $this->set_links($pagename, false);
 161     }
 162
 163     function rename_page($pagename, $to) {
 164         $result = $this->_pagedb->get($pagename);
 165         if ($result) {
 166             list($version,$flags,$data) = explode(':', $result, 3);
 167             $data = unserialize($data);
 168         }
 169         else
 170             return false;
 171
 172         $this->_pagedb->delete($pagename);
 173         $data['pagename'] = $to;
 174         $this->_pagedb->set($to,
 175                             (int)$version . ':'
 176                             . (int)$flags . ':'
 177                             . serialize($data));
 178         // move over the latest version only
 179         $pvdata = $this->get_versiondata($pagename, $version, true);
 180         $this->set_versiondata($to, $version, $pvdata);
 181         return true;
 182     }
 183
 184     /**
 185      * Delete an old revision of a page.
 186      */
 187     function delete_versiondata($pagename, $version) {
 188         $versdb = &$this->_versiondb;
 189
 190         $latest = $this->get_latest_version($pagename);
 191
 192         assert($version > 0);
 193         assert($version <= $latest);
 194
 195         $versdb->set((int)$version . ":$pagename", false);
 196
 197         if ($version == $latest) {
 198             $previous = $this->get_previous_version($version);
 199             if ($previous > 0) {
 200                 $pvdata = $this->get_versiondata($pagename, $previous);
 201                 $is_empty = empty($pvdata['%content']);
 202             }
 203             else
 204                 $is_empty = true;
 205             $this->_update_latest_version($pagename, $previous, $is_empty);
 206         }
 207     }
 208
 209     /**
 210      * Create a new revision of a page.
 211      */
 212     function set_versiondata($pagename, $version, $data) {
 213         $versdb = &$this->_versiondb;
 214
 215         $versdb->set((int)$version . ":$pagename", serialize($data));
 216         if ($version > $this->get_latest_version($pagename))
 217             $this->_update_latest_version($pagename, $version, empty($data['%content']));
 218     }
 219
 220     function _update_latest_version($pagename, $latest, $flags) {
 221         $pagedb = &$this->_pagedb;
 222
 223         $pdata = $pagedb->get($pagename);
 224         if ($pdata)
 225             list(,,$pagedata) = explode(':',$pdata,3);
 226         else
 227             $pagedata = serialize(array());
 228
 229         $pagedb->set($pagename, (int)$latest . ':' . (int)$flags . ":$pagedata");
 230     }
 231
 232     function numPages($include_empty=false, $exclude=false) {
 233         $pagedb = &$this->_pagedb;
 234         $count = 0;
 235         for ($page = $pagedb->firstkey(); $page!== false; $page = $pagedb->nextkey()) {
 236             if (!$page) {
 237                 assert(!empty($page));
 238                 continue;
 239             }
 240             if ($exclude and in_array($page, $exclude)) continue;
 241             if (!$include_empty) {
 242                 if (!($data = $pagedb->get($page))) continue;
 243                 list($latestversion,$flags,) = explode(':', $data, 3);
 244                 unset($data);
 245                 if ($latestversion == 0 || $flags != 0)
 246                     continue;   // current content is empty
 247             }
 248             $count++;
 249         }
 250         return $count;
 251     }
 252
 253     function get_all_pages($include_empty=false, $sortby=false, $limit=false, $exclude=false) {
 254         $pagedb = &$this->_pagedb;
 255         $pages = array();
 256         for ($page = $pagedb->firstkey(); $page!== false; $page = $pagedb->nextkey()) {
 257             if (!$page) {
 258                 assert(!empty($page));
 259                 continue;
 260             }
 261             if ($exclude and in_array($page, $exclude)) continue;
 262             if ($limit and count($pages) > $limit) break;
 263             if (!$include_empty) {
 264                 if (!($data = $pagedb->get($page))) continue;
 265                 list($latestversion,$flags,) = explode(':', $data, 3);
 266                 unset($data);
 267                 if ($latestversion == 0 || $flags != 0)
 268                     continue;   // current content is empty
 269             }
 270             $pages[] = $page;
 271         }
 272         return new WikiDB_backend_dbaBase_pageiter($this, $pages,
 273                                                    array('sortby'=>$sortby,
 274                                                          'limit' =>$limit));
 275     }
 276
 277     function set_links($pagename, $links) {
 278         $this->_linkdb->set_links($pagename, $links);
 279     }
 280
 281     function get_links($pagename, $reversed=true, $include_empty=false,
 282                        $sortby=false, $limit=false, $exclude=false) {
 283         $links = $this->_linkdb->get_links($pagename, $reversed);
 284         return new WikiDB_backend_dbaBase_pageiter($this, $links,
 285                                                    array('sortby'=>$sortby,
 286                                                          'limit' =>$limit,
 287                                                          'exclude'=>$exclude,
 288                                                          ));
 289     }
 290 };
 291
 292 function WikiDB_backend_dbaBase_sortby_pagename_ASC ($a, $b) {
 293     return strcasecmp($a, $b);
 294 }
 295 function WikiDB_backend_dbaBase_sortby_pagename_DESC ($a, $b) {
 296     return strcasecmp($b, $a);
 297 }
 298 function WikiDB_backend_dbaBase_sortby_mtime_ASC ($a, $b) {
 299     return WikiDB_backend_dbaBase_sortby_num($a, $b, 'mtime');
 300 }
 301 function WikiDB_backend_dbaBase_sortby_mtime_DESC ($a, $b) {
 302     return WikiDB_backend_dbaBase_sortby_num($b, $a, 'mtime');
 303 }
 304 /*
 305 function WikiDB_backend_dbaBase_sortby_hits_ASC ($a, $b) {
 306     return WikiDB_backend_dbaBase_sortby_num($a, $b, 'hits');
 307 }
 308 function WikiDB_backend_dbaBase_sortby_hits_DESC ($a, $b) {
 309     return WikiDB_backend_dbaBase_sortby_num($b, $a, 'hits');
 310 }
 311 */
 312 function WikiDB_backend_dbaBase_sortby_num($aname, $bname, $field) {
 313     global $request;
 314     $dbi = $request->getDbh();
 315     // fields are stored in versiondata
 316     $av = $dbi->_backend->get_latest_version($aname);
 317     $bv = $dbi->_backend->get_latest_version($bname);
 318     $a = $dbi->_backend->get_versiondata($aname, $av, false);
 319     if (!$a) return 0;
 320     $b = $dbi->_backend->get_versiondata($bname, $bv, false);
 321     if (!$b) return 0;
 322     if ((!isset($a[$field]) && !isset($b[$field])) || ($a[$field] === $b[$field])) {
 323         return 0;
 324     } else {
 325         return (!isset($a[$field]) || ($a[$field] < $b[$field])) ? -1 : 1;
 326     }
 327 }
 328
 329 class WikiDB_backend_dbaBase_pageiter
 330 extends WikiDB_backend_iterator
 331 {
 332     function WikiDB_backend_dbaBase_pageiter(&$backend, &$pages, $options=false) {
 333         $this->_backend = $backend;
 334         $this->_options = $options;
 335         if ($pages) {
 336             if (!empty($options['sortby'])) {
 337                 $sortby = WikiDB_backend::sortby($options['sortby'], 'db', array('pagename','mtime'));
 338                 if ($sortby and !strstr($sortby, "hits ")) { // check for which column to sortby
 339                     usort($pages, 'WikiDB_backend_dbaBase_sortby_'.str_replace(' ','_',$sortby));
 340                 }
 341             }
 342             if (!empty($options['limit'])) {
 343                 list($offset,$limit) = WikiDB_backend::limit($options['limit']);
 344                 $pages = array_slice($pages, $offset, $limit);
 345             }
 346             $this->_pages = $pages;
 347         } else
 348             $this->_pages = array();
 349     }
 350
 351     function next() {
 352         if ( ! ($next = array_shift($this->_pages)) )
 353             return false;
 354         if (!empty($options['exclude']) and in_array($next, $options['exclude']))
 355             return $this->next();
 356         return array('pagename' => $next);
 357     }
 358
 359     function count() {
 360         return count($this->_pages);
 361     }
 362
 363     function asArray() {
 364         reset($this->_pages);
 365         return $this->_pages;
 366     }
 367
 368     function free() {
 369         $this->_pages = array();
 370     }
 371 };
 372
 373 class WikiDB_backend_dbaBase_linktable
 374 {
 375     function WikiDB_backend_dbaBase_linktable(&$dba) {
 376         $this->_db = &$dba;
 377     }
 378
 379     //FIXME: try storing link lists as hashes rather than arrays.
 380     // (backlink deletion would be faster.)
 381     function get_links($page, $reversed=true) {
 382         return $this->_get_links($reversed ? 'i' : 'o', $page);
 383     }
 384
 385     function set_links($page, $newlinks) {
 386
 387         $oldlinks = $this->_get_links('o', $page);
 388
 389         if (!is_array($newlinks)) {
 390             assert(empty($newlinks));
 391             $newlinks = array();
 392         }
 393         else {
 394             $newlinks = array_unique($newlinks);
 395         }
 396         sort($newlinks);
 397         $this->_set_links('o', $page, $newlinks);
 398
 399         reset($newlinks);
 400         reset($oldlinks);
 401         $new = current($newlinks);
 402         $old = current($oldlinks);
 403         while ($new !== false || $old !== false) {
 404             if ($old === false || ($new !== false && $new < $old)) {
 405                 // $new is a new link (not in $oldlinks).
 406                 $this->_add_backlink($new, $page);
 407                 $new = next($newlinks);
 408             }
 409             elseif ($new === false || $old < $new) {
 410                 // $old is a obsolete link (not in $newlinks).
 411                 $this->_delete_backlink($old, $page);
 412                 $old = next($oldlinks);
 413             }
 414             else {
 415                 // Unchanged link (in both $newlist and $oldlinks).
 416                 assert($new == $old);
 417                 $new = next($newlinks);
 418                 $old = next($oldlinks);
 419             }
 420         }
 421     }
 422
 423     /**
 424      * Rebuild the back-link index.
 425      *
 426      * This should never be needed, but if the database gets hosed for some reason,
 427      * this should put it back into a consistent state.
 428      *
 429      * We assume the forward links in the our table are correct, and recalculate
 430      * all the backlinks appropriately.
 431      */
 432     function rebuild () {
 433         $db = &$this->_db;
 434
 435         // Delete the backlink tables, make a list of page names.
 436         $okeys = array();
 437         $ikeys = array();
 438         for ($key = $db->firstkey(); $key; $key = $db->nextkey()) {
 439             if ($key[0] == 'i')
 440                 $ikeys[] = $key;
 441             elseif ($key[0] == 'o')
 442                 $okeys[] = $key;
 443             else {
 444                 trigger_error("Bad key in linktable: '$key'", E_USER_WARNING);
 445                 $ikeys[] = $key;
 446             }
 447         }
 448         foreach ($ikeys as $key) {
 449             $db->delete($key);
 450         }
 451         foreach ($okeys as $key) {
 452             $page = substr($key,1);
 453             $links = $this->_get_links('o', $page);
 454             $db->delete($key);
 455             $this->set_links($page, $links);
 456         }
 457     }
 458
 459     function check() {
 460         $db = &$this->_db;
 461
 462         // FIXME: check for sortedness and uniqueness in links lists.
 463
 464         for ($key = $db->firstkey(); $key; $key = $db->nextkey()) {
 465             if (strlen($key) < 1 || ($key[0] != 'i' && $key[0] != 'o')) {
 466                 $errs[] = "Bad key '$key' in table";
 467                 continue;
 468             }
 469             $page = substr($key, 1);
 470             if ($key[0] == 'o') {
 471                 // Forward links.
 472                 foreach($this->_get_links('o', $page) as $link) {
 473                     if (!$this->_has_link('i', $link, $page))
 474                         $errs[] = "backlink entry missing for link '$page'->'$link'";
 475                 }
 476             }
 477             else {
 478                 assert($key[0] == 'i');
 479                 // Backlinks.
 480                 foreach($this->_get_links('i', $page) as $link) {
 481                     if (!$this->_has_link('o', $link, $page))
 482                         $errs[] = "link entry missing for backlink '$page'<-'$link'";
 483                 }
 484             }
 485         }
 486
 487         return isset($errs) ? $errs : false;
 488     }
 489
 490
 491     function _add_backlink($page, $linkedfrom) {
 492         $backlinks = $this->_get_links('i', $page);
 493         $backlinks[] = $linkedfrom;
 494         sort($backlinks);
 495         $this->_set_links('i', $page, $backlinks);
 496     }
 497
 498     function _delete_backlink($page, $linkedfrom) {
 499         $backlinks = $this->_get_links('i', $page);
 500         foreach ($backlinks as $key => $backlink) {
 501             if ($backlink == $linkedfrom)
 502                 unset($backlinks[$key]);
 503         }
 504         $this->_set_links('i', $page, $backlinks);
 505     }
 506
 507     function _has_link($which, $page, $link) {
 508         $links = $this->_get_links($which, $page);
 509         foreach($links as $l) {
 510             if ($l == $link)
 511                 return true;
 512         }
 513         return false;
 514     }
 515
 516     function _get_links($which, $page) {
 517         $data = $this->_db->get($which . $page);
 518         return $data ? unserialize($data) : array();
 519     }
 520
 521     function _set_links($which, $page, &$links) {
 522         $key = $which . $page;
 523         if ($links)
 524             $this->_db->set($key, serialize($links));
 525         else
 526             $this->_db->set($key, false);
 527     }
 528 }
 529
 530 // (c-file-style: "gnu")
 531 // Local Variables:
 532 // mode: php
 533 // tab-width: 8
 534 // c-basic-offset: 4
 535 // c-hanging-comment-ender-p: nil
 536 // indent-tabs-mode: nil
 537 // End:
 538 ?>