collapser.h

Go to the documentation of this file.

 
/* Copyright (C) 2009,2011,2017 Olly Betts
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see
 * <https://www.gnu.org/licenses/>.
 */
 
#ifndef XAPIAN_INCLUDED_COLLAPSER_H
#define XAPIAN_INCLUDED_COLLAPSER_H
 
#include "backends/documentinternal.h"
#include "msetcmp.h"
#include "omassert.h"
#include "api/result.h"
 
#include <unordered_map>
#include <vector>
 
typedef enum {
    EMPTY,
    NEW,
    ADD,
    REJECT,
    REPLACE
} collapse_result;
 
class CollapseData {
    std::vector<std::pair<Xapian::doccount, Xapian::docid>> items;
 
    double next_best_weight = 0.0;
 
    Xapian::doccount collapse_count = 0;
 
  public:
    CollapseData(Xapian::doccount item, Xapian::docid did)
        : items(1, { item, did })
    { }
 
    collapse_result check_item(const std::vector<Result>& results,
                               const Result& result,
                               Xapian::doccount collapse_max,
                               MSetCmp mcmp,
                               Xapian::doccount& old_item);
 
    void set_item(Xapian::doccount item);
 
    void add_item(const std::vector<Result>& results,
                  Xapian::doccount item,
                  Xapian::doccount collapse_max,
                  MSetCmp mcmp);
 
    void result_has_moved(Xapian::doccount from, Xapian::doccount to) {
        // Yes, this *is* a linear search, but only through up to collapse_max
        // items and we expect collapse_max to be very small (it's the maximum
        // number of items to keep for each collapse key value).
        for (auto&& item : items) {
            if (item.first == from) {
                item.first = to;
                return;
            }
        }
        // The entry ought to be present.
        Assert(false);
    }
 
    double get_next_best_weight() const { return next_best_weight; }
 
    Xapian::doccount get_collapse_count() const { return collapse_count; }
};
 
class Collapser {
    std::unordered_map<std::string, CollapseData> table;
 
    Xapian::doccount entry_count = 0;
 
    Xapian::doccount no_collapse_key = 0;
 
    Xapian::doccount dups_ignored = 0;
 
    Xapian::doccount docs_considered = 0;
 
    Xapian::valueno slot;
 
    Xapian::doccount collapse_max;
 
    std::vector<Result>& results;
 
    MSetCmp mcmp;
 
    CollapseData* ptr = NULL;
 
    bool operator()(Xapian::doccount a, Xapian::doccount b) const {
        return mcmp(results[a], results[b]);
    }
 
  public:
    Xapian::doccount old_item = 0;
 
    Collapser(Xapian::valueno slot_,
              Xapian::doccount collapse_max_,
              std::vector<Result>& results_,
              MSetCmp mcmp_)
        : slot(slot_),
          collapse_max(collapse_max_),
          results(results_),
          mcmp(mcmp_) { }
 
    operator bool() const { return collapse_max != 0; }
 
    collapse_result check(Result& result,
                          Xapian::Document::Internal & vsdoc);
 
    void process(collapse_result action, Xapian::doccount item);
 
    void result_has_moved(Xapian::doccount from, Xapian::doccount to) {
        const std::string& collapse_key = results[to].get_collapse_key();
        if (collapse_key.empty()) {
            return;
        }
        auto it = table.find(collapse_key);
        if (rare(it == table.end())) {
            // The entry ought to be present.
            Assert(false);
            return;
        }
 
        CollapseData& collapse_data = it->second;
        collapse_data.result_has_moved(from, to);
    }
 
    Xapian::doccount get_collapse_count(const std::string & collapse_key,
                                        int percent_threshold,
                                        double min_weight) const;
 
    Xapian::doccount get_docs_considered() const { return docs_considered; }
 
    Xapian::doccount get_dups_ignored() const { return dups_ignored; }
 
    Xapian::doccount get_entries() const { return entry_count; }
 
    Xapian::doccount get_matches_lower_bound() const;
 
    void finalise(double min_weight, int percent_threshold);
};
 
class CollapserLite {
    std::unordered_map<std::string, Xapian::doccount> table;
 
    Xapian::doccount entry_count = 0;
 
    Xapian::doccount no_collapse_key = 0;
 
    Xapian::doccount dups_ignored = 0;
 
    Xapian::doccount docs_considered = 0;
 
    Xapian::doccount collapse_max;
 
  public:
    CollapserLite(Xapian::doccount collapse_max_)
        : collapse_max(collapse_max_) {}
 
    operator bool() const { return collapse_max != 0; }
 
    bool add(const std::string& key) {
        ++docs_considered;
 
        if (key.empty()) {
            ++no_collapse_key;
            return true;
        }
 
        auto r = table.emplace(key, 1);
        if (r.second) {
            // New entry, set to 1.
        } else if (r.first->second == collapse_max) {
            // Already seen collapse_max with this key so reject.
            ++dups_ignored;
            return false;
        } else {
            // Increment count.
            ++r.first->second;
        }
        ++entry_count;
        return true;
    }
 
    Xapian::doccount get_docs_considered() const { return docs_considered; }
 
    Xapian::doccount get_dups_ignored() const { return dups_ignored; }
 
    Xapian::doccount get_entries() const { return entry_count; }
 
    Xapian::doccount get_matches_lower_bound() const {
        return no_collapse_key + entry_count;
    }
 
    void finalise(std::vector<Result>& results, int percent_threshold) {
        if (table.empty() || results.empty())
            return;
 
        // We need to fill in collapse_count values in results using the
        // information stored in table.
        Xapian::doccount todo = entry_count;
        for (Result& result : results) {
            const std::string& key = result.get_collapse_key();
            if (key.empty())
                continue;
 
            // Adjust collapse_count.
            if (percent_threshold) {
                // FIXME: We can probably do better here.
                result.set_collapse_count(1);
            } else {
                auto c = result.get_collapse_count() + table[key];
                result.set_collapse_count(c);
            }
 
            if (--todo == 0) {
                // Terminate early if we've handled all non-empty entries.
                break;
            }
        }
    }
};
 
#endif // XAPIAN_INCLUDED_COLLAPSER_H