PostList class implementing unweighted Query::OP_OR. More...

#include <boolorpostlist.h>

Inheritance diagram for BoolOrPostList:

Collaboration diagram for BoolOrPostList:

Classes
struct	PostListAndDocID

Public Member Functions
template<class RandomItor >
	BoolOrPostList (RandomItor pl_begin, RandomItor pl_end, Xapian::doccount db_size)
	Construct from 2 random-access iterators to a container of PostList*, a pointer to the matcher, and the document collection size. More...

	~BoolOrPostList ()

Xapian::docid	get_docid () const
	Return the current docid. More...

double	get_weight (Xapian::termcount doclen, Xapian::termcount unique_terms, Xapian::termcount wdfdocmax) const
	Return the weight contribution for the current position. More...

bool	at_end () const
	Return true if the current position is past the last entry in this list. More...

double	recalc_maxweight ()
	Recalculate the upper bound on what get_weight() can return. More...

PostList *	next (double w_min)
	Advance the current position to the next document in the postlist. More...

PostList *	skip_to (Xapian::docid did, double w_min)
	Skip forward to the specified docid. More...

void	get_docid_range (Xapian::docid &first, Xapian::docid &last) const
	Get the bounds on the range of docids this PostList can return. More...

std::string	get_description () const
	Return a string description of this object. More...

Xapian::termcount	get_wdf () const
	Return the wdf for the document at the current position. More...

Xapian::termcount	count_matching_subqs () const
	Count the number of leaf subqueries which match at the current position. More...

void	gather_position_lists (OrPositionList *orposlist)
	Gather PositionList* objects for a subtree. More...

Public Member Functions inherited from Xapian::Internal::PostList
virtual	~PostList ()
	We have virtual methods and want to be able to delete derived classes using a pointer to the base class, so we need a virtual destructor. More...

Xapian::doccount	get_termfreq () const
	Get an estimate of the number of documents this PostList will return. More...

virtual PositionList *	read_position_list ()
	Read the position list for the term in the current document and return a pointer to it (owned by the PostList). More...

virtual PositionList *	open_position_list () const
	Read the position list for the term in the current document and return a pointer to it (not owned by the PostList). More...

virtual PostList *	check (Xapian::docid did, double w_min, bool &valid)
	Check if the specified docid occurs in this postlist. More...

PostList *	next ()
	Advance the current position to the next document in the postlist. More...

PostList *	skip_to (Xapian::docid did)
	Skip forward to the specified docid. More...

Private Member Functions
void	operator= (const BoolOrPostList &)=delete
	Don't allow assignment. More...

	BoolOrPostList (const BoolOrPostList &)=delete
	Don't allow copying. More...

template<typename F >
Xapian::termcount	for_all_matches (F func) const
	Helper to apply operation to all postlists matching current docid. More...

Private Attributes
Xapian::docid	did = 0
	The current docid, or zero if we haven't started or are at_end. More...

size_t	n_kids
	The number of sub-postlists. More...

PostListAndDocID *	plist = nullptr
	Array of pointers to sub-postlists. More...

Additional Inherited Members
Protected Member Functions inherited from Xapian::Internal::PostList
	PostList ()
	Only constructable as a base class for derived classes. More...

Protected Attributes inherited from Xapian::Internal::PostList
Xapian::doccount	termfreq
	Estimate of the number of documents this PostList will return. More...

Detailed Description

PostList class implementing unweighted Query::OP_OR.

Definition at line 27 of file boolorpostlist.h.

Constructor & Destructor Documentation

◆ BoolOrPostList() [1/2]

BoolOrPostList::BoolOrPostList ( const BoolOrPostList & )

privatedelete

Don't allow copying.

◆ BoolOrPostList() [2/2]

template<class RandomItor >

BoolOrPostList::BoolOrPostList	(	RandomItor	pl_begin,
		RandomItor	pl_end,
		Xapian::doccount	db_size
	)

inline

Construct from 2 random-access iterators to a container of PostList*, a pointer to the matcher, and the document collection size.

Definition at line 148 of file boolorpostlist.h.

References Assert, Xapian::Internal::PostList::get_termfreq(), n_kids, BoolOrPostList::PostListAndDocID::pl, plist, and Xapian::Internal::PostList::termfreq.

◆ ~BoolOrPostList()

BoolOrPostList::~BoolOrPostList ( )

Definition at line 33 of file boolorpostlist.cc.

Member Function Documentation

◆ at_end()

bool BoolOrPostList::at_end ( ) const

virtual

Return true if the current position is past the last entry in this list.

Implements Xapian::Internal::PostList.

Definition at line 149 of file boolorpostlist.cc.

◆ count_matching_subqs()

Xapian::termcount BoolOrPostList::count_matching_subqs ( ) const

virtual

Count the number of leaf subqueries which match at the current position.

Reimplemented from Xapian::Internal::PostList.

Definition at line 192 of file boolorpostlist.cc.

References Xapian::Internal::PostList::count_matching_subqs().

◆ for_all_matches()

template<typename F >

Xapian::termcount BoolOrPostList::for_all_matches ( F func ) const

inlineprivate

Helper to apply operation to all postlists matching current docid.

For each matching postlist this helper evaluates func, and accumulates the returned Xapian::termcount value. Of the three current uses, two want to accumulate a value of this type, while the other doesn't need to accumulate anything. This is an inlined template so the compiler's optimiser should be able to see the result of the accumulation isn't used and eliminate it.

This function makes use of the heap structure by walking the tree of the heap in a particular order, descending to any children which match the current docid (i.e. the docid of the tip of the heap) to visit every postlist matching the current docid (due to the heap property, for any such postlist all ancestors must also match the current docid).

At each step we do the first of the following which stays within the heap and matches the current docid:

go down+right
go down+left
go left if we're the right descendent of our parent
go up until we can go left (or we reach the root where we stop)

This effectively recurses the tree, but only needs O(1) storage. It requires O(n) in time where n is the number of postlists matching the current docid, but that's inherent as we need to call func n times.

Going down+right in preference to down+left simplifies the "go left" step a little because any right descendent must have a left sibling, but if the last entry in index order is a left descendent it doesn't have a right sibling. It also makes it easy to implement an optimisation which can ascend multiple levels in one go if the compiler provides __builtin_ffs().

Definition at line 94 of file boolorpostlist.h.

References AssertEq, did, n_kids, and plist.

◆ gather_position_lists()

void BoolOrPostList::gather_position_lists ( OrPositionList * orposlist )

virtual

Gather PositionList* objects for a subtree.

Reimplemented from Xapian::Internal::PostList.

Definition at line 200 of file boolorpostlist.cc.

References Xapian::Internal::PostList::gather_position_lists().

◆ get_description()

std::string BoolOrPostList::get_description ( ) const

virtual

Return a string description of this object.

Implements Xapian::Internal::PostList.

Definition at line 171 of file boolorpostlist.cc.

◆ get_docid()

Xapian::docid BoolOrPostList::get_docid ( ) const

virtual

Return the current docid.

Implements Xapian::Internal::PostList.

Definition at line 44 of file boolorpostlist.cc.

References Assert.

◆ get_docid_range()

void BoolOrPostList::get_docid_range	(	Xapian::docid &	first,
		Xapian::docid &	last
	)		const

virtual

Get the bounds on the range of docids this PostList can return.

Parameters

[out]	first	Set to a lower bound on the docids that can be returned, or not changed if there's no known lower bound (other than 1).
[out]	last	Set to an upper bound on the docids that can be returned, or not changed if there's no known upper bound (other than the highest used docid).

The default implementation (PostList::get_docid_range()) does nothing, which is suitable when there's no known lower or upper bound.

Reimplemented from Xapian::Internal::PostList.

Definition at line 159 of file boolorpostlist.cc.

◆ get_wdf()

Xapian::termcount BoolOrPostList::get_wdf ( ) const

virtual

Return the wdf for the document at the current position.

The default implementation throws Xapian::UnimplementedError.

Reimplemented from Xapian::Internal::PostList.

Definition at line 184 of file boolorpostlist.cc.

References Xapian::Internal::PostList::get_wdf().

◆ get_weight()

double BoolOrPostList::get_weight	(	Xapian::termcount	doclen,
		Xapian::termcount	unique_terms,
		Xapian::termcount	wdfdocmax
	)		const

virtual

Return the weight contribution for the current position.

Implements Xapian::Internal::PostList.

Definition at line 51 of file boolorpostlist.cc.

◆ next()

PostList * BoolOrPostList::next ( double w_min )

virtual

Advance the current position to the next document in the postlist.

The list starts before the first entry in the list, so next(), skip_to() or check() must be called before any methods which need the context of the current position.

Parameters

w_min The minimum weight contribution that is needed (this is just a hint which PostList subclasses may ignore).

Returns: If a non-NULL pointer is returned, then the caller should substitute the returned pointer for its pointer to us, and then delete us. This "pruning" can only happen for a non-leaf subclass of this class.

Implements Xapian::Internal::PostList.

Definition at line 65 of file boolorpostlist.cc.

References Xapian::Internal::PostList::next(), Heap::pop(), and Heap::replace().

◆ operator=()

void BoolOrPostList::operator= ( const BoolOrPostList & )

privatedelete

Don't allow assignment.

◆ recalc_maxweight()

double BoolOrPostList::recalc_maxweight ( )

virtual

Recalculate the upper bound on what get_weight() can return.

The maximum weight that get_weight() can return can decrease as the match progresses (typically when the PostList tree prunes) - calling this method calculates a current upper bound.

Note that this method may be called after the postlist has reached the end. In this situation, the method should return 0.

Implements Xapian::Internal::PostList.

Definition at line 59 of file boolorpostlist.cc.

◆ skip_to()

PostList * BoolOrPostList::skip_to	(	Xapian::docid	did,
		double	w_min
	)

virtual

Skip forward to the specified docid.

If the specified docid isn't in the list, position ourselves on the first document after it (or at_end() if no greater docids are present).

Parameters

w_min The minimum weight contribution that is needed (this is just a hint which PostList subclasses may ignore).

Returns: If a non-NULL pointer is returned, then the caller should substitute the returned pointer for its pointer to us, and then delete us. This "pruning" can only happen for a non-leaf subclass of this class.

Implements Xapian::Internal::PostList.

Definition at line 100 of file boolorpostlist.cc.

References Assert, Xapian::Internal::PostList::get_docid(), Heap::make(), rare, and Xapian::Internal::PostList::skip_to().

Member Data Documentation

◆ did

Xapian::docid BoolOrPostList::did = 0

private

The current docid, or zero if we haven't started or are at_end.

Definition at line 35 of file boolorpostlist.h.

Referenced by for_all_matches().

◆ n_kids

size_t BoolOrPostList::n_kids

private

The number of sub-postlists.

Definition at line 38 of file boolorpostlist.h.

Referenced by BoolOrPostList(), and for_all_matches().

◆ plist

PostListAndDocID* BoolOrPostList::plist = nullptr

private

Array of pointers to sub-postlists.

Definition at line 55 of file boolorpostlist.h.

Referenced by BoolOrPostList(), and for_all_matches().

The documentation for this class was generated from the following files:

matcher/boolorpostlist.h
matcher/boolorpostlist.cc

Classes

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ BoolOrPostList() [1/2]

◆ BoolOrPostList() [2/2]

◆ ~BoolOrPostList()

Member Function Documentation

◆ at_end()

◆ count_matching_subqs()

◆ for_all_matches()

◆ gather_position_lists()

◆ get_description()

◆ get_docid()

◆ get_docid_range()

◆ get_wdf()

◆ get_weight()

◆ next()

◆ operator=()

◆ recalc_maxweight()

◆ skip_to()

Member Data Documentation

◆ did

◆ n_kids

◆ plist