From 33a334ce77e6dd0c81e97edc4bfba1fe50d947fa Mon Sep 17 00:00:00 2001 From: Dimitri van Heesch Date: Sat, 3 Oct 2020 15:21:15 +0200 Subject: refactoring: modernize search index Also QVector has been removed from qtools as it was no longer used. --- qtools/CMakeLists.txt | 1 - qtools/qcollection.h | 3 +- qtools/qglist.cpp | 28 +-- qtools/qglist.h | 5 +- qtools/qgvector.cpp | 638 ------------------------------------------------- qtools/qgvector.h | 120 ---------- qtools/qinternallist.h | 3 +- qtools/qlist.doc | 11 +- qtools/qvector.doc | 344 -------------------------- qtools/qvector.h | 85 ------- src/searchindex.cpp | 231 +++++++----------- src/searchindex.h | 42 ++-- 12 files changed, 124 insertions(+), 1387 deletions(-) delete mode 100644 qtools/qgvector.cpp delete mode 100644 qtools/qgvector.h delete mode 100644 qtools/qvector.doc delete mode 100644 qtools/qvector.h diff --git a/qtools/CMakeLists.txt b/qtools/CMakeLists.txt index 0a77289..d49ca47 100644 --- a/qtools/CMakeLists.txt +++ b/qtools/CMakeLists.txt @@ -14,7 +14,6 @@ qgdict.cpp qglist.cpp qglobal.cpp qgstring.cpp -qgvector.cpp qiodevice.cpp qregexp.cpp qstring.cpp diff --git a/qtools/qcollection.h b/qtools/qcollection.h index a169b7c..c187569 100644 --- a/qtools/qcollection.h +++ b/qtools/qcollection.h @@ -1,5 +1,5 @@ /**************************************************************************** -** +** ** ** Definition of base class for all collection classes ** @@ -43,7 +43,6 @@ #endif // QT_H -class QGVector; class QGList; class QGDict; diff --git a/qtools/qglist.cpp b/qtools/qglist.cpp index 8197db5..878aa04 100644 --- a/qtools/qglist.cpp +++ b/qtools/qglist.cpp @@ -1,5 +1,5 @@ /**************************************************************************** -** +** ** ** Implementation of QGList and QGListIterator classes ** @@ -36,7 +36,6 @@ **********************************************************************/ #include "qglist.h" -#include "qgvector.h" #include "qdatastream.h" @@ -243,10 +242,10 @@ bool QGList::operator==( const QGList &list ) const { if ( count() != list.count() ) return FALSE; - + if ( count() == 0 ) return TRUE; - + QLNode *n1 = firstNode; QLNode *n2 = list.firstNode; while ( n1 && n2 ) { @@ -256,7 +255,7 @@ bool QGList::operator==( const QGList &list ) const n1 = n1->next; n2 = n2->next; } - + return TRUE; } @@ -866,25 +865,6 @@ QCollection::Item QGList::prev() } -/*! - \internal - Converts the list to a vector. -*/ - -void QGList::toVector( QGVector *vector ) const -{ - vector->clear(); - if ( !vector->resize( count() ) ) - return; - QLNode *n = firstNode; - uint i = 0; - while ( n ) { - vector->insert( i, n->data ); - n = n->next; - i++; - } -} - void QGList::heapSortPushDown( QCollection::Item* heap, int first, int last ) { int r = first; diff --git a/qtools/qglist.h b/qtools/qglist.h index f400b64..0f30594 100644 --- a/qtools/qglist.h +++ b/qtools/qglist.h @@ -1,5 +1,5 @@ /**************************************************************************** -** +** ** ** Definition of QGList and QGListIterator classes ** @@ -68,7 +68,6 @@ private: class Q_EXPORT QGList : public QCollection // doubly linked generic list { friend class QGListIterator; -friend class QGVector; // needed by QGVector::toList public: uint count() const; // return number of nodes @@ -122,8 +121,6 @@ protected: QCollection::Item next(); // set next item in list curr QCollection::Item prev(); // set prev item in list curr - void toVector( QGVector * ) const; // put items in vector - virtual int compareItems( QCollection::Item, QCollection::Item ); #ifndef QT_NO_DATASTREAM diff --git a/qtools/qgvector.cpp b/qtools/qgvector.cpp deleted file mode 100644 index 2d08ede..0000000 --- a/qtools/qgvector.cpp +++ /dev/null @@ -1,638 +0,0 @@ -/**************************************************************************** -** -** -** Implementation of QGVector class -** -** Created : 930907 -** -** Copyright (C) 1992-2000 Trolltech AS. All rights reserved. -** -** This file is part of the tools module of the Qt GUI Toolkit. -** -** This file may be distributed under the terms of the Q Public License -** as defined by Trolltech AS of Norway and appearing in the file -** LICENSE.QPL included in the packaging of this file. -** -** This file may be distributed and/or modified under the terms of the -** GNU General Public License version 2 as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL included in the -** packaging of this file. -** -** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition -** licenses may use this file in accordance with the Qt Commercial License -** Agreement provided with the Software. -** -** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE -** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. -** -** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for -** information about Qt Commercial License Agreements. -** See http://www.trolltech.com/qpl/ for QPL licensing information. -** See http://www.trolltech.com/gpl/ for GPL licensing information. -** -** Contact info@trolltech.com if any conditions of this licensing are -** not clear to you. -** -**********************************************************************/ - -#define QGVECTOR_CPP -#include "qgvector.h" -#include "qglist.h" -#include "qstring.h" -#include "qdatastream.h" -#include - -#define USE_MALLOC // comment to use new/delete - -#undef NEW -#undef DELETE - -#if defined(USE_MALLOC) -#define NEW(type,size) ((type*)malloc(size*sizeof(type))) -#define DELETE(array) (free((char*)array)) -#else -#define NEW(type,size) (new type[size]) -#define DELETE(array) (delete[] array) -#define DONT_USE_REALLOC // comment to use realloc() -#endif - -// NOT REVISED - -/*! - \class QGVector qgvector.h - - \brief The QGVector class is an internal class for implementing Qt - collection classes. - - QGVector is a strictly internal class that acts as a base class for - the QVector collection class. - - QGVector has some virtual functions that may be reimplemented in - subclasses to customize behavior. - - -*/ - -/***************************************************************************** - Default implementation of virtual functions - *****************************************************************************/ - -/*! - This virtual function compares two list items. - - Returns: - - - This function returns \e int rather than \e bool so that - reimplementations can return one of three values and use it to sort - by: - - - - The QVector::sort() and QVector::bsearch() functions require that - compareItems() is implemented as described here. - - This function should not modify the vector because some const - functions call compareItems(). -*/ - -int QGVector::compareItems( Item d1, Item d2 ) -{ - return d1 != d2; // compare pointers -} - -#ifndef QT_NO_DATASTREAM -/*! - Reads a collection/vector item from the stream \a s and returns a reference - to the stream. - - The default implementation sets \e item to 0. - - \sa write() -*/ - -QDataStream &QGVector::read( QDataStream &s, Item &d ) -{ // read item from stream - d = 0; - return s; -} - -/*! - Writes a collection/vector item to the stream \a s and returns a reference - to the stream. - - The default implementation does nothing. - - \sa read() -*/ - -QDataStream &QGVector::write( QDataStream &s, Item ) const -{ // write item to stream - return s; -} -#endif // QT_NO_DATASTREAM - -/***************************************************************************** - QGVector member functions - *****************************************************************************/ - -/*! - \internal -*/ - -QGVector::QGVector() // create empty vector -{ - vec = 0; - len = numItems = 0; -} - -/*! - \internal -*/ -QGVector::QGVector( uint size ) // create vectors with nullptrs -{ - len = size; - numItems = 0; - if ( len == 0 ) { // zero length - vec = 0; - return; - } - vec = NEW(Item,len); - CHECK_PTR( vec ); - memset( (void*)vec, 0, len*sizeof(Item) ); // fill with nulls -} - -/*! - \internal -*/ - -QGVector::QGVector( const QGVector &a ) // make copy of other vector - : QCollection( a ) -{ - len = a.len; - numItems = a.numItems; - vec = NEW(Item,len); - CHECK_PTR( vec ); - for ( uint i=0; i= len ) { // range error - qWarning( "QGVector::insert: Index %d out of range", index ); - return FALSE; - } -#endif - if ( vec[index] ) { // remove old item - deleteItem( vec[index] ); - numItems--; - } - if ( d ) { - vec[index] = newItem( d ); - CHECK_PTR( vec[index] ); - numItems++; - return vec[index] != 0; - } else { - vec[index] = 0; // reset item - } - return TRUE; -} - -/*! - \internal -*/ - -bool QGVector::remove( uint index ) // remove item at index -{ -#if defined(CHECK_RANGE) - if ( index >= len ) { // range error - qWarning( "QGVector::remove: Index %d out of range", index ); - return FALSE; - } -#endif - if ( vec[index] ) { // valid item - deleteItem( vec[index] ); // delete it - vec[index] = 0; // reset pointer - numItems--; - } - return TRUE; -} - -/*! - \internal -*/ - -QCollection::Item QGVector::take( uint index ) // take out item -{ -#if defined(CHECK_RANGE) - if ( index >= len ) { // range error - qWarning( "QGVector::take: Index %d out of range", index ); - return 0; - } -#endif - Item d = vec[index]; // don't delete item - if ( d ) - numItems--; - vec[index] = 0; - return d; -} - - -/*! - \internal -*/ - -void QGVector::clear() // clear vector -{ - if ( vec ) { - for ( uint i=0; i len ) // init extra space added - memset( (void*)&vec[len], 0, (newsize-len)*sizeof(Item) ); - len = newsize; - return TRUE; -} - - -/*! - \internal -*/ - -bool QGVector::fill( Item d, int flen ) // resize and fill vector -{ - if ( flen < 0 ) - flen = len; // default: use vector length - else if ( !resize( flen ) ) - return FALSE; - for ( uint i=0; i<(uint)flen; i++ ) // insert d at every index - insert( i, d ); - return TRUE; -} - - -static QGVector *sort_vec=0; // current sort vector - - -#if defined(Q_C_CALLBACKS) -extern "C" { -#endif - -static int cmp_vec( const void *n1, const void *n2 ) -{ - return sort_vec->compareItems( *((QCollection::Item*)n1), *((QCollection::Item*)n2) ); -} - -#if defined(Q_C_CALLBACKS) -} -#endif - - -/*! - \internal -*/ - -void QGVector::sort() // sort vector -{ - if ( count() == 0 ) // no elements - return; - Item *start = &vec[0]; - Item *end = &vec[len-1]; - Item tmp; - while ( TRUE ) { // put all zero elements behind - while ( start < end && *start != 0 ) - start++; - while ( end > start && *end == 0 ) - end--; - if ( start < end ) { - tmp = *start; - *start = *end; - *end = tmp; - } else { - break; - } - } - sort_vec = (QGVector*)this; - qsort( vec, count(), sizeof(Item), cmp_vec ); - sort_vec = 0; -} - -/*! - \internal -*/ - -int QGVector::bsearch( Item d ) const // binary search; when sorted -{ - if ( !len ) - return -1; - if ( !d ) { -#if defined(CHECK_NULL) - qWarning( "QGVector::bsearch: Cannot search for null object" ); -#endif - return -1; - } - int n1 = 0; - int n2 = len - 1; - int mid = 0; - bool found = FALSE; - while ( n1 <= n2 ) { - int res; - mid = (n1 + n2)/2; - if ( vec[mid] == 0 ) // null item greater - res = -1; - else - res = ((QGVector*)this)->compareItems( d, vec[mid] ); - if ( res < 0 ) - n2 = mid - 1; - else if ( res > 0 ) - n1 = mid + 1; - else { // found it - found = TRUE; - break; - } - } - if ( !found ) - return -1; - // search to first of equal items - while ( (mid - 1 >= 0) && !((QGVector*)this)->compareItems(d, vec[mid-1]) ) - mid--; - return mid; -} - - -/*! - \internal -*/ - -int QGVector::findRef( Item d, uint index) const // find exact item in vector -{ -#if defined(CHECK_RANGE) - if ( index >= len ) { // range error - qWarning( "QGVector::findRef: Index %d out of range", index ); - return -1; - } -#endif - for ( uint i=index; i= len ) { // range error - qWarning( "QGVector::find: Index %d out of range", index ); - return -1; - } -#endif - for ( uint i=index; icompareItems( vec[i], d ) == 0 ) - return i; - } - return -1; -} - -/*! - \internal -*/ - -uint QGVector::containsRef( Item d ) const // get number of exact matches -{ - uint count = 0; - for ( uint i=0; icompareItems( vec[i], d ) == 0 ) - count++; - } - return count; -} - - -/*! - \internal -*/ - -bool QGVector::insertExpand( uint index, Item d )// insert and grow if necessary -{ - if ( index >= len ) { - if ( !resize( index+1 ) ) // no memory - return FALSE; - } - insert( index, d ); - return TRUE; -} - - -/*! - \internal -*/ - -void QGVector::toList( QGList *list ) const // store items in list -{ - list->clear(); - for ( uint i=0; iappend( vec[i] ); - } -} - - -void QGVector::warningIndexRange( uint i ) -{ -#if defined(CHECK_RANGE) - qWarning( "QGVector::operator[]: Index %d out of range", i ); -#else - Q_UNUSED( i ) -#endif -} - - -/***************************************************************************** - QGVector stream functions - *****************************************************************************/ -#ifndef QT_NO_DATASTREAM -QDataStream &operator>>( QDataStream &s, QGVector &vec ) -{ // read vector - return vec.read( s ); -} - -QDataStream &operator<<( QDataStream &s, const QGVector &vec ) -{ // write vector - return vec.write( s ); -} - -/*! - \internal -*/ - -QDataStream &QGVector::read( QDataStream &s ) // read vector from stream -{ - uint num; - s >> num; // read number of items - clear(); // clear vector - resize( num ); - for (uint i=0; i= len ) - warningIndexRange( index ); -#endif - return vec[index]; - } - - bool insertExpand( uint index, Item ); // insert, expand if necessary - - void toList( QGList * ) const; // put items in list - -#ifndef QT_NO_DATASTREAM - virtual QDataStream &read( QDataStream &, Item & ); - virtual QDataStream &write( QDataStream &, Item ) const; -#endif -private: - Item *vec; - uint len; - uint numItems; - - static void warningIndexRange( uint ); -}; - - -/***************************************************************************** - QGVector stream functions - *****************************************************************************/ - -#ifndef QT_NO_DATASTREAM -Q_EXPORT QDataStream &operator>>( QDataStream &, QGVector & ); -Q_EXPORT QDataStream &operator<<( QDataStream &, const QGVector & ); -#endif - -#endif // QGVECTOR_H diff --git a/qtools/qinternallist.h b/qtools/qinternallist.h index 09dbfce..b1cc64e 100644 --- a/qtools/qinternallist.h +++ b/qtools/qinternallist.h @@ -1,5 +1,5 @@ /**************************************************************************** -** +** ** ** Definition of QList template/macro class ** @@ -88,7 +88,6 @@ public: type *last() { return (type *)QGList::last(); } type *next() { return (type *)QGList::next(); } type *prev() { return (type *)QGList::prev(); } - void toVector( QGVector *vec )const{ QGList::toVector(vec); } private: void deleteItem( QCollection::Item d ); }; diff --git a/qtools/qlist.doc b/qtools/qlist.doc index 4f97e35..d28d662 100644 --- a/qtools/qlist.doc +++ b/qtools/qlist.doc @@ -1,5 +1,5 @@ /**************************************************************************** -** +** ** ** QList and QListIterator class documentation ** @@ -681,15 +681,6 @@ \sa first(), last(), next(), current() */ -/*! - \fn void QList::toVector( QGVector *vec ) const - Stores all list items in the vector \e vec. - - The vector must be have the same item type, otherwise the result - will be undefined. -*/ - - /***************************************************************************** QListIterator documentation *****************************************************************************/ diff --git a/qtools/qvector.doc b/qtools/qvector.doc deleted file mode 100644 index 2acf567..0000000 --- a/qtools/qvector.doc +++ /dev/null @@ -1,344 +0,0 @@ -/**************************************************************************** -** -** -** QVector class documentation -** -** Copyright (C) 1992-2000 Trolltech AS. All rights reserved. -** -** This file is part of the Qt GUI Toolkit. -** -** This file may be distributed under the terms of the Q Public License -** as defined by Trolltech AS of Norway and appearing in the file -** LICENSE.QPL included in the packaging of this file. -** -** This file may be distributed and/or modified under the terms of the -** GNU General Public License version 2 as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL included in the -** packaging of this file. -** -** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition -** licenses may use this file in accordance with the Qt Commercial License -** Agreement provided with the Software. -** -** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE -** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. -** -** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for -** information about Qt Commercial License Agreements. -** See http://www.trolltech.com/qpl/ for QPL licensing information. -** See http://www.trolltech.com/gpl/ for GPL licensing information. -** -** Contact info@trolltech.com if any conditions of this licensing are -** not clear to you. -** -**********************************************************************/ - - -/***************************************************************************** - QVector documentation - *****************************************************************************/ - -// BEING REVISED: ettrich -/*! - \class QVector qvector.h - - \brief The QVector class is a template collection class that - provides a vector (array). - - \ingroup tools - - QVector is implemented as a template class. Define a template - instance QVector\ to create a vector that contains pointers to - X, or X*. - - A vector is the same as an array. The main difference between - QVector and QArray is that QVector stores pointers to the elements, - while QArray stores the elements themselves (i.e. QArray is - value-based). - - Unless where otherwise stated, all functions that remove items from - the vector will also delete the element pointed to if auto-deletion - is enabled - see setAutoDelete(). By default, auto-deletion is - disabled. This behaviour can be changed in a subclass by - reimplementing the virtual method deleteItem(). - - Functions that compares items, e.g. find() and sort(), will do so - using the virtual function compareItems(). The default - implementation of this function will only compare the absolute - pointer values. Reimplement compareItems() in a subclass to get - searching and sorting based on the item contents. - - \sa \link collection.html Collection Classes\endlink, QArray -*/ - -/*! - \fn QVector::QVector() - - Constructs a null vector. - - \sa isNull() -*/ - -/*! - \fn QVector::QVector( uint size ) - - Constructs an vector with room for \a size items. Makes a null - vector if \a size == 0. - - All \a size positions in the vector are initialized to 0. - - \sa size(), resize(), isNull() -*/ - -/*! - \fn QVector::QVector( const QVector &v ) - - Constructs a copy of \a v. Only the pointers are copied (i.e. shallow copy). -*/ - -/*! - \fn QVector::~QVector() - - Removes all items from the vector, and destroys the vector itself. - - \sa clear() -*/ - -/*! - \fn QVector &QVector::operator=( const QVector &v ) - - Assigns \a v to this vector and returns a reference to this vector. - - This vector is first cleared, then all the items from \a v is copied - into this vector. Only the pointers are copied (i.e. shallow copy). - - \sa clear() -*/ - -/*! - \fn type **QVector::data() const - Returns a pointer to the actual vector data, which is an array of type*. - - The vector is a null vector if data() == 0 (null pointer). - - \sa isNull() -*/ - -/*! - \fn uint QVector::size() const - - Returns the size of the vector, i.e. the number of vector - positions. This is also the maximum number of items the vector can - hold. - - The vector is a null vector if size() == 0. - - \sa isNull(), resize(), count() -*/ - -/*! - \fn uint QVector::count() const - - Returns the number of items in the vector. The vector is empty if - count() == 0. - - \sa isEmpty(), size() -*/ - -/*! - \fn bool QVector::isEmpty() const - - Returns TRUE if the vector is empty, i.e. count() == 0, otherwise FALSE. - - \sa count() -*/ - -/*! - \fn bool QVector::isNull() const - - Returns TRUE if the vector is null, otherwise FALSE. - - A null vector has size() == 0 and data() == 0. - - \sa size() -*/ - -/*! - \fn bool QVector::resize( uint size ) - Resizes (expands or shrinks) the vector to \a size elements. The array - becomes a null array if \a size == 0. - - Any items in position \a size or beyond in the vector are removed. - New positions are initialized 0. - - Returns TRUE if successful, or FALSE if the memory cannot be allocated. - - \sa size(), isNull() -*/ - -/*! - \fn bool QVector::insert( uint i, const type *d ) - - Sets position \a i in the vector to contain the item \a d. \a i must - be less than size(). Any previous element in position \a i is removed. - - \sa at() -*/ - -/*! - \fn bool QVector::remove( uint i ) - - Removes the item at position \a i in the vector, if there is one. - \a i must be less than size(). - - Returns TRUE unless \a i is out of range. - - \sa take(), at() -*/ - -/*! - \fn type* QVector::take( uint i ) - - Returns the item at position \a i in the vector, and removes that - item from the vector. \a i must be less than size(). If there is no - item at position \a i, 0 is returned. - - In contrast to remove(), this function does \e not call deleteItem() - for the removed item. - - \sa remove(), at() -*/ - -/*! - \fn void QVector::clear() - - Removes all items from the vector, and destroys the vector - itself. - - The vector becomes a null vector. - - \sa isNull() -*/ - -/*! - \fn bool QVector::fill( const type *d, int size ) - - Inserts item \a d in all positions in the vector. Any existing items - are removed. If \a d is 0, the vector becomes empty. - - If \a size >= 0, the vector is first resized to \a size. By default, - \a size is -1. - - Returns TRUE if successful, or FALSE if the memory cannot be allocated - (only if a resize has been requested). - - \sa resize(), insert(), isEmpty() -*/ - -/*! - \fn void QVector::sort() - - Sorts the items in ascending order. Any empty positions will be put - last. - - Compares items using the virtual function compareItems(). - - \sa bsearch() -*/ - -/*! - \fn int QVector::bsearch( const type* d ) const - - In a sorted array, finds the first occurrence of \a d using binary - search. For a sorted array, this is generally much faster than - find(), which does a linear search. - - Returns the position of \a d, or -1 if \a d could not be found. \a d - may not be 0. - - Compares items using the virtual function compareItems(). - - \sa sort(), find() -*/ - - -/*! - \fn int QVector::findRef( const type *d, uint i ) const - - Finds the first occurrence of the item pointer \a d in the vector, - using linear search. The search starts at position \a i, which must - be less than size(). \a i is by default 0; i.e. the search starts at - the start of the vector. - - Returns the position of \a d, or -1 if \a d could not be found. - - This function does \e not use compareItems() to compare items. - - \sa find(), bsearch() -*/ - -/*! - \fn int QVector::find( const type *d, uint i ) const - - Finds the first occurrence of item \a d in the vector, using linear - search. The search starts at position \a i, which must be less than - size(). \a i is by default 0; i.e. the search starts at the start of - the vector. - - Returns the position of \e v, or -1 if \e v could not be found. - - Compares items using the virtual function compareItems(). - - \sa findRef(), bsearch() -*/ - - -/*! - \fn uint QVector::containsRef( const type *d ) const - - Returns the number of occurrences of the item pointer \a d in the - vector. - - This function does \e not use compareItems() to compare items. - - \sa findRef() -*/ - -/*! - \fn uint QVector::contains( const type *d ) const - - Returns the number of occurrences of item \a d in the vector. - - Compares items using the virtual function compareItems(). - - \sa containsRef() -*/ - -/*! - \fn type *QVector::operator[]( int i ) const - - Returns the item at position \a i, or 0 if there is no item at - that position. \a i must be less than size(). - - Equivalent to at( \a i ). - - \sa at() -*/ - -/*! - \fn type *QVector::at( uint i ) const - - Returns the item at position \a i, or 0 if there is no item at - that position. \a i must be less than size(). -*/ - - -/*! - \fn void QVector::toList( QGList *list ) const - - Copies all items in this vector to the list \a list. First, \a list - is cleared, then all items are appended to \a list. - - \sa QList, QStack, QQueue -*/ - diff --git a/qtools/qvector.h b/qtools/qvector.h deleted file mode 100644 index 36f0be7..0000000 --- a/qtools/qvector.h +++ /dev/null @@ -1,85 +0,0 @@ -/**************************************************************************** -** -** -** Definition of QVector template/macro class -** -** Created : 930907 -** -** Copyright (C) 1992-2000 Trolltech AS. All rights reserved. -** -** This file is part of the tools module of the Qt GUI Toolkit. -** -** This file may be distributed under the terms of the Q Public License -** as defined by Trolltech AS of Norway and appearing in the file -** LICENSE.QPL included in the packaging of this file. -** -** This file may be distributed and/or modified under the terms of the -** GNU General Public License version 2 as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL included in the -** packaging of this file. -** -** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition -** licenses may use this file in accordance with the Qt Commercial License -** Agreement provided with the Software. -** -** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE -** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. -** -** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for -** information about Qt Commercial License Agreements. -** See http://www.trolltech.com/qpl/ for QPL licensing information. -** See http://www.trolltech.com/gpl/ for GPL licensing information. -** -** Contact info@trolltech.com if any conditions of this licensing are -** not clear to you. -** -**********************************************************************/ - -#ifndef QVECTOR_H -#define QVECTOR_H - -#ifndef QT_H -#include "qgvector.h" -#endif // QT_H - - -template class QVector : public QGVector -{ -public: - QVector() {} - QVector( uint size ) : QGVector(size) {} - QVector( const QVector &v ) : QGVector(v) {} - ~QVector() { clear(); } - QVector &operator=(const QVector &v) - { return (QVector&)QGVector::operator=(v); } - type **data() const { return (type **)QGVector::data(); } - uint size() const { return QGVector::size(); } - uint count() const { return QGVector::count(); } - bool isEmpty() const { return QGVector::count() == 0; } - bool isNull() const { return QGVector::size() == 0; } - bool resize( uint size ) { return QGVector::resize(size); } - bool insert( uint i, const type *d){ return QGVector::insert(i,(Item)d); } - bool remove( uint i ) { return QGVector::remove(i); } - type *take( uint i ) { return (type *)QGVector::take(i); } - void clear() { QGVector::clear(); } - bool fill( const type *d, int size=-1 ) - { return QGVector::fill((Item)d,size);} - void sort() { QGVector::sort(); } - int bsearch( const type *d ) const{ return QGVector::bsearch((Item)d); } - int findRef( const type *d, uint i=0 ) const - { return QGVector::findRef((Item)d,i);} - int find( const type *d, uint i= 0 ) const - { return QGVector::find((Item)d,i); } - uint containsRef( const type *d ) const - { return QGVector::containsRef((Item)d); } - uint contains( const type *d ) const - { return QGVector::contains((Item)d); } - type *operator[]( int i ) const { return (type *)QGVector::at(i); } - type *at( uint i ) const { return (type *)QGVector::at(i); } - void toList( QGList *list ) const { QGVector::toList(list); } -private: - void deleteItem( Item d ) { if ( del_item ) delete (type *)d; } -}; - - -#endif // QVECTOR_H diff --git a/src/searchindex.cpp b/src/searchindex.cpp index d9e5c99..067370b 100644 --- a/src/searchindex.cpp +++ b/src/searchindex.cpp @@ -37,6 +37,8 @@ #include "filename.h" #include "membername.h" #include "resourcemgr.h" +#include "namespacedef.h" +#include "classdef.h" // file format: (all multi-byte values are stored in big endian format) // 4 byte header @@ -49,41 +51,33 @@ // (4 bytes index to url string + 4 bytes frequency counter) // for each url: a \0 terminated string -const int numIndexEntries = 256*256; +const size_t numIndexEntries = 256*256; //-------------------------------------------------------------------- -IndexWord::IndexWord(const char *word) : m_word(word), m_urls(17) +IndexWord::IndexWord(QCString word) : m_word(word) { - m_urls.setAutoDelete(TRUE); //printf("IndexWord::IndexWord(%s)\n",word); } void IndexWord::addUrlIndex(int idx,bool hiPriority) { //printf("IndexWord::addUrlIndex(%d,%d)\n",idx,hiPriority); - URLInfo *ui = m_urls.find(idx); - if (ui==0) + auto it = m_urls.find(idx); + if (it==m_urls.end()) { //printf("URLInfo::URLInfo(%d)\n",idx); - ui=new URLInfo(idx,0); - m_urls.insert(idx,ui); + it = m_urls.insert(std::make_pair(idx,URLInfo(idx,0))).first; } - ui->freq+=2; - if (hiPriority) ui->freq|=1; // mark as high priority document + it->second.freq+=2; + if (hiPriority) it->second.freq|=1; // mark as high priority document } //-------------------------------------------------------------------- -SearchIndex::SearchIndex() : SearchIndexIntf(Internal), - m_words(328829), m_index(numIndexEntries), m_url2IdMap(10007), m_urls(10007), m_urlIndex(-1) +SearchIndex::SearchIndex() : SearchIndexIntf(Internal) { - int i; - m_words.setAutoDelete(TRUE); - m_url2IdMap.setAutoDelete(TRUE); - m_urls.setAutoDelete(TRUE); - m_index.setAutoDelete(TRUE); - for (i=0;i); + m_index.resize(numIndexEntries); } void SearchIndex::setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile) @@ -167,16 +161,16 @@ void SearchIndex::setCurrentDoc(const Definition *ctx,const char *anchor,bool is } } - int *pIndex = m_url2IdMap.find(baseUrl); - if (pIndex==0) + auto it = m_url2IdMap.find(baseUrl.str()); + if (it == m_url2IdMap.end()) { ++m_urlIndex; - m_url2IdMap.insert(baseUrl,new int(m_urlIndex)); - m_urls.insert(m_urlIndex,new URL(name,url)); + m_url2IdMap.insert(std::make_pair(baseUrl.str(),m_urlIndex)); + m_urls.insert(std::make_pair(m_urlIndex,URL(name,url))); } else { - m_urls.insert(*pIndex,new URL(name,url)); + m_urls.insert(std::make_pair(it->second,URL(name,url))); } } @@ -208,17 +202,16 @@ void SearchIndex::addWord(const char *word,bool hiPriority,bool recurse) if (word==0 || word[0]=='\0') return; QCString wStr = QCString(word).lower(); //printf("SearchIndex::addWord(%s,%d) wStr=%s\n",word,hiPriority,wStr.data()); - IndexWord *w = m_words[wStr]; - if (w==0) + int idx=charsToIndex(wStr); + if (idx<0 || idx>=static_cast(m_index.size())) return; + auto it = m_words.find(wStr.str()); + if (it==m_words.end()) { - int idx=charsToIndex(wStr); //fprintf(stderr,"addWord(%s) at index %d\n",word,idx); - if (idx<0) return; - w = new IndexWord(wStr); - m_index[idx]->append(w); - m_words.insert(wStr,w); + m_index[idx].push_back(IndexWord(wStr)); + it = m_words.insert({ wStr.str(), m_index[idx].size()-1 }).first; } - w->addUrlIndex(m_urlIndex,hiPriority); + m_index[idx][it->second].addUrlIndex(m_urlIndex,hiPriority); int i; bool found=FALSE; if (!recurse) // the first time we check if we can strip the prefix @@ -244,12 +237,12 @@ void SearchIndex::addWord(const char *word,bool hiPriority) addWord(word,hiPriority,FALSE); } -static void writeInt(QFile &f,int index) +static void writeInt(QFile &f,size_t index) { - f.putch(((uint)index)>>24); - f.putch((((uint)index)>>16)&0xff); - f.putch((((uint)index)>>8)&0xff); - f.putch(((uint)index)&0xff); + f.putch(index>>24); + f.putch((index>>16)&0xff); + f.putch((index>>8)&0xff); + f.putch(index&0xff); } static void writeString(QFile &f,const char *s) @@ -261,21 +254,19 @@ static void writeString(QFile &f,const char *s) void SearchIndex::write(const char *fileName) { - int i; - int size=4; // for the header + size_t i; + size_t size=4; // for the header size+=4*numIndexEntries; // for the index - int wordsOffset = size; + size_t wordsOffset = size; // first pass: compute the size of the wordlist for (i=0;i *wlist = m_index[i]; - if (!wlist->isEmpty()) + const auto &wlist = m_index[i]; + if (!wlist.empty()) { - QListIterator iwi(*wlist); - IndexWord *iw; - for (iwi.toFirst();(iw=iwi.current());++iwi) + for (const auto &iw : wlist) { - int ws = iw->word().length()+1; + int ws = iw.word().length()+1; size+=ws+4; // word + url info list offset } size+=1; // zero list terminator @@ -283,19 +274,17 @@ void SearchIndex::write(const char *fileName) } // second pass: compute the offsets in the index - int indexOffsets[numIndexEntries]; - int offset=wordsOffset; + size_t indexOffsets[numIndexEntries]; + size_t offset=wordsOffset; for (i=0;i *wlist = m_index[i]; - if (!wlist->isEmpty()) + const auto &wlist = m_index[i]; + if (!wlist.empty()) { indexOffsets[i]=offset; - QListIterator iwi(*wlist); - IndexWord *iw; - for (iwi.toFirst();(iw=iwi.current());++iwi) + for (const auto &iw : wlist) { - offset+= iw->word().length()+1; + offset+= iw.word().length()+1; offset+=4; // word + offset to url info array } offset+=1; // zero list terminator @@ -305,42 +294,36 @@ void SearchIndex::write(const char *fileName) indexOffsets[i]=0; } } - int padding = size; + size_t padding = size; size = (size+3)&~3; // round up to 4 byte boundary padding = size - padding; - //int statsOffset = size; - //IndexWord *iw; - int *wordStatOffsets = new int[m_words.count()]; + std::vector wordStatOffsets(m_words.size()); int count=0; // third pass: compute offset to stats info for each word for (i=0;i *wlist = m_index[i]; - if (!wlist->isEmpty()) + const auto &wlist = m_index[i]; + if (!wlist.empty()) { - QListIterator iwi(*wlist); - IndexWord *iw; - for (iwi.toFirst();(iw=iwi.current());++iwi) + for (const auto &iw : wlist) { //printf("wordStatOffsets[%d]=%d\n",count,size); wordStatOffsets[count++] = size; - size+=4+iw->urls().count()*8; // count + (url_index,freq) per url + size+=4 + iw.urls().size() * 8; // count + (url_index,freq) per url } } } - int *urlOffsets = new int[m_urls.count()]; - //int urlsOffset = size; - QIntDictIterator udi(m_urls); - URL *url; - for (udi.toFirst();(url=udi.current());++udi) + std::vector urlOffsets(m_urls.size()); + for (const auto &udi : m_urls) { - urlOffsets[udi.currentKey()]=size; - size+=url->name.length()+1+ - url->url.length()+1; + urlOffsets[udi.first]=size; + size+=udi.second.name.length()+1+ + udi.second.url.length()+1; } + //printf("Total size %x bytes (word=%x stats=%x urls=%x)\n",size,wordsOffset,statsOffset,urlsOffset); QFile f(fileName); if (f.open(IO_WriteOnly)) @@ -356,14 +339,12 @@ void SearchIndex::write(const char *fileName) count=0; for (i=0;i *wlist = m_index[i]; - if (!wlist->isEmpty()) + const auto &wlist = m_index[i]; + if (!wlist.empty()) { - QListIterator iwi(*wlist); - IndexWord *iw; - for (iwi.toFirst();(iw=iwi.current());++iwi) + for (const auto &iw : wlist) { - writeString(f,iw->word()); + writeString(f,iw.word()); writeInt(f,wordStatOffsets[count++]); } f.putch(0); @@ -374,35 +355,29 @@ void SearchIndex::write(const char *fileName) // write word statistics for (i=0;i *wlist = m_index[i]; - if (!wlist->isEmpty()) + const auto &wlist = m_index[i]; + if (!wlist.empty()) { - QListIterator iwi(*wlist); - IndexWord *iw; - for (iwi.toFirst();(iw=iwi.current());++iwi) + for (const auto &iw : wlist) { - int numUrls = iw->urls().count(); + size_t numUrls = iw.urls().size(); writeInt(f,numUrls); - QIntDictIterator uli(iw->urls()); - URLInfo *ui; - for (uli.toFirst();(ui=uli.current());++uli) + for (const auto &ui : iw.urls()) { - writeInt(f,urlOffsets[ui->urlIdx]); - writeInt(f,ui->freq); + writeInt(f,urlOffsets[ui.second.urlIdx]); + writeInt(f,ui.second.freq); } } } } // write urls - for (udi.toFirst();(url=udi.current());++udi) + for (const auto &udi : m_urls) { - writeString(f,url->name); - writeString(f,url->url); + writeString(f,udi.second.name); + writeString(f,udi.second.url); } } - delete[] urlOffsets; - delete[] wordStatOffsets; } @@ -422,22 +397,12 @@ struct SearchDocEntry struct SearchIndexExternal::Private { - Private() : docEntries(12251) {} - SDict docEntries; + std::map docEntries; SearchDocEntry *current = 0; }; -SearchIndexExternal::SearchIndexExternal() : SearchIndexIntf(External) -{ - p = new SearchIndexExternal::Private; - p->docEntries.setAutoDelete(TRUE); - p->current=0; -} - -SearchIndexExternal::~SearchIndexExternal() +SearchIndexExternal::SearchIndexExternal() : SearchIndexIntf(External), p(std::make_unique()) { - //printf("p->docEntries.count()=%d\n",p->docEntries.count()); - delete p; } static QCString definitionToName(const Definition *ctx) @@ -497,29 +462,28 @@ static QCString definitionToName(const Definition *ctx) void SearchIndexExternal::setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile) { - QCString extId = stripPath(Config_getString(EXTERNAL_SEARCH_ID)); + static QCString extId = stripPath(Config_getString(EXTERNAL_SEARCH_ID)); QCString baseName = isSourceFile ? (dynamic_cast(ctx))->getSourceFileBase() : ctx->getOutputFileBase(); QCString url = baseName + Doxygen::htmlFileExtension; if (anchor) url+=QCString("#")+anchor; QCString key = extId+";"+url; - p->current = p->docEntries.find(key); - //printf("setCurrentDoc(url=%s,isSourceFile=%d) current=%p\n",url.data(),isSourceFile,p->current); - if (!p->current) + auto it = p->docEntries.find(key.str()); + if (it == p->docEntries.end()) { - SearchDocEntry *e = new SearchDocEntry; - e->type = isSourceFile ? QCString("source") : definitionToName(ctx); - e->name = ctx->qualifiedName(); + SearchDocEntry e; + e.type = isSourceFile ? QCString("source") : definitionToName(ctx); + e.name = ctx->qualifiedName(); if (ctx->definitionType()==Definition::TypeMember) { - e->args = (dynamic_cast(ctx))->argsString(); + e.args = (dynamic_cast(ctx))->argsString(); } - e->extId = extId; - e->url = url; - p->current = e; - p->docEntries.append(key,e); + e.extId = extId; + e.url = url; + it = p->docEntries.insert({key.str(),e}).first; //printf("searchIndexExt %s : %s\n",e->name.data(),e->url.data()); } + p->current = &it->second; } void SearchIndexExternal::addWord(const char *word,bool hiPriority) @@ -539,26 +503,25 @@ void SearchIndexExternal::write(const char *fileName) FTextStream t(&f); t << "" << endl; t << "" << endl; - SDict::Iterator it(p->docEntries); - SearchDocEntry *doc; - for (it.toFirst();(doc=it.current());++it) + for (auto &kv : p->docEntries) { - doc->normalText.addChar(0); // make sure buffer ends with a 0 terminator - doc->importantText.addChar(0); // make sure buffer ends with a 0 terminator + SearchDocEntry &doc = kv.second; + doc.normalText.addChar(0); // make sure buffer ends with a 0 terminator + doc.importantText.addChar(0); // make sure buffer ends with a 0 terminator t << " " << endl; - t << " " << doc->type << "" << endl; - t << " " << convertToXML(doc->name) << "" << endl; - if (!doc->args.isEmpty()) + t << " " << doc.type << "" << endl; + t << " " << convertToXML(doc.name) << "" << endl; + if (!doc.args.isEmpty()) { - t << " " << convertToXML(doc->args) << "" << endl; + t << " " << convertToXML(doc.args) << "" << endl; } - if (!doc->extId.isEmpty()) + if (!doc.extId.isEmpty()) { - t << " " << convertToXML(doc->extId) << "" << endl; + t << " " << convertToXML(doc.extId) << "" << endl; } - t << " " << convertToXML(doc->url) << "" << endl; - t << " " << convertToXML(doc->importantText.get()) << "" << endl; - t << " " << convertToXML(doc->normalText.get()) << "" << endl; + t << " " << convertToXML(doc.url) << "" << endl; + t << " " << convertToXML(doc.importantText.get()) << "" << endl; + t << " " << convertToXML(doc.normalText.get()) << "" << endl; t << " " << endl; } t << "" << endl; @@ -572,14 +535,6 @@ void SearchIndexExternal::write(const char *fileName) //--------------------------------------------------------------------------- // the following part is for the javascript based search engine -#include "memberdef.h" -#include "namespacedef.h" -#include "pagedef.h" -#include "classdef.h" -#include "filedef.h" -#include "language.h" -#include "doxygen.h" -#include "message.h" static SearchIndexInfo g_searchIndexInfo[NUM_SEARCH_INDICES]; diff --git a/src/searchindex.h b/src/searchindex.h index 923973c..71c1ce1 100644 --- a/src/searchindex.h +++ b/src/searchindex.h @@ -1,12 +1,12 @@ /****************************************************************************** * - * + * * * Copyright (C) 1997-2015 by Dimitri van Heesch. * * Permission to use, copy, modify, and distribute this software and its - * documentation under the terms of the GNU General Public License is hereby - * granted. No representations are made about the suitability of this software + * documentation under the terms of the GNU General Public License is hereby + * granted. No representations are made about the suitability of this software * for any purpose. It is provided "as is" without express or implied warranty. * See the GNU General Public License for more details. * @@ -18,11 +18,15 @@ #ifndef _SEARCHINDEX_H #define _SEARCHINDEX_H +#include +#include +#include +#include +#include + #include #include -#include #include -#include #include "sortdict.h" #include "definition.h" #include "util.h" @@ -40,7 +44,7 @@ void finalizeSearchIndexer(); struct URL { - URL(const char *n,const char *u) : name(n), url(u) {} + URL(QCString n,QCString u) : name(n), url(u) {} QCString name; QCString url; }; @@ -56,14 +60,15 @@ struct URLInfo class IndexWord { public: - IndexWord(const char *word); + using URLInfoMap = std::unordered_map; + IndexWord(QCString word); void addUrlIndex(int,bool); - const QIntDict &urls() const { return m_urls; } + URLInfoMap urls() const { return m_urls; } QCString word() const { return m_word; } private: QCString m_word; - QIntDict m_urls; + URLInfoMap m_urls; }; class SearchIndexIntf @@ -84,16 +89,16 @@ class SearchIndex : public SearchIndexIntf { public: SearchIndex(); - void setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile); - void addWord(const char *word,bool hiPriority); - void write(const char *file); + void setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile) override; + void addWord(const char *word,bool hiPriority) override; + void write(const char *file) override; private: void addWord(const char *word,bool hiPrio,bool recurse); - QDict m_words; - QVector< QList > m_index; - QDict m_url2IdMap; - QIntDict m_urls; - int m_urlIndex; + std::unordered_map m_words; + std::vector< std::vector< IndexWord> > m_index; + std::unordered_map m_url2IdMap; + std::map m_urls; + int m_urlIndex = -1; }; @@ -102,12 +107,11 @@ class SearchIndexExternal : public SearchIndexIntf struct Private; public: SearchIndexExternal(); - ~SearchIndexExternal(); void setCurrentDoc(const Definition *ctx,const char *anchor,bool isSourceFile); void addWord(const char *word,bool hiPriority); void write(const char *file); private: - Private *p; + std::unique_ptr p; }; //------- client side search index ---------------------- -- cgit v0.12