diff --git a/CMakeLists.txt b/CMakeLists.txt index d8b4e4f82..554469fa2 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -1,174 +1,176 @@ +cmake_minimum_required(VERSION 2.8.12) + # kdevplatform version set(KDEVPLATFORM_VERSION_MAJOR 5) set(KDEVPLATFORM_VERSION_MINOR 0) set(KDEVPLATFORM_VERSION_PATCH 80) # plugin versions listed in the .desktop files set(KDEV_PLUGIN_VERSION 27) # Increase this to reset incompatible item-repositories set(KDEV_ITEMREPOSITORY_VERSION 86) # library version / SO version set(KDEVPLATFORM_LIB_VERSION 10.0.0) set(KDEVPLATFORM_LIB_SOVERSION 10) -################################################################################ - -cmake_minimum_required(VERSION 2.8.12) project(KDevPlatform) # we need some parts of the ECM CMake helpers find_package (ECM 0.0.9 REQUIRED NO_MODULE) set(CMAKE_MODULE_PATH ${KDevPlatform_SOURCE_DIR}/cmake/modules ${ECM_MODULE_PATH}) include(KDECompilerSettings NO_POLICY_SCOPE) include(ECMAddTests) include(ECMOptionalAddSubdirectory) include(ECMInstallIcons) include(ECMSetupVersion) include(ECMMarkAsTest) include(ECMMarkNonGuiExecutable) include(ECMGenerateHeaders) include(ECMPackageConfigHelpers) include(GenerateExportHeader) include(FeatureSummary) include(WriteBasicConfigVersionFile) include(CheckFunctionExists) include(KDEInstallDirs) include(KDECMakeSettings) include(KDevPlatformMacros) set(QT_MIN_VERSION "5.4.0") find_package(Qt5 ${QT_MIN_VERSION} CONFIG REQUIRED Core DBus Widgets WebKitWidgets Concurrent Test) find_package(Qt5QuickWidgets ${QT_MIN_VERSION}) set_package_properties(Qt5QuickWidgets PROPERTIES PURPOSE "Qt5 QuickWidgets library (part of Qt >=5.3). Required for the Welcome Page plugin." ) set(KF5_DEP_VERSION "5.18.0") # need KAboutData::fromPluginMetaData in kcoreaddons find_package(KF5 ${KF5_DEP_VERSION} REQUIRED COMPONENTS Archive Config GuiAddons WidgetsAddons IconThemes I18n ItemModels ItemViews JobWidgets KCMUtils KIO NewStuff Notifications NotifyConfig Parts Service Sonnet TextEditor ThreadWeaver WindowSystem Declarative XmlGui ) find_package(Grantlee5) set_package_properties(Grantlee5 PROPERTIES PURPOSE "Grantlee templating library, needed for file templates" URL "http://www.grantlee.org/" TYPE RECOMMENDED) set(Boost_ADDITIONAL_VERSIONS 1.39.0 1.39) find_package(Boost 1.35.0) set_package_properties(Boost PROPERTIES PURPOSE "Boost libraries for enabling the classbrowser" URL "http://www.boost.org" TYPE REQUIRED) add_definitions( -DQT_DEPRECATED_WARNINGS -DQT_DISABLE_DEPRECATED_BEFORE=0x050400 -DQT_NO_URL_CAST_FROM_STRING -DQT_STRICT_ITERATORS -DQT_USE_FAST_CONCATENATION -DQT_USE_FAST_OPERATOR_PLUS ) # Turn off missing-field-initializers warning for GCC to avoid noise from false positives with empty {} # See discussion: http://mail.kde.org/pipermail/kdevelop-devel/2014-February/046910.html check_cxx_compiler_flag(-Wno-missing-field-initializers HAVE_MFI_FLAG) check_cxx_compiler_flag(-Werror=undefined-bool-conversion HAVE_UBC_FLAG) check_cxx_compiler_flag(-Werror=tautological-undefined-compare HAVE_TUC_FLAG) if (HAVE_MFI_FLAG) set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wno-missing-field-initializers") endif() if (HAVE_UBC_FLAG) set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Werror=undefined-bool-conversion") endif() if (HAVE_TUC_FLAG) set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Werror=tautological-undefined-compare") endif() +if (CMAKE_CXX_COMPILER_ID MATCHES "Clang") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wdocumentation") +endif() configure_file( ${CMAKE_CURRENT_SOURCE_DIR}/config-kdevplatform.h.cmake ${CMAKE_CURRENT_BINARY_DIR}/config-kdevplatform.h ) include_directories(${KDevPlatform_SOURCE_DIR} ${KDevPlatform_BINARY_DIR}) string(TOLOWER "${CMAKE_BUILD_TYPE}" CMAKE_BUILD_TYPE_TOLOWER) if(CMAKE_BUILD_TYPE_TOLOWER MATCHES "debug" OR CMAKE_BUILD_TYPE_TOLOWER STREQUAL "") set(COMPILER_OPTIMIZATIONS_DISABLED TRUE) else() set(COMPILER_OPTIMIZATIONS_DISABLED FALSE) endif() add_subdirectory(sublime) add_subdirectory(interfaces) add_subdirectory(project) add_subdirectory(language) add_subdirectory(shell) add_subdirectory(util) add_subdirectory(outputview) add_subdirectory(vcs) add_subdirectory(pics) add_subdirectory(debugger) add_subdirectory(documentation) add_subdirectory(serialization) add_subdirectory(template) add_subdirectory(tests) add_subdirectory(plugins) set(CMAKECONFIG_INSTALL_DIR "${KDE_INSTALL_CMAKEPACKAGEDIR}/KDevPlatform") ecm_configure_package_config_file("${CMAKE_CURRENT_SOURCE_DIR}/KDevPlatformConfig.cmake.in" "${CMAKE_CURRENT_BINARY_DIR}/KDevPlatformConfig.cmake" INSTALL_DESTINATION ${CMAKECONFIG_INSTALL_DIR} ) ecm_setup_version(${KDEVPLATFORM_VERSION_MAJOR}.${KDEVPLATFORM_VERSION_MINOR}.${KDEVPLATFORM_VERSION_PATCH} VARIABLE_PREFIX KDEVPLATFORM VERSION_HEADER "${CMAKE_CURRENT_BINARY_DIR}/kdevplatform_version.h" PACKAGE_VERSION_FILE "${CMAKE_CURRENT_BINARY_DIR}/KDevPlatformConfigVersion.cmake" SOVERSION ${KDEVPLATFORM_LIB_SOVERSION}) install( FILES "${KDevPlatform_BINARY_DIR}/kdevplatform_version.h" "${KDevPlatform_BINARY_DIR}/config-kdevplatform.h" DESTINATION "${KDE_INSTALL_INCLUDEDIR}/kdevplatform" ) install( FILES "${KDevPlatform_BINARY_DIR}/KDevPlatformConfig.cmake" "${KDevPlatform_BINARY_DIR}/KDevPlatformConfigVersion.cmake" cmake/modules/KDevPlatformMacros.cmake DESTINATION "${CMAKECONFIG_INSTALL_DIR}" ) install( EXPORT KDevPlatformTargets DESTINATION "${CMAKECONFIG_INSTALL_DIR}" NAMESPACE KDev:: FILE KDevPlatformTargets.cmake ) include(CTest) # CTestCustom.cmake has to be in the CTEST_BINARY_DIR. # in the KDE build system, this is the same as CMAKE_BINARY_DIR. configure_file(${CMAKE_SOURCE_DIR}/CTestCustom.cmake ${CMAKE_BINARY_DIR}/CTestCustom.cmake) feature_summary(WHAT ALL FATAL_ON_MISSING_REQUIRED_PACKAGES) diff --git a/language/backgroundparser/backgroundparser.h b/language/backgroundparser/backgroundparser.h index c14b75b4a..642b0e128 100644 --- a/language/backgroundparser/backgroundparser.h +++ b/language/backgroundparser/backgroundparser.h @@ -1,246 +1,246 @@ /* * This file is part of KDevelop * * Copyright 2006 Adam Treat * Copyright 2007 Kris Wong * Copyright 2007-2008 David Nolden * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU Library 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, write to the * Free Software Foundation, Inc., * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef KDEVPLATFORM_BACKGROUNDPARSER_H #define KDEVPLATFORM_BACKGROUNDPARSER_H #include #include #include #include #include #include #include #include "parsejob.h" class QMutex; namespace ThreadWeaver { class Job; class QObjectDecorator; class Weaver; } namespace KDevelop { class DocumentChangeTracker; class IDocument; class IProject; class ILanguageController; class ParseJob; class ParserDependencyPolicy; /** * This class handles the creation of parse jobs for given file URLs. * * For performance reasons you must always use clean, canonical URLs. If you do not do that, * issues might arise (and the debug build will assert). */ class KDEVPLATFORMLANGUAGE_EXPORT BackgroundParser : public QObject, public IStatus { Q_OBJECT Q_INTERFACES( KDevelop::IStatus ) public: explicit BackgroundParser(ILanguageController *languageController); ~BackgroundParser() override; QString statusName() const override; enum { BestPriority = -10000, ///Best possible job-priority. No jobs should actually have this. NormalPriority = 0, ///Standard job-priority. This priority is used for parse-jobs caused by document-editing/opening. ///There is an additional parsing-thread reserved for jobs with this and better priority, to improve responsiveness. InitialParsePriority = 10000, ///Priority used when adding file on project loading WorstPriority = 100000 ///Worst possible job-priority. }; /** * Queries the background parser as to whether there is currently * a parse job for @p document, and if so, returns it. * * This may not contain all of the parse jobs that are intended * unless you call in from your job's ThreadWeaver::Job::aboutToBeQueued() * function. */ Q_SCRIPTABLE ParseJob* parseJobForDocument(const IndexedString& document) const; /** * Set how many ThreadWeaver threads the background parser should set up and use. */ Q_SCRIPTABLE void setThreadCount(int threadCount); /** * Return how many ThreadWeaver threads the background parser should set up and use. */ Q_SCRIPTABLE int threadCount() const; /** * Set the delay in milliseconds before the background parser starts parsing. */ Q_SCRIPTABLE void setDelay(int milliseconds); /** * Returns all documents that were added through addManagedTopRange. This is typically the currently * open documents. */ Q_SCRIPTABLE QList managedDocuments(); /** * Returns the tracker for the given url if the document is being tracked, else returns zero. * This function is thread-safe, but the returned object also isn't, so you must not use it * when you're in a background thread without the foreground lock acquired. * */ DocumentChangeTracker* trackerForUrl(const IndexedString& url) const; Q_SIGNALS: - /** - * Emitted whenever a document parse-job has finished. - * The job contains the du-chain(if one was created) etc. - * - * The job is deleted after this signal has been emitted. Receivers should not hold - * references to it. + /** + * Emitted whenever a document parse-job has finished. + * The job contains the du-chain(if one was created) etc. + * + * The job is deleted after this signal has been emitted. Receivers should not hold + * references to it. * * Note that if you want to be get updated for all DUChain updates, use * DUChain::updateReady instead, as a single ParseJob may update multiple * DUChain top contexts. * * @sa DUChain::updateReady - */ + */ void parseJobFinished(KDevelop::ParseJob* job); // Implementations of IStatus signals void clearMessage( KDevelop::IStatus* ) override; void showMessage( KDevelop::IStatus*, const QString & message, int timeout = 0) override; void hideProgress( KDevelop::IStatus* ) override; void showProgress( KDevelop::IStatus*, int minimum, int maximum, int value) override; void showErrorMessage( const QString&, int ) override; public Q_SLOTS: /** * Aborts all parse jobs */ void abortAllJobs(); /** * Suspends execution of the background parser */ void suspend(); /** * Resumes execution of the background parser */ void resume(); - ///Reverts all requests that were made for the given notification-target. - ///priorities and requested features will be reverted as well. - ///When @p notifyWhenReady is set to a nullptr, all requests will be reverted. + /// Reverts all requests that were made for the given notification-target. + /// priorities and requested features will be reverted as well. + /// When @p notifyWhenReady is set to a nullptr, all requests will be reverted. void revertAllRequests(QObject* notifyWhenReady); /** * Queues up the @p url to be parsed. * @p features The minimum features that should be computed for this top-context * @p priority A value that manages the order of parsing. Documents with lowest priority are parsed first. * @param notifyWhenReady An optional pointer to a QObject that should contain a slot * "void updateReady(KDevelop::IndexedString url, KDevelop::ReferencedTopDUContext topContext)". * The notification is guaranteed to be called once for each call to addDocument. The given top-context * may be invalid if the update failed. * @param flags Flags indicating how the document should be treated in the queue * @param delay_ms The delay in milliseconds to add the job with, or one of the values of the * ILanguageSupport::ReparseDelaySpecialValues enum. */ void addDocument(const IndexedString& url, TopDUContext::Features features = TopDUContext::VisibleDeclarationsAndContexts, int priority = 0, QObject* notifyWhenReady = nullptr, ParseJob::SequentialProcessingFlags flags = ParseJob::IgnoresSequentialProcessing, int delay_ms = ILanguageSupport::DefaultDelay); /** * Removes the @p url that is registered for the given notification from the url. * * @param notifyWhenReady Notifier the document was added with. */ void removeDocument(const IndexedString& url, QObject* notifyWhenReady = nullptr); /** * Forces the current queue to be parsed. */ void parseDocuments(); void updateProgressData(); - ///Disables processing for all jobs that have a worse priority than @param priority - ///This can be used to temporarily limit the processing to only the most important jobs. - ///To only enable processing for important jobs, call setNeededPriority(0). - ///This should only be used to temporarily alter the processing. A progress-bar - ///will still be shown for the not yet processed jobs. + /// Disables processing for all jobs that have a worse priority than @p priority + /// This can be used to temporarily limit the processing to only the most important jobs. + /// To only enable processing for important jobs, call setNeededPriority(0). + /// This should only be used to temporarily alter the processing. A progress-bar + /// will still be shown for the not yet processed jobs. void setNeededPriority(int priority); - ///Disables all processing of new jobs, equivalent to setNeededPriority(BestPriority) + /// Disables all processing of new jobs, equivalent to setNeededPriority(BestPriority) void disableProcessing(); - ///Enables all processing of new jobs, equivalent to setNeededPriority(WorstPriority) + /// Enables all processing of new jobs, equivalent to setNeededPriority(WorstPriority) void enableProcessing(); - ///Returns true if the given url is queued for parsing + /// Returns true if the given url is queued for parsing bool isQueued(const IndexedString& url) const; - ///Retrieve the current priority for the given URL. - ///You need to check whether @param url is queued before calling this function. + /// Retrieve the current priority for the given URL. + /// You need to check whether @param url is queued before calling this function. int priorityForDocument(const IndexedString& url) const; - ///Returns the number of queued jobs (not yet running nor submitted to ThreadWeaver) + /// Returns the number of queued jobs (not yet running nor submitted to ThreadWeaver) int queuedCount() const; - ///Returns true if there are no jobs running nor queued anywhere + /// Returns true if there are no jobs running nor queued anywhere bool isIdle() const; void documentClosed(KDevelop::IDocument*); void documentLoaded(KDevelop::IDocument*); void documentUrlChanged(KDevelop::IDocument*); void loadSettings(); protected Q_SLOTS: void parseComplete(const ThreadWeaver::JobPointer& job); void parseProgress(KDevelop::ParseJob*, float value, QString text); void startTimer(int delay); void aboutToQuit(); void updateProgressBar(); private: friend class BackgroundParserPrivate; class BackgroundParserPrivate *d; private Q_SLOTS: /// Tracking of projects in state of loading. void projectAboutToBeOpened(KDevelop::IProject* project); void projectOpened(KDevelop::IProject* project); void projectOpeningAborted(KDevelop::IProject* project); }; } #endif diff --git a/language/codecompletion/codecompletionitem.h b/language/codecompletion/codecompletionitem.h index 666190916..df260b2ca 100644 --- a/language/codecompletion/codecompletionitem.h +++ b/language/codecompletion/codecompletionitem.h @@ -1,152 +1,152 @@ /* * KDevelop Generic Code Completion Support * * Copyright 2007-2008 David Nolden * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU Library 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, write to the * Free Software Foundation, Inc., * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef KDEVPLATFORM_KDEV_CODECOMPLETIONITEM_H #define KDEVPLATFORM_KDEV_CODECOMPLETIONITEM_H #include #include "../duchain/duchainpointer.h" #include "codecompletioncontext.h" namespace KTextEditor { class CodeCompletionModel; class Range; class Cursor; } class QModelIndex; namespace KDevelop { class CodeCompletionModel; struct CompletionTreeNode; class CompletionTreeItem; class IndexedType; class KDEVPLATFORMLANGUAGE_EXPORT CompletionTreeElement : public QSharedData { public: CompletionTreeElement(); virtual ~CompletionTreeElement(); CompletionTreeElement* parent() const; - ///Reparenting is not supported. This is only allowed if parent() is still zero. + /// Reparenting is not supported. This is only allowed if parent() is still zero. void setParent(CompletionTreeElement*); int rowInParent() const; int columnInParent() const; - ///Each element is either a node, or an item. + /// Each element is either a node, or an item. CompletionTreeNode* asNode(); CompletionTreeItem* asItem(); template T* asItem() { return dynamic_cast(this); } template const T* asItem() const { return dynamic_cast(this); } const CompletionTreeNode* asNode() const; const CompletionTreeItem* asItem() const; private: CompletionTreeElement* m_parent; int m_rowInParent; }; struct KDEVPLATFORMLANGUAGE_EXPORT CompletionTreeNode : public CompletionTreeElement { CompletionTreeNode(); ~CompletionTreeNode() override; KTextEditor::CodeCompletionModel::ExtraItemDataRoles role; QVariant roleValue; - ///Will append the child, and initialize it correctly to create a working tree-structure + /// Will append the child, and initialize it correctly to create a working tree-structure void appendChild(QExplicitlySharedDataPointer); void appendChildren(QList >); void appendChildren(QList >); - ///@warning Do not manipulate this directly, that's bad for consistency. Use appendChild instead. + /// @warning Do not manipulate this directly, that's bad for consistency. Use appendChild instead. QList > children; }; class KDEVPLATFORMLANGUAGE_EXPORT CompletionTreeItem : public CompletionTreeElement { public: - ///Execute the completion item. The default implementation does nothing. + /// Execute the completion item. The default implementation does nothing. virtual void execute(KTextEditor::View* view, const KTextEditor::Range& word); - ///Should return normal completion data, @see KTextEditor::CodeCompletionModel - ///The default implementation returns "unimplemented", so re-implement it! - ///The duchain is not locked when this is called - ///Navigation-widgets should be registered to the model, then it will care about the interaction. + /// Should return normal completion data, @see KTextEditor::CodeCompletionModel + /// The default implementation returns "unimplemented", so re-implement it! + /// The duchain is not locked when this is called + /// Navigation-widgets should be registered to the model, then it will care about the interaction. virtual QVariant data(const QModelIndex& index, int role, const CodeCompletionModel* model) const; - ///Should return the inheritance-depth. The completion-items don't need to return it through the data() function. + /// Should return the inheritance-depth. The completion-items don't need to return it through the data() function. virtual int inheritanceDepth() const; - ///Should return the argument-hint depth. The completion-items don't need to return it through the data() function. + /// Should return the argument-hint depth. The completion-items don't need to return it through the data() function. virtual int argumentHintDepth() const; - ///The default-implementation calls DUChainUtils::completionProperties + /// The default-implementation calls DUChainUtils::completionProperties virtual KTextEditor::CodeCompletionModel::CompletionProperties completionProperties() const; - ///If this item represents a Declaration, this should return the declaration. - ///The default-implementation returns zero. + /// If this item represents a Declaration, this should return the declaration. + /// The default-implementation returns zero. virtual DeclarationPointer declaration() const; - ///Should return the types should be used for matching items against this one when it's an argument hint. - ///The matching against all types should be done, and the best one will be used as final match result. + /// Should return the types should be used for matching items against this one when it's an argument hint. + /// The matching against all types should be done, and the best one will be used as final match result. virtual QList typeForArgumentMatching() const; - ///Should return whether this completion-items data changes with input done by the user during code-completion. - ///Returning true is very expensive. + /// Should return whether this completion-items data changes with input done by the user during code-completion. + /// Returning true is very expensive. virtual bool dataChangedWithInput() const; }; - ///A custom-group node, that can be used as-is. Just create it, and call appendChild to add group items. - ///The items in the group will be shown in the completion-list with a group-header that contains the given name +/// A custom-group node, that can be used as-is. Just create it, and call appendChild to add group items. +/// The items in the group will be shown in the completion-list with a group-header that contains the given name struct KDEVPLATFORMLANGUAGE_EXPORT CompletionCustomGroupNode : public CompletionTreeNode { - ///@param inheritanceDepth @ref KTextEditor::CodeCompletionModel::GroupRole + /// @param inheritanceDepth See KTextEditor::CodeCompletionModel::GroupRole explicit CompletionCustomGroupNode(QString groupName, int inheritanceDepth = 700); int inheritanceDepth; }; typedef QExplicitlySharedDataPointer CompletionTreeItemPointer; typedef QExplicitlySharedDataPointer CompletionTreeElementPointer; } Q_DECLARE_METATYPE(KDevelop::CompletionTreeElementPointer); #endif diff --git a/language/codecompletion/codecompletionmodel.cpp b/language/codecompletion/codecompletionmodel.cpp index 63bbe8a95..4d6247c6b 100644 --- a/language/codecompletion/codecompletionmodel.cpp +++ b/language/codecompletion/codecompletionmodel.cpp @@ -1,454 +1,454 @@ /* * KDevelop Generic Code Completion Support * * Copyright 2006-2008 Hamish Rodda * Copyright 2007-2008 David Nolden * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU Library 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, write to the * Free Software Foundation, Inc., * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #include "codecompletionmodel.h" #include #include #include #include #include #include #include #include #include #include "../duchain/declaration.h" #include "../duchain/classfunctiondeclaration.h" #include "../duchain/ducontext.h" #include "../duchain/duchain.h" #include "../duchain/namespacealiasdeclaration.h" #include "../duchain/parsingenvironment.h" #include "../duchain/duchainlock.h" #include "../duchain/duchainbase.h" #include "../duchain/topducontext.h" #include "../duchain/duchainutils.h" #include "../interfaces/quickopendataprovider.h" #include "../interfaces/icore.h" #include "../interfaces/ilanguagecontroller.h" #include "../interfaces/icompletionsettings.h" #include "util/debug.h" #include "codecompletionworker.h" #include "codecompletioncontext.h" #include #if KTEXTEDITOR_VERSION < QT_VERSION_CHECK(5, 10, 0) Q_DECLARE_METATYPE(KTextEditor::Cursor) #endif using namespace KTextEditor; //Multi-threaded completion creates some multi-threading related crashes, and sometimes shows the completions in the wrong position if the cursor was moved // #define SINGLE_THREADED_COMPLETION namespace KDevelop { class CompletionWorkerThread : public QThread { Q_OBJECT public: explicit CompletionWorkerThread(CodeCompletionModel* model) : QThread(model), m_model(model), m_worker(m_model->createCompletionWorker()) { Q_ASSERT(m_worker->parent() == nullptr); // Must be null, else we cannot change the thread affinity! m_worker->moveToThread(this); Q_ASSERT(m_worker->thread() == this); } ~CompletionWorkerThread() override { delete m_worker; } void run () override { //We connect directly, so we can do the pre-grouping within the background thread connect(m_worker, &CodeCompletionWorker::foundDeclarationsReal, m_model, &CodeCompletionModel::foundDeclarations, Qt::QueuedConnection); connect(m_model, &CodeCompletionModel::completionsNeeded, m_worker, static_cast,const Cursor&,View*)>(&CodeCompletionWorker::computeCompletions), Qt::QueuedConnection); connect(m_model, &CodeCompletionModel::doSpecialProcessingInBackground, m_worker, &CodeCompletionWorker::doSpecialProcessing); exec(); } CodeCompletionModel* m_model; CodeCompletionWorker* m_worker; }; bool CodeCompletionModel::forceWaitForModel() { return m_forceWaitForModel; } void CodeCompletionModel::setForceWaitForModel(bool wait) { m_forceWaitForModel = wait; } CodeCompletionModel::CodeCompletionModel( QObject * parent ) : KTextEditor::CodeCompletionModel(parent) , m_forceWaitForModel(false) , m_fullCompletion(true) , m_mutex(new QMutex) , m_thread(nullptr) { qRegisterMetaType(); } void CodeCompletionModel::initialize() { if(!m_thread) { m_thread = new CompletionWorkerThread(this); #ifdef SINGLE_THREADED_COMPLETION m_thread->m_worker = createCompletionWorker(); #endif m_thread->start(); } } CodeCompletionModel::~CodeCompletionModel() { if(m_thread->m_worker) m_thread->m_worker->abortCurrentCompletion(); m_thread->quit(); m_thread->wait(); delete m_thread; delete m_mutex; } void CodeCompletionModel::addNavigationWidget(const CompletionTreeElement* element, QWidget* widget) const { Q_ASSERT(dynamic_cast(widget)); m_navigationWidgets[element] = widget; } bool CodeCompletionModel::fullCompletion() const { return m_fullCompletion; } KDevelop::CodeCompletionWorker* CodeCompletionModel::worker() const { return m_thread->m_worker; } void CodeCompletionModel::clear() { beginResetModel(); m_completionItems.clear(); m_navigationWidgets.clear(); m_completionContext.reset(); endResetModel(); } void CodeCompletionModel::completionInvokedInternal(KTextEditor::View* view, const KTextEditor::Range& range, InvocationType invocationType, const QUrl& url) { Q_ASSERT(m_thread == worker()->thread()); Q_UNUSED(invocationType) DUChainReadLocker lock(DUChain::lock(), 400); if( !lock.locked() ) { qCDebug(LANGUAGE) << "could not lock du-chain in time"; return; } TopDUContext* top = DUChainUtils::standardContextForUrl( url ); if(!top) { return; } setCurrentTopContext(TopDUContextPointer(top)); RangeInRevision rangeInRevision = top->transformToLocalRevision(KTextEditor::Range(range)); if (top) { qCDebug(LANGUAGE) << "completion invoked for context" << (DUContext*)top; if( top->parsingEnvironmentFile() && top->parsingEnvironmentFile()->modificationRevision() != ModificationRevision::revisionForFile(IndexedString(url.toString())) ) { - qCDebug(LANGUAGE) << "Found context is not current. Its revision is " /*<< top->parsingEnvironmentFile()->modificationRevision() << " while the document-revision is " << ModificationRevision::revisionForFile(IndexedString(url.toString()))*/; + qCDebug(LANGUAGE) << "Found context is not current."; } DUContextPointer thisContext; { qCDebug(LANGUAGE) << "apply specialization:" << range.start(); thisContext = SpecializationStore::self().applySpecialization(top->findContextAt(rangeInRevision.start), top); if ( thisContext ) { qCDebug(LANGUAGE) << "after specialization:" << thisContext->localScopeIdentifier().toString() << thisContext->rangeInCurrentRevision(); } if(!thisContext) thisContext = top; qCDebug(LANGUAGE) << "context is set to" << thisContext.data(); if( !thisContext ) { qCDebug(LANGUAGE) << "================== NO CONTEXT FOUND ======================="; beginResetModel(); m_completionItems.clear(); m_navigationWidgets.clear(); endResetModel(); return; } } lock.unlock(); if(m_forceWaitForModel) emit waitForReset(); emit completionsNeeded(thisContext, range.start(), view); } else { qCDebug(LANGUAGE) << "Completion invoked for unknown context. Document:" << url << ", Known documents:" << DUChain::self()->documents(); } } void CodeCompletionModel::completionInvoked(KTextEditor::View* view, const KTextEditor::Range& range, InvocationType invocationType) { //If this triggers, initialize() has not been called after creation. Q_ASSERT(m_thread); KDevelop::ICompletionSettings::CompletionLevel level = KDevelop::ICore::self()->languageController()->completionSettings()->completionLevel(); if(level == KDevelop::ICompletionSettings::AlwaysFull || (invocationType != AutomaticInvocation && level == KDevelop::ICompletionSettings::MinimalWhenAutomatic)) m_fullCompletion = true; else m_fullCompletion = false; //Only use grouping in full completion mode setHasGroups(m_fullCompletion); Q_UNUSED(invocationType) if (!worker()) { qCWarning(LANGUAGE) << "Completion invoked on a completion model which has no code completion worker assigned!"; } beginResetModel(); m_navigationWidgets.clear(); m_completionItems.clear(); endResetModel(); worker()->abortCurrentCompletion(); worker()->setFullCompletion(m_fullCompletion); QUrl url = view->document()->url(); completionInvokedInternal(view, range, invocationType, url); } void CodeCompletionModel::foundDeclarations(const QList>& items, const QExplicitlySharedDataPointer& completionContext) { m_completionContext = completionContext; if(m_completionItems.isEmpty() && items.isEmpty()) { if(m_forceWaitForModel) { // TODO KF5: Check if this actually works beginResetModel(); endResetModel(); //If we need to reset the model, reset it } return; //We don't need to reset, which is bad for target model } beginResetModel(); m_completionItems = items; endResetModel(); if(m_completionContext) { qCDebug(LANGUAGE) << "got completion-context with " << m_completionContext->ungroupedElements().size() << "ungrouped elements"; } } KTextEditor::CodeCompletionModelControllerInterface::MatchReaction CodeCompletionModel::matchingItem(const QModelIndex& /*matched*/) { return None; } void CodeCompletionModel::setCompletionContext(QExplicitlySharedDataPointer completionContext) { QMutexLocker lock(m_mutex); m_completionContext = completionContext; if(m_completionContext) { qCDebug(LANGUAGE) << "got completion-context with " << m_completionContext->ungroupedElements().size() << "ungrouped elements"; } } QExplicitlySharedDataPointer CodeCompletionModel::completionContext() const { QMutexLocker lock(m_mutex); return m_completionContext; } void CodeCompletionModel::executeCompletionItem(View* view, const KTextEditor::Range& word, const QModelIndex& index) const { //We must not lock the duchain at this place, because the items might rely on that CompletionTreeElement* element = static_cast(index.internalPointer()); if( !element || !element->asItem() ) return; element->asItem()->execute(view, word); } QExplicitlySharedDataPointer< KDevelop::CompletionTreeElement > CodeCompletionModel::itemForIndex(QModelIndex index) const { CompletionTreeElement* element = static_cast(index.internalPointer()); return QExplicitlySharedDataPointer< KDevelop::CompletionTreeElement >(element); } QVariant CodeCompletionModel::data(const QModelIndex& index, int role) const { if ( role == Qt::TextAlignmentRole && index.column() == 0 ) { return Qt::AlignRight; } auto element = static_cast(index.internalPointer()); if( !element ) return QVariant(); if( role == CodeCompletionModel::GroupRole ) { if( element->asNode() ) { return QVariant(element->asNode()->role); }else { qCDebug(LANGUAGE) << "Requested group-role from leaf tree element"; return QVariant(); } }else{ if( element->asNode() ) { if( role == CodeCompletionModel::InheritanceDepth ) { auto customGroupNode = dynamic_cast(element); if(customGroupNode) return QVariant(customGroupNode->inheritanceDepth); } if( role == element->asNode()->role ) { return element->asNode()->roleValue; } else { return QVariant(); } } } if(!element->asItem()) { qCWarning(LANGUAGE) << "Error in completion model"; return QVariant(); } //Navigation widget interaction is done here, the other stuff is done within the tree-elements switch (role) { case CodeCompletionModel::InheritanceDepth: return element->asItem()->inheritanceDepth(); case CodeCompletionModel::ArgumentHintDepth: return element->asItem()->argumentHintDepth(); case CodeCompletionModel::ItemSelected: { DeclarationPointer decl = element->asItem()->declaration(); if(decl) { DUChain::self()->emitDeclarationSelected(decl); } break; } } //In minimal completion mode, hide all columns except the "name" one if(!m_fullCompletion && role == Qt::DisplayRole && index.column() != Name && (element->asItem()->argumentHintDepth() == 0 || index.column() == Prefix)) return QVariant(); //In reduced completion mode, don't show information text with the selected items if(role == ItemSelected && (!m_fullCompletion || !ICore::self()->languageController()->completionSettings()->showMultiLineSelectionInformation())) return QVariant(); return element->asItem()->data(index, role, this); } KDevelop::TopDUContextPointer CodeCompletionModel::currentTopContext() const { return m_currentTopContext; } void CodeCompletionModel::setCurrentTopContext(KDevelop::TopDUContextPointer topContext) { m_currentTopContext = topContext; } QModelIndex CodeCompletionModel::index(int row, int column, const QModelIndex& parent) const { if( parent.isValid() ) { CompletionTreeElement* element = static_cast(parent.internalPointer()); CompletionTreeNode* node = element->asNode(); if( !node ) { qCDebug(LANGUAGE) << "Requested sub-index of leaf node"; return QModelIndex(); } if (row < 0 || row >= node->children.count() || column < 0 || column >= ColumnCount) return QModelIndex(); return createIndex(row, column, node->children[row].data()); } else { if (row < 0 || row >= m_completionItems.count() || column < 0 || column >= ColumnCount) return QModelIndex(); return createIndex(row, column, const_cast(m_completionItems[row].data())); } } QModelIndex CodeCompletionModel::parent ( const QModelIndex & index ) const { if(rowCount() == 0) return QModelIndex(); if( index.isValid() ) { CompletionTreeElement* element = static_cast(index.internalPointer()); if( element->parent() ) return createIndex( element->rowInParent(), element->columnInParent(), element->parent() ); } return QModelIndex(); } int CodeCompletionModel::rowCount ( const QModelIndex & parent ) const { if( parent.isValid() ) { CompletionTreeElement* element = static_cast(parent.internalPointer()); CompletionTreeNode* node = element->asNode(); if( !node ) return 0; return node->children.count(); }else{ return m_completionItems.count(); } } QString CodeCompletionModel::filterString(KTextEditor::View* view, const KTextEditor::Range& range, const KTextEditor::Cursor& position) { m_filterString = KTextEditor::CodeCompletionModelControllerInterface::filterString(view, range, position); return m_filterString; } } #include "moc_codecompletionmodel.cpp" #include "codecompletionmodel.moc" diff --git a/language/duchain/types/arraytype.h b/language/duchain/types/arraytype.h index 5b82a53a9..3187ac138 100644 --- a/language/duchain/types/arraytype.h +++ b/language/duchain/types/arraytype.h @@ -1,108 +1,106 @@ /* This file is part of KDevelop Copyright 2006 Roberto Raggi Copyright 2006-2008 Hamish Rodda Copyright 2007-2008 David Nolden This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License version 2 as published by the Free Software Foundation. This library 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 Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; see the file COPYING.LIB. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef KDEVPLATFORM_ARRAYTYPE_H #define KDEVPLATFORM_ARRAYTYPE_H #include "abstracttype.h" namespace KDevelop { class ArrayTypeData; class KDEVPLATFORMLANGUAGE_EXPORT ArrayType : public AbstractType { public: typedef TypePtr Ptr; /// Default constructor ArrayType(); /// Copy constructor. \param rhs type to copy ArrayType(const ArrayType& rhs); /// Constructor using raw data. \param data internal data. explicit ArrayType(ArrayTypeData& data); /// Destructor virtual ~ArrayType(); AbstractType* clone() const override; bool equals(const AbstractType* rhs) const override; /** * Retrieve the dimension of this array type. Multiple-dimensioned * arrays will have another array type as their elementType(). * * \returns the dimension of the array, or zero if the array is dimensionless (eg. int[]) */ int dimension () const; /** * Set this array type's dimension. * If @p dimension is zero, the array is considered dimensionless (eg. int[]). * * \param dimension new dimension, set to zero for a dimensionless type (eg. int[]) */ void setDimension(int dimension); /** * Retrieve the element type of the array, e.g. "int" for int[3]. * * \returns the element type. */ AbstractType::Ptr elementType () const; /** * Set the element type of the array, e.g. "int" for int[3]. - * - * \returns the element type. */ void setElementType(AbstractType::Ptr type); QString toString() const override; uint hash() const override; WhichType whichType() const override; void exchangeTypes( TypeExchanger* exchanger ) override; enum { Identity = 7 }; typedef ArrayTypeData Data; protected: void accept0 (TypeVisitor *v) const override; TYPE_DECLARE_DATA(ArrayType) }; template<> inline ArrayType* fastCast(AbstractType* from) { if(!from || from->whichType() != AbstractType::TypeArray) return nullptr; else return static_cast(from); } } #endif // KDEVPLATFORM_TYPESYSTEM_H diff --git a/plugins/quickopen/quickopenwidget.h b/plugins/quickopen/quickopenwidget.h index a39d25826..407fb31b8 100644 --- a/plugins/quickopen/quickopenwidget.h +++ b/plugins/quickopen/quickopenwidget.h @@ -1,110 +1,112 @@ /* * This file is part of KDevelop * * Copyright 2007 David Nolden * Copyright 2016 Kevin Funk * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU Library 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, write to the * Free Software Foundation, Inc., * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef KDEVPLATFORM_PLUGIN_QUICKOPENWIDGET_H #define KDEVPLATFORM_PLUGIN_QUICKOPENWIDGET_H #include "ui_quickopenwidget.h" #include #include #include class QuickOpenModel; class QLineEdit; -///Will delete itself once the dialog is closed, so use QPointer when referencing it permanently +/// Will delete itself once the dialog is closed, so use QPointer when referencing it permanently class QuickOpenWidget : public QMenu { Q_OBJECT public: /** * @param initialItems List of items that should initially be enabled in the quickopen-list. If empty, all are enabled. * @param initialScopes List of scopes that should initially be enabled in the quickopen-list. If empty, all are enabled. * @param listOnly when this is true, the given items will be listed, but all filtering using checkboxes is disabled. - * @param noSearchFied when this is true, no search-line is shown. + * @param noSearchField when this is true, no search-line is shown. * */ QuickOpenWidget( QString title, QuickOpenModel* model, const QStringList& initialItems, const QStringList& initialScopes, bool listOnly = false, bool noSearchField = false ); ~QuickOpenWidget() override; void setPreselectedText(const QString &text); void prepareShow(); void setAlternativeSearchField(QLineEdit* alterantiveSearchField); //Shows OK + Cancel. By default they are hidden void showStandardButtons(bool show); void showSearchField(bool show); signals: void scopesChanged( const QStringList& scopes ); void itemsChanged( const QStringList& scopes ); void ready(); private slots: void callRowSelected(); void updateTimerInterval( bool cheapFilterChange ); void accept(); void textChanged( const QString& str ); void updateProviders(); void doubleClicked ( const QModelIndex & index ); void applyFilter(); private: void showEvent(QShowEvent *) override; bool eventFilter ( QObject * watched, QEvent * event ) override; void avoidMenuAltFocus(); QuickOpenModel* m_model; bool m_expandedTemporary, m_hadNoCommandSinceAlt; QTime m_altDownTime; QString m_preselectedText; QTimer m_filterTimer; QString m_filter; public: Ui::QuickOpenWidget ui; friend class QuickOpenWidgetDialog; friend class QuickOpenPlugin; friend class QuickOpenLineEdit; }; class QuickOpenWidgetDialog : public QObject { Q_OBJECT public: QuickOpenWidgetDialog( QString title, QuickOpenModel* model, const QStringList& initialItems, const QStringList& initialScopes, bool listOnly = false, bool noSearchField = false ); ~QuickOpenWidgetDialog() override; - ///Shows the dialog + + /// Shows the dialog void run(); + QuickOpenWidget* widget() const { return m_widget; } private: - QDialog* m_dialog; //Warning: m_dialog is also the parent + QDialog* m_dialog; /// @warning m_dialog is also the parent QuickOpenWidget* m_widget; }; #endif diff --git a/plugins/subversion/CMakeLists.txt b/plugins/subversion/CMakeLists.txt index 12ac84cf7..0336574f6 100644 --- a/plugins/subversion/CMakeLists.txt +++ b/plugins/subversion/CMakeLists.txt @@ -1,98 +1,98 @@ add_definitions(-DTRANSLATION_DOMAIN=\"kdevsubversion\") # silence the deprecation warnings # if someone wants to fix the code, I'd welcome it # but for now, we won't spend time on it... add_definitions(-DSVN_DEPRECATED=) -project(KDevSubversionPlugin) +string(REPLACE "-Wdocumentation" "" CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS}") add_subdirectory(tests) add_subdirectory(icons) include_directories( - ${SUBVERSION_INCLUDE_DIRS} + SYSTEM ${SUBVERSION_INCLUDE_DIRS} ) kde_enable_exceptions() ########### next target ############### set(kdevsubversion_WRAPPER_SRCS kdevsvncpp/apr.cpp kdevsvncpp/client_annotate.cpp kdevsvncpp/client_cat.cpp kdevsvncpp/client.cpp kdevsvncpp/client_diff.cpp kdevsvncpp/client_ls.cpp kdevsvncpp/client_modify.cpp kdevsvncpp/client_property.cpp kdevsvncpp/client_status.cpp kdevsvncpp/context.cpp kdevsvncpp/datetime.cpp kdevsvncpp/dirent.cpp kdevsvncpp/entry.cpp kdevsvncpp/exception.cpp kdevsvncpp/info.cpp kdevsvncpp/log_entry.cpp kdevsvncpp/path.cpp kdevsvncpp/pool.cpp kdevsvncpp/property.cpp kdevsvncpp/revision.cpp kdevsvncpp/status.cpp kdevsvncpp/status_selection.cpp kdevsvncpp/targets.cpp kdevsvncpp/url.cpp kdevsvncpp/wc.cpp ) set(kdevsubversion_JOB_SRCS svninternaljobbase.cpp svnjobbase.cpp svncommitjob.cpp svnstatusjob.cpp svnaddjob.cpp svnupdatejob.cpp svnrevertjob.cpp svnremovejob.cpp svninfojob.cpp svndiffjob.cpp svncatjob.cpp svncopyjob.cpp svnmovejob.cpp svnlogjob.cpp svnblamejob.cpp svnimportjob.cpp svncheckoutjob.cpp ) set(kdevsubversion_PART_SRCS kdevsvnplugin.cpp svnssldialog.cpp svnimportmetadatawidget.cpp svncheckoutmetadatawidget.cpp svnclient.cpp svnlocationwidget.cpp ) set(kdevsubversion_PART_UI ui/ssltrustdialog.ui ui/importmetadatawidget.ui ui/checkoutmetadatawidget.ui ) ki18n_wrap_ui(kdevsubversion_PART_SRCS ${kdevsubversion_PART_UI}) kdevplatform_add_plugin(kdevsubversion JSON kdevsubversion.json SOURCES ${kdevsubversion_PART_SRCS} ${kdevsubversion_JOB_SRCS} ${kdevsubversion_WRAPPER_SRCS}) target_link_libraries(kdevsubversion ${SUBVERSION_LIBRARIES} KF5::KIOCore KF5::TextEditor KF5::ThreadWeaver KF5::Parts KDev::Interfaces KDev::Vcs KDev::OutputView KDev::Project ) diff --git a/serialization/itemrepository.h b/serialization/itemrepository.h index 1667c1082..a3a27896a 100644 --- a/serialization/itemrepository.h +++ b/serialization/itemrepository.h @@ -1,2251 +1,2250 @@ /* Copyright 2008 David Nolden This library is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License version 2 as published by the Free Software Foundation. This library 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 Library General Public License for more details. You should have received a copy of the GNU Library General Public License along with this library; see the file COPYING.LIB. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ #ifndef KDEVPLATFORM_ITEMREPOSITORY_H #define KDEVPLATFORM_ITEMREPOSITORY_H #include #include #include #include #include #include "referencecounting.h" #include "abstractitemrepository.h" #include "repositorymanager.h" #include "itemrepositoryregistry.h" //#define DEBUG_MONSTERBUCKETS // #define DEBUG_ITEMREPOSITORY_LOADING // #define ifDebugInfiniteRecursion(x) x #define ifDebugInfiniteRecursion(x) // #define ifDebugLostSpace(x) x #define ifDebugLostSpace(x) // #define DEBUG_INCORRECT_DELETE //Makes sure that all items stay reachable through the basic hash // #define DEBUG_ITEM_REACHABILITY ///@todo Dynamic bucket hash size #ifdef DEBUG_ITEM_REACHABILITY #define ENSURE_REACHABLE(bucket) Q_ASSERT(allItemsReachable(bucket)); #define IF_ENSURE_REACHABLE(x) x #else #define ENSURE_REACHABLE(bucket) #define IF_ENSURE_REACHABLE(x) #endif #define ITEMREPOSITORY_USE_MMAP_LOADING //Assertion macro that prevents warnings if debugging is disabled //Only use it to verify values, it should not call any functions, since else the function will even be called in release mode #ifdef QT_NO_DEBUG #define VERIFY(X) if(!(X)) {qWarning() << "Failed to verify expression" << #X;} #else #define VERIFY(X) Q_ASSERT(X) #endif ///When this is uncommented, a 64-bit test-value is written behind the area an item is allowed to write into before ///createItem(..) is called, and an assertion triggers when it was changed during createItem(), which means createItem wrote too long. ///The problem: This temporarily overwrites valid data in the following item, so it will cause serious problems if that data is accessed ///during the call to createItem(). // #define DEBUG_WRITING_EXTENTS class TestItemRepository; namespace KDevelop { /** * This file implements a generic bucket-based indexing repository, that can be used for example to index strings. * * All you need to do is define your item type that you want to store into the repository, and create a request item * similar to ExampleItemRequest that compares and fills the defined item type. * * For example the string repository uses "unsigned short" as item-type, uses that actual value to store the length of the string, * and uses the space behind to store the actual string content. * * @see AbstractItemRepository * @see ItemRepository * * @see ExampleItem * @see ExampleItemRequest * * @see typerepository.h * @see stringrepository.h * @see indexedstring.h */ enum { ItemRepositoryBucketSize = 1<<16, ItemRepositoryBucketLimit = 1<<16 }; /** * Buckets are the memory-units that are used to store the data in an ItemRepository. * * About monster buckets: Normally a bucket has a size of 64kb, but when an item is * allocated that is larger than that, a "monster bucket" is allocated, which spans the * space of multiple buckets. */ template class Bucket { public: enum { AdditionalSpacePerItem = 2 }; enum { ObjectMapSize = ((ItemRepositoryBucketSize / ItemRequest::AverageSize) * 3) / 2 + 1, MaxFreeItemsForHide = 0, //When less than this count of free items in one buckets is reached, the bucket is removed from the global list of buckets with free items MaxFreeSizeForHide = fixedItemSize ? fixedItemSize : 0, //Only when the largest free size is smaller then this, the bucket is taken from the free list MinFreeItemsForReuse = 10,//When this count of free items in one bucket is reached, consider re-assigning them to new requests MinFreeSizeForReuse = ItemRepositoryBucketSize/20 //When the largest free item is bigger then this, the bucket is automatically added to the free list }; enum { NextBucketHashSize = ObjectMapSize, //Affects the average count of bucket-chains that need to be walked in ItemRepository::index. Must be a multiple of ObjectMapSize DataSize = sizeof(char) + sizeof(unsigned int) * 3 + ItemRepositoryBucketSize + sizeof(short unsigned int) * (ObjectMapSize + NextBucketHashSize + 1) }; enum { CheckStart = 0xff00ff1, CheckEnd = 0xfafcfb }; Bucket() : m_monsterBucketExtent(0) , m_available(0) , m_data(nullptr) , m_mappedData(nullptr) , m_objectMap(nullptr) , m_largestFreeItem(0) , m_freeItemCount(0) , m_nextBucketHash(nullptr) , m_dirty(false) , m_changed(false) , m_lastUsed(0) { } ~Bucket() { if(m_data != m_mappedData) { delete[] m_data; delete[] m_nextBucketHash; delete[] m_objectMap; } } void initialize(int monsterBucketExtent) { if(!m_data) { m_monsterBucketExtent = monsterBucketExtent; m_available = ItemRepositoryBucketSize; m_data = new char[ItemRepositoryBucketSize + monsterBucketExtent * DataSize]; memset(m_data, 0, (ItemRepositoryBucketSize + monsterBucketExtent * DataSize) * sizeof(char)); //The bigger we make the map, the lower the probability of a clash(and thus bad performance). However it increases memory usage. m_objectMap = new short unsigned int[ObjectMapSize]; memset(m_objectMap, 0, ObjectMapSize * sizeof(short unsigned int)); m_nextBucketHash = new short unsigned int[NextBucketHashSize]; memset(m_nextBucketHash, 0, NextBucketHashSize * sizeof(short unsigned int)); m_changed = true; m_dirty = false; m_lastUsed = 0; } } template void readValue(char*& from, T& to) { to = *reinterpret_cast(from); from += sizeof(T); } void initializeFromMap(char* current) { if(!m_data) { char* start = current; readValue(current, m_monsterBucketExtent); Q_ASSERT(current - start == 4); readValue(current, m_available); m_objectMap = reinterpret_cast(current); current += sizeof(short unsigned int) * ObjectMapSize; m_nextBucketHash = reinterpret_cast(current); current += sizeof(short unsigned int) * NextBucketHashSize; readValue(current, m_largestFreeItem); readValue(current, m_freeItemCount); readValue(current, m_dirty); m_data = current; m_mappedData = current; m_changed = false; m_lastUsed = 0; VERIFY(current - start == (DataSize - ItemRepositoryBucketSize)); } } void store(QFile* file, size_t offset) { if(!m_data) return; if(static_cast(file->size()) < offset + (1+m_monsterBucketExtent)*DataSize) file->resize(offset + (1+m_monsterBucketExtent)*DataSize); file->seek(offset); file->write((char*)&m_monsterBucketExtent, sizeof(unsigned int)); file->write((char*)&m_available, sizeof(unsigned int)); file->write((char*)m_objectMap, sizeof(short unsigned int) * ObjectMapSize); file->write((char*)m_nextBucketHash, sizeof(short unsigned int) * NextBucketHashSize); file->write((char*)&m_largestFreeItem, sizeof(short unsigned int)); file->write((char*)&m_freeItemCount, sizeof(unsigned int)); file->write((char*)&m_dirty, sizeof(bool)); file->write(m_data, ItemRepositoryBucketSize + m_monsterBucketExtent * DataSize); if(static_cast(file->pos()) != offset + (1+m_monsterBucketExtent)*DataSize) { KMessageBox::error(nullptr, i18n("Failed writing to %1, probably the disk is full", file->fileName())); abort(); } m_changed = false; #ifdef DEBUG_ITEMREPOSITORY_LOADING { file->flush(); file->seek(offset); uint available, freeItemCount, monsterBucketExtent; short unsigned int largestFree; bool dirty; short unsigned int* m = new short unsigned int[ObjectMapSize]; short unsigned int* h = new short unsigned int[NextBucketHashSize]; file->read((char*)&monsterBucketExtent, sizeof(unsigned int)); char* d = new char[ItemRepositoryBucketSize + monsterBucketExtent * DataSize]; file->read((char*)&available, sizeof(unsigned int)); file->read((char*)m, sizeof(short unsigned int) * ObjectMapSize); file->read((char*)h, sizeof(short unsigned int) * NextBucketHashSize); file->read((char*)&largestFree, sizeof(short unsigned int)); file->read((char*)&freeItemCount, sizeof(unsigned int)); file->read((char*)&dirty, sizeof(bool)); file->read(d, ItemRepositoryBucketSize); Q_ASSERT(monsterBucketExtent == m_monsterBucketExtent); Q_ASSERT(available == m_available); Q_ASSERT(memcmp(d, m_data, ItemRepositoryBucketSize + monsterBucketExtent * DataSize) == 0); Q_ASSERT(memcmp(m, m_objectMap, sizeof(short unsigned int) * ObjectMapSize) == 0); Q_ASSERT(memcmp(h, m_nextBucketHash, sizeof(short unsigned int) * NextBucketHashSize) == 0); Q_ASSERT(m_largestFreeItem == largestFree); Q_ASSERT(m_freeItemCount == freeItemCount); Q_ASSERT(m_dirty == dirty); Q_ASSERT(static_cast(file->pos()) == offset + DataSize + m_monsterBucketExtent * DataSize); delete[] d; delete[] m; delete[] h; } #endif } inline char* data() { return m_data; } inline uint dataSize() const { return ItemRepositoryBucketSize + m_monsterBucketExtent * DataSize; } //Tries to find the index this item has in this bucket, or returns zero if the item isn't there yet. unsigned short findIndex(const ItemRequest& request) const { m_lastUsed = 0; unsigned short localHash = request.hash() % ObjectMapSize; unsigned short index = m_objectMap[localHash]; unsigned short follower = 0; //Walk the chain of items with the same local hash while(index && (follower = followerIndex(index)) && !(request.equals(itemFromIndex(index)))) index = follower; if(index && request.equals(itemFromIndex(index))) { return index; //We have found the item } return 0; } //Tries to get the index within this bucket, or returns zero. Will put the item into the bucket if there is room. //Created indices will never begin with 0xffff____, so you can use that index-range for own purposes. unsigned short index(const ItemRequest& request, unsigned int itemSize) { m_lastUsed = 0; unsigned short localHash = request.hash() % ObjectMapSize; unsigned short index = m_objectMap[localHash]; unsigned short insertedAt = 0; unsigned short follower = 0; //Walk the chain of items with the same local hash while(index && (follower = followerIndex(index)) && !(request.equals(itemFromIndex(index)))) index = follower; if(index && request.equals(itemFromIndex(index))) return index; //We have found the item ifDebugLostSpace( Q_ASSERT(!lostSpace()); ) prepareChange(); unsigned int totalSize = itemSize + AdditionalSpacePerItem; if(m_monsterBucketExtent) { ///This is a monster-bucket. Other rules are applied here. Only one item can be allocated, and that must be bigger than the bucket data Q_ASSERT(totalSize > ItemRepositoryBucketSize); Q_ASSERT(m_available); m_available = 0; insertedAt = AdditionalSpacePerItem; setFollowerIndex(insertedAt, 0); Q_ASSERT(m_objectMap[localHash] == 0); m_objectMap[localHash] = insertedAt; if(markForReferenceCounting) enableDUChainReferenceCounting(m_data, dataSize()); request.createItem(reinterpret_cast(m_data + insertedAt)); if(markForReferenceCounting) disableDUChainReferenceCounting(m_data); return insertedAt; } //The second condition is needed, else we can get problems with zero-length items and an overflow in insertedAt to zero if(totalSize > m_available || (!itemSize && totalSize == m_available)) { //Try finding the smallest freed item that can hold the data unsigned short currentIndex = m_largestFreeItem; unsigned short previousIndex = 0; unsigned short freeChunkSize = 0; ///@todo Achieve this without full iteration while(currentIndex && freeSize(currentIndex) > itemSize) { unsigned short follower = followerIndex(currentIndex); if(follower && freeSize(follower) >= itemSize) { //The item also fits into the smaller follower, so use that one previousIndex = currentIndex; currentIndex = follower; }else{ //The item fits into currentIndex, but not into the follower. So use currentIndex freeChunkSize = freeSize(currentIndex) - itemSize; //We need 2 bytes to store the free size if(freeChunkSize != 0 && freeChunkSize < AdditionalSpacePerItem+2) { //we can not manage the resulting free chunk as a separate item, so we cannot use this position. //Just pick the biggest free item, because there we can be sure that //either we can manage the split, or we cannot do anything at all in this bucket. freeChunkSize = freeSize(m_largestFreeItem) - itemSize; if(freeChunkSize == 0 || freeChunkSize >= AdditionalSpacePerItem+2) { previousIndex = 0; currentIndex = m_largestFreeItem; }else{ currentIndex = 0; } } break; } } if(!currentIndex || freeSize(currentIndex) < (totalSize-AdditionalSpacePerItem)) return 0; if(previousIndex) setFollowerIndex(previousIndex, followerIndex(currentIndex)); else m_largestFreeItem = followerIndex(currentIndex); --m_freeItemCount; //Took one free item out of the chain ifDebugLostSpace( Q_ASSERT((uint)lostSpace() == (uint)(freeSize(currentIndex) + AdditionalSpacePerItem)); ) if(freeChunkSize) { Q_ASSERT(freeChunkSize >= AdditionalSpacePerItem+2); unsigned short freeItemSize = freeChunkSize - AdditionalSpacePerItem; unsigned short freeItemPosition; //Insert the resulting free chunk into the list of free items, so we don't lose it if(isBehindFreeSpace(currentIndex)) { //Create the free item at the beginning of currentIndex, so it can be merged with the free space in front freeItemPosition = currentIndex; currentIndex += freeItemSize + AdditionalSpacePerItem; }else{ //Create the free item behind currentIndex freeItemPosition = currentIndex + itemSize + AdditionalSpacePerItem; } setFreeSize(freeItemPosition, freeItemSize); insertFreeItem(freeItemPosition); } insertedAt = currentIndex; Q_ASSERT((bool)m_freeItemCount == (bool)m_largestFreeItem); }else{ //We have to insert the item insertedAt = ItemRepositoryBucketSize - m_available; insertedAt += AdditionalSpacePerItem; //Room for the prepended follower-index m_available -= totalSize; } ifDebugLostSpace( Q_ASSERT(lostSpace() == totalSize); ) Q_ASSERT(!index || !followerIndex(index)); Q_ASSERT(!m_objectMap[localHash] || index); if(index) setFollowerIndex(index, insertedAt); setFollowerIndex(insertedAt, 0); if(m_objectMap[localHash] == 0) m_objectMap[localHash] = insertedAt; #ifdef DEBUG_CREATEITEM_EXTENTS char* borderBehind = m_data + insertedAt + (totalSize-AdditionalSpacePerItem); quint64 oldValueBehind = 0; if(m_available >= 8) { oldValueBehind = *(quint64*)borderBehind; *((quint64*)borderBehind) = 0xfafafafafafafafaLLU; } #endif //Last thing we do, because createItem may recursively do even more transformation of the repository if(markForReferenceCounting) enableDUChainReferenceCounting(m_data, dataSize()); request.createItem(reinterpret_cast(m_data + insertedAt)); if(markForReferenceCounting) disableDUChainReferenceCounting(m_data); #ifdef DEBUG_CREATEITEM_EXTENTS if(m_available >= 8) { //If this assertion triggers, then the item writes a bigger range than it advertised in Q_ASSERT(*((quint64*)borderBehind) == 0xfafafafafafafafaLLU); *((quint64*)borderBehind) = oldValueBehind; } #endif Q_ASSERT(itemFromIndex(insertedAt)->hash() == request.hash()); Q_ASSERT(itemFromIndex(insertedAt)->itemSize() == itemSize); ifDebugLostSpace( if(lostSpace()) qDebug() << "lost space:" << lostSpace(); Q_ASSERT(!lostSpace()); ) return insertedAt; } - ///@param modulo Returns whether this bucket contains an item with (hash % modulo) == (item.hash % modulo) - /// The default-parameter is the size of the next-bucket hash that is used by setNextBucketForHash and nextBucketForHash - ///@note modulo MUST be a multiple of ObjectMapSize, because (b-a) | (x * h1) => (b-a) | h2, where a|b means a is a multiple of b. - /// This this allows efficiently computing the clashes using the local object map hash. - + /// @param modulo Returns whether this bucket contains an item with (hash % modulo) == (item.hash % modulo) + /// The default-parameter is the size of the next-bucket hash that is used by setNextBucketForHash and nextBucketForHash + /// @note modulo MUST be a multiple of ObjectMapSize, because (b-a) | (x * h1) => (b-a) | h2, where a|b means a is a multiple of b. + /// This this allows efficiently computing the clashes using the local object map hash. bool hasClashingItem(uint hash, uint modulo) { Q_ASSERT(modulo % ObjectMapSize == 0); m_lastUsed = 0; uint hashMod = hash % modulo; unsigned short localHash = hash % ObjectMapSize; unsigned short currentIndex = m_objectMap[localHash]; if(currentIndex == 0) return false; while(currentIndex) { uint currentHash = itemFromIndex(currentIndex)->hash(); Q_ASSERT(currentHash % ObjectMapSize == localHash); if(currentHash % modulo == hashMod) return true; //Clash currentIndex = followerIndex(currentIndex); } return false; } void countFollowerIndexLengths(uint& usedSlots, uint& lengths, uint& slotCount, uint& longestInBucketFollowerChain) { for(uint a = 0; a < ObjectMapSize; ++a) { unsigned short currentIndex = m_objectMap[a]; ++slotCount; uint length = 0; if(currentIndex) { ++usedSlots; while(currentIndex) { ++length; ++lengths; currentIndex = followerIndex(currentIndex); } if(length > longestInBucketFollowerChain) { // qDebug() << "follower-chain at" << a << ":" << length; longestInBucketFollowerChain = length; } } } } //Returns whether the given item is reachabe within this bucket, through its hash. bool itemReachable(const Item* item, uint hash) const { unsigned short localHash = hash % ObjectMapSize; unsigned short currentIndex = m_objectMap[localHash]; while(currentIndex) { if(itemFromIndex(currentIndex) == item) return true; currentIndex = followerIndex(currentIndex); } return false; } template void deleteItem(unsigned short index, unsigned int hash, Repository& repository) { ifDebugLostSpace( Q_ASSERT(!lostSpace()); ) m_lastUsed = 0; prepareChange(); unsigned int size = itemFromIndex(index)->itemSize(); //Step 1: Remove the item from the data-structures that allow finding it: m_objectMap unsigned short localHash = hash % ObjectMapSize; unsigned short currentIndex = m_objectMap[localHash]; unsigned short previousIndex = 0; //Fix the follower-link by setting the follower of the previous item to the next one, or updating m_objectMap while(currentIndex != index) { previousIndex = currentIndex; currentIndex = followerIndex(currentIndex); //If this assertion triggers, the deleted item was not registered under the given hash Q_ASSERT(currentIndex); } Q_ASSERT(currentIndex == index); if(!previousIndex) //The item was directly in the object map m_objectMap[localHash] = followerIndex(index); else setFollowerIndex(previousIndex, followerIndex(index)); Item* item = const_cast(itemFromIndex(index)); if(markForReferenceCounting) enableDUChainReferenceCounting(m_data, dataSize()); ItemRequest::destroy(item, repository); if(markForReferenceCounting) disableDUChainReferenceCounting(m_data); memset(item, 0, size); //For debugging, so we notice the data is wrong if(m_monsterBucketExtent) { ///This is a monster-bucket. Make it completely empty again. Q_ASSERT(!m_available); m_available = ItemRepositoryBucketSize; //Items are always inserted into monster-buckets at a fixed position Q_ASSERT(currentIndex == AdditionalSpacePerItem); Q_ASSERT(m_objectMap[localHash] == 0); }else{ ///Put the space into the free-set setFreeSize(index, size); //Try merging the created free item to other free items around, else add it into the free list insertFreeItem(index); if(m_freeItemCount == 1 && freeSize(m_largestFreeItem) + m_available == ItemRepositoryBucketSize) { //Everything has been deleted, there is only free space left. Make the bucket empty again, //so it can later also be used as a monster-bucket. m_available = ItemRepositoryBucketSize; m_freeItemCount = 0; m_largestFreeItem = 0; } } Q_ASSERT((bool)m_freeItemCount == (bool)m_largestFreeItem); ifDebugLostSpace( Q_ASSERT(!lostSpace()); ) #ifdef DEBUG_INCORRECT_DELETE //Make sure the item cannot be found any more { unsigned short localHash = hash % ObjectMapSize; unsigned short currentIndex = m_objectMap[localHash]; while(currentIndex && currentIndex != index) { previousIndex = currentIndex; currentIndex = followerIndex(currentIndex); } Q_ASSERT(!currentIndex); //The item must not be found } #endif // Q_ASSERT(canAllocateItem(size)); } ///@warning The returned item may be in write-protected memory, so never try doing a const_cast and changing some data /// If you need to change something, use dynamicItemFromIndex ///@warning When using multi-threading, mutex() must be locked as long as you use the returned data inline const Item* itemFromIndex(unsigned short index) const { m_lastUsed = 0; return reinterpret_cast(m_data+index); } bool isEmpty() const { return m_available == ItemRepositoryBucketSize; } ///Returns true if this bucket has no nextBucketForHash links bool noNextBuckets() const { for(int a = 0; a < NextBucketHashSize; ++a) if(m_nextBucketHash[a]) return false; return true; } uint available() const { return m_available; } uint usedMemory() const { return ItemRepositoryBucketSize - m_available; } template bool visitAllItems(Visitor& visitor) const { m_lastUsed = 0; for(uint a = 0; a < ObjectMapSize; ++a) { uint currentIndex = m_objectMap[a]; while(currentIndex) { //Get the follower early, so there is no problems when the current //index is removed if(!visitor(reinterpret_cast(m_data+currentIndex))) return false; currentIndex = followerIndex(currentIndex); } } return true; } ///Returns whether something was changed template int finalCleanup(Repository& repository) { int changed = 0; while(m_dirty) { m_dirty = false; for(uint a = 0; a < ObjectMapSize; ++a) { uint currentIndex = m_objectMap[a]; while(currentIndex) { //Get the follower early, so there is no problems when the current //index is removed const Item* item = reinterpret_cast(m_data+currentIndex); if(!ItemRequest::persistent(item)) { changed += item->itemSize(); deleteItem(currentIndex, item->hash(), repository); m_dirty = true; //Set to dirty so we re-iterate break; } currentIndex = followerIndex(currentIndex); } } } return changed; } unsigned short nextBucketForHash(uint hash) const { m_lastUsed = 0; return m_nextBucketHash[hash % NextBucketHashSize]; } void setNextBucketForHash(unsigned int hash, unsigned short bucket) { m_lastUsed = 0; prepareChange(); m_nextBucketHash[hash % NextBucketHashSize] = bucket; } uint freeItemCount() const { return m_freeItemCount; } short unsigned int totalFreeItemsSize() const { short unsigned int ret = 0; short unsigned int currentIndex = m_largestFreeItem; while(currentIndex) { ret += freeSize(currentIndex); currentIndex = followerIndex(currentIndex); } return ret; } //Size of the largest item that could be inserted into this bucket short unsigned int largestFreeSize() const { short unsigned int ret = 0; if(m_largestFreeItem) ret = freeSize(m_largestFreeItem); if(m_available > (uint)(AdditionalSpacePerItem + (uint)ret)) { ret = m_available - AdditionalSpacePerItem; Q_ASSERT(ret == (m_available - AdditionalSpacePerItem)); } return ret; } bool canAllocateItem(unsigned int size) const { short unsigned int currentIndex = m_largestFreeItem; while(currentIndex) { short unsigned int currentFree = freeSize(currentIndex); if(currentFree < size) return false; //Either we need an exact match, or 2 additional bytes to manage the resulting gap if(size == currentFree || currentFree - size >= AdditionalSpacePerItem + 2) return true; currentIndex = followerIndex(currentIndex); } return false; } void tick() const { ++m_lastUsed; } //How many ticks ago the item was last used int lastUsed() const { return m_lastUsed; } //Whether this bucket was changed since it was last stored bool changed() const { return m_changed; } void prepareChange() { m_changed = true; m_dirty = true; makeDataPrivate(); } bool dirty() const { return m_dirty; } ///Returns the count of following buckets that were merged onto this buckets data array int monsterBucketExtent() const { return m_monsterBucketExtent; } //Counts together the space that is neither accessible through m_objectMap nor through the free items uint lostSpace() { if(m_monsterBucketExtent) return 0; uint need = ItemRepositoryBucketSize - m_available; uint found = 0; for(uint a = 0; a < ObjectMapSize; ++a) { uint currentIndex = m_objectMap[a]; while(currentIndex) { found += reinterpret_cast(m_data+currentIndex)->itemSize() + AdditionalSpacePerItem; currentIndex = followerIndex(currentIndex); } } uint currentIndex = m_largestFreeItem; while(currentIndex) { found += freeSize(currentIndex) + AdditionalSpacePerItem; currentIndex = followerIndex(currentIndex); } return need-found; } private: void makeDataPrivate() { if(m_mappedData == m_data) { short unsigned int* oldObjectMap = m_objectMap; short unsigned int* oldNextBucketHash = m_nextBucketHash; m_data = new char[ItemRepositoryBucketSize + m_monsterBucketExtent * DataSize]; m_objectMap = new short unsigned int[ObjectMapSize]; m_nextBucketHash = new short unsigned int[NextBucketHashSize]; memcpy(m_data, m_mappedData, ItemRepositoryBucketSize + m_monsterBucketExtent * DataSize); memcpy(m_objectMap, oldObjectMap, ObjectMapSize * sizeof(short unsigned int)); memcpy(m_nextBucketHash, oldNextBucketHash, NextBucketHashSize * sizeof(short unsigned int)); } } ///Merges the given index item, which must have a freeSize() set, to surrounding free items, and inserts the result. ///The given index itself should not be in the free items chain yet. ///Returns whether the item was inserted somewhere. void insertFreeItem(unsigned short index) { //If the item-size is fixed, we don't need to do any management. Just keep a list of free items. Items of other size will never be requested. if(!fixedItemSize) { unsigned short currentIndex = m_largestFreeItem; unsigned short previousIndex = 0; while(currentIndex) { Q_ASSERT(currentIndex != index); #ifndef QT_NO_DEBUG unsigned short currentFreeSize = freeSize(currentIndex); #endif ///@todo Achieve this without iterating through all items in the bucket(This is very slow) //Merge behind index if(currentIndex == index + freeSize(index) + AdditionalSpacePerItem) { //Remove currentIndex from the free chain, since it's merged backwards into index if(previousIndex && followerIndex(currentIndex)) Q_ASSERT(freeSize(previousIndex) >= freeSize(followerIndex(currentIndex))); if(previousIndex) setFollowerIndex(previousIndex, followerIndex(currentIndex)); else m_largestFreeItem = followerIndex(currentIndex); --m_freeItemCount; //One was removed //currentIndex is directly behind index, touching its space. Merge them. setFreeSize(index, freeSize(index) + AdditionalSpacePerItem + freeSize(currentIndex)); //Recurse to do even more merging insertFreeItem(index); return; } //Merge before index if(index == currentIndex + freeSize(currentIndex) + AdditionalSpacePerItem) { if(previousIndex && followerIndex(currentIndex)) Q_ASSERT(freeSize(previousIndex) >= freeSize(followerIndex(currentIndex))); //Remove currentIndex from the free chain, since insertFreeItem wants //it not to be in the chain, and it will be inserted in another place if(previousIndex) setFollowerIndex(previousIndex, followerIndex(currentIndex)); else m_largestFreeItem = followerIndex(currentIndex); --m_freeItemCount; //One was removed //index is directly behind currentIndex, touching its space. Merge them. setFreeSize(currentIndex, freeSize(currentIndex) + AdditionalSpacePerItem + freeSize(index)); //Recurse to do even more merging insertFreeItem(currentIndex); return; } previousIndex = currentIndex; currentIndex = followerIndex(currentIndex); #ifndef QT_NO_DEBUG if(currentIndex) Q_ASSERT(freeSize(currentIndex) <= currentFreeSize); #endif } } insertToFreeChain(index); } ///Only inserts the item in the correct position into the free chain. index must not be in the chain yet. void insertToFreeChain(unsigned short index) { if(!fixedItemSize) { ///@todo Use some kind of tree to find the correct position in the chain(This is very slow) //Insert the free item into the chain opened by m_largestFreeItem unsigned short currentIndex = m_largestFreeItem; unsigned short previousIndex = 0; unsigned short size = freeSize(index); while(currentIndex && freeSize(currentIndex) > size) { Q_ASSERT(currentIndex != index); //must not be in the chain yet previousIndex = currentIndex; currentIndex = followerIndex(currentIndex); } if(currentIndex) Q_ASSERT(freeSize(currentIndex) <= size); setFollowerIndex(index, currentIndex); if(previousIndex) { Q_ASSERT(freeSize(previousIndex) >= size); setFollowerIndex(previousIndex, index); } else //This item is larger than all already registered free items, or there are none. m_largestFreeItem = index; }else{ Q_ASSERT(freeSize(index) == fixedItemSize); //When all items have the same size, just prepent to the front. setFollowerIndex(index, m_largestFreeItem); m_largestFreeItem = index; } ++m_freeItemCount; } - ///Returns true if the given index is right behind free space, and thus can be merged to the free space. + /// Returns true if the given index is right behind free space, and thus can be merged to the free space. bool isBehindFreeSpace(unsigned short index) const { - ///@todo Without iteration! + // TODO: Without iteration! unsigned short currentIndex = m_largestFreeItem; while(currentIndex) { if(index == currentIndex + freeSize(currentIndex) + AdditionalSpacePerItem) return true; currentIndex = followerIndex(currentIndex); } return false; } - ///@param index the index of an item @return The index of the next item in the chain of items with a same local hash, or zero + /// @param index the index of an item @return The index of the next item in the chain of items with a same local hash, or zero inline unsigned short followerIndex(unsigned short index) const { Q_ASSERT(index >= 2); return *reinterpret_cast(m_data+(index-2)); } void setFollowerIndex(unsigned short index, unsigned short follower) { Q_ASSERT(index >= 2); *reinterpret_cast(m_data+(index-2)) = follower; } // Only returns the current value if the item is actually free inline unsigned short freeSize(unsigned short index) const { return *reinterpret_cast(m_data+index); } //Convenience function to set the free-size, only for freed items void setFreeSize(unsigned short index, unsigned short size) { *reinterpret_cast(m_data+index) = size; } int m_monsterBucketExtent; //If this is a monster-bucket, this contains the count of follower-buckets that belong to this one unsigned int m_available; char* m_data; //Structure of the data: (2 byte), (item.size() byte) char* m_mappedData; //Read-only memory-mapped data. If this equals m_data, m_data must not be written short unsigned int* m_objectMap; //Points to the first object in m_data with (hash % ObjectMapSize) == index. Points to the item itself, so subtract 1 to get the pointer to the next item with same local hash. short unsigned int m_largestFreeItem; //Points to the largest item that is currently marked as free, or zero. That one points to the next largest one through followerIndex unsigned int m_freeItemCount; unsigned short* m_nextBucketHash; bool m_dirty; //Whether the data was changed since the last finalCleanup bool m_changed; //Whether this bucket was changed since it was last stored to disk mutable int m_lastUsed; //How many ticks ago this bucket was last accessed }; template struct Locker { //This is a dummy that does nothing template explicit Locker(const T& /*t*/) { } }; template<> struct Locker { explicit Locker(QMutex* mutex) : m_mutex(mutex) { m_mutex->lock(); } ~Locker() { m_mutex->unlock(); } QMutex* m_mutex; }; ///This object needs to be kept alive as long as you change the contents of an item ///stored in the repository. It is needed to correctly track the reference counting ///within disk-storage. ///@warning You can not freely copy this around, when you create a copy, the copy source /// becomes invalid template class DynamicItem { public: DynamicItem(Item* i, void* start, uint size) : m_item(i), m_start(start) { if(markForReferenceCounting) enableDUChainReferenceCounting(m_start, size); // qDebug() << "enabling" << i << "to" << (void*)(((char*)i)+size); } ~DynamicItem() { if(m_start) { // qDebug() << "destructor-disabling" << m_item; if(markForReferenceCounting) disableDUChainReferenceCounting(m_start); } } DynamicItem(const DynamicItem& rhs) : m_item(rhs.m_item), m_start(rhs.m_start) { // qDebug() << "stealing" << m_item; Q_ASSERT(rhs.m_start); rhs.m_start = nullptr; } Item* operator->() { return m_item; } Item* m_item; private: mutable void* m_start; DynamicItem& operator=(const DynamicItem&); }; ///@tparam Item See ExampleItem ///@tparam ItemRequest See ExampleReqestItem ///@tparam fixedItemSize When this is true, all inserted items must have the same size. /// This greatly simplifies and speeds up the task of managing free items within the buckets. ///@tparam markForReferenceCounting Whether the data within the repository should be marked for reference-counting. /// This costs a bit of performance, but must be enabled if there may be data in the repository /// that does on-disk reference counting, like IndexedString, IndexedIdentifier, etc. ///@tparam threadSafe Whether class access should be thread-safe. Disabling this is dangerous when you do multi-threading. /// You have to make sure that mutex() is locked whenever the repository is accessed. template class ItemRepository : public AbstractItemRepository { typedef Locker ThisLocker; typedef Bucket MyBucket; enum { //Must be a multiple of Bucket::ObjectMapSize, so Bucket::hasClashingItem can be computed //Must also be a multiple of Bucket::NextBucketHashSize, for the same reason.(Currently those are same) bucketHashSize = (targetBucketHashSize / MyBucket::ObjectMapSize) * MyBucket::ObjectMapSize }; enum { BucketStartOffset = sizeof(uint) * 7 + sizeof(short unsigned int) * bucketHashSize //Position in the data where the bucket array starts }; public: ///@param registry May be zero, then the repository will not be registered at all. Else, the repository will register itself to that registry. /// If this is zero, you have to care about storing the data using store() and/or close() by yourself. It does not happen automatically. /// For the global standard registry, the storing/loading is triggered from within duchain, so you don't need to care about it. explicit ItemRepository(const QString& repositoryName, ItemRepositoryRegistry* registry = &globalItemRepositoryRegistry(), uint repositoryVersion = 1, AbstractRepositoryManager* manager = nullptr) : m_ownMutex(QMutex::Recursive) , m_mutex(&m_ownMutex) , m_repositoryName(repositoryName) , m_registry(registry) , m_file(nullptr) , m_dynamicFile(nullptr) , m_repositoryVersion(repositoryVersion) , m_manager(manager) { m_unloadingEnabled = true; m_metaDataChanged = true; m_buckets.resize(10); m_buckets.fill(nullptr); memset(m_firstBucketForHash, 0, bucketHashSize * sizeof(short unsigned int)); m_statBucketHashClashes = m_statItemCount = 0; m_currentBucket = 1; //Skip the first bucket, we won't use it so we have the zero indices for special purposes if(m_registry) m_registry->registerRepository(this, m_manager); } ~ItemRepository() { if(m_registry) m_registry->unRegisterRepository(this); close(); } ///Unloading of buckets is enabled by default. Use this to disable it. When unloading is enabled, the data ///gotten from must only itemFromIndex must not be used for a long time. void setUnloadingEnabled(bool enabled) { m_unloadingEnabled = enabled; } ///Returns the index for the given item. If the item is not in the repository yet, it is inserted. ///The index can never be zero. Zero is reserved for your own usage as invalid ///@param request Item to retrieve the index from unsigned int index(const ItemRequest& request) { ThisLocker lock(m_mutex); const uint hash = request.hash(); const uint size = request.itemSize(); // Bucket indexes tracked while walking the bucket chain for this request hash unsigned short bucketInChainWithSpace = 0; unsigned short lastBucketWalked = 0; const ushort foundIndexInBucket = walkBucketChain(hash, [&](ushort bucketIdx, const MyBucket* bucketPtr) { lastBucketWalked = bucketIdx; const ushort found = bucketPtr->findIndex(request); if (!found && !bucketInChainWithSpace && bucketPtr->canAllocateItem(size)) { bucketInChainWithSpace = bucketIdx; } return found; }); if (foundIndexInBucket) { // 'request' is already present, return the existing index return createIndex(lastBucketWalked, foundIndexInBucket); } /* * Disclaimer: Writer of comment != writer of code, believe with caution * * Requested item does not yet exist. Need to find a place to put it... * * First choice is to place it in an existing bucket in the chain for the request hash * Second choice is to find an existing bucket anywhere with enough space * Otherwise use m_currentBucket (the latest unused bucket) * * If the chosen bucket fails to allocate the item, merge buckets to create a monster (dragon?) * * Finally, if the first option failed or the selected bucket failed to allocate, add the * bucket which the item ended up in to the chain of buckets for the request's hash */ m_metaDataChanged = true; const bool pickedBucketInChain = bucketInChainWithSpace; int useBucket = bucketInChainWithSpace; int reOrderFreeSpaceBucketIndex = -1; if (!pickedBucketInChain) { //Try finding an existing bucket with deleted space to store the data into for(int a = 0; a < m_freeSpaceBuckets.size(); ++a) { MyBucket* bucketPtr = bucketForIndex(m_freeSpaceBuckets[a]); Q_ASSERT(bucketPtr->largestFreeSize()); if(bucketPtr->canAllocateItem(size)) { //The item fits into the bucket. useBucket = m_freeSpaceBuckets[a]; reOrderFreeSpaceBucketIndex = a; break; } } if (!useBucket) { useBucket = m_currentBucket; } } else { reOrderFreeSpaceBucketIndex = m_freeSpaceBuckets.indexOf(useBucket); } //The item isn't in the repository yet, find a new bucket for it while(1) { if(useBucket >= m_buckets.size()) { if(m_buckets.size() >= 0xfffe) { //We have reserved the last bucket index 0xffff for special purposes //the repository has overflown. qWarning() << "Found no room for an item in" << m_repositoryName << "size of the item:" << request.itemSize(); return 0; }else{ //Allocate new buckets m_buckets.resize(m_buckets.size() + 10); } } MyBucket* bucketPtr = m_buckets.at(useBucket); if(!bucketPtr) { initializeBucket(useBucket); bucketPtr = m_buckets.at(useBucket); } ENSURE_REACHABLE(useBucket); Q_ASSERT_X(!bucketPtr->findIndex(request), Q_FUNC_INFO, "found item in unexpected bucket, ensure your ItemRequest::equals method is correct. Note: For custom AbstractType's e.g. ensure you have a proper equals() override"); unsigned short indexInBucket = bucketPtr->index(request, size); //If we could not allocate the item in an empty bucket, then we need to create a monster-bucket that //can hold the data. if(bucketPtr->isEmpty() && !indexInBucket) { ///@todo Move this compound statement into an own function uint totalSize = size + MyBucket::AdditionalSpacePerItem; Q_ASSERT((totalSize > ItemRepositoryBucketSize)); useBucket = 0; //The item did not fit in, we need a monster-bucket(Merge consecutive buckets) ///Step one: Search whether we can merge multiple empty buckets in the free-list into one monster-bucket int rangeStart = -1; int rangeEnd = -1; for(int a = 0; a < m_freeSpaceBuckets.size(); ++a) { MyBucket* bucketPtr = bucketForIndex(m_freeSpaceBuckets[a]); if(bucketPtr->isEmpty()) { //This bucket is a candidate for monster-bucket merging int index = (int)m_freeSpaceBuckets[a]; if(rangeEnd != index) { rangeStart = index; rangeEnd = index+1; }else{ ++rangeEnd; } if(rangeStart != rangeEnd) { uint extent = rangeEnd - rangeStart - 1; uint totalAvailableSpace = bucketForIndex(rangeStart)->available() + MyBucket::DataSize * (rangeEnd - rangeStart - 1); if(totalAvailableSpace > totalSize) { Q_ASSERT(extent); ///We can merge these buckets into one monster-bucket that can hold the data Q_ASSERT((uint)m_freeSpaceBuckets[a-extent] == (uint)rangeStart); m_freeSpaceBuckets.remove(a-extent, extent+1); useBucket = rangeStart; convertMonsterBucket(rangeStart, extent); break; } } } } if(!useBucket) { //Create a new monster-bucket at the end of the data int needMonsterExtent = (totalSize - ItemRepositoryBucketSize) / MyBucket::DataSize + 1; Q_ASSERT(needMonsterExtent); if(m_currentBucket + needMonsterExtent + 1 > m_buckets.size()) { m_buckets.resize(m_buckets.size() + 10 + needMonsterExtent + 1); } useBucket = m_currentBucket; convertMonsterBucket(useBucket, needMonsterExtent); m_currentBucket += 1 + needMonsterExtent; Q_ASSERT(m_currentBucket < ItemRepositoryBucketLimit); Q_ASSERT(m_buckets[m_currentBucket - 1 - needMonsterExtent] && m_buckets[m_currentBucket - 1 - needMonsterExtent]->monsterBucketExtent() == needMonsterExtent); } Q_ASSERT(useBucket); bucketPtr = bucketForIndex(useBucket); indexInBucket = bucketPtr->index(request, size); Q_ASSERT(indexInBucket); } if(indexInBucket) { ++m_statItemCount; const int previousBucketNumber = lastBucketWalked; unsigned short* const bucketHashPosition = m_firstBucketForHash + (hash % bucketHashSize); if(!(*bucketHashPosition)) { Q_ASSERT(!previousBucketNumber); (*bucketHashPosition) = useBucket; ENSURE_REACHABLE(useBucket); } else if(!pickedBucketInChain && previousBucketNumber && previousBucketNumber != useBucket) { //Should happen rarely ++m_statBucketHashClashes; ///Debug: Detect infinite recursion ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, previousBucketNumber));) //Find the position where the paths of useBucket and *bucketHashPosition intersect, and insert useBucket //there. That way, we don't create loops. QPair intersect = hashChainIntersection(*bucketHashPosition, useBucket, hash); Q_ASSERT(m_buckets[previousBucketNumber]->nextBucketForHash(hash) == 0); if(!intersect.second) { ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(*bucketHashPosition, hash, useBucket));) ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(useBucket, hash, previousBucketNumber));) Q_ASSERT(m_buckets[previousBucketNumber]->nextBucketForHash(hash) == 0); m_buckets[previousBucketNumber]->setNextBucketForHash(hash, useBucket); ENSURE_REACHABLE(useBucket); ENSURE_REACHABLE(previousBucketNumber); ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, useBucket));) } else if(intersect.first) { ifDebugInfiniteRecursion(Q_ASSERT(bucketForIndex(intersect.first)->nextBucketForHash(hash) == intersect.second);) ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(*bucketHashPosition, hash, useBucket));) ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, intersect.second));) ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, intersect.first));) ifDebugInfiniteRecursion(Q_ASSERT(bucketForIndex(intersect.first)->nextBucketForHash(hash) == intersect.second);) ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(useBucket, hash, intersect.second));) ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(useBucket, hash, intersect.first));) bucketForIndex(intersect.first)->setNextBucketForHash(hash, useBucket); ENSURE_REACHABLE(useBucket); ENSURE_REACHABLE(intersect.second); ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, useBucket));) ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(*bucketHashPosition, hash, intersect.second));) } else { //State: intersect.first == 0 && intersect.second != 0. This means that whole compleet //chain opened by *bucketHashPosition with the hash-value is also following useBucket, //so useBucket can just be inserted at the top ifDebugInfiniteRecursion(Q_ASSERT(!walkBucketLinks(*bucketHashPosition, hash, useBucket));) ifDebugInfiniteRecursion(Q_ASSERT(walkBucketLinks(useBucket, hash, *bucketHashPosition));) unsigned short oldStart = *bucketHashPosition; *bucketHashPosition = useBucket; ENSURE_REACHABLE(useBucket); ENSURE_REACHABLE(oldStart); Q_UNUSED(oldStart); } } if(reOrderFreeSpaceBucketIndex != -1) updateFreeSpaceOrder(reOrderFreeSpaceBucketIndex); return createIndex(useBucket, indexInBucket); }else{ //This should never happen when we picked a bucket for re-use Q_ASSERT(!pickedBucketInChain); Q_ASSERT(reOrderFreeSpaceBucketIndex == -1); Q_ASSERT(useBucket == m_currentBucket); if(!bucketForIndex(useBucket)->isEmpty()) putIntoFreeList(useBucket, bucketPtr); ++m_currentBucket; Q_ASSERT(m_currentBucket < ItemRepositoryBucketLimit); useBucket = m_currentBucket; } } //We haven't found a bucket that already contains the item, so append it to the current bucket qWarning() << "Found no bucket for an item in" << m_repositoryName; return 0; } ///Returns zero if the item is not in the repository yet unsigned int findIndex(const ItemRequest& request) { ThisLocker lock(m_mutex); return walkBucketChain(request.hash(), [this, &request](ushort bucketIdx, const MyBucket* bucketPtr) { const ushort indexInBucket = bucketPtr->findIndex(request); return indexInBucket ? createIndex(bucketIdx, indexInBucket) : 0u; }); } ///Deletes the item from the repository. void deleteItem(unsigned int index) { verifyIndex(index); ThisLocker lock(m_mutex); m_metaDataChanged = true; const uint hash = itemFromIndex(index)->hash(); const ushort bucket = (index >> 16); //Apart from removing the item itself, we may have to recreate the nextBucketForHash link, so we need the previous bucket MyBucket* previousBucketPtr = nullptr; MyBucket* const bucketPtr = walkBucketChain(hash, [bucket, &previousBucketPtr](ushort bucketIdx, MyBucket* bucketPtr) -> MyBucket* { if (bucket != bucketIdx) { previousBucketPtr = bucketPtr; return nullptr; } return bucketPtr; // found bucket, stop looking }); //Make sure the index was reachable through the hash chain Q_ASSERT(bucketPtr); --m_statItemCount; bucketPtr->deleteItem(index, hash, *this); /** * Now check whether the link root/previousBucketNumber -> bucket is still needed. */ if (!previousBucketPtr) { // This bucket is linked in the m_firstBucketForHash array, find the next clashing bucket in the chain // There may be items in the chain that clash only with MyBucket::NextBucketHashSize, skipped here m_firstBucketForHash[hash % bucketHashSize] = walkBucketChain(hash, [hash](ushort bucketIdx, MyBucket *bucketPtr){ if (bucketPtr->hasClashingItem(hash, bucketHashSize)) { return bucketIdx; } return static_cast(0); }); } else if(!bucketPtr->hasClashingItem(hash, MyBucket::NextBucketHashSize)) { // TODO: Skip clashing items reachable from m_firstBucketForHash // (see note in usePermissiveModuloWhenRemovingClashLinks() test) ENSURE_REACHABLE(bucket); previousBucketPtr->setNextBucketForHash(hash, bucketPtr->nextBucketForHash(hash)); Q_ASSERT(m_buckets[bucketPtr->nextBucketForHash(hash)] != previousBucketPtr); } ENSURE_REACHABLE(bucket); if(bucketPtr->monsterBucketExtent()) { //Convert the monster-bucket back to multiple normal buckets, and put them into the free list uint newBuckets = bucketPtr->monsterBucketExtent()+1; Q_ASSERT(bucketPtr->isEmpty()); if (!previousBucketPtr) { // see https://bugs.kde.org/show_bug.cgi?id=272408 // the monster bucket will be deleted and new smaller ones created // the next bucket for this hash is invalid anyways as done above // but calling the below unconditionally leads to other issues... bucketPtr->setNextBucketForHash(hash, 0); } convertMonsterBucket(bucket, 0); for(uint created = bucket; created < bucket + newBuckets; ++created) { putIntoFreeList(created, bucketForIndex(created)); #ifdef DEBUG_MONSTERBUCKETS Q_ASSERT(m_freeSpaceBuckets.indexOf(created) != -1); #endif } }else{ putIntoFreeList(bucket, bucketPtr); } } typedef DynamicItem MyDynamicItem; ///This returns an editable version of the item. @warning: Never change an entry that affects the hash, ///or the equals(..) function. That would completely destroy the consistency. ///@param index The index. It must be valid(match an existing item), and nonzero. ///@warning If you use this, make sure you lock mutex() before calling, /// and hold it until you're ready using/changing the data.. MyDynamicItem dynamicItemFromIndex(unsigned int index) { verifyIndex(index); ThisLocker lock(m_mutex); unsigned short bucket = (index >> 16); MyBucket* bucketPtr = m_buckets.at(bucket); if(!bucketPtr) { initializeBucket(bucket); bucketPtr = m_buckets.at(bucket); } bucketPtr->prepareChange(); unsigned short indexInBucket = index & 0xffff; return MyDynamicItem(const_cast(bucketPtr->itemFromIndex(indexInBucket)), bucketPtr->data(), bucketPtr->dataSize()); } ///This returns an editable version of the item. @warning: Never change an entry that affects the hash, ///or the equals(..) function. That would completely destroy the consistency. ///@param index The index. It must be valid(match an existing item), and nonzero. ///@warning If you use this, make sure you lock mutex() before calling, /// and hold it until you're ready using/changing the data.. ///@warning If you change contained complex items that depend on reference-counting, you /// must use dynamicItemFromIndex(..) instead of dynamicItemFromIndexSimple(..) Item* dynamicItemFromIndexSimple(unsigned int index) { verifyIndex(index); ThisLocker lock(m_mutex); unsigned short bucket = (index >> 16); MyBucket* bucketPtr = m_buckets.at(bucket); if(!bucketPtr) { initializeBucket(bucket); bucketPtr = m_buckets.at(bucket); } bucketPtr->prepareChange(); unsigned short indexInBucket = index & 0xffff; return const_cast(bucketPtr->itemFromIndex(indexInBucket)); } ///@param index The index. It must be valid(match an existing item), and nonzero. const Item* itemFromIndex(unsigned int index) const { verifyIndex(index); ThisLocker lock(m_mutex); unsigned short bucket = (index >> 16); const MyBucket* bucketPtr = m_buckets.at(bucket); if(!bucketPtr) { initializeBucket(bucket); bucketPtr = m_buckets.at(bucket); } unsigned short indexInBucket = index & 0xffff; return bucketPtr->itemFromIndex(indexInBucket); } struct Statistics { Statistics() : loadedBuckets(-1), currentBucket(-1), usedMemory(-1), loadedMonsterBuckets(-1), usedSpaceForBuckets(-1), freeSpaceInBuckets(-1), lostSpace(-1), freeUnreachableSpace(-1), hashClashedItems(-1), totalItems(-1), hashSize(-1), hashUse(-1), averageInBucketHashSize(-1), averageInBucketUsedSlotCount(-1), averageInBucketSlotChainLength(-1), longestInBucketChain(-1), longestNextBucketChain(-1), totalBucketFollowerSlots(-1), averageNextBucketForHashSequenceLength(-1) { } uint loadedBuckets; uint currentBucket; uint usedMemory; uint loadedMonsterBuckets; uint usedSpaceForBuckets; uint freeSpaceInBuckets; uint lostSpace; uint freeUnreachableSpace; uint hashClashedItems; uint totalItems; uint emptyBuckets; uint hashSize; //How big the hash is uint hashUse; //How many slots in the hash are used uint averageInBucketHashSize; uint averageInBucketUsedSlotCount; float averageInBucketSlotChainLength; uint longestInBucketChain; uint longestNextBucketChain; uint totalBucketFollowerSlots; //Total count of used slots in the nextBucketForHash structure float averageNextBucketForHashSequenceLength; //Average sequence length of a nextBucketForHash sequence(If not empty) QString print() const { QString ret; ret += QStringLiteral("loaded buckets: %1 current bucket: %2 used memory: %3 loaded monster buckets: %4").arg(loadedBuckets).arg(currentBucket).arg(usedMemory).arg(loadedMonsterBuckets); ret += QStringLiteral("\nbucket hash clashed items: %1 total items: %2").arg(hashClashedItems).arg(totalItems); ret += QStringLiteral("\nused space for buckets: %1 free space in buckets: %2 lost space: %3").arg(usedSpaceForBuckets).arg(freeSpaceInBuckets).arg(lostSpace); ret += QStringLiteral("\nfree unreachable space: %1 empty buckets: %2").arg(freeUnreachableSpace).arg(emptyBuckets); ret += QStringLiteral("\nhash size: %1 hash slots used: %2").arg(hashSize).arg(hashUse); ret += QStringLiteral("\naverage in-bucket hash size: %1 average in-bucket used hash slot count: %2 average in-bucket slot chain length: %3 longest in-bucket follower chain: %4").arg(averageInBucketHashSize).arg(averageInBucketUsedSlotCount).arg(averageInBucketSlotChainLength).arg(longestInBucketChain); ret += QStringLiteral("\ntotal count of used next-bucket-for-hash slots: %1 average next-bucket-for-hash sequence length: %2 longest next-bucket chain: %3").arg(totalBucketFollowerSlots).arg(averageNextBucketForHashSequenceLength).arg(longestNextBucketChain); return ret; } operator QString() const { return print(); } }; QString printStatistics() const override { return statistics().print(); } Statistics statistics() const { Statistics ret; uint loadedBuckets = 0; for(int a = 0; a < m_buckets.size(); ++a) if(m_buckets[a]) ++loadedBuckets; #ifdef DEBUG_MONSTERBUCKETS for(int a = 0; a < m_freeSpaceBuckets.size(); ++a) { if(a > 0) { uint prev = a-1; uint prevLargestFree = bucketForIndex(m_freeSpaceBuckets[prev])->largestFreeSize(); uint largestFree = bucketForIndex(m_freeSpaceBuckets[a])->largestFreeSize(); Q_ASSERT( (prevLargestFree < largestFree) || (prevLargestFree == largestFree && m_freeSpaceBuckets[prev] < m_freeSpaceBuckets[a]) ); } } #endif ret.hashSize = bucketHashSize; ret.hashUse = 0; for(uint a = 0; a < bucketHashSize; ++a) if(m_firstBucketForHash[a]) ++ret.hashUse; ret.emptyBuckets = 0; uint loadedMonsterBuckets = 0; for(int a = 0; a < m_buckets.size(); ++a) if(m_buckets[a] && m_buckets[a]->monsterBucketExtent()) loadedMonsterBuckets += m_buckets[a]->monsterBucketExtent()+1; uint usedBucketSpace = MyBucket::DataSize * m_currentBucket; uint freeBucketSpace = 0, freeUnreachableSpace = 0; uint lostSpace = 0; //Should be zero, else something is wrong uint totalInBucketHashSize = 0, totalInBucketUsedSlotCount = 0, totalInBucketChainLengths = 0; uint bucketCount = 0; ret.totalBucketFollowerSlots = 0; ret.averageNextBucketForHashSequenceLength = 0; ret.longestNextBucketChain = 0; ret.longestInBucketChain = 0; for(int a = 1; a < m_currentBucket+1; ++a) { MyBucket* bucket = bucketForIndex(a); if(bucket) { ++bucketCount; bucket->countFollowerIndexLengths(totalInBucketUsedSlotCount, totalInBucketChainLengths, totalInBucketHashSize, ret.longestInBucketChain); for(uint aa = 0; aa < MyBucket::NextBucketHashSize; ++aa) { uint length = 0; uint next = bucket->nextBucketForHash(aa); if(next) { ++ret.totalBucketFollowerSlots; while(next) { ++length; ++ret.averageNextBucketForHashSequenceLength; next = bucketForIndex(next)->nextBucketForHash(aa); } } if(length > ret.longestNextBucketChain) { // qDebug() << "next-bucket-chain in" << a << aa << ":" << length; ret.longestNextBucketChain = length; } } uint bucketFreeSpace = bucket->totalFreeItemsSize() + bucket->available(); freeBucketSpace += bucketFreeSpace; if(m_freeSpaceBuckets.indexOf(a) == -1) freeUnreachableSpace += bucketFreeSpace; if(bucket->isEmpty()) { ++ret.emptyBuckets; Q_ASSERT(!bucket->monsterBucketExtent()); #ifdef DEBUG_MONSTERBUCKETS Q_ASSERT(m_freeSpaceBuckets.contains(a)); #endif } lostSpace += bucket->lostSpace(); a += bucket->monsterBucketExtent(); } } if(ret.totalBucketFollowerSlots) ret.averageNextBucketForHashSequenceLength /= ret.totalBucketFollowerSlots; ret.loadedBuckets = loadedBuckets; ret.currentBucket = m_currentBucket; ret.usedMemory = usedMemory(); ret.loadedMonsterBuckets = loadedMonsterBuckets; ret.hashClashedItems = m_statBucketHashClashes; ret.totalItems = m_statItemCount; ret.usedSpaceForBuckets = usedBucketSpace; ret.freeSpaceInBuckets = freeBucketSpace; ret.lostSpace = lostSpace; ret.freeUnreachableSpace = freeUnreachableSpace; ret.averageInBucketHashSize = totalInBucketHashSize / bucketCount; ret.averageInBucketUsedSlotCount = totalInBucketUsedSlotCount / bucketCount; ret.averageInBucketSlotChainLength = float(totalInBucketChainLengths) / totalInBucketUsedSlotCount; //If m_statBucketHashClashes is high, the bucket-hash needs to be bigger return ret; } uint usedMemory() const { uint used = 0; for(int a = 0; a < m_buckets.size(); ++a) { if(m_buckets[a]) { used += m_buckets[a]->usedMemory(); } } return used; } ///This can be used to safely iterate through all items in the repository ///@param visitor Should be an instance of a class that has a bool operator()(const Item*) member function, /// that returns whether more items are wanted. ///@param onlyInMemory If this is true, only items are visited that are currently in memory. template void visitAllItems(Visitor& visitor, bool onlyInMemory = false) const { ThisLocker lock(m_mutex); for(int a = 1; a <= m_currentBucket; ++a) { if(!onlyInMemory || m_buckets.at(a)) { if(bucketForIndex(a) && !bucketForIndex(a)->visitAllItems(visitor)) return; } } } ///Synchronizes the state on disk to the one in memory, and does some memory-management. ///Should be called on a regular basis. Can be called centrally from the global item repository registry. void store() override { QMutexLocker lock(m_mutex); if(m_file) { if(!m_file->open( QFile::ReadWrite ) || !m_dynamicFile->open( QFile::ReadWrite )) { qFatal("cannot re-open repository file for storing"); return; } for(int a = 0; a < m_buckets.size(); ++a) { if(m_buckets[a]) { if(m_buckets[a]->changed()) { storeBucket(a); } if(m_unloadingEnabled) { const int unloadAfterTicks = 2; if(m_buckets[a]->lastUsed() > unloadAfterTicks) { delete m_buckets[a]; m_buckets[a] = nullptr; }else{ m_buckets[a]->tick(); } } } } if(m_metaDataChanged) { Q_ASSERT(m_dynamicFile); m_file->seek(0); m_file->write((char*)&m_repositoryVersion, sizeof(uint)); uint hashSize = bucketHashSize; m_file->write((char*)&hashSize, sizeof(uint)); uint itemRepositoryVersion = staticItemRepositoryVersion(); m_file->write((char*)&itemRepositoryVersion, sizeof(uint)); m_file->write((char*)&m_statBucketHashClashes, sizeof(uint)); m_file->write((char*)&m_statItemCount, sizeof(uint)); const uint bucketCount = static_cast(m_buckets.size()); m_file->write((char*)&bucketCount, sizeof(uint)); m_file->write((char*)&m_currentBucket, sizeof(uint)); m_file->write((char*)m_firstBucketForHash, sizeof(short unsigned int) * bucketHashSize); Q_ASSERT(m_file->pos() == BucketStartOffset); m_dynamicFile->seek(0); const uint freeSpaceBucketsSize = static_cast(m_freeSpaceBuckets.size()); m_dynamicFile->write((char*)&freeSpaceBucketsSize, sizeof(uint)); m_dynamicFile->write((char*)m_freeSpaceBuckets.data(), sizeof(uint) * freeSpaceBucketsSize); } //To protect us from inconsistency due to crashes. flush() is not enough. We need to close. m_file->close(); m_dynamicFile->close(); Q_ASSERT(!m_file->isOpen()); Q_ASSERT(!m_dynamicFile->isOpen()); } } ///This mutex is used for the thread-safe locking when threadSafe is true. Even if threadSafe is false, it is ///always locked before storing to or loading from disk. ///@warning If threadSafe is false, and you sometimes call store() from within another thread(As happens in duchain), /// you must always make sure that this mutex is locked before you access this repository. /// Else you will get crashes and inconsistencies. /// In KDevelop This means: Make sure you _always_ lock this mutex before accessing the repository. QMutex* mutex() const { return m_mutex; } ///With this, you can replace the internal mutex with another one. void setMutex(QMutex* mutex) { m_mutex = mutex; } QString repositoryName() const override { return m_repositoryName; } private: uint createIndex(ushort bucketIndex, ushort indexInBucket) { //Combine the index in the bucket, and the bucket number into one index const uint index = (bucketIndex << 16) + indexInBucket; verifyIndex(index); return index; } /** * Walks through all buckets clashing with @p hash * * Will return the value returned by the lambda, returning early if truthy */ template auto walkBucketChain(unsigned int hash, const Visitor& visitor) const -> decltype(visitor(0, nullptr)) { unsigned short bucketIndex = m_firstBucketForHash[hash % bucketHashSize]; while (bucketIndex) { auto* bucketPtr = m_buckets.at(bucketIndex); if (!bucketPtr) { initializeBucket(bucketIndex); bucketPtr = m_buckets.at(bucketIndex); } if (auto visitResult = visitor(bucketIndex, bucketPtr)) { return visitResult; } bucketIndex = bucketPtr->nextBucketForHash(hash); } return {}; } ///Makes sure the order within m_freeSpaceBuckets is correct, after largestFreeSize has been changed for m_freeSpaceBuckets[index]. ///If too few space is free within the given bucket, it is removed from m_freeSpaceBuckets. void updateFreeSpaceOrder(uint index) { m_metaDataChanged = true; unsigned int* freeSpaceBuckets = m_freeSpaceBuckets.data(); Q_ASSERT(index < static_cast(m_freeSpaceBuckets.size())); MyBucket* bucketPtr = bucketForIndex(freeSpaceBuckets[index]); unsigned short largestFreeSize = bucketPtr->largestFreeSize(); if(largestFreeSize == 0 || (bucketPtr->freeItemCount() <= MyBucket::MaxFreeItemsForHide && largestFreeSize <= MyBucket::MaxFreeSizeForHide)) { //Remove the item from freeSpaceBuckets m_freeSpaceBuckets.remove(index); }else{ while(1) { int prev = index-1; int next = index+1; if(prev >= 0 && (bucketForIndex(freeSpaceBuckets[prev])->largestFreeSize() > largestFreeSize || (bucketForIndex(freeSpaceBuckets[prev])->largestFreeSize() == largestFreeSize && freeSpaceBuckets[index] < freeSpaceBuckets[prev])) ) { //This item should be behind the successor, either because it has a lower largestFreeSize, or because the index is lower uint oldPrevValue = freeSpaceBuckets[prev]; freeSpaceBuckets[prev] = freeSpaceBuckets[index]; freeSpaceBuckets[index] = oldPrevValue; index = prev; }else if(next < m_freeSpaceBuckets.size() && (bucketForIndex(freeSpaceBuckets[next])->largestFreeSize() < largestFreeSize || (bucketForIndex(freeSpaceBuckets[next])->largestFreeSize() == largestFreeSize && freeSpaceBuckets[index] > freeSpaceBuckets[next]))) { //This item should be behind the successor, either because it has a higher largestFreeSize, or because the index is higher uint oldNextValue = freeSpaceBuckets[next]; freeSpaceBuckets[next] = freeSpaceBuckets[index]; freeSpaceBuckets[index] = oldNextValue; index = next; }else { break; } } } } ///Does conversion from monster-bucket to normal bucket and from normal bucket to monster-bucket ///The bucket @param bucketNumber must already be loaded and empty. the "extent" buckets behind must also be loaded, ///and also be empty. ///The created buckets are not registered anywhere. When converting from monster-bucket to normal bucket, ///oldExtent+1 normal buckets are created, that must be registered somewhere. ///@warning During conversion, all the touched buckets are deleted and re-created ///@param extent When this is zero, the bucket is converted from monster-bucket to normal bucket. /// When it is nonzero, it is converted to a monster-bucket. MyBucket* convertMonsterBucket(int bucketNumber, int extent) { Q_ASSERT(bucketNumber); MyBucket* bucketPtr = m_buckets.at(bucketNumber); if(!bucketPtr) { initializeBucket(bucketNumber); bucketPtr = m_buckets.at(bucketNumber); } if(extent) { //Convert to monster-bucket #ifdef DEBUG_MONSTERBUCKETS for(int index = bucketNumber; index < bucketNumber + 1 + extent; ++index) { Q_ASSERT(bucketPtr->isEmpty()); Q_ASSERT(!bucketPtr->monsterBucketExtent()); Q_ASSERT(m_freeSpaceBuckets.indexOf(index) == -1); } #endif for(int index = bucketNumber; index < bucketNumber + 1 + extent; ++index) deleteBucket(index); m_buckets[bucketNumber] = new MyBucket(); m_buckets[bucketNumber]->initialize(extent); #ifdef DEBUG_MONSTERBUCKETS for(uint index = bucketNumber+1; index < bucketNumber + 1 + extent; ++index) { Q_ASSERT(!m_buckets[index]); } #endif }else{ Q_ASSERT(bucketPtr->monsterBucketExtent()); Q_ASSERT(bucketPtr->isEmpty()); const int oldExtent = bucketPtr->monsterBucketExtent(); deleteBucket(bucketNumber); //Delete the monster-bucket for(int index = bucketNumber; index < bucketNumber + 1 + oldExtent; ++index) { Q_ASSERT(!m_buckets[index]); m_buckets[index] = new MyBucket(); m_buckets[index]->initialize(0); Q_ASSERT(!m_buckets[index]->monsterBucketExtent()); } } return m_buckets[bucketNumber]; } MyBucket* bucketForIndex(short unsigned int index) const { MyBucket* bucketPtr = m_buckets.at(index); if(!bucketPtr) { initializeBucket(index); bucketPtr = m_buckets.at(index); } return bucketPtr; } bool open(const QString& path) override { QMutexLocker lock(m_mutex); close(); //qDebug() << "opening repository" << m_repositoryName << "at" << path; QDir dir(path); m_file = new QFile(dir.absoluteFilePath( m_repositoryName )); m_dynamicFile = new QFile(dir.absoluteFilePath( m_repositoryName + QLatin1String("_dynamic") )); if(!m_file->open( QFile::ReadWrite ) || !m_dynamicFile->open( QFile::ReadWrite ) ) { delete m_file; m_file = nullptr; delete m_dynamicFile; m_dynamicFile = nullptr; return false; } m_metaDataChanged = true; if(m_file->size() == 0) { m_file->resize(0); m_file->write((char*)&m_repositoryVersion, sizeof(uint)); uint hashSize = bucketHashSize; m_file->write((char*)&hashSize, sizeof(uint)); uint itemRepositoryVersion = staticItemRepositoryVersion(); m_file->write((char*)&itemRepositoryVersion, sizeof(uint)); m_statBucketHashClashes = m_statItemCount = 0; m_file->write((char*)&m_statBucketHashClashes, sizeof(uint)); m_file->write((char*)&m_statItemCount, sizeof(uint)); m_buckets.resize(10); m_buckets.fill(nullptr); uint bucketCount = m_buckets.size(); m_file->write((char*)&bucketCount, sizeof(uint)); memset(m_firstBucketForHash, 0, bucketHashSize * sizeof(short unsigned int)); m_currentBucket = 1; //Skip the first bucket, we won't use it so we have the zero indices for special purposes m_file->write((char*)&m_currentBucket, sizeof(uint)); m_file->write((char*)m_firstBucketForHash, sizeof(short unsigned int) * bucketHashSize); //We have completely initialized the file now if(m_file->pos() != BucketStartOffset) { KMessageBox::error(nullptr, i18n("Failed writing to %1, probably the disk is full", m_file->fileName())); abort(); } const uint freeSpaceBucketsSize = 0; m_dynamicFile->write((char*)&freeSpaceBucketsSize, sizeof(uint)); m_freeSpaceBuckets.clear(); }else{ m_file->close(); bool res = m_file->open( QFile::ReadOnly ); //Re-open in read-only mode, so we create a read-only m_fileMap VERIFY(res); //Check that the version is correct uint storedVersion = 0, hashSize = 0, itemRepositoryVersion = 0; m_file->read((char*)&storedVersion, sizeof(uint)); m_file->read((char*)&hashSize, sizeof(uint)); m_file->read((char*)&itemRepositoryVersion, sizeof(uint)); m_file->read((char*)&m_statBucketHashClashes, sizeof(uint)); m_file->read((char*)&m_statItemCount, sizeof(uint)); if(storedVersion != m_repositoryVersion || hashSize != bucketHashSize || itemRepositoryVersion != staticItemRepositoryVersion()) { qDebug() << "repository" << m_repositoryName << "version mismatch in" << m_file->fileName() << ", stored: version " << storedVersion << "hashsize" << hashSize << "repository-version" << itemRepositoryVersion << " current: version" << m_repositoryVersion << "hashsize" << bucketHashSize << "repository-version" << staticItemRepositoryVersion(); delete m_file; m_file = nullptr; delete m_dynamicFile; m_dynamicFile = nullptr; return false; } m_metaDataChanged = false; uint bucketCount = 0; m_file->read((char*)&bucketCount, sizeof(uint)); m_buckets.resize(bucketCount); m_file->read((char*)&m_currentBucket, sizeof(uint)); m_file->read((char*)m_firstBucketForHash, sizeof(short unsigned int) * bucketHashSize); Q_ASSERT(m_file->pos() == BucketStartOffset); uint freeSpaceBucketsSize = 0; m_dynamicFile->read((char*)&freeSpaceBucketsSize, sizeof(uint)); m_freeSpaceBuckets.resize(freeSpaceBucketsSize); m_dynamicFile->read((char*)m_freeSpaceBuckets.data(), sizeof(uint) * freeSpaceBucketsSize); } m_fileMapSize = 0; m_fileMap = nullptr; #ifdef ITEMREPOSITORY_USE_MMAP_LOADING if(m_file->size() > BucketStartOffset){ m_fileMap = m_file->map(BucketStartOffset, m_file->size() - BucketStartOffset); Q_ASSERT(m_file->isOpen()); Q_ASSERT(m_file->size() >= BucketStartOffset); if(m_fileMap){ m_fileMapSize = m_file->size() - BucketStartOffset; }else{ qWarning() << "mapping" << m_file->fileName() << "FAILED!"; } } #endif //To protect us from inconsistency due to crashes. flush() is not enough. m_file->close(); m_dynamicFile->close(); return true; } ///@warning by default, this does not store the current state to disk. void close(bool doStore = false) override { if(doStore) store(); if(m_file) m_file->close(); delete m_file; m_file = nullptr; m_fileMap = nullptr; m_fileMapSize = 0; if(m_dynamicFile) m_dynamicFile->close(); delete m_dynamicFile; m_dynamicFile = nullptr; qDeleteAll(m_buckets); m_buckets.clear(); memset(m_firstBucketForHash, 0, bucketHashSize * sizeof(short unsigned int)); } struct AllItemsReachableVisitor { explicit AllItemsReachableVisitor(ItemRepository* rep) : repository(rep) { } bool operator()(const Item* item) { return repository->itemReachable(item); } ItemRepository* repository; }; //Returns whether the given item is reachable through its hash bool itemReachable(const Item* item) const { const uint hash = item->hash(); return walkBucketChain(hash, [=](ushort /*bucketIndex*/, const MyBucket* bucketPtr) { return bucketPtr->itemReachable(item, hash); }); } //Returns true if all items in the given bucket are reachable through their hashes bool allItemsReachable(unsigned short bucket) { if(!bucket) return true; MyBucket* bucketPtr = bucketForIndex(bucket); AllItemsReachableVisitor visitor(this); return bucketPtr->visitAllItems(visitor); } int finalCleanup() override { ThisLocker lock(m_mutex); int changed = 0; for(int a = 1; a <= m_currentBucket; ++a) { MyBucket* bucket = bucketForIndex(a); if(bucket && bucket->dirty()) { ///@todo Faster dirty check, without loading bucket changed += bucket->finalCleanup(*this); } a += bucket->monsterBucketExtent(); //Skip buckets that are attached as tail to monster-buckets } return changed; } inline void initializeBucket(int bucketNumber) const { Q_ASSERT(bucketNumber); #ifdef DEBUG_MONSTERBUCKETS for(uint offset = 1; offset < 5; ++offset) { int test = bucketNumber - offset; if(test >= 0 && m_buckets[test]) { Q_ASSERT(m_buckets[test]->monsterBucketExtent() < offset); } } #endif if(!m_buckets[bucketNumber]) { m_buckets[bucketNumber] = new MyBucket(); bool doMMapLoading = (bool)m_fileMap; uint offset = ((bucketNumber-1) * MyBucket::DataSize); if(m_file && offset < m_fileMapSize && doMMapLoading && *reinterpret_cast(m_fileMap + offset) == 0) { // qDebug() << "loading bucket mmap:" << bucketNumber; m_buckets[bucketNumber]->initializeFromMap(reinterpret_cast(m_fileMap + offset)); } else if(m_file) { //Either memory-mapping is disabled, or the item is not in the existing memory-map, //so we have to load it the classical way. bool res = m_file->open( QFile::ReadOnly ); if(offset + BucketStartOffset < m_file->size()) { VERIFY(res); offset += BucketStartOffset; m_file->seek(offset); uint monsterBucketExtent; m_file->read((char*)(&monsterBucketExtent), sizeof(unsigned int));; m_file->seek(offset); ///FIXME: use the data here instead of copying it again in prepareChange QByteArray data = m_file->read((1+monsterBucketExtent) * MyBucket::DataSize); m_buckets[bucketNumber]->initializeFromMap(data.data()); m_buckets[bucketNumber]->prepareChange(); }else{ m_buckets[bucketNumber]->initialize(0); } m_file->close(); }else{ m_buckets[bucketNumber]->initialize(0); } }else{ m_buckets[bucketNumber]->initialize(0); } } ///Can only be called on empty buckets void deleteBucket(int bucketNumber) { Q_ASSERT(bucketForIndex(bucketNumber)->isEmpty()); Q_ASSERT(bucketForIndex(bucketNumber)->noNextBuckets()); delete m_buckets[bucketNumber]; m_buckets[bucketNumber] = nullptr; } //m_file must be opened void storeBucket(int bucketNumber) const { if(m_file && m_buckets[bucketNumber]) { m_buckets[bucketNumber]->store(m_file, BucketStartOffset + (bucketNumber-1) * MyBucket::DataSize); } } - ///Returns whether @param mustFindBucket was found - ///If mustFindBucket is zero, the whole chain is just walked. This is good for debugging for infinite recursion. + /// If mustFindBucket is zero, the whole chain is just walked. This is good for debugging for infinite recursion. + /// @return whether @p mustFindBucket was found bool walkBucketLinks(uint checkBucket, uint hash, uint mustFindBucket = 0) const { bool found = false; while(checkBucket) { if(checkBucket == mustFindBucket) found = true; checkBucket = bucketForIndex(checkBucket)->nextBucketForHash(hash); } return found || (mustFindBucket == 0); } - ///Computes the bucket where the chains opened by the buckets @param mainHead and @param intersectorHead - ///with hash @param hash meet each other. - ///@return + /// Computes the bucket where the chains opened by the buckets @p mainHead and @p intersectorHead + /// with hash @p hash meet each other. + /// @return QPair hashChainIntersection(uint mainHead, uint intersectorHead, uint hash) const { uint previous = 0; uint current = mainHead; while(current) { ///@todo Make this more efficient if(walkBucketLinks(intersectorHead, hash, current)) return qMakePair(previous, current); previous = current; current = bucketForIndex(current)->nextBucketForHash(hash); } return qMakePair(0u, 0u); } void putIntoFreeList(unsigned short bucket, MyBucket* bucketPtr) { Q_ASSERT(!bucketPtr->monsterBucketExtent()); int indexInFree = m_freeSpaceBuckets.indexOf(bucket); if(indexInFree == -1 && (bucketPtr->freeItemCount() >= MyBucket::MinFreeItemsForReuse || bucketPtr->largestFreeSize() >= MyBucket::MinFreeSizeForReuse)) { //Add the bucket to the list of buckets from where to re-assign free space //We only do it when a specific threshold of empty items is reached, because that way items can stay "somewhat" semantically ordered. Q_ASSERT(bucketPtr->largestFreeSize()); int insertPos; for(insertPos = 0; insertPos < m_freeSpaceBuckets.size(); ++insertPos) { if(bucketForIndex(m_freeSpaceBuckets[insertPos])->largestFreeSize() > bucketPtr->largestFreeSize()) break; } m_freeSpaceBuckets.insert(insertPos, bucket); updateFreeSpaceOrder(insertPos); }else if(indexInFree != -1) { ///Re-order so the order in m_freeSpaceBuckets is correct(sorted by largest free item size) updateFreeSpaceOrder(indexInFree); } #ifdef DEBUG_MONSTERBUCKETS if(bucketPtr->isEmpty()) { Q_ASSERT(m_freeSpaceBuckets.contains(bucket)); } #endif } void verifyIndex(uint index) const { // We don't use zero indices Q_ASSERT(index); int bucket = (index >> 16); // nor zero buckets Q_ASSERT(bucket); Q_ASSERT_X(bucket < m_buckets.size(), Q_FUNC_INFO, qPrintable(QStringLiteral("index %1 gives invalid bucket number %2, current count is: %3") .arg(index) .arg(bucket) .arg(m_buckets.size()))); // don't trigger compile warnings in release mode Q_UNUSED(bucket); Q_UNUSED(index); } bool m_metaDataChanged; mutable QMutex m_ownMutex; mutable QMutex* m_mutex; QString m_repositoryName; mutable int m_currentBucket; //List of buckets that have free space available that can be assigned. Sorted by size: Smallest space first. Second order sorting: Bucket index QVector m_freeSpaceBuckets; mutable QVector m_buckets; uint m_statBucketHashClashes, m_statItemCount; //Maps hash-values modulo 1<