lib/WikiDB/backend/dbaBase.php

   1 <?php // -*-php-*-
   2 rcs_id('$Id: dbaBase.php,v 1.30 2007-07-15 17:39:25 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         parent::rebuild();
  77         // rebuild backlink table
  78         $this->_linkdb->rebuild();
  79         $this->optimize();
  80     }
  81
  82     function check() {
  83         return $this->_linkdb->check();
  84     }
  85
  86     function get_pagedata($pagename) {
  87         $result = $this->_pagedb->get($pagename);
  88         if (!$result)
  89             return false;
  90         list(,,$packed) = explode(':', $result, 3);
  91         $data = unserialize($packed);
  92         return $data;
  93     }
  94
  95     function update_pagedata($pagename, $newdata) {
  96         $result = $this->_pagedb->get($pagename);
  97         if ($result) {
  98             list($latestversion,$flags,$data) = explode(':', $result, 3);
  99             $data = unserialize($data);
 100         }
 101         else {
 102             $latestversion = $flags = 0;
 103             $data = array();
 104         }
 105
 106         foreach ($newdata as $key => $val) {
 107             if (empty($val))
 108                 unset($data[$key]);
 109             else
 110                 $data[$key] = $val;
 111         }
 112         $this->_pagedb->set($pagename,
 113                             (int)$latestversion . ':'
 114                             . (int)$flags . ':'
 115                             . serialize($data));
 116     }
 117
 118     function get_latest_version($pagename) {
 119         return (int) $this->_pagedb->get($pagename);
 120     }
 121
 122     function get_previous_version($pagename, $version) {
 123         $versdb = &$this->_versiondb;
 124
 125         while (--$version > 0) {
 126             if ($versdb->exists($version . ":$pagename"))
 127                 return $version;
 128         }
 129         return false;
 130     }
 131
 132     //check $want_content
 133     function get_versiondata($pagename, $version, $want_content=false) {
 134         $data = $this->_versiondb->get((int)$version . ":$pagename");
 135         if (empty($data)) return false;
 136         else {
 137             $data = unserialize($data);
 138             if (!$want_content)
 139                 $data['%content'] = !empty($data['%content']);
 140             return $data;
 141         }
 142     }
 143
 144     /**
 145      * See ADODB for a better delete_page(), which can be undone and is seen in RecentChanges.
 146      * See backend.php
 147      */
 148     //function delete_page($pagename) { $this->purge_page($pagename);  }
 149
 150     /**
 151      * Completely delete page from the database.
 152      */
 153     function purge_page($pagename) {
 154         $pagedb = &$this->_pagedb;
 155         $versdb = &$this->_versiondb;
 156
 157         $version = $this->get_latest_version($pagename);
 158         while ($version > 0) {
 159             $versdb->set($version-- . ":$pagename", false);
 160         }
 161         $pagedb->set($pagename, false);
 162
 163         $this->set_links($pagename, false);
 164     }
 165
 166     function rename_page($pagename, $to) {
 167         $result = $this->_pagedb->get($pagename);
 168         if ($result) {
 169             list($version, $flags, $data) = explode(':', $result, 3);
 170             $data = unserialize($data);
 171         }
 172         else
 173             return false;
 174
 175         $links = $this->_linkdb->get_links($pagename, false, false);
 176         $this->_pagedb->delete($pagename);
 177         $data['pagename'] = $to;
 178         $this->_pagedb->set($to,
 179                             (int)$version . ':'
 180                             . (int)$flags . ':'
 181                             . serialize($data));
 182         // move over the latest version only
 183         $pvdata = $this->get_versiondata($pagename, $version, true);
 184         $this->set_versiondata($to, $version, $pvdata);
 185
 186         // update links and backlinks
 187         $this->_linkdb->set_links($to, $links);
 188
 189         return true;
 190     }
 191
 192     /**
 193      * Delete an old revision of a page.
 194      */
 195     function delete_versiondata($pagename, $version) {
 196         $versdb = &$this->_versiondb;
 197
 198         $latest = $this->get_latest_version($pagename);
 199
 200         assert($version > 0);
 201         assert($version <= $latest);
 202
 203         $versdb->set((int)$version . ":$pagename", false);
 204
 205         if ($version == $latest) {
 206             $previous = $this->get_previous_version($version);
 207             if ($previous > 0) {
 208                 $pvdata = $this->get_versiondata($pagename, $previous);
 209                 $is_empty = empty($pvdata['%content']);
 210             }
 211             else
 212                 $is_empty = true;
 213             $this->_update_latest_version($pagename, $previous, $is_empty);
 214         }
 215     }
 216
 217     /**
 218      * Create a new revision of a page.
 219      */
 220     function set_versiondata($pagename, $version, $data) {
 221         $versdb = &$this->_versiondb;
 222
 223         $versdb->set((int)$version . ":$pagename", serialize($data));
 224         if ($version > $this->get_latest_version($pagename))
 225             $this->_update_latest_version($pagename, $version, empty($data['%content']));
 226     }
 227
 228     function _update_latest_version($pagename, $latest, $flags) {
 229         $pagedb = &$this->_pagedb;
 230
 231         $pdata = $pagedb->get($pagename);
 232         if ($pdata)
 233             list(,,$pagedata) = explode(':',$pdata,3);
 234         else
 235             $pagedata = serialize(array());
 236
 237         $pagedb->set($pagename, (int)$latest . ':' . (int)$flags . ":$pagedata");
 238     }
 239
 240     function numPages($include_empty=false, $exclude='') {
 241         $pagedb = &$this->_pagedb;
 242         $count = 0;
 243         for ($page = $pagedb->firstkey(); $page!== false; $page = $pagedb->nextkey()) {
 244             if (!$page) {
 245                 assert(!empty($page));
 246                 continue;
 247             }
 248             if ($exclude and in_array($page, $exclude)) continue;
 249             if (!$include_empty) {
 250                 if (!($data = $pagedb->get($page))) continue;
 251                 list($latestversion,$flags,) = explode(':', $data, 3);
 252                 unset($data);
 253                 if ($latestversion == 0 || $flags != 0)
 254                     continue;   // current content is empty
 255             }
 256             $count++;
 257         }
 258         return $count;
 259     }
 260
 261     function get_all_pages($include_empty=false, $sortby='', $limit='', $exclude='') {
 262         $pagedb = &$this->_pagedb;
 263         $pages = array();
 264         if ($limit) // extract from,count from limit
 265             list($from,$count) = $this->limit($limit);
 266         for ($page = $pagedb->firstkey(); $page!== false; $page = $pagedb->nextkey()) {
 267             if (!$page) {
 268                 assert(!empty($page));
 269                 continue;
 270             }
 271             if ($exclude and in_array($page, $exclude)) continue;
 272             if ($limit and $from) {
 273                 $i++;
 274                 if ($i < $from) continue;
 275             }
 276             if ($limit and count($pages) > $count) break;
 277             if (!$include_empty) {
 278                 if (!($data = $pagedb->get($page))) continue;
 279                 list($latestversion,$flags,) = explode(':', $data, 3);
 280                 unset($data);
 281                 if ($latestversion == 0 || $flags != 0)
 282                     continue;   // current content is empty
 283             }
 284             $pages[] = $page;
 285         }
 286         return new WikiDB_backend_dbaBase_pageiter($this, $pages,
 287                                                    array('sortby'=>$sortby/*,
 288                                                          'limit' =>$limit*/));
 289     }
 290
 291     function set_links($pagename, $links) {
 292         $this->_linkdb->set_links($pagename, $links);
 293     }
 294
 295     function get_links($pagename, $reversed=true, $include_empty=false,
 296                        $sortby='', $limit='', $exclude='',
 297                        $want_relations=false)
 298     {
 299         // optimization: if no relation at all is found, mark it in the iterator.
 300         $links = $this->_linkdb->get_links($pagename, $reversed, $want_relations);
 301
 302         return new WikiDB_backend_dbaBase_pageiter
 303             ($this, $links,
 304              array('sortby'=>$sortby,
 305                    'limit' =>$limit,
 306                    'exclude'=>$exclude,
 307                    'want_relations'=>$want_relations,
 308                    'found_relations' => $want_relations ? $this->_linkdb->found_relations : 0
 309                    ));
 310     }
 311
 312     /**
 313      * @access public
 314      *
 315      * @return array of all linkrelations
 316      * Faster than the dumb WikiDB method.
 317      */
 318     function list_relations($also_attributes=false, $only_attributes=false, $sorted=true) {
 319         $linkdb = &$this->_linkdb;
 320         $relations = array();
 321         for ($link = $linkdb->_db->firstkey(); $link!== false; $link = $linkdb->_db->nextkey()) {
 322             if ($link[0] != 'o') continue;
 323             $links = $linkdb->_get_links('o', substr($link,1));
 324             foreach ($links as $link) { // linkto => page, linkrelation => page
 325                 if (is_array($link)
 326                     and $link['relation']
 327                     and !in_array($link['relation'], $relations))
 328                 {
 329                     $is_attribute = empty($link['linkto']); // a relation has both
 330                     if ($is_attribute) {
 331                         if ($only_attributes or $also_attributes)
 332                             $relations[] = $link['relation'];
 333                     } elseif (!$only_attributes) {
 334                           $relations[] = $link['relation'];
 335                     }
 336                 }
 337             }
 338         }
 339         if ($sorted) {
 340             sort($relations);
 341             reset($relations);
 342         }
 343         return $relations;
 344     }
 345
 346     /**
 347      * WikiDB_backend_dumb_LinkSearchIter searches over all pages and then all its links.
 348      * Since there are less links than pages, and we easily get the pagename from the link key,
 349      * we iterate here directly over the linkdb and check the pagematch there.
 350      *
 351      * @param $pages     object A TextSearchQuery object for the pagename filter.
 352      * @param $query     object A SearchQuery object (Text or Numeric) for the linkvalues,
 353      *                          linkto, linkfrom (=backlink), relation or attribute values.
 354      * @param $linktype  string One of the 4 linktypes "linkto", "linkfrom" (=backlink), "relation" or "attribute".
 355      *                          Maybe also "relation+attribute" for the advanced search.
 356      * @param $relation  object A TextSearchQuery for the linkname or false.
 357      * @param $options   array Currently ignored. hash of sortby, limit, exclude.
 358      * @return object A WikiDB_backend_iterator.
 359      * @see WikiDB::linkSearch
 360      */
 361     function link_search( $pages, $query, $linktype, $relation=false, $options=array() ) {
 362         $linkdb = &$this->_linkdb;
 363         $links = array();
 364         $reverse = false;
 365         $want_relations = false;
 366         if ($linktype == 'relation') {
 367             $want_relations = true;
 368             $field = 'linkrelation';
 369         }
 370         if ($linktype == 'attribute') {
 371             $want_relations = true;
 372             $field = 'attribute';
 373         }
 374         if ($linktype == 'linkfrom') {
 375             $reverse = true;
 376         }
 377
 378         for ($link = $linkdb->_db->firstkey(); $link!== false; $link = $linkdb->_db->nextkey()) {
 379             $type = $reverse ? 'i' : 'o';
 380             if ($link[0] != $type) continue;
 381             $pagename = substr($link, 1);
 382             if (!$pages->match($pagename)) continue;
 383             if ($linktype == 'attribute') {
 384                 $page = $GLOBALS['request']->_dbi->getPage($pagename);
 385                 $attribs = $page->get('attributes');
 386                 if ($attribs) {
 387                     /* Optimization on expressive searches:
 388                        for queries with multiple attributes.
 389                        Just take the defined placeholders from the query(ies)
 390                        if there are more attributes than query variables.
 391                     */
 392                     if ($query->getType() != 'text'
 393                         and !$relation
 394                         and ((count($vars = $query->getVars()) > 1)
 395                              or (count($attribs) > count($vars))))
 396                     {
 397                         // names must strictly match. no * allowed
 398                         if (!$query->can_match($attribs)) continue;
 399                         if (!($result = $query->match($attribs))) continue;
 400                         foreach ($result as $r) {
 401                             $r['pagename'] = $pagename;
 402                             $links[] = $r;
 403                         }
 404                     } else {
 405                         // textsearch or simple value. no strict bind by name needed
 406                         foreach ($attribs as $attribute => $value) {
 407                             if ($relation and !$relation->match($attribute)) continue;
 408                             if (!$query->match($value)) continue;
 409                             $links[] = array('pagename'  => $pagename,
 410                                              'linkname'  => $attribute,
 411                                              'linkvalue' => $value);
 412                         }
 413                     }
 414                 }
 415             }
 416             else {
 417                 // TODO: honor limits. this can get large.
 418                 if ($want_relations) {
 419                     // MAP linkrelation : pagename => thispagename : linkname : linkvalue
 420                     $_links = $linkdb->_get_links('o', $pagename);
 421                     foreach ($_links as $link) { // linkto => page, linkrelation => page
 422                         if (!isset($link['relation']) or !$link['relation']) continue;
 423                         if ($relation and !$relation->match($link['relation'])) continue;
 424                         if (!$query->match($link['linkto'])) continue;
 425                         $links[] = array('pagename'  => $pagename,
 426                                          'linkname'  => $link['relation'],
 427                                          'linkvalue' => $link['linkto']);
 428                     }
 429                 } else {
 430                     $_links = $linkdb->_get_links($reverse ? 'i' : 'o', $pagename);
 431                     foreach ($_links as $link) { // linkto => page
 432                         if (is_array($link))
 433                             $link = $link['linkto'];
 434                         if (!$query->match($link)) continue;
 435                         $links[] = array('pagename'  => $pagename,
 436                                          'linkname'  => '',
 437                                          'linkvalue' => $link);
 438                     }
 439                 }
 440             }
 441         }
 442         $options['want_relations'] = true; // Iter hack to force return of the whole hash
 443         return new WikiDB_backend_dbaBase_pageiter($this, $links, $options);
 444     }
 445
 446     /**
 447      * Handle multi-searches for many relations and attributes in one expression.
 448      * Bind all required attributes and relations per page together and pass it to one query.
 449      *   (is_a::city and population < 20000) and (*::city and area > 1000000)
 450      *   (is_a::city or linkto::CategoryCountry) and population < 20000 and area > 1000000
 451      * Note that the 'linkto' and 'linkfrom' links are relations, containing an array.
 452      *
 453      * @param $pages     object A TextSearchQuery object for the pagename filter.
 454      * @param $query     object A SemanticSearchQuery object for the links.
 455      * @param $options   array  Currently ignored. hash of sortby, limit, exclude for the pagelist.
 456      * @return object A WikiDB_backend_iterator.
 457      * @see WikiDB::linkSearch
 458      */
 459     function relation_search( $pages, $query, $options=array() ) {
 460         $linkdb = &$this->_linkdb;
 461         $links = array();
 462         // We need to detect which attributes and relation names we should look for. NYI
 463         $want_attributes = $query->hasAttributes();
 464         $want_relation = $query->hasRelations();
 465         $linknames = $query->getLinkNames();
 466         // create a hash for faster checks
 467         $linkcheck = array();
 468         foreach ($linknames as $l) $linkcheck[$l] = 1;
 469
 470         for ($link = $linkdb->_db->firstkey(); $link!== false; $link = $linkdb->_db->nextkey()) {
 471             $type = $reverse ? 'i' : 'o';
 472             if ($link[0] != $type) continue;
 473             $pagename = substr($link, 1);
 474             if (!$pages->match($pagename)) continue;
 475             $pagelinks = array();
 476             if ($want_attributes) {
 477                 $page = $GLOBALS['request']->_dbi->getPage($pagename);
 478                 $attribs = $page->get('attributes');
 479                 $pagelinks = $attribs;
 480             }
 481             if ($want_relations) {
 482                 // all links contain arrays of pagenames, just the attributes
 483                 // are guaranteed to be singular
 484                 if (isset($linkcheck['linkfrom'])) {
 485                     $pagelinks['linkfrom'] = $linkdb->_get_links('i', $pagename);
 486                 }
 487                 $outlinks = $linkdb->_get_links('o', $pagename);
 488                 $want_to = isset($linkcheck['linkto']);
 489                 foreach ($outlinks as $link) { // linkto => page, relation => page
 490                     // all named links
 491                     if ((isset($link['relation'])) and $link['relation']
 492                         and isset($linkcheck[$link['relation']]))
 493                         $pagelinks[$link['relation']][] = $link['linkto'];
 494                     if ($want_to)
 495                         $pagelinks['linkto'][] = is_array($link) ? $link['linkto'] : $link;
 496                 }
 497             }
 498             if ($result = $query->match($pagelinks)) {
 499                 $links = array_merge($links, $result);
 500             }
 501         }
 502         $options['want_relations'] = true; // Iter hack to force return of the whole hash
 503         return new WikiDB_backend_dbaBase_pageiter($this, $links, $options);
 504     }
 505 };
 506
 507 function WikiDB_backend_dbaBase_sortby_pagename_ASC ($a, $b) {
 508     return strcasecmp($a, $b);
 509 }
 510 function WikiDB_backend_dbaBase_sortby_pagename_DESC ($a, $b) {
 511     return strcasecmp($b, $a);
 512 }
 513 function WikiDB_backend_dbaBase_sortby_mtime_ASC ($a, $b) {
 514     return WikiDB_backend_dbaBase_sortby_num($a, $b, 'mtime');
 515 }
 516 function WikiDB_backend_dbaBase_sortby_mtime_DESC ($a, $b) {
 517     return WikiDB_backend_dbaBase_sortby_num($b, $a, 'mtime');
 518 }
 519 /*
 520 function WikiDB_backend_dbaBase_sortby_hits_ASC ($a, $b) {
 521     return WikiDB_backend_dbaBase_sortby_num($a, $b, 'hits');
 522 }
 523 function WikiDB_backend_dbaBase_sortby_hits_DESC ($a, $b) {
 524     return WikiDB_backend_dbaBase_sortby_num($b, $a, 'hits');
 525 }
 526 */
 527 function WikiDB_backend_dbaBase_sortby_num($aname, $bname, $field) {
 528     global $request;
 529     $dbi = $request->getDbh();
 530     // fields are stored in versiondata
 531     $av = $dbi->_backend->get_latest_version($aname);
 532     $bv = $dbi->_backend->get_latest_version($bname);
 533     $a = $dbi->_backend->get_versiondata($aname, $av, false);
 534     if (!$a) return 0;
 535     $b = $dbi->_backend->get_versiondata($bname, $bv, false);
 536     if (!$b) return 0;
 537     if ((!isset($a[$field]) && !isset($b[$field])) || ($a[$field] === $b[$field])) {
 538         return 0;
 539     } else {
 540         return (!isset($a[$field]) || ($a[$field] < $b[$field])) ? -1 : 1;
 541     }
 542 }
 543
 544 class WikiDB_backend_dbaBase_pageiter
 545 extends WikiDB_backend_iterator
 546 {
 547     // fixed for linkrelations
 548     function WikiDB_backend_dbaBase_pageiter(&$backend, &$pages, $options=false) {
 549         $this->_backend = $backend;
 550         $this->_options = $options;
 551         if ($pages) {
 552             if (!empty($options['sortby'])) {
 553                 $sortby = WikiDB_backend::sortby($options['sortby'], 'db', array('pagename','mtime'));
 554                 if ($sortby and !strstr($sortby, "hits ")) { // check for which column to sortby
 555                     usort($pages, 'WikiDB_backend_dbaBase_sortby_'.str_replace(' ','_',$sortby));
 556                 }
 557             }
 558             if (!empty($options['limit'])) {
 559                 list($offset,$limit) = WikiDB_backend::limit($options['limit']);
 560                 $pages = array_slice($pages, $offset, $limit);
 561             }
 562             $this->_pages = $pages;
 563         } else
 564             $this->_pages = array();
 565     }
 566
 567     // fixed for relations
 568     function next() {
 569         if ( ! ($page = array_shift($this->_pages)) )
 570             return false;
 571         if (!empty($this->_options['want_relations'])) {
 572             // $linkrelation = $page['linkrelation'];
 573             $pagename = $page['pagename'];
 574             if (!empty($this->_options['exclude']) and in_array($pagename, $this->_options['exclude']))
 575                 return $this->next();
 576             return $page;
 577         }
 578         if (!empty($this->_options['exclude']) and in_array($page, $this->_options['exclude']))
 579             return $this->next();
 580         return array('pagename' => $page);
 581     }
 582
 583     function free() {
 584         $this->_pages = array();
 585     }
 586 };
 587
 588 class WikiDB_backend_dbaBase_linktable
 589 {
 590     function WikiDB_backend_dbaBase_linktable(&$dba) {
 591         $this->_db = &$dba;
 592     }
 593
 594     //TODO: try storing link lists as hashes rather than arrays.
 595     //      backlink deletion would be faster.
 596     function get_links($page, $reversed=true, $want_relations=false) {
 597         if ($want_relations) {
 598             $this->found_relations = 0;
 599             $links = $this->_get_links($reversed ? 'i' : 'o', $page);
 600             $linksonly = array();
 601             foreach ($links as $link) { // linkto => page, linkrelation => page
 602                 if (is_array($link) and isset($link['relation'])) {
 603                     if ($link['relation'])
 604                         $this->found_relations++;
 605                     $linksonly[] = array('pagename'     => $link['linkto'],
 606                                          'linkrelation' => $link['relation']);
 607                 } else { // empty relations are stripped
 608                     $linksonly[] = array('pagename' => $link['linkto']);
 609                 }
 610             }
 611             return $linksonly;
 612         } else {
 613             $links = $this->_get_links($reversed ? 'i' : 'o', $page);
 614             $linksonly = array();
 615             foreach ($links as $link) {
 616                 if (is_array($link)) {
 617                     $linksonly[] = $link['linkto'];
 618                 } else
 619                     $linksonly[] = $link;
 620             }
 621             return $linksonly;
 622         }
 623     }
 624
 625     // fixed: relations ready
 626     function set_links($page, $links) {
 627
 628         $oldlinks = $this->get_links($page, false, false);
 629
 630         if (!is_array($links)) {
 631             assert(empty($links));
 632             $links = array();
 633         }
 634         $this->_set_links('o', $page, $links);
 635
 636         /* Now for the backlink update we squash the linkto hashes into a simple array */
 637         $newlinks = array();
 638         foreach ($links as $hash) {
 639             if (!empty($hash['linkto'])
 640                 and !in_array($hash['linkto'], $newlinks))
 641                  // for attributes it's empty
 642                 $newlinks[] = $hash['linkto'];
 643         }
 644         //$newlinks = array_unique($newlinks);
 645         sort($oldlinks);
 646         sort($newlinks);
 647
 648         reset($newlinks);
 649         reset($oldlinks);
 650         $new = current($newlinks);
 651         $old = current($oldlinks);
 652         while ($new !== false || $old !== false) {
 653             if ($old === false || ($new !== false && $new < $old)) {
 654                 // $new is a new link (not in $oldlinks).
 655                 $this->_add_backlink($new, $page);
 656                 $new = next($newlinks);
 657             }
 658             elseif ($new === false || $old < $new) {
 659                 // $old is a obsolete link (not in $newlinks).
 660                 $this->_delete_backlink($old, $page);
 661                 $old = next($oldlinks);
 662             }
 663             else {
 664                 // Unchanged link (in both $newlist and $oldlinks).
 665                 assert($new == $old);
 666                 $new = next($newlinks);
 667                 $old = next($oldlinks);
 668             }
 669         }
 670     }
 671
 672     /**
 673      * Rebuild the back-link index.
 674      *
 675      * This should never be needed, but if the database gets hosed for some reason,
 676      * this should put it back into a consistent state.
 677      *
 678      * We assume the forward links in the our table are correct, and recalculate
 679      * all the backlinks appropriately.
 680      */
 681     function rebuild () {
 682         $db = &$this->_db;
 683
 684         // Delete the backlink tables, make a list of lo.page keys.
 685         $okeys = array();
 686         for ($key = $db->firstkey(); $key; $key = $db->nextkey()) {
 687             if ($key[0] == 'i')
 688                 $db->delete($key);
 689             elseif ($key[0] == 'o')
 690                 $okeys[] = $key;
 691             else {
 692                 trigger_error("Bad key in linktable: '$key'", E_USER_WARNING);
 693             $db->delete($key);
 694         }
 695         }
 696         foreach ($okeys as $key) {
 697             $page = substr($key,1);
 698             $links = $this->_get_links('o', $page);
 699             $db->delete($key);
 700             $this->set_links($page, $links);
 701         }
 702     }
 703
 704     function check() {
 705         $db = &$this->_db;
 706
 707         // FIXME: check for sortedness and uniqueness in links lists.
 708
 709         for ($key = $db->firstkey(); $key; $key = $db->nextkey()) {
 710             if (strlen($key) < 1 || ($key[0] != 'i' && $key[0] != 'o')) {
 711                 $errs[] = "Bad key '$key' in table";
 712                 continue;
 713             }
 714             $page = substr($key, 1);
 715             if ($key[0] == 'o') {
 716                 // Forward links.
 717                 foreach($this->_get_links('o', $page) as $link) {
 718                     $link = $link['linkto'];
 719                     if (!$this->_has_link('i', $link, $page))
 720                         $errs[] = "backlink entry missing for link '$page'->'$link'";
 721                 }
 722             }
 723             else {
 724                 assert($key[0] == 'i');
 725                 // Backlinks.
 726                 foreach($this->_get_links('i', $page) as $link) {
 727                     if (!$this->_has_link('o', $link, $page))
 728                         $errs[] = "link entry missing for backlink '$page'<-'$link'";
 729                 }
 730             }
 731         }
 732         //if ($errs) $this->rebuild();
 733         return isset($errs) ? $errs : false;
 734     }
 735
 736     /* TODO: Add another lrRelationName key for relations.
 737      * lrRelationName: frompage => topage
 738      */
 739
 740     function _add_relation($page, $linkedfrom) {
 741         $relations = $this->_get_links('r', $page);
 742         $backlinks[] = $linkedfrom;
 743         sort($backlinks);
 744         $this->_set_links('i', $page, $backlinks);
 745     }
 746
 747     function _add_backlink($page, $linkedfrom) {
 748         $backlinks = $this->_get_links('i', $page);
 749         $backlinks[] = $linkedfrom;
 750         sort($backlinks);
 751         $this->_set_links('i', $page, $backlinks);
 752     }
 753
 754     function _delete_backlink($page, $linkedfrom) {
 755         $backlinks = $this->_get_links('i', $page);
 756         foreach ($backlinks as $key => $backlink) {
 757             if ($backlink == $linkedfrom)
 758                 unset($backlinks[$key]);
 759         }
 760         $this->_set_links('i', $page, $backlinks);
 761     }
 762
 763     function _has_link($which, $page, $link) {
 764         $links = $this->_get_links($which, $page);
 765         // since links are always sorted, break if >
 766         // TODO: binary search
 767         foreach($links as $l) {
 768             if ($l['linkto'] == $link)
 769                 return true;
 770             if ($l['linkto'] > $link)
 771                 return false;
 772         }
 773         return false;
 774     }
 775
 776     function _get_links($which, $page) {
 777         $data = $this->_db->get($which . $page);
 778         return $data ? unserialize($data) : array();
 779     }
 780
 781     function _set_links($which, $page, &$links) {
 782         $key = $which . $page;
 783         if ($links)
 784             $this->_db->set($key, serialize($links));
 785         else
 786             $this->_db->set($key, false);
 787     }
 788 }
 789
 790 // $Log: not supported by cvs2svn $
 791 // Revision 1.29  2007/05/24 18:39:10  rurban
 792 // limits for get_all_pages, improved WantedPages
 793 //
 794 // Revision 1.28  2007/01/03 21:26:01  rurban
 795 // Fix dba searching for relations. Optimize link_search for strict attribute search. Add relation_search()
 796 //
 797 // Revision 1.27  2007/01/02 13:19:33  rurban
 798 // faster list_relations method. new native link_search method. additions to rebuild() (still very slow), fix iterator options (for want_relations and exclude). Clarify API: sortby,limit and exclude are strings
 799 //
 800 // Revision 1.26  2006/12/22 00:27:37  rurban
 801 // just add Log
 802 //
 803
 804 // (c-file-style: "gnu")
 805 // Local Variables:
 806 // mode: php
 807 // tab-width: 8
 808 // c-basic-offset: 4
 809 // c-hanging-comment-ender-p: nil
 810 // indent-tabs-mode: nil
 811 // End:
 812 ?>