/usr/include/CLucene/util/Arrays.h is in libclucene-dev 0.9.21b-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 | /*------------------------------------------------------------------------------
* Copyright (C) 2003-2006 Ben van Klinken and the CLucene Team
*
* Distributable under the terms of either the Apache License (Version 2.0) or
* the GNU Lesser General Public License, as specified in the COPYING file.
------------------------------------------------------------------------------*/
#ifndef _lucene_util_Arrays_
#define _lucene_util_Arrays_
#if defined(_LUCENE_PRAGMA_ONCE)
# pragma once
#endif
#include "VoidList.h"
CL_NS_DEF(util)
class Arrays{
public:
template<typename _type>
class _Arrays {
protected:
//used by binarySearch to check for equality
virtual bool equals(_type a,_type b) const = 0;
virtual int32_t compare(_type a,_type b) const = 0;
public:
virtual ~_Arrays(){
}
void sort(_type* a, int32_t alen, int32_t fromIndex, int32_t toIndex) const{
CND_PRECONDITION(fromIndex < toIndex,"fromIndex >= toIndex");
CND_PRECONDITION(fromIndex >= 0,"fromIndex < 0");
// First presort the array in chunks of length 6 with insertion
// sort. A mergesort would give too much overhead for this length.
for (int32_t chunk = fromIndex; chunk < toIndex; chunk += 6)
{
int32_t end = min(chunk + 6, toIndex);
for (int32_t i = chunk + 1; i < end; i++)
{
if (compare(a[i - 1], a[i]) > 0)
{
// not already sorted
int32_t j = i;
_type elem = a[j];
do
{
a[j] = a[j - 1];
j--;
}
while (j > chunk && compare(a[j - 1], elem) > 0);
a[j] = elem;
}
}
}
int32_t len = toIndex - fromIndex;
// If length is smaller or equal 6 we are done.
if (len <= 6)
return;
_type* src = a;
_type* dest = _CL_NEWARRAY(_type,alen);
_type* t = NULL; // t is used for swapping src and dest
// The difference of the fromIndex of the src and dest array.
int32_t srcDestDiff = -fromIndex;
// The merges are done in this loop
for (int32_t size = 6; size < len; size <<= 1)
{
for (int32_t start = fromIndex; start < toIndex; start += size << 1)
{
// mid is the start of the second sublist;
// end the start of the next sublist (or end of array).
int32_t mid = start + size;
int32_t end = min(toIndex, mid + size);
// The second list is empty or the elements are already in
// order - no need to merge
if (mid >= end || compare(src[mid - 1], src[mid]) <= 0)
{
memcpy(dest + start + srcDestDiff, src+start, (end-start)*sizeof(_type));
}// The two halves just need swapping - no need to merge
else if (compare(src[start], src[end - 1]) > 0)
{
memcpy(dest+end-size+srcDestDiff, src+start, size * sizeof(_type));
memcpy(dest+start+srcDestDiff, src+mid, (end-mid) * sizeof(_type));
}else{
// Declare a lot of variables to save repeating
// calculations. Hopefully a decent JIT will put these
// in registers and make this fast
int32_t p1 = start;
int32_t p2 = mid;
int32_t i = start + srcDestDiff;
// The main merge loop; terminates as soon as either
// half is ended
while (p1 < mid && p2 < end)
{
dest[i++] = src[(compare(src[p1], src[p2]) <= 0
? p1++ : p2++)];
}
// Finish up by copying the remainder of whichever half
// wasn't finished.
if (p1 < mid)
memcpy(dest+i,src+p1, (mid-p1) * sizeof(_type));
else
memcpy(dest+i,src+p2, (end-p2) * sizeof(_type));
}
}
// swap src and dest ready for the next merge
t = src;
src = dest;
dest = t;
fromIndex += srcDestDiff;
toIndex += srcDestDiff;
srcDestDiff = -srcDestDiff;
}
// make sure the result ends up back in the right place. Note
// that src and dest may have been swapped above, so src
// contains the sorted array.
if (src != a)
{
// Note that fromIndex == 0.
memcpy(a+srcDestDiff,src,toIndex * sizeof(_type));
}
}
};
};
template <typename _kt, typename _comparator,
typename class1, typename class2>
class CLListEquals:
public CL_NS_STD(binary_function)<class1*,class2*,bool>
{
typedef typename class1::const_iterator _itr1;
typedef typename class2::const_iterator _itr2;
public:
CLListEquals(){
}
bool equals( class1* val1, class2* val2 ) const{
static _comparator comp;
if ( val1 == val2 )
return true;
size_t size = val1->size();
if ( size != val2->size() )
return false;
_itr1 itr1 = val1->begin();
_itr2 itr2 = val2->begin();
while ( --size >= 0 ){
if ( !comp(*itr1,*itr2) )
return false;
itr1++;
itr2++;
}
return true;
}
};
CL_NS_END
#endif
|