lib/WikiDB/backend/dbaBase.php

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