diff options
author | Henning Baldersheim <balder@yahoo-inc.com> | 2019-09-30 17:24:43 +0000 |
---|---|---|
committer | Henning Baldersheim <balder@yahoo-inc.com> | 2019-09-30 17:24:43 +0000 |
commit | 73e520ba529c8e68a38e8c9048529da5f84b4996 (patch) | |
tree | 884305dc5ff38ca71d311ddfd1416df278e5bc52 /searchcore | |
parent | cd700875d174d8d12ea501f5ca71f2723307c65c (diff) |
GC unused files
Diffstat (limited to 'searchcore')
30 files changed, 0 insertions, 681 deletions
diff --git a/searchcore/CMakeLists.txt b/searchcore/CMakeLists.txt index ee262a5fa5c..53435780d9a 100644 --- a/searchcore/CMakeLists.txt +++ b/searchcore/CMakeLists.txt @@ -40,7 +40,6 @@ vespa_define_module( src/vespa/searchcore/proton/server src/vespa/searchcore/proton/summaryengine src/vespa/searchcore/proton/test - src/vespa/searchcore/util APPS src/apps/proton diff --git a/searchcore/src/apps/proton/CMakeLists.txt b/searchcore/src/apps/proton/CMakeLists.txt index a8bfa9a39a8..c42ed048ce1 100644 --- a/searchcore/src/apps/proton/CMakeLists.txt +++ b/searchcore/src/apps/proton/CMakeLists.txt @@ -24,7 +24,6 @@ vespa_add_executable(searchcore_proton_app searchcore_grouping searchcore_proton_metrics searchcore_fconfig - searchcore_util storageserver_storageapp searchlib_searchlib_uca ) diff --git a/searchcore/src/apps/tests/CMakeLists.txt b/searchcore/src/apps/tests/CMakeLists.txt index 55c371791a3..42be4091f66 100644 --- a/searchcore/src/apps/tests/CMakeLists.txt +++ b/searchcore/src/apps/tests/CMakeLists.txt @@ -19,7 +19,6 @@ vespa_add_executable(searchcore_persistenceconformance_test_app TEST searchcore_grouping searchcore_proton_metrics searchcore_fconfig - searchcore_util vdstestlib persistence_persistence_conformancetest searchlib_searchlib_uca diff --git a/searchcore/src/tests/proton/common/attribute_updater/CMakeLists.txt b/searchcore/src/tests/proton/common/attribute_updater/CMakeLists.txt index d25a88c1a71..8b552cb2b47 100644 --- a/searchcore/src/tests/proton/common/attribute_updater/CMakeLists.txt +++ b/searchcore/src/tests/proton/common/attribute_updater/CMakeLists.txt @@ -4,6 +4,5 @@ vespa_add_executable(searchcore_attribute_updater_test_app TEST attribute_updater_test.cpp DEPENDS searchcore_pcommon - searchcore_util ) vespa_add_test(NAME searchcore_attribute_updater_test_app COMMAND searchcore_attribute_updater_test_app) diff --git a/searchcore/src/tests/proton/docsummary/CMakeLists.txt b/searchcore/src/tests/proton/docsummary/CMakeLists.txt index 906a1e642f5..ce1a0b3d68c 100644 --- a/searchcore/src/tests/proton/docsummary/CMakeLists.txt +++ b/searchcore/src/tests/proton/docsummary/CMakeLists.txt @@ -22,7 +22,6 @@ vespa_add_executable(searchcore_docsummary_test_app TEST searchcore_grouping searchcore_proton_metrics searchcore_fconfig - searchcore_util searchlib_searchlib_uca ) vespa_add_executable(searchcore_summaryfieldconverter_test_app diff --git a/searchcore/src/tests/proton/documentdb/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/CMakeLists.txt index cd67bd82a06..d4a08e9de5c 100644 --- a/searchcore/src/tests/proton/documentdb/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/CMakeLists.txt @@ -19,7 +19,6 @@ vespa_add_executable(searchcore_documentdb_test_app TEST searchcore_grouping searchcore_proton_metrics searchcore_fconfig - searchcore_util searchlib_searchlib_uca ) vespa_add_test(NAME searchcore_documentdb_test_app COMMAND ${CMAKE_CURRENT_SOURCE_DIR}/documentdb_test.sh diff --git a/searchcore/src/tests/proton/documentdb/buckethandler/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/buckethandler/CMakeLists.txt index d48778ffd1b..e955aa76d37 100644 --- a/searchcore/src/tests/proton/documentdb/buckethandler/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/buckethandler/CMakeLists.txt @@ -12,7 +12,6 @@ vespa_add_executable(searchcore_buckethandler_test_app TEST searchcore_bucketdb searchcore_pcommon searchcore_grouping - searchcore_util searchcore_fconfig ) vespa_add_test(NAME searchcore_buckethandler_test_app COMMAND searchcore_buckethandler_test_app) diff --git a/searchcore/src/tests/proton/documentdb/clusterstatehandler/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/clusterstatehandler/CMakeLists.txt index 28b79100eda..77bdae70ebd 100644 --- a/searchcore/src/tests/proton/documentdb/clusterstatehandler/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/clusterstatehandler/CMakeLists.txt @@ -10,7 +10,6 @@ vespa_add_executable(searchcore_clusterstatehandler_test_app TEST searchcore_attribute searchcore_pcommon searchcore_grouping - searchcore_util searchcore_fconfig ) vespa_add_test(NAME searchcore_clusterstatehandler_test_app COMMAND searchcore_clusterstatehandler_test_app) diff --git a/searchcore/src/tests/proton/documentdb/combiningfeedview/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/combiningfeedview/CMakeLists.txt index e046b81b8bd..e810b2191bb 100644 --- a/searchcore/src/tests/proton/documentdb/combiningfeedview/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/combiningfeedview/CMakeLists.txt @@ -13,7 +13,6 @@ vespa_add_executable(searchcore_combiningfeedview_test_app TEST searchcore_pcommon searchcore_grouping searchcore_proton_metrics - searchcore_util searchcore_fconfig ) vespa_add_test(NAME searchcore_combiningfeedview_test_app COMMAND searchcore_combiningfeedview_test_app) diff --git a/searchcore/src/tests/proton/documentdb/configurer/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/configurer/CMakeLists.txt index fe09e017ba5..a7cdfff8085 100644 --- a/searchcore/src/tests/proton/documentdb/configurer/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/configurer/CMakeLists.txt @@ -18,7 +18,6 @@ vespa_add_executable(searchcore_configurer_test_app TEST searchcore_grouping searchcore_proton_metrics searchcore_fconfig - searchcore_util searchlib_searchlib_uca ) vespa_add_test(NAME searchcore_configurer_test_app COMMAND searchcore_configurer_test_app) diff --git a/searchcore/src/tests/proton/documentdb/document_subdbs/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/document_subdbs/CMakeLists.txt index f4a9d90add9..697666f8e02 100644 --- a/searchcore/src/tests/proton/documentdb/document_subdbs/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/document_subdbs/CMakeLists.txt @@ -18,7 +18,6 @@ vespa_add_executable(searchcore_document_subdbs_test_app TEST searchcore_pcommon searchcore_grouping searchcore_proton_metrics - searchcore_util searchcore_fconfig searchlib_searchlib_uca ) diff --git a/searchcore/src/tests/proton/documentdb/documentbucketmover/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/documentbucketmover/CMakeLists.txt index b23ab73cd6e..1c11ed745a6 100644 --- a/searchcore/src/tests/proton/documentdb/documentbucketmover/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/documentbucketmover/CMakeLists.txt @@ -13,7 +13,6 @@ vespa_add_executable(searchcore_documentbucketmover_test_app TEST searchcore_bucketdb searchcore_pcommon searchcore_grouping - searchcore_util searchcore_fconfig ) vespa_add_test(NAME searchcore_documentbucketmover_test_app COMMAND searchcore_documentbucketmover_test_app) diff --git a/searchcore/src/tests/proton/documentdb/feedhandler/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/feedhandler/CMakeLists.txt index 8f93629b6a6..84027130cdb 100644 --- a/searchcore/src/tests/proton/documentdb/feedhandler/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/feedhandler/CMakeLists.txt @@ -13,7 +13,6 @@ vespa_add_executable(searchcore_feedhandler_test_app TEST searchcore_pcommon searchcore_grouping searchcore_proton_metrics - searchcore_util searchcore_fconfig ) vespa_add_test(NAME searchcore_feedhandler_test_app COMMAND ${CMAKE_CURRENT_SOURCE_DIR}/feedhandler_test.sh diff --git a/searchcore/src/tests/proton/documentdb/feedview/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/feedview/CMakeLists.txt index ebf28f3bf16..a46ca246d9a 100644 --- a/searchcore/src/tests/proton/documentdb/feedview/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/feedview/CMakeLists.txt @@ -14,7 +14,6 @@ vespa_add_executable(searchcore_feedview_test_app TEST searchcore_pcommon searchcore_grouping searchcore_proton_metrics - searchcore_util searchcore_fconfig ) vespa_add_test(NAME searchcore_feedview_test_app COMMAND searchcore_feedview_test_app) diff --git a/searchcore/src/tests/proton/documentdb/maintenancecontroller/CMakeLists.txt b/searchcore/src/tests/proton/documentdb/maintenancecontroller/CMakeLists.txt index 6b25971df83..0864f444ecf 100644 --- a/searchcore/src/tests/proton/documentdb/maintenancecontroller/CMakeLists.txt +++ b/searchcore/src/tests/proton/documentdb/maintenancecontroller/CMakeLists.txt @@ -14,7 +14,6 @@ vespa_add_executable(searchcore_maintenancecontroller_test_app TEST searchcore_persistenceengine searchcore_grouping searchcore_proton_metrics - searchcore_util searchcore_fconfig searchlib_test ) @@ -33,7 +32,6 @@ vespa_add_executable(searchcore_frozenbucketsmap_test_app TEST searchcore_persistenceengine searchcore_grouping searchcore_proton_metrics - searchcore_util searchcore_fconfig ) vespa_add_test(NAME searchcore_frozenbucketsmap_test_app COMMAND searchcore_frozenbucketsmap_test_app) diff --git a/searchcore/src/tests/proton/feed_and_search/CMakeLists.txt b/searchcore/src/tests/proton/feed_and_search/CMakeLists.txt index fdc2a925ae1..2c37e4f4a71 100644 --- a/searchcore/src/tests/proton/feed_and_search/CMakeLists.txt +++ b/searchcore/src/tests/proton/feed_and_search/CMakeLists.txt @@ -3,6 +3,5 @@ vespa_add_executable(searchcore_feed_and_search_test_app TEST SOURCES feed_and_search.cpp DEPENDS - searchcore_util ) vespa_add_test(NAME searchcore_feed_and_search_test_app COMMAND searchcore_feed_and_search_test_app) diff --git a/searchcore/src/tests/proton/index/CMakeLists.txt b/searchcore/src/tests/proton/index/CMakeLists.txt index ef40e291e18..1ffad6cdbf8 100644 --- a/searchcore/src/tests/proton/index/CMakeLists.txt +++ b/searchcore/src/tests/proton/index/CMakeLists.txt @@ -7,7 +7,6 @@ vespa_add_executable(searchcore_indexmanager_test_app TEST searchcore_index searchcore_flushengine searchcore_pcommon - searchcore_util gtest ) vespa_add_executable(searchcore_fusionrunner_test_app TEST @@ -17,7 +16,6 @@ vespa_add_executable(searchcore_fusionrunner_test_app TEST searchcore_server searchcore_index searchcore_pcommon - searchcore_util ) vespa_add_executable(searchcore_diskindexcleaner_test_app TEST SOURCES diff --git a/searchcore/src/tests/proton/matching/CMakeLists.txt b/searchcore/src/tests/proton/matching/CMakeLists.txt index 0fce2f6aca2..e3c5fa2bd97 100644 --- a/searchcore/src/tests/proton/matching/CMakeLists.txt +++ b/searchcore/src/tests/proton/matching/CMakeLists.txt @@ -12,7 +12,6 @@ vespa_add_executable(searchcore_matching_test_app TEST searchcore_bucketdb searchcore_pcommon searchcore_grouping - searchcore_util searchlib_searchlib_uca searchlib_test ) diff --git a/searchcore/src/vespa/searchcore/common/.gitignore b/searchcore/src/vespa/searchcore/common/.gitignore deleted file mode 100644 index e69de29bb2d..00000000000 --- a/searchcore/src/vespa/searchcore/common/.gitignore +++ /dev/null diff --git a/searchcore/src/vespa/searchcore/common/OWNERS b/searchcore/src/vespa/searchcore/common/OWNERS deleted file mode 100644 index 9dc0c2d970d..00000000000 --- a/searchcore/src/vespa/searchcore/common/OWNERS +++ /dev/null @@ -1 +0,0 @@ -baldersheim diff --git a/searchcore/src/vespa/searchcore/util/.gitignore b/searchcore/src/vespa/searchcore/util/.gitignore deleted file mode 100644 index 51f1b16bde5..00000000000 --- a/searchcore/src/vespa/searchcore/util/.gitignore +++ /dev/null @@ -1,14 +0,0 @@ -*.exp -*.ilk -*.lib -*.pdb -.depend -ID -Makefile -extcase -extcase.exe -extprop -extprop.exe -mklicense -result -util.lib diff --git a/searchcore/src/vespa/searchcore/util/CMakeLists.txt b/searchcore/src/vespa/searchcore/util/CMakeLists.txt deleted file mode 100644 index 0d02385be94..00000000000 --- a/searchcore/src/vespa/searchcore/util/CMakeLists.txt +++ /dev/null @@ -1,7 +0,0 @@ -# Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. -vespa_add_library(searchcore_util STATIC - SOURCES - eventloop.cpp - log.cpp - DEPENDS -) diff --git a/searchcore/src/vespa/searchcore/util/OWNERS b/searchcore/src/vespa/searchcore/util/OWNERS deleted file mode 100644 index 9dc0c2d970d..00000000000 --- a/searchcore/src/vespa/searchcore/util/OWNERS +++ /dev/null @@ -1 +0,0 @@ -baldersheim diff --git a/searchcore/src/vespa/searchcore/util/autoptr.h b/searchcore/src/vespa/searchcore/util/autoptr.h deleted file mode 100644 index ba294e097e4..00000000000 --- a/searchcore/src/vespa/searchcore/util/autoptr.h +++ /dev/null @@ -1,108 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#pragma once - -template <class T> -class FastS_AutoPtr -{ -private: - FastS_AutoPtr(const FastS_AutoPtr &); - FastS_AutoPtr& operator=(const FastS_AutoPtr &); - - T *_val; - void Clean() { - if (_val != NULL) { - delete _val; - _val = NULL; - } - } -public: - FastS_AutoPtr() : _val(NULL) { } - explicit FastS_AutoPtr(T *val) - : _val(val) - { - } - ~FastS_AutoPtr() { Clean(); } - void Set(T *val) { Clean(); _val = val; } - T *Get() const { return _val; } - T *HandOver() { T *ret = _val; _val = NULL; return ret; } - void Drop() { - if (_val != NULL) { - delete _val; - _val = NULL; - } - } -}; - - -template <class T> -class FastS_AutoRefCntPtr -{ -private: - FastS_AutoRefCntPtr(const FastS_AutoRefCntPtr &); - FastS_AutoRefCntPtr& operator=(const FastS_AutoRefCntPtr &); - - T *_val; - void Clean() { - if (_val != NULL) - _val->subRef(); - } -public: - FastS_AutoRefCntPtr() : _val(NULL) { } - explicit FastS_AutoRefCntPtr(T *val) {_val = val; } - ~FastS_AutoRefCntPtr() { Clean(); } - void Set(T *val) { Clean(); _val = val; } - void SetDup(T *val) { - Clean(); - if (val != NULL) - val->addRef(); - _val = val; - } - T *Get() const { return _val; } - T *GetDup() { - if (_val != NULL) - _val->addRef(); - return _val; - } - T *HandOver() { T *ret = _val; _val = NULL; return ret; } - void Drop() { - if (_val != NULL) { - _val->subRef(); - _val = NULL; - } - } -}; - - -class FastS_AutoCharPtr -{ -private: - FastS_AutoCharPtr(const FastS_AutoCharPtr &); - FastS_AutoCharPtr& operator=(const FastS_AutoCharPtr &); - - char *_val; - void Clean() { - if (_val != NULL) - free(_val); - } -public: - FastS_AutoCharPtr() - : _val(NULL) - { - } - explicit FastS_AutoCharPtr(char *val) - : _val(val) - { - } - ~FastS_AutoCharPtr() { Clean(); } - void Set(char *val) { Clean(); _val = val; } - char *Get() const { return _val; } - char *HandOver() { char *ret = _val; _val = NULL; return ret; } - void Drop() { - if (_val != NULL) { - free(_val); - _val = NULL; - } - } -}; - diff --git a/searchcore/src/vespa/searchcore/util/description.html b/searchcore/src/vespa/searchcore/util/description.html deleted file mode 100644 index 025ae212095..00000000000 --- a/searchcore/src/vespa/searchcore/util/description.html +++ /dev/null @@ -1 +0,0 @@ -<!-- Short description for make kdoc. --> diff --git a/searchcore/src/vespa/searchcore/util/eventloop.cpp b/searchcore/src/vespa/searchcore/util/eventloop.cpp deleted file mode 100644 index 3cc9bf3bfc6..00000000000 --- a/searchcore/src/vespa/searchcore/util/eventloop.cpp +++ /dev/null @@ -1,12 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#include "eventloop.h" -#include <cstdio> - -double FastS_TimeOut::_val[FastS_TimeOut::valCnt]; - -void -FastS_TimeOut::WriteTime(char* buffer, size_t bufsize, double xtime) -{ - snprintf(buffer, bufsize, "%.3fs ", xtime); -} diff --git a/searchcore/src/vespa/searchcore/util/eventloop.h b/searchcore/src/vespa/searchcore/util/eventloop.h deleted file mode 100644 index 0a17ec1287a..00000000000 --- a/searchcore/src/vespa/searchcore/util/eventloop.h +++ /dev/null @@ -1,19 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#pragma once - -#include <cstddef> - -class FastS_TimeOut -{ -public: - enum ValName { - maxSockSilent, // 0 - valCnt // 1 - Must be last, used as array size: - }; - static double _val[valCnt]; - - static void WriteTime(char* buffer, size_t bufsize, double xtime); -}; - - diff --git a/searchcore/src/vespa/searchcore/util/log.cpp b/searchcore/src/vespa/searchcore/util/log.cpp deleted file mode 100644 index fc25fa1f346..00000000000 --- a/searchcore/src/vespa/searchcore/util/log.cpp +++ /dev/null @@ -1,51 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#include <vespa/searchcore/util/log.h> - -#include <vespa/log/log.h> -LOG_SETUP(".searchcore.util.log"); - -/** - * assert and abort functions. - */ -void __FastS_assert_fail(const char *assertion, - const char *file, - unsigned int line, - const char * function) -{ - const char *vtag = V_TAG; - if (function != NULL) { - LOG(error, "FATAL: %s:%d (%s) %s: Failed assertion: '%s'", - file, line, vtag, function, assertion); - fprintf(stderr, "%s:%d (%s) %s: Failed assertion: '%s'\n", - file, line, vtag, function, assertion); - } else { - LOG(error, "FATAL: %s:%d (%s): Failed assertion: '%s'", - file, line, vtag, assertion); - fprintf(stderr, "%s:%d (%s): Failed assertion: '%s'\n", - file, line, vtag, assertion); - } - EV_STOPPING("", "assert failed"); - abort(); -} - -void __FastS_abort(const char *message, - const char *file, - unsigned int line, - const char * function) -{ - const char *vtag = V_TAG; - if (function != NULL) { - LOG(error, "FATAL: %s:%d (%s) %s: Abort called. Reason: %s", - file, line, vtag, function, message); - fprintf(stderr, "%s:%d (%s) %s: Abort called. Reason: %s\n", - file, line, vtag, function, message); - } else { - LOG(error, "FATAL: %s:%d (%s): Abort called. Reason: %s", - file, line, vtag, message); - fprintf(stderr, "%s:%d (%s): Abort called. Reason: %s\n", - file, line, vtag, message); - } - EV_STOPPING("", "aborted"); - abort(); -} diff --git a/searchcore/src/vespa/searchcore/util/log.h b/searchcore/src/vespa/searchcore/util/log.h deleted file mode 100644 index 72aa525a421..00000000000 --- a/searchcore/src/vespa/searchcore/util/log.h +++ /dev/null @@ -1,51 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#pragma once - - -/* - * Define FastS_abort and FastS_assert macro's. - */ - -/** - * This logs an "assertion failed" message and aborts. - */ -extern void __FastS_assert_fail(const char *assertion, - const char *file, - unsigned int line, - const char * function); - -/** - * This logs an "abort" message and aborts. - */ -extern void __FastS_abort(const char *message, - const char *file, - unsigned int line, - const char * function); - -# ifndef __STRING -# define __STRING(x) #x -# endif - -# ifndef V_TAG -# define V_TAG "NOTAG" -# endif - -# ifndef __ASSERT_FUNCTION -# define __ASSERT_FUNCTION NULL -# endif - - -# define FastS_abort(msg) \ - (__FastS_abort(msg, __FILE__, __LINE__, __ASSERT_FUNCTION), abort()) - -# ifndef NDEBUG -# define FastS_assert(expr) \ - ((void) ((expr) ? 0 : \ - (__FastS_assert_fail (__STRING(expr), \ - __FILE__, __LINE__, \ - __ASSERT_FUNCTION), 0))) -# else -# define FastS_assert(expr) -# endif // #ifndef NDEBUG - diff --git a/searchcore/src/vespa/searchcore/util/stlishheap.h b/searchcore/src/vespa/searchcore/util/stlishheap.h deleted file mode 100644 index 3a04f8f2d39..00000000000 --- a/searchcore/src/vespa/searchcore/util/stlishheap.h +++ /dev/null @@ -1,396 +0,0 @@ -// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root. - -#pragma once - -/* These algorithms only work for standard C-type arrays, not generic - iterators the way STL works. To make them work for stl-type - iterators, we need to create a set of traits classes, but that is - kind of overkill until we need that functionality. */ - -/* You can use these functions to customize the heap */ - -template<typename T> -inline bool -FastS_min(T a, T b) -{ - return a < b; -} - -template<typename T> -inline bool -FastS_max(T a, T b) -{ - return b < a; -} - -/* Push obj onto the heap first of length len. len must be large - * enough to include the new object. For example if you have a heap - * with 3 elements and want to push a new element onto the heap, len - * should be 4. - */ - -template <typename T, typename Comp> -inline void -FastS_push_heap(T *first, int len, T obj, Comp comp) -{ - int x = len - 1; - int parent = (x - 1)/2; - while (x > 0 && comp(*(first + parent), obj)) { - *(first + x) = *(first + parent); - x = parent; - parent = (x - 1)/2; - } - *(first + x) = obj; -} - -/* Pop the largest element off the heap, reducing the size of the heap - * by 1. (Note: it is the responsibility of the caller to keep track - * of the size of the heap.) - */ - -template<typename T, typename Comp> -inline T -FastS_pop_heap(T *first, int len, Comp comp) -{ - /* The algorithm we use is a variation of the textbook algorithm. - We first remove the first element, then instead of putting the - last element at the top of the heap and heapify(), we propagate - the "hole" left by the removed first element to the bottom. Then - we copy the last element into the hole and push this element - upwards. Since the last element has a high probability of being - pushed down to the bottom anyways, this reduces the number of - comparisons we need to do. */ - T ret = *first; - /* right child */ - int topidx = 0; - int childidx = 2; - /* while both right and left child exist.. */ - while (childidx < len) { - /* compare right to left child */ - if (comp(*(first + childidx), *(first + childidx - 1))) - childidx--; - *(first + topidx) = *(first + childidx); - topidx = childidx; - childidx = 2 * (topidx + 1); - } - /* if only left child exists.. */ - if (childidx == len) { - *(first + topidx) = *(first + childidx - 1); - topidx = childidx - 1; - } - /* now topidx is the hole.. */ - FastS_push_heap(first, topidx + 1, *(first + len - 1), comp); - return ret; -} - -/* Pop the largest element off the heap, and push a new element on the - * heap in the same operation. - */ - -template<typename T, typename Comp> -inline T -FastS_pop_push_heap(T *first, int len, T obj, Comp comp) -{ - T ret = *first; - /* right child */ - int topidx = 0; - int childidx = 2; - /* while both right and left child exist.. */ - while (childidx < len) { - /* compare right to left child */ - if (comp(*(first + childidx), *(first + childidx - 1))) - childidx--; - *(first + topidx) = *(first + childidx); - topidx = childidx; - childidx = 2 * (topidx + 1); - } - /* if only left child exists.. */ - if (childidx == len) { - *(first + topidx) = *(first + childidx - 1); - topidx = childidx - 1; - } - /* now topidx is the hole.. */ - FastS_push_heap(first, topidx + 1, obj, comp); - return ret; -} - -/* Similar to FastS_pop_heap, this function, given a "hole" in the - * heap, heapify()es the heap downwards. It then inserts obj and - * adjusts the heap upwards. - */ - -template<typename T, typename Comp> -inline void -FastS__adjust_heap(T *first, int len, int hole, T obj, Comp comp) -{ - /* right child */ - int topidx = hole; - int childidx = 2 * (hole + 1); - /* while both right and left child exist.. */ - while (childidx < len) { - /* compare right to left child */ - if (comp(*(first + childidx), *(first + childidx - 1))) - childidx--; - *(first + topidx) = *(first + childidx); - topidx = childidx; - childidx = 2 * (topidx + 1); - } - /* if only left child exists.. */ - if (childidx == len) { - *(first + topidx) = *(first + childidx - 1); - topidx = childidx - 1; - } - /* now first[topidx] is the hole.. */ - FastS_push_heap(first, topidx + 1, obj, comp); -} - -template <typename T, typename Comp> -inline void -FastS_make_heap(T *first, int len, Comp comp) -{ - if (len < 2) - return; - int parent = (len - 2)/2; - for (/**/; parent >= 0; parent--) { - int holeidx = parent; - T obj = *(first + parent); - int childidx = 2 * (parent + 1); - while (childidx < len) { - if (comp(*(first + childidx), *(first + childidx - 1))) - childidx--; - if (comp(*(first + childidx), obj)) { - *(first + holeidx) = obj; - goto nextparent; - } else { - *(first + holeidx) = *(first + childidx); - holeidx = childidx; - childidx = 2* (holeidx + 1); - } - } - if (childidx == len) { - if (comp(*(first + childidx - 1), obj)) { - *(first + holeidx) = obj; - } else { - *(first + holeidx) = *(first + childidx - 1); - *(first + childidx - 1) = obj; - } - } else /* childidx > len */ - *(first + holeidx) = obj; - nextparent: - ; - } -} - -template <typename T, typename Comp> -inline void -FastS_sort_heap(T *first, int len, Comp comp) -{ - while (len > 0) { - *(first + len - 1) = FastS_pop_heap(first, len, comp); - len--; - } -} - -template <typename T, typename Comp> -inline bool -FastS_is_heap(T *first, int len, Comp comp) -{ - for (int i = 0; i < len; i++) { - int left = 2 * i + 1; - int right = 2 * i + 2; - if (left < len && comp(*(first + i), *(first + left))) - return false; - if (right < len && comp(*(first + i), *(first + right))) - return false; - } - return true; -} - -//////////////////////////////////////////////////////// -// Similar to the above, but without comparator support -//////////////////////////////////////////////////////// - -template <typename T> -inline void -FastS_push_heap(T *first, int len, T obj) -{ - int x = len - 1; - int parent = (x - 1)/2; - while (x > 0 && *(first + parent) < obj) { - *(first + x) = *(first + parent); - x = parent; - parent = (x - 1)/2; - } - *(first + x) = obj; -} - -/* Pop the largest element off the heap, reducing the size of the heap - * by 1. (Note: it is the responsibility of the caller to keep track - * of the size of the heap.) - */ - -template<typename T> -inline T -FastS_pop_heap(T *first, int len) -{ - /* The algorithm we use is a variation of the textbook algorithm. - We first remove the first element, then instead of putting the - last element at the top of the heap and heapify(), we propagate - the "hole" left by the removed first element to the bottom. Then - we copy the last element into the hole and push this element - upwards. Since the last element has a high probability of being - pushed down to the bottom anyways, this reduces the number of - comparisons we need to do. */ - T ret = *first; - /* right child */ - int topidx = 0; - int childidx = 2; - /* while both right and left child exist.. */ - while (childidx < len) { - /* compare right to left child */ - if (*(first + childidx) < *(first + childidx - 1)) - childidx--; - *(first + topidx) = *(first + childidx); - topidx = childidx; - childidx = 2 * (topidx + 1); - } - /* if only left child exists.. */ - if (childidx == len) { - *(first + topidx) = *(first + childidx - 1); - topidx = childidx - 1; - } - /* now topidx is the hole.. */ - FastS_push_heap(first, topidx + 1, *(first + len - 1)); - return ret; -} - - -/* Pop the largest element off the heap, and push a new element on the - * heap in the same operation. - */ - -template<typename T> -inline T -FastS_pop_push_heap(T *first, int len, T obj) -{ - T ret = *first; - /* right child */ - int topidx = 0; - int childidx = 2; - /* while both right and left child exist.. */ - while (childidx < len) { - /* compare right to left child */ - if (*(first + childidx) < *(first + childidx - 1)) - childidx--; - *(first + topidx) = *(first + childidx); - topidx = childidx; - childidx = 2 * (topidx + 1); - } - /* if only left child exists.. */ - if (childidx == len) { - *(first + topidx) = *(first + childidx - 1); - topidx = childidx - 1; - } - /* now topidx is the hole.. */ - FastS_push_heap(first, topidx + 1, obj); - return ret; -} - - -/* Similar to FastS_pop_heap, this function, given a "hole" in the - * heap, heapify()es the heap downwards. It then inserts obj and - * adjusts the heap upwards. - */ - -template<typename T> -inline void -FastS__adjust_heap(T *first, int len, int hole, T obj) -{ - /* right child */ - int topidx = hole; - int childidx = 2 * (hole + 1); - /* while both right and left child exist.. */ - while (childidx < len) { - /* compare right to left child */ - if (*(first + childidx) < *(first + childidx - 1)) - childidx--; - *(first + topidx) = *(first + childidx); - topidx = childidx; - childidx = 2 * (topidx + 1); - } - /* if only left child exists.. */ - if (childidx == len) { - *(first + topidx) = *(first + childidx - 1); - topidx = childidx - 1; - } - /* now first[topidx] is the hole.. */ - FastS_push_heap(first, topidx + 1, obj); -} - -template <typename T> -inline void -FastS_make_heap(T *first, int len) -{ - if (len < 2) - return; - int parent = (len - 2)/2; - for (/**/; parent >= 0; parent--) { - int holeidx = parent; - T obj = *(first + parent); - int childidx = 2 * (parent + 1); - while (childidx < len) { - // Find largest of left, right child of holeidx, and object. - if (*(first + childidx) < *(first + childidx - 1)) - childidx--; - if (*(first + childidx) < obj) { - *(first + holeidx) = obj; - goto nextparent; - } else { - // If child is largest, put it at holeidx, and - // look further down. - *(first + holeidx) = *(first + childidx); - holeidx = childidx; - childidx = 2* (holeidx + 1); - } - } - if (childidx == len) { - // Only left child exists - if (*(first + childidx - 1) < obj) { - *(first + holeidx) = obj; - } else { - *(first + holeidx) = *(first + childidx - 1); - *(first + childidx - 1) = obj; - } - } else /* childidx > len */ - *(first + holeidx) = obj; - nextparent: - ; - } -} - -template <typename T> -inline void -FastS_sort_heap(T *first, int len) -{ - while (len > 0) { - *(first + len - 1) = FastS_pop_heap(first, len); - len--; - } -} - -template <typename T> -inline bool -FastS_is_heap(T *first, int len) -{ - for (int i = 0; i < len; i++) { - int left = 2 * i + 1; - int right = 2 * i + 2; - if (left < len && *(first + i) < *(first + left)) - return false; - if (right < len && *(first + i) < *(first + right)) - return false; - } - return true; -} - - |