1 //
2 // $Id$
3 //
4
5 //
6 // Copyright (c) 2001-2016, Andrew Aksyonoff
7 // Copyright (c) 2008-2016, Sphinx Technologies Inc
8 // All rights reserved
9 //
10 // This program is free software; you can redistribute it and/or modify
11 // it under the terms of the GNU General Public License. You should have
12 // received a copy of the GPL license along with this program; if you
13 // did not, you can find it at http://www.gnu.org/
14 //
15
16 #ifndef _sphinxstd_
17 #define _sphinxstd_
18
19 #if _MSC_VER>=1400
20 #define _CRT_SECURE_NO_DEPRECATE 1
21 #define _CRT_NONSTDC_NO_DEPRECATE 1
22 #endif
23
24 #if _MSC_VER>=1600
25 #define HAVE_STDINT_H 1
26 #endif
27
28 #if (_MSC_VER>=1000) && !defined(__midl) && defined(_PREFAST_)
29 typedef int __declspec("SAL_nokernel") __declspec("SAL_nodriver") __prefast_flag_kernel_driver_mode;
30 #endif
31
32 #if defined(_MSC_VER) && (_MSC_VER<1400)
33 #define vsnprintf _vsnprintf
34 #endif
35
36 #ifndef __GNUC__
37 #define __attribute__(x)
38 #endif
39
40 #if HAVE_CONFIG_H
41 #include "config.h"
42 #endif
43
44 #include <string.h>
45 #include <stdlib.h>
46 #include <stdio.h>
47 #include <assert.h>
48 #include <ctype.h>
49 #include <stdarg.h>
50
51 // for 64-bit types
52 #if HAVE_STDINT_H
53 #include <stdint.h>
54 #endif
55
56 #if HAVE_INTTYPES_H
57 #define __STDC_FORMAT_MACROS
58 #include <inttypes.h>
59 #endif
60
61 #if HAVE_SYS_TYPES_H
62 #include <sys/types.h>
63 #endif
64
65 #ifndef USE_WINDOWS
66 #ifdef _MSC_VER
67 #define USE_WINDOWS 1
68 #else
69 #define USE_WINDOWS 0
70 #endif // _MSC_VER
71 #endif
72
73 #if !USE_WINDOWS
74 #include <sys/mman.h>
75 #include <errno.h>
76 #include <pthread.h>
77 #ifdef __FreeBSD__
78 #include <semaphore.h>
79 #endif
80 #endif
81
82 /////////////////////////////////////////////////////////////////////////////
83 // COMPILE-TIME CHECKS
84 /////////////////////////////////////////////////////////////////////////////
85
86 #if defined (__GNUC__)
87 #define SPH_ATTR_UNUSED __attribute__((unused))
88 #else
89 #define SPH_ATTR_UNUSED
90 #endif
91
92 #define STATIC_ASSERT(_cond,_name) typedef char STATIC_ASSERT_FAILED_ ## _name [ (_cond) ? 1 : -1 ] SPH_ATTR_UNUSED
93 #define STATIC_SIZE_ASSERT(_type,_size) STATIC_ASSERT ( sizeof(_type)==_size, _type ## _MUST_BE_ ## _size ## _BYTES )
94
95
96 #ifndef __analysis_assume
97 #define __analysis_assume(_arg)
98 #endif
99
100
101 /// some function arguments only need to have a name in debug builds
102 #ifndef NDEBUG
103 #define DEBUGARG(_arg) _arg
104 #else
105 #define DEBUGARG(_arg)
106 #endif
107
108 /////////////////////////////////////////////////////////////////////////////
109 // PORTABILITY
110 /////////////////////////////////////////////////////////////////////////////
111
112 #if _WIN32
113
114 #define WIN32_LEAN_AND_MEAN
115 #define NOMINMAX
116 #include <windows.h>
117
118 #include <intrin.h> // for bsr
119 #pragma intrinsic(_BitScanReverse)
120
121 #define strcasecmp strcmpi
122 #define strncasecmp _strnicmp
123 #define snprintf _snprintf
124 #define strtoll _strtoi64
125 #define strtoull _strtoui64
126
127 #else
128
129 #if USE_ODBC
130 // UnixODBC compatible DWORD
131 #if defined(__alpha) || defined(__sparcv9) || defined(__LP64__) || (defined(__HOS_AIX__) && defined(_LP64)) || defined(__APPLE__)
132 typedef unsigned int DWORD;
133 #else
134 typedef unsigned long DWORD;
135 #endif
136 #else
137 // default DWORD
138 typedef unsigned int DWORD;
139 #endif // USE_ODBC
140
141 typedef unsigned short WORD;
142 typedef unsigned char BYTE;
143
144 #endif // _WIN32
145
146 /////////////////////////////////////////////////////////////////////////////
147 // 64-BIT INTEGER TYPES AND MACROS
148 /////////////////////////////////////////////////////////////////////////////
149
150 #if defined(U64C) || defined(I64C)
151 #error "Internal 64-bit integer macros already defined."
152 #endif
153
154 #if !HAVE_STDINT_H
155
156 #if defined(_MSC_VER)
157 typedef __int64 int64_t;
158 typedef unsigned __int64 uint64_t;
159 #define U64C(v) v ## UI64
160 #define I64C(v) v ## I64
161 #define PRIu64 "I64d"
162 #define PRIi64 "I64d"
163 #else // !defined(_MSC_VER)
164 typedef long long int64_t;
165 typedef unsigned long long uint64_t;
166 #endif // !defined(_MSC_VER)
167
168 #endif // no stdint.h
169
170 // if platform-specific macros were not supplied, use common defaults
171 #ifndef U64C
172 #define U64C(v) v ## ULL
173 #endif
174
175 #ifndef I64C
176 #define I64C(v) v ## LL
177 #endif
178
179 #ifndef PRIu64
180 #define PRIu64 "llu"
181 #endif
182
183 #ifndef PRIi64
184 #define PRIi64 "lld"
185 #endif
186
187 #define UINT64_FMT "%" PRIu64
188 #define INT64_FMT "%" PRIi64
189
190 #ifndef UINT64_MAX
191 #define UINT64_MAX U64C(0xffffffffffffffff)
192 #endif
193
194 #ifndef INT64_MIN
195 #define INT64_MIN I64C(0x8000000000000000)
196 #endif
197
198 #ifndef INT64_MAX
199 #define INT64_MAX I64C(0x7fffffffffffffff)
200 #endif
201
202 STATIC_SIZE_ASSERT ( uint64_t, 8 );
203 STATIC_SIZE_ASSERT ( int64_t, 8 );
204
205 // conversion macros that suppress %lld format warnings vs printf
206 // problem is, on 64-bit Linux systems with gcc and stdint.h, int64_t is long int
207 // and despite sizeof(long int)==sizeof(long long int)==8, gcc bitches about that
208 // using PRIi64 instead of %lld is of course The Right Way, but ugly like fuck
209 // so lets wrap them args in INT64() instead
210 #define INT64(_v) ((long long int)(_v))
211 #define UINT64(_v) ((unsigned long long int)(_v))
212
213 /////////////////////////////////////////////////////////////////////////////
214 // MEMORY MANAGEMENT
215 /////////////////////////////////////////////////////////////////////////////
216
217 #define SPH_DEBUG_LEAKS 0
218 #define SPH_ALLOC_FILL 0
219 #define SPH_ALLOCS_PROFILER 0
220 #define SPH_DEBUG_BACKTRACES 0 // will add not only file/line, but also full backtrace
221
222 #if SPH_DEBUG_LEAKS || SPH_ALLOCS_PROFILER
223
224 /// debug new that tracks memory leaks
225 void * operator new ( size_t iSize, const char * sFile, int iLine );
226
227 /// debug new that tracks memory leaks
228 void * operator new [] ( size_t iSize, const char * sFile, int iLine );
229
230 /// get current allocs count
231 int sphAllocsCount ();
232
233 /// total allocated bytes
234 int64_t sphAllocBytes ();
235
236 /// get last alloc id
237 int sphAllocsLastID ();
238
239 /// dump all allocs since given id
240 void sphAllocsDump ( int iFile, int iSinceID );
241
242 /// dump stats to stdout
243 void sphAllocsStats ();
244
245 /// check all existing allocs; raises assertion failure in cases of errors
246 void sphAllocsCheck ();
247
248 void sphMemStatDump ( int iFD );
249
250 void sphMemStatMMapAdd ( int64_t iSize );
251 void sphMemStatMMapDel ( int64_t iSize );
252
253 #undef new
254 #define new new(__FILE__,__LINE__)
255
256 #if USE_RE2
257 void operator delete ( void * pPtr ) throw ();
258 void operator delete [] ( void * pPtr ) throw ();
259 #else
260 /// delete for my new
261 void operator delete ( void * pPtr );
262
263 /// delete for my new
264 void operator delete [] ( void * pPtr );
265 #endif
266 #endif // SPH_DEBUG_LEAKS || SPH_ALLOCS_PROFILER
267
268 /////////////////////////////////////////////////////////////////////////////
269 // HELPERS
270 /////////////////////////////////////////////////////////////////////////////
271
sphBitCount(DWORD n)272 inline int sphBitCount ( DWORD n )
273 {
274 // MIT HACKMEM count
275 // works for 32-bit numbers only
276 // fix last line for 64-bit numbers
277 DWORD tmp;
278 tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
279 return ( (tmp + (tmp >> 3) ) & 030707070707) % 63;
280 }
281
282 typedef bool ( *SphDieCallback_t ) ( const char * );
283
284 /// crash with an error message, and do not have searchd watchdog attempt to resurrect
285 void sphDie ( const char * sMessage, ... ) __attribute__ ( ( format ( printf, 1, 2 ) ) );
286
287 /// crash with an error message, but have searchd watchdog attempt to resurrect
288 void sphDieRestart ( const char * sMessage, ... ) __attribute__ ( ( format ( printf, 1, 2 ) ) );
289
290 /// setup a callback function to call from sphDie() before exit
291 /// if callback returns false, sphDie() will not log to stdout
292 void sphSetDieCallback ( SphDieCallback_t pfDieCallback );
293
294 /// how much bits do we need for given int
sphLog2(uint64_t uValue)295 inline int sphLog2 ( uint64_t uValue )
296 {
297 #if USE_WINDOWS
298 DWORD uRes;
299 if ( BitScanReverse ( &uRes, (DWORD)( uValue>>32 ) ) )
300 return 33+uRes;
301 BitScanReverse ( &uRes, DWORD(uValue) );
302 return 1+uRes;
303 #elif __GNUC__ || __clang__
304 if ( !uValue )
305 return 0;
306 return 64 - __builtin_clzl(uValue);
307 #else
308 int iBits = 0;
309 while ( uValue )
310 {
311 uValue >>= 1;
312 iBits++;
313 }
314 return iBits;
315 #endif
316 }
317
318 /// float vs dword conversion
sphF2DW(float f)319 inline DWORD sphF2DW ( float f ) { union { float f; DWORD d; } u; u.f = f; return u.d; }
320
321 /// dword vs float conversion
sphDW2F(DWORD d)322 inline float sphDW2F ( DWORD d ) { union { float f; DWORD d; } u; u.d = d; return u.f; }
323
324 /// double to bigint conversion
sphD2QW(double f)325 inline uint64_t sphD2QW ( double f ) { union { double f; uint64_t d; } u; u.f = f; return u.d; }
326
327 /// bigint to double conversion
sphQW2D(uint64_t d)328 inline double sphQW2D ( uint64_t d ) { union { double f; uint64_t d; } u; u.d = d; return u.f; }
329
330 /// microsecond precision timestamp
331 /// current UNIX timestamp in seconds multiplied by 1000000, plus microseconds since the beginning of current second
332 int64_t sphMicroTimer ();
333
334 /// double argument squared
sqr(double v)335 inline double sqr ( double v ) { return v*v;}
336
337 /// float argument squared
fsqr(float v)338 inline float fsqr ( float v ) { return v*v; }
339
340 //////////////////////////////////////////////////////////////////////////
341 // RANDOM NUMBERS GENERATOR
342 //////////////////////////////////////////////////////////////////////////
343
344 /// seed RNG
345 void sphSrand ( DWORD uSeed );
346
347 /// auto-seed RNG based on time and PID
348 void sphAutoSrand ();
349
350 /// generate another random
351 DWORD sphRand ();
352
353 /////////////////////////////////////////////////////////////////////////////
354 // DEBUGGING
355 /////////////////////////////////////////////////////////////////////////////
356
357 #if USE_WINDOWS
358 #ifndef NDEBUG
359
360 void sphAssert ( const char * sExpr, const char * sFile, int iLine );
361
362 #undef assert
363 #define assert(_expr) (void)( (_expr) || ( sphAssert ( #_expr, __FILE__, __LINE__ ), 0 ) )
364
365 #endif // !NDEBUG
366 #endif // USE_WINDOWS
367
368
369 // to avoid disappearing of _expr in release builds
370 #ifndef NDEBUG
371 #define Verify(_expr) assert(_expr)
372 #else
373 #define Verify(_expr) _expr
374 #endif
375
376 /////////////////////////////////////////////////////////////////////////////
377 // GENERICS
378 /////////////////////////////////////////////////////////////////////////////
379
Min(T a,T b)380 template <typename T> T Min ( T a, T b ) { return a<b ? a : b; }
Min(T a,U b)381 template <typename T, typename U> T Min ( T a, U b )
382 {
383 STATIC_ASSERT ( sizeof(U)<=sizeof(T), WIDEST_ARG_FIRST );
384 return a<b ? a : b;
385 }
Max(T a,T b)386 template <typename T> T Max ( T a, T b ) { return a<b ? b : a; }
Max(T a,U b)387 template <typename T, typename U> T Max ( T a, U b )
388 {
389 STATIC_ASSERT ( sizeof(U)<=sizeof(T), WIDEST_ARG_FIRST );
390 return a<b ? b : a;
391 }
392 #define SafeDelete(_x) { if (_x) { delete (_x); (_x) = NULL; } }
393 #define SafeDeleteArray(_x) { if (_x) { delete [] (_x); (_x) = NULL; } }
394 #define SafeRelease(_x) { if (_x) { (_x)->Release(); (_x) = NULL; } }
395
396 /// swap
Swap(T & v1,T & v2)397 template < typename T > inline void Swap ( T & v1, T & v2 )
398 {
399 T temp = v1;
400 v1 = v2;
401 v2 = temp;
402 }
403
404 /// prevent copy
405 class ISphNoncopyable
406 {
407 public:
ISphNoncopyable()408 ISphNoncopyable () {}
409
410 private:
ISphNoncopyable(const ISphNoncopyable &)411 ISphNoncopyable ( const ISphNoncopyable & ) {}
412 const ISphNoncopyable & operator = ( const ISphNoncopyable & ) { return *this; }
413 };
414
415 //////////////////////////////////////////////////////////////////////////////
416
417 /// generic comparator
418 template < typename T >
419 struct SphLess_T
420 {
IsLessSphLess_T421 inline bool IsLess ( const T & a, const T & b ) const
422 {
423 return a < b;
424 }
425 };
426
427
428 /// generic comparator
429 template < typename T >
430 struct SphGreater_T
431 {
IsLessSphGreater_T432 inline bool IsLess ( const T & a, const T & b ) const
433 {
434 return b < a;
435 }
436 };
437
438
439 /// generic comparator
440 template < typename T, typename C >
441 struct SphMemberLess_T
442 {
443 const T C::* m_pMember;
444
SphMemberLess_TSphMemberLess_T445 explicit SphMemberLess_T ( T C::* pMember )
446 : m_pMember ( pMember )
447 {}
448
IsLessSphMemberLess_T449 inline bool IsLess ( const C & a, const C & b ) const
450 {
451 return ( (&a)->*m_pMember ) < ( (&b)->*m_pMember );
452 }
453 };
454
455 template < typename T, typename C >
456 inline SphMemberLess_T<T,C>
sphMemberLess(T C::* pMember)457 sphMemberLess ( T C::* pMember )
458 {
459 return SphMemberLess_T<T,C> ( pMember );
460 }
461
462
463 /// generic accessor
464 template < typename T >
465 struct SphAccessor_T
466 {
467 typedef T MEDIAN_TYPE;
468
KeySphAccessor_T469 MEDIAN_TYPE & Key ( T * a ) const
470 {
471 return *a;
472 }
473
CopyKeySphAccessor_T474 void CopyKey ( MEDIAN_TYPE * pMed, T * pVal ) const
475 {
476 *pMed = Key(pVal);
477 }
478
SwapSphAccessor_T479 void Swap ( T * a, T * b ) const
480 {
481 ::Swap ( *a, *b );
482 }
483
AddSphAccessor_T484 T * Add ( T * p, int i ) const
485 {
486 return p+i;
487 }
488
SubSphAccessor_T489 int Sub ( T * b, T * a ) const
490 {
491 return (int)(b-a);
492 }
493 };
494
495
496 /// heap sort helper
497 template < typename T, typename U, typename V >
sphSiftDown(T * pData,int iStart,int iEnd,U COMP,V ACC)498 void sphSiftDown ( T * pData, int iStart, int iEnd, U COMP, V ACC )
499 {
500 for ( ;; )
501 {
502 int iChild = iStart*2+1;
503 if ( iChild>iEnd )
504 return;
505
506 int iChild1 = iChild+1;
507 if ( iChild1<=iEnd && COMP.IsLess ( ACC.Key ( ACC.Add ( pData, iChild ) ), ACC.Key ( ACC.Add ( pData, iChild1 ) ) ) )
508 iChild = iChild1;
509
510 if ( COMP.IsLess ( ACC.Key ( ACC.Add ( pData, iChild ) ), ACC.Key ( ACC.Add ( pData, iStart ) ) ) )
511 return;
512 ACC.Swap ( ACC.Add ( pData, iChild ), ACC.Add ( pData, iStart ) );
513 iStart = iChild;
514 }
515 }
516
517
518 /// heap sort
519 template < typename T, typename U, typename V >
sphHeapSort(T * pData,int iCount,U COMP,V ACC)520 void sphHeapSort ( T * pData, int iCount, U COMP, V ACC )
521 {
522 if ( !pData || iCount<=1 )
523 return;
524
525 // build a max-heap, so that the largest element is root
526 for ( int iStart=( iCount-2 )>>1; iStart>=0; iStart-- )
527 sphSiftDown ( pData, iStart, iCount-1, COMP, ACC );
528
529 // now keep popping root into the end of array
530 for ( int iEnd=iCount-1; iEnd>0; )
531 {
532 ACC.Swap ( pData, ACC.Add ( pData, iEnd ) );
533 sphSiftDown ( pData, 0, --iEnd, COMP, ACC );
534 }
535 }
536
537
538 /// generic sort
539 template < typename T, typename U, typename V >
sphSort(T * pData,int iCount,U COMP,V ACC)540 void sphSort ( T * pData, int iCount, U COMP, V ACC )
541 {
542 if ( iCount<2 )
543 return;
544
545 typedef T * P;
546 // st0 and st1 are stacks with left and right bounds of array-part.
547 // They allow us to avoid recursion in quicksort implementation.
548 P st0[32], st1[32], a, b, i, j;
549 typename V::MEDIAN_TYPE x;
550 int k;
551
552 const int SMALL_THRESH = 32;
553 int iDepthLimit = sphLog2 ( iCount );
554 iDepthLimit = ( ( iDepthLimit<<2 ) + iDepthLimit ) >> 1; // x2.5
555
556 k = 1;
557 st0[0] = pData;
558 st1[0] = ACC.Add ( pData, iCount-1 );
559 while ( k )
560 {
561 k--;
562 i = a = st0[k];
563 j = b = st1[k];
564
565 // if quicksort fails on this data; switch to heapsort
566 if ( !k )
567 {
568 if ( !--iDepthLimit )
569 {
570 sphHeapSort ( a, ACC.Sub ( b, a )+1, COMP, ACC );
571 return;
572 }
573 }
574
575 // for tiny arrays, switch to insertion sort
576 int iLen = ACC.Sub ( b, a );
577 if ( iLen<=SMALL_THRESH )
578 {
579 for ( i=ACC.Add ( a, 1 ); i<=b; i=ACC.Add ( i, 1 ) )
580 {
581 for ( j=i; j>a; )
582 {
583 P j1 = ACC.Add ( j, -1 );
584 if ( COMP.IsLess ( ACC.Key(j1), ACC.Key(j) ) )
585 break;
586 ACC.Swap ( j, j1 );
587 j = j1;
588 }
589 }
590 continue;
591 }
592
593 // ATTENTION! This copy can lead to memleaks if your CopyKey
594 // copies something which is not freed by objects destructor.
595 ACC.CopyKey ( &x, ACC.Add ( a, iLen/2 ) );
596 while ( a<b )
597 {
598 while ( i<=j )
599 {
600 while ( COMP.IsLess ( ACC.Key(i), x ) )
601 i = ACC.Add ( i, 1 );
602 while ( COMP.IsLess ( x, ACC.Key(j) ) )
603 j = ACC.Add ( j, -1 );
604 if ( i<=j )
605 {
606 ACC.Swap ( i, j );
607 i = ACC.Add ( i, 1 );
608 j = ACC.Add ( j, -1 );
609 }
610 }
611
612 // Not so obvious optimization. We put smaller array-parts
613 // to the top of stack. That reduces peak stack size.
614 if ( ACC.Sub ( j, a )>=ACC.Sub ( b, i ) )
615 {
616 if ( a<j ) { st0[k] = a; st1[k] = j; k++; }
617 a = i;
618 } else
619 {
620 if ( i<b ) { st0[k] = i; st1[k] = b; k++; }
621 b = j;
622 }
623 }
624 }
625 }
626
627
628 template < typename T, typename U >
sphSort(T * pData,int iCount,U COMP)629 void sphSort ( T * pData, int iCount, U COMP )
630 {
631 sphSort ( pData, iCount, COMP, SphAccessor_T<T>() );
632 }
633
634
635 template < typename T >
sphSort(T * pData,int iCount)636 void sphSort ( T * pData, int iCount )
637 {
638 sphSort ( pData, iCount, SphLess_T<T>() );
639 }
640
641 //////////////////////////////////////////////////////////////////////////
642
643 /// member functor, wraps object member access
644 template < typename T, typename CLASS >
645 struct SphMemberFunctor_T
646 {
647 const T CLASS::* m_pMember;
648
SphMemberFunctor_TSphMemberFunctor_T649 explicit SphMemberFunctor_T ( T CLASS::* pMember ) : m_pMember ( pMember ) {}
operatorSphMemberFunctor_T650 const T & operator () ( const CLASS & arg ) const { return (&arg)->*m_pMember; }
651
IsLessSphMemberFunctor_T652 inline bool IsLess ( const CLASS & a, const CLASS & b ) const
653 {
654 return (&a)->*m_pMember < (&b)->*m_pMember;
655 }
656
IsEqSphMemberFunctor_T657 inline bool IsEq ( const CLASS & a, T b )
658 {
659 return ( (&a)->*m_pMember )==b;
660 }
661 };
662
663
664 /// handy member functor generator
665 /// this sugar allows you to write like this
666 /// dArr.Sort ( bind ( &CSphType::m_iMember ) );
667 /// dArr.BinarySearch ( bind ( &CSphType::m_iMember ), iValue );
668 template < typename T, typename CLASS >
669 inline SphMemberFunctor_T < T, CLASS >
bind(T CLASS::* ptr)670 bind ( T CLASS::* ptr )
671 {
672 return SphMemberFunctor_T < T, CLASS > ( ptr );
673 }
674
675
676 /// identity functor
677 template < typename T >
678 struct SphIdentityFunctor_T
679 {
operatorSphIdentityFunctor_T680 const T & operator () ( const T & arg ) const { return arg; }
681 };
682
683 //////////////////////////////////////////////////////////////////////////
684
685 /// generic binary search
686 template < typename T, typename U, typename PRED >
sphBinarySearch(T * pStart,T * pEnd,const PRED & tPred,U tRef)687 T * sphBinarySearch ( T * pStart, T * pEnd, const PRED & tPred, U tRef )
688 {
689 if ( !pStart || pEnd<pStart )
690 return NULL;
691
692 if ( tPred(*pStart)==tRef )
693 return pStart;
694
695 if ( tPred(*pEnd)==tRef )
696 return pEnd;
697
698 while ( pEnd-pStart>1 )
699 {
700 if ( tRef<tPred(*pStart) || tPred(*pEnd)<tRef )
701 break;
702 assert ( tPred(*pStart)<tRef );
703 assert ( tRef<tPred(*pEnd) );
704
705 T * pMid = pStart + (pEnd-pStart)/2;
706 if ( tRef==tPred(*pMid) )
707 return pMid;
708
709 if ( tRef<tPred(*pMid) )
710 pEnd = pMid;
711 else
712 pStart = pMid;
713 }
714 return NULL;
715 }
716
717
718 /// generic binary search
719 template < typename T >
sphBinarySearch(T * pStart,T * pEnd,T & tRef)720 T * sphBinarySearch ( T * pStart, T * pEnd, T & tRef )
721 {
722 return sphBinarySearch ( pStart, pEnd, SphIdentityFunctor_T<T>(), tRef );
723 }
724
725 /// generic uniq
726 template < typename T, typename T_COUNTER >
sphUniq(T * pData,T_COUNTER iCount)727 T_COUNTER sphUniq ( T * pData, T_COUNTER iCount )
728 {
729 if ( !iCount )
730 return 0;
731
732 T_COUNTER iSrc = 1, iDst = 1;
733 while ( iSrc<iCount )
734 {
735 if ( pData[iDst-1]==pData[iSrc] )
736 iSrc++;
737 else
738 pData[iDst++] = pData[iSrc++];
739 }
740 return iDst;
741 }
742
743
744 //////////////////////////////////////////////////////////////////////////
745
746 /// default vector policy
747 /// grow 2x and copy using assignment operator on resize
748 template < typename T >
749 class CSphVectorPolicy
750 {
751 protected:
752 static const int MAGIC_INITIAL_LIMIT = 8;
753
754 public:
Copy(T * pNew,T * pData,int iLength)755 static inline void Copy ( T * pNew, T * pData, int iLength )
756 {
757 for ( int i=0; i<iLength; i++ )
758 pNew[i] = pData[i];
759 }
760
Relimit(int iLimit,int iNewLimit)761 static inline int Relimit ( int iLimit, int iNewLimit )
762 {
763 if ( !iLimit )
764 iLimit = MAGIC_INITIAL_LIMIT;
765 while ( iLimit<iNewLimit )
766 {
767 iLimit *= 2;
768 assert ( iLimit>0 );
769 }
770 return iLimit;
771 }
772 };
773
774 /// generic vector
775 /// (don't even ask why it's not std::vector)
776 template < typename T, typename POLICY=CSphVectorPolicy<T> > class CSphVector
777 {
778 public:
779 /// ctor
CSphVector()780 CSphVector ()
781 : m_iLength ( 0 )
782 , m_iLimit ( 0 )
783 , m_pData ( NULL )
784 {
785 }
786
787 /// ctor with initial size
CSphVector(int iCount)788 explicit CSphVector ( int iCount )
789 : m_iLength ( 0 )
790 , m_iLimit ( 0 )
791 , m_pData ( NULL )
792 {
793 Resize ( iCount );
794 }
795
796 /// copy ctor
CSphVector(const CSphVector<T> & rhs)797 CSphVector ( const CSphVector<T> & rhs )
798 {
799 m_iLength = 0;
800 m_iLimit = 0;
801 m_pData = NULL;
802 *this = rhs;
803 }
804
805 /// dtor
~CSphVector()806 ~CSphVector ()
807 {
808 Reset ();
809 }
810
811 /// add entry
Add()812 T & Add ()
813 {
814 if ( m_iLength>=m_iLimit )
815 Reserve ( 1+m_iLength );
816 return m_pData [ m_iLength++ ];
817 }
818
819 /// add entry
Add(const T & tValue)820 void Add ( const T & tValue )
821 {
822 assert ( (&tValue<m_pData || &tValue>=(m_pData+m_iLength)) && "inserting own value (like last()) by ref!" );
823 if ( m_iLength>=m_iLimit )
824 Reserve ( 1+m_iLength );
825 m_pData [ m_iLength++ ] = tValue;
826 }
827
828 /// add N more entries, and return a pointer to that buffer
AddN(int iCount)829 T * AddN ( int iCount )
830 {
831 if ( m_iLength + iCount > m_iLimit )
832 Reserve ( m_iLength + iCount );
833 m_iLength += iCount;
834 return m_pData + m_iLength - iCount;
835 }
836
837 /// add unique entry (ie. do not add if equal to last one)
AddUnique(const T & tValue)838 void AddUnique ( const T & tValue )
839 {
840 assert ( (&tValue<m_pData || &tValue>=(m_pData+m_iLength)) && "inserting own value (like last()) by ref!" );
841 if ( m_iLength>=m_iLimit )
842 Reserve ( 1+m_iLength );
843
844 if ( m_iLength==0 || m_pData[m_iLength-1]!=tValue )
845 m_pData [ m_iLength++ ] = tValue;
846 }
847
848 /// get first entry ptr
Begin()849 T * Begin ()
850 {
851 return m_iLength ? m_pData : NULL;
852 }
853
854 /// get first entry ptr
Begin()855 const T * Begin () const
856 {
857 return m_iLength ? m_pData : NULL;
858 }
859
860 /// get last entry
Last()861 T & Last ()
862 {
863 return (*this) [ m_iLength-1 ];
864 }
865
866 /// get last entry
Last()867 const T & Last () const
868 {
869 return (*this) [ m_iLength-1 ];
870 }
871
872 /// remove element by index
Remove(int iIndex)873 void Remove ( int iIndex )
874 {
875 assert ( iIndex>=0 && iIndex<m_iLength );
876
877 m_iLength--;
878 for ( int i=iIndex; i<m_iLength; i++ )
879 m_pData[i] = m_pData[i+1];
880 }
881
882 /// remove element by index, swapping it with the tail
RemoveFast(int iIndex)883 void RemoveFast ( int iIndex )
884 {
885 assert ( iIndex>=0 && iIndex<m_iLength );
886 if ( iIndex!=--m_iLength )
887 Swap ( m_pData[iIndex], m_pData[m_iLength] );
888 }
889
890 /// remove element by value (warning, linear O(n) search)
RemoveValue(T tValue)891 bool RemoveValue ( T tValue )
892 {
893 for ( int i=0; i<m_iLength; i++ )
894 if ( m_pData[i]==tValue )
895 {
896 Remove ( i );
897 return true;
898 }
899 return false;
900 }
901
902 /// remove element by value (warning, linear O(n) search)
903 template < typename FUNCTOR, typename U >
RemoveValue(FUNCTOR COMP,U tValue)904 bool RemoveValue ( FUNCTOR COMP, U tValue )
905 {
906 for ( int i=0; i<m_iLength; i++ )
907 if ( COMP.IsEq ( m_pData[i], tValue ) )
908 {
909 Remove ( i );
910 return true;
911 }
912 return false;
913 }
914
915 /// pop last value
Pop()916 const T & Pop ()
917 {
918 assert ( m_iLength>0 );
919 return m_pData[--m_iLength];
920 }
921
922 public:
923 /// grow enough to hold that much entries, if needed, but do *not* change the length
Reserve(int iNewLimit)924 void Reserve ( int iNewLimit )
925 {
926 // check that we really need to be called
927 assert ( iNewLimit>=0 );
928 if ( iNewLimit<=m_iLimit )
929 return;
930
931 // calc new limit
932 m_iLimit = POLICY::Relimit ( m_iLimit, iNewLimit );
933
934 // realloc
935 // FIXME! optimize for POD case
936 T * pNew = NULL;
937 if ( m_iLimit )
938 pNew = new T [ m_iLimit ];
939 __analysis_assume ( m_iLength<=m_iLimit );
940
941 POLICY::Copy ( pNew, m_pData, m_iLength );
942 delete [] m_pData;
943
944 m_pData = pNew;
945 }
946
947 /// resize
Resize(int iNewLength)948 void Resize ( int iNewLength )
949 {
950 assert ( iNewLength>=0 );
951 if ( (unsigned int)iNewLength>(unsigned int)m_iLength )
952 Reserve ( iNewLength );
953 m_iLength = iNewLength;
954 }
955
956 /// reset
Reset()957 void Reset ()
958 {
959 m_iLength = 0;
960 m_iLimit = 0;
961 SafeDeleteArray ( m_pData );
962 }
963
964 /// query current length, in elements
GetLength()965 inline int GetLength () const
966 {
967 return m_iLength;
968 }
969
970 /// query current reserved size, in elements
GetLimit()971 inline int GetLimit () const
972 {
973 return m_iLimit;
974 }
975
976 /// query currently used RAM, in bytes
GetSizeBytes()977 inline int GetSizeBytes() const
978 {
979 return m_iLimit*sizeof(T);
980 }
981
982 public:
983 /// filter unique
Uniq()984 void Uniq ()
985 {
986 if ( !m_iLength )
987 return;
988
989 Sort ();
990 int iLeft = sphUniq ( m_pData, m_iLength );
991 Resize ( iLeft );
992 }
993
994 /// default sort
995 void Sort ( int iStart=0, int iEnd=-1 )
996 {
997 Sort ( SphLess_T<T>(), iStart, iEnd );
998 }
999
1000 /// default reverse sort
1001 void RSort ( int iStart=0, int iEnd=-1 )
1002 {
1003 Sort ( SphGreater_T<T>(), iStart, iEnd );
1004 }
1005
1006 /// generic sort
1007 template < typename F > void Sort ( F COMP, int iStart=0, int iEnd=-1 )
1008 {
1009 if ( m_iLength<2 ) return;
1010 if ( iStart<0 ) iStart = m_iLength+iStart;
1011 if ( iEnd<0 ) iEnd = m_iLength+iEnd;
1012 assert ( iStart<=iEnd );
1013
1014 sphSort ( m_pData+iStart, iEnd-iStart+1, COMP );
1015 }
1016
1017 /// accessor by forward index
1018 const T & operator [] ( int iIndex ) const
1019 {
1020 assert ( iIndex>=0 && iIndex<m_iLength );
1021 return m_pData [ iIndex ];
1022 }
1023
1024 /// accessor by forward index
1025 T & operator [] ( int iIndex )
1026 {
1027 assert ( iIndex>=0 && iIndex<m_iLength );
1028 return m_pData [ iIndex ];
1029 }
1030
1031 /// copy
1032 const CSphVector<T> & operator = ( const CSphVector<T> & rhs )
1033 {
1034 Reset ();
1035
1036 m_iLength = rhs.m_iLength;
1037 m_iLimit = rhs.m_iLimit;
1038 if ( m_iLimit )
1039 m_pData = new T [ m_iLimit ];
1040 __analysis_assume ( m_iLength<=m_iLimit );
1041 for ( int i=0; i<rhs.m_iLength; i++ )
1042 m_pData[i] = rhs.m_pData[i];
1043
1044 return *this;
1045 }
1046
1047 /// swap
SwapData(CSphVector<T,POLICY> & rhs)1048 void SwapData ( CSphVector<T, POLICY> & rhs )
1049 {
1050 Swap ( m_iLength, rhs.m_iLength );
1051 Swap ( m_iLimit, rhs.m_iLimit );
1052 Swap ( m_pData, rhs.m_pData );
1053 }
1054
1055 /// leak
LeakData()1056 T * LeakData ()
1057 {
1058 T * pData = m_pData;
1059 m_pData = NULL;
1060 Reset();
1061 return pData;
1062 }
1063
1064 /// generic binary search
1065 /// assumes that the array is sorted in ascending order
1066 template < typename U, typename PRED >
BinarySearch(const PRED & tPred,U tRef)1067 const T * BinarySearch ( const PRED & tPred, U tRef ) const
1068 {
1069 return sphBinarySearch ( m_pData, m_pData+m_iLength-1, tPred, tRef );
1070 }
1071
1072 /// generic binary search
1073 /// assumes that the array is sorted in ascending order
BinarySearch(T tRef)1074 const T * BinarySearch ( T tRef ) const
1075 {
1076 return sphBinarySearch ( m_pData, m_pData+m_iLength-1, tRef );
1077 }
1078
1079 /// generic linear search
Contains(T tRef)1080 bool Contains ( T tRef ) const
1081 {
1082 for ( int i=0; i<m_iLength; i++ )
1083 if ( m_pData[i]==tRef )
1084 return true;
1085 return false;
1086 }
1087
1088 /// generic linear search
1089 template < typename FUNCTOR, typename U >
Contains(FUNCTOR COMP,U tValue)1090 bool Contains ( FUNCTOR COMP, U tValue )
1091 {
1092 for ( int i=0; i<m_iLength; i++ )
1093 if ( COMP.IsEq ( m_pData[i], tValue ) )
1094 return true;
1095 return false;
1096 }
1097
1098 /// fill with given value
Fill(const T & rhs)1099 void Fill ( const T & rhs )
1100 {
1101 for ( int i=0; i<m_iLength; i++ )
1102 m_pData[i] = rhs;
1103 }
1104
1105 /// insert into a middle
Insert(int iIndex,const T & tValue)1106 void Insert ( int iIndex, const T & tValue )
1107 {
1108 assert ( iIndex>=0 && iIndex<=m_iLength );
1109
1110 if ( m_iLength>=m_iLimit )
1111 Reserve ( m_iLength+1 );
1112
1113 // FIXME! this will not work for SwapVector
1114 for ( int i=m_iLength-1; i>=iIndex; i-- )
1115 m_pData [ i+1 ] = m_pData[i];
1116 m_pData[iIndex] = tValue;
1117 m_iLength++;
1118 }
1119
1120 protected:
1121 int m_iLength; ///< entries actually used
1122 int m_iLimit; ///< entries allocated
1123 T * m_pData; ///< entries
1124 };
1125
1126
1127 #define ARRAY_FOREACH(_index,_array) \
1128 for ( int _index=0; _index<_array.GetLength(); _index++ )
1129
1130 #define ARRAY_FOREACH_COND(_index,_array,_cond) \
1131 for ( int _index=0; _index<_array.GetLength() && (_cond); _index++ )
1132
1133 #define ARRAY_ANY(_res,_array,_cond) \
1134 false; \
1135 for ( int _any=0; _any<_array.GetLength() && !_res; _any++ ) \
1136 _res |= ( _cond ); \
1137
1138 #define ARRAY_ALL(_res,_array,_cond) \
1139 true; \
1140 for ( int _all=0; _all<_array.GetLength() && _res; _all++ ) \
1141 _res &= ( _cond ); \
1142
1143 //////////////////////////////////////////////////////////////////////////
1144
1145 /// swap-vector policy (for non-copyable classes)
1146 /// use Swap() instead of assignment on resize
1147 template < typename T >
1148 class CSphSwapVectorPolicy : public CSphVectorPolicy<T>
1149 {
1150 public:
Copy(T * pNew,T * pData,int iLength)1151 static inline void Copy ( T * pNew, T * pData, int iLength )
1152 {
1153 for ( int i=0; i<iLength; i++ )
1154 Swap ( pNew[i], pData[i] );
1155 }
1156 };
1157
1158 /// tight-vector policy
1159 /// grow only 1.2x on resize (not 2x) starting from a certain threshold
1160 template < typename T >
1161 class CSphTightVectorPolicy : public CSphVectorPolicy<T>
1162 {
1163 protected:
1164 static const int SLOW_GROW_TRESHOLD = 1024;
1165
1166 public:
Relimit(int iLimit,int iNewLimit)1167 static inline int Relimit ( int iLimit, int iNewLimit )
1168 {
1169 if ( !iLimit )
1170 iLimit = CSphVectorPolicy<T>::MAGIC_INITIAL_LIMIT;
1171 while ( iLimit<iNewLimit && iLimit<SLOW_GROW_TRESHOLD )
1172 {
1173 iLimit *= 2;
1174 assert ( iLimit>0 );
1175 }
1176 while ( iLimit<iNewLimit )
1177 {
1178 iLimit = (int)( iLimit*1.2f );
1179 assert ( iLimit>0 );
1180 }
1181 return iLimit;
1182 }
1183 };
1184
1185 /// swap-vector
1186 template < typename T >
1187 class CSphSwapVector : public CSphVector < T, CSphSwapVectorPolicy<T> >
1188 {
1189 };
1190
1191 /// tight-vector
1192 template < typename T >
1193 class CSphTightVector : public CSphVector < T, CSphTightVectorPolicy<T> >
1194 {
1195 };
1196
1197 //////////////////////////////////////////////////////////////////////////
1198
1199 /// dynamically allocated fixed-size vector
1200 template < typename T >
1201 class CSphFixedVector : public ISphNoncopyable
1202 {
1203 protected:
1204 T * m_pData;
1205 int m_iSize;
1206
1207 public:
CSphFixedVector(int iSize)1208 explicit CSphFixedVector ( int iSize )
1209 : m_iSize ( iSize )
1210 {
1211 assert ( iSize>=0 );
1212 m_pData = ( iSize>0 ) ? new T [ iSize ] : NULL;
1213 }
1214
~CSphFixedVector()1215 ~CSphFixedVector ()
1216 {
1217 SafeDeleteArray ( m_pData );
1218 }
1219
1220 T & operator [] ( int iIndex ) const
1221 {
1222 assert ( iIndex>=0 && iIndex<m_iSize );
1223 return m_pData[iIndex];
1224 }
1225
Begin()1226 T * Begin () const
1227 {
1228 return m_pData;
1229 }
1230
Last()1231 T & Last () const
1232 {
1233 return (*this) [ m_iSize-1 ];
1234 }
1235
Reset(int iSize)1236 void Reset ( int iSize )
1237 {
1238 SafeDeleteArray ( m_pData );
1239 assert ( iSize>=0 );
1240 m_pData = ( iSize>0 ) ? new T [ iSize ] : NULL;
1241 m_iSize = iSize;
1242 }
1243
GetLength()1244 int GetLength() const
1245 {
1246 return m_iSize;
1247 }
1248
GetSizeBytes()1249 int GetSizeBytes() const
1250 {
1251 return m_iSize*sizeof(T);
1252 }
1253
LeakData()1254 T * LeakData ()
1255 {
1256 T * pData = m_pData;
1257 m_pData = NULL;
1258 Reset ( 0 );
1259 return pData;
1260 }
1261
1262 /// swap
SwapData(CSphFixedVector<T> & rhs)1263 void SwapData ( CSphFixedVector<T> & rhs )
1264 {
1265 Swap ( m_pData, rhs.m_pData );
1266 Swap ( m_iSize, rhs.m_iSize );
1267 }
1268
BinarySearch(T tRef)1269 const T * BinarySearch ( T tRef ) const
1270 {
1271 return sphBinarySearch ( m_pData, m_pData+m_iSize-1, tRef );
1272 }
1273 };
1274
1275 //////////////////////////////////////////////////////////////////////////
1276
1277 /// simple dynamic hash
1278 /// implementation: fixed-size bucket + chaining
1279 /// keeps the order, so Iterate() return the entries in the order they was inserted
1280 /// WARNING: slow copy
1281 template < typename T, typename KEY, typename HASHFUNC, int LENGTH >
1282 class CSphOrderedHash
1283 {
1284 protected:
1285 struct HashEntry_t
1286 {
1287 KEY m_tKey; ///< key, owned by the hash
1288 T m_tValue; ///< data, owned by the hash
1289 HashEntry_t * m_pNextByHash; ///< next entry in hash list
1290 HashEntry_t * m_pPrevByOrder; ///< prev entry in the insertion order
1291 HashEntry_t * m_pNextByOrder; ///< next entry in the insertion order
1292 };
1293
1294
1295 protected:
1296 HashEntry_t * m_dHash [ LENGTH ]; ///< all the hash entries
1297 HashEntry_t * m_pFirstByOrder; ///< first entry in the insertion order
1298 HashEntry_t * m_pLastByOrder; ///< last entry in the insertion order
1299 int m_iLength; ///< entries count
1300
1301 protected:
1302 /// find entry by key
FindByKey(const KEY & tKey)1303 HashEntry_t * FindByKey ( const KEY & tKey ) const
1304 {
1305 unsigned int uHash = ( (unsigned int) HASHFUNC::Hash ( tKey ) ) % LENGTH;
1306 HashEntry_t * pEntry = m_dHash [ uHash ];
1307
1308 while ( pEntry )
1309 {
1310 if ( pEntry->m_tKey==tKey )
1311 return pEntry;
1312 pEntry = pEntry->m_pNextByHash;
1313 }
1314 return NULL;
1315 }
1316
1317 public:
1318 /// ctor
CSphOrderedHash()1319 CSphOrderedHash ()
1320 : m_pFirstByOrder ( NULL )
1321 , m_pLastByOrder ( NULL )
1322 , m_iLength ( 0 )
1323 , m_pIterator ( NULL )
1324 {
1325 for ( int i=0; i<LENGTH; i++ )
1326 m_dHash[i] = NULL;
1327 }
1328
1329 /// dtor
~CSphOrderedHash()1330 ~CSphOrderedHash ()
1331 {
1332 Reset ();
1333 }
1334
1335 /// reset
Reset()1336 void Reset ()
1337 {
1338 assert ( ( m_pFirstByOrder && m_iLength ) || ( !m_pFirstByOrder && !m_iLength ) );
1339 HashEntry_t * pKill = m_pFirstByOrder;
1340 while ( pKill )
1341 {
1342 HashEntry_t * pNext = pKill->m_pNextByOrder;
1343 SafeDelete ( pKill );
1344 pKill = pNext;
1345 }
1346
1347 for ( int i=0; i<LENGTH; i++ )
1348 m_dHash[i] = 0;
1349
1350 m_pFirstByOrder = NULL;
1351 m_pLastByOrder = NULL;
1352 m_pIterator = NULL;
1353 m_iLength = 0;
1354 }
1355
1356 /// add new entry
1357 /// returns true on success
1358 /// returns false if this key is already hashed
Add(const T & tValue,const KEY & tKey)1359 bool Add ( const T & tValue, const KEY & tKey )
1360 {
1361 unsigned int uHash = ( (unsigned int) HASHFUNC::Hash ( tKey ) ) % LENGTH;
1362
1363 // check if this key is already hashed
1364 HashEntry_t * pEntry = m_dHash [ uHash ];
1365 HashEntry_t ** ppEntry = &m_dHash [ uHash ];
1366 while ( pEntry )
1367 {
1368 if ( pEntry->m_tKey==tKey )
1369 return false;
1370
1371 ppEntry = &pEntry->m_pNextByHash;
1372 pEntry = pEntry->m_pNextByHash;
1373 }
1374
1375 // it's not; let's add the entry
1376 assert ( !pEntry );
1377 assert ( !*ppEntry );
1378
1379 pEntry = new HashEntry_t;
1380 pEntry->m_tKey = tKey;
1381 pEntry->m_tValue = tValue;
1382 pEntry->m_pNextByHash = NULL;
1383 pEntry->m_pPrevByOrder = NULL;
1384 pEntry->m_pNextByOrder = NULL;
1385
1386 *ppEntry = pEntry;
1387
1388 if ( !m_pFirstByOrder )
1389 m_pFirstByOrder = pEntry;
1390
1391 if ( m_pLastByOrder )
1392 {
1393 assert ( !m_pLastByOrder->m_pNextByOrder );
1394 assert ( !pEntry->m_pNextByOrder );
1395 m_pLastByOrder->m_pNextByOrder = pEntry;
1396 pEntry->m_pPrevByOrder = m_pLastByOrder;
1397 }
1398 m_pLastByOrder = pEntry;
1399
1400 m_iLength++;
1401 return true;
1402 }
1403
1404 /// add new entry
1405 /// returns the pointer to just inserted or previously cached (if dupe) value
AddUnique(const KEY & tKey)1406 T & AddUnique ( const KEY & tKey )
1407 {
1408 unsigned int uHash = ( (unsigned int) HASHFUNC::Hash ( tKey ) ) % LENGTH;
1409
1410 // check if this key is already hashed
1411 HashEntry_t * pEntry = m_dHash [ uHash ];
1412 HashEntry_t ** ppEntry = &m_dHash [ uHash ];
1413 while ( pEntry )
1414 {
1415 if ( pEntry->m_tKey==tKey )
1416 return pEntry->m_tValue;
1417
1418 ppEntry = &pEntry->m_pNextByHash;
1419 pEntry = pEntry->m_pNextByHash;
1420 }
1421
1422 // it's not; let's add the entry
1423 assert ( !pEntry );
1424 assert ( !*ppEntry );
1425
1426 pEntry = new HashEntry_t;
1427 pEntry->m_tKey = tKey;
1428 pEntry->m_pNextByHash = NULL;
1429 pEntry->m_pPrevByOrder = NULL;
1430 pEntry->m_pNextByOrder = NULL;
1431
1432 *ppEntry = pEntry;
1433
1434 if ( !m_pFirstByOrder )
1435 m_pFirstByOrder = pEntry;
1436
1437 if ( m_pLastByOrder )
1438 {
1439 assert ( !m_pLastByOrder->m_pNextByOrder );
1440 assert ( !pEntry->m_pNextByOrder );
1441 m_pLastByOrder->m_pNextByOrder = pEntry;
1442 pEntry->m_pPrevByOrder = m_pLastByOrder;
1443 }
1444 m_pLastByOrder = pEntry;
1445
1446 m_iLength++;
1447 return pEntry->m_tValue;
1448 }
1449
1450 /// delete an entry
Delete(const KEY & tKey)1451 bool Delete ( const KEY & tKey )
1452 {
1453 unsigned int uHash = ( (unsigned int) HASHFUNC::Hash ( tKey ) ) % LENGTH;
1454 HashEntry_t * pEntry = m_dHash [ uHash ];
1455
1456 HashEntry_t * pPrevEntry = NULL;
1457 HashEntry_t * pToDelete = NULL;
1458 while ( pEntry )
1459 {
1460 if ( pEntry->m_tKey==tKey )
1461 {
1462 pToDelete = pEntry;
1463 if ( pPrevEntry )
1464 pPrevEntry->m_pNextByHash = pEntry->m_pNextByHash;
1465 else
1466 m_dHash [ uHash ] = pEntry->m_pNextByHash;
1467
1468 break;
1469 }
1470
1471 pPrevEntry = pEntry;
1472 pEntry = pEntry->m_pNextByHash;
1473 }
1474
1475 if ( !pToDelete )
1476 return false;
1477
1478 if ( pToDelete->m_pPrevByOrder )
1479 pToDelete->m_pPrevByOrder->m_pNextByOrder = pToDelete->m_pNextByOrder;
1480 else
1481 m_pFirstByOrder = pToDelete->m_pNextByOrder;
1482
1483 if ( pToDelete->m_pNextByOrder )
1484 pToDelete->m_pNextByOrder->m_pPrevByOrder = pToDelete->m_pPrevByOrder;
1485 else
1486 m_pLastByOrder = pToDelete->m_pPrevByOrder;
1487
1488 // step the iterator one item back - to gracefully hold deletion in iteration cycle
1489 if ( pToDelete==m_pIterator )
1490 m_pIterator = pToDelete->m_pPrevByOrder;
1491
1492 SafeDelete ( pToDelete );
1493 --m_iLength;
1494
1495 return true;
1496 }
1497
1498 /// check if key exists
Exists(const KEY & tKey)1499 bool Exists ( const KEY & tKey ) const
1500 {
1501 return FindByKey ( tKey )!=NULL;
1502 }
1503
1504 /// get value pointer by key
operator()1505 T * operator () ( const KEY & tKey ) const
1506 {
1507 HashEntry_t * pEntry = FindByKey ( tKey );
1508 return pEntry ? &pEntry->m_tValue : NULL;
1509 }
1510
1511 /// get value reference by key, asserting that the key exists in hash
1512 T & operator [] ( const KEY & tKey ) const
1513 {
1514 HashEntry_t * pEntry = FindByKey ( tKey );
1515 assert ( pEntry && "hash missing value in operator []" );
1516
1517 return pEntry->m_tValue;
1518 }
1519
1520 /// get pointer to key storage
GetKeyPtr(const KEY & tKey)1521 const KEY * GetKeyPtr ( const KEY & tKey ) const
1522 {
1523 HashEntry_t * pEntry = FindByKey ( tKey );
1524 return pEntry ? &pEntry->m_tKey : NULL;
1525 }
1526
1527 /// copying
1528 const CSphOrderedHash<T,KEY,HASHFUNC,LENGTH> & operator = ( const CSphOrderedHash<T,KEY,HASHFUNC,LENGTH> & rhs )
1529 {
1530 if ( this!=&rhs )
1531 {
1532 Reset ();
1533
1534 rhs.IterateStart ();
1535 while ( rhs.IterateNext() )
1536 Add ( rhs.IterateGet(), rhs.IterateGetKey() );
1537 }
1538 return *this;
1539 }
1540
1541 /// copying ctor
1542 CSphOrderedHash<T,KEY,HASHFUNC,LENGTH> ( const CSphOrderedHash<T,KEY,HASHFUNC,LENGTH> & rhs )
m_pFirstByOrder(NULL)1543 : m_pFirstByOrder ( NULL )
1544 , m_pLastByOrder ( NULL )
1545 , m_iLength ( 0 )
1546 , m_pIterator ( NULL )
1547 {
1548 for ( int i=0; i<LENGTH; i++ )
1549 m_dHash[i] = NULL;
1550 *this = rhs;
1551 }
1552
1553 /// length query
GetLength()1554 int GetLength () const
1555 {
1556 return m_iLength;
1557 }
1558
1559 public:
1560 /// start iterating
IterateStart()1561 void IterateStart () const
1562 {
1563 m_pIterator = NULL;
1564 }
1565
1566 /// start iterating from key element
IterateStart(const KEY & tKey)1567 bool IterateStart ( const KEY & tKey ) const
1568 {
1569 m_pIterator = FindByKey ( tKey );
1570 return m_pIterator!=NULL;
1571 }
1572
1573 /// go to next existing entry
IterateNext()1574 bool IterateNext () const
1575 {
1576 m_pIterator = m_pIterator ? m_pIterator->m_pNextByOrder : m_pFirstByOrder;
1577 return m_pIterator!=NULL;
1578 }
1579
1580 /// get entry value
IterateGet()1581 T & IterateGet () const
1582 {
1583 assert ( m_pIterator );
1584 return m_pIterator->m_tValue;
1585 }
1586
1587 /// get entry key
IterateGetKey()1588 const KEY & IterateGetKey () const
1589 {
1590 assert ( m_pIterator );
1591 return m_pIterator->m_tKey;
1592 }
1593
1594 /// go to next existing entry in terms of external independed iterator
IterateNext(void ** ppCookie)1595 bool IterateNext ( void ** ppCookie ) const
1596 {
1597 HashEntry_t ** ppIterator = reinterpret_cast < HashEntry_t** > ( ppCookie );
1598 *ppIterator = ( *ppIterator ) ? ( *ppIterator )->m_pNextByOrder : m_pFirstByOrder;
1599 return ( *ppIterator )!=NULL;
1600 }
1601
1602 /// get entry value in terms of external independed iterator
IterateGet(void ** ppCookie)1603 static T & IterateGet ( void ** ppCookie )
1604 {
1605 assert ( ppCookie );
1606 HashEntry_t ** ppIterator = reinterpret_cast < HashEntry_t** > ( ppCookie );
1607 assert ( *ppIterator );
1608 return ( *ppIterator )->m_tValue;
1609 }
1610
1611 /// get entry key in terms of external independed iterator
IterateGetKey(void ** ppCookie)1612 static const KEY & IterateGetKey ( void ** ppCookie )
1613 {
1614 assert ( ppCookie );
1615 HashEntry_t ** ppIterator = reinterpret_cast < HashEntry_t** > ( ppCookie );
1616 assert ( *ppIterator );
1617 return ( *ppIterator )->m_tKey;
1618 }
1619
1620
1621 private:
1622 /// current iterator
1623 mutable HashEntry_t * m_pIterator;
1624 };
1625
1626 /// very popular and so, moved here
1627 /// use integer values as hash values (like document IDs, for example)
1628 struct IdentityHash_fn
1629 {
1630 template <typename INT>
HashIdentityHash_fn1631 static inline INT Hash ( INT iValue ) { return iValue; }
1632 };
1633
1634 /////////////////////////////////////////////////////////////////////////////
1635
1636 /// immutable C string proxy
1637 struct CSphString
1638 {
1639 protected:
1640 char * m_sValue;
1641 // Empty ("") string optimization.
1642 static char EMPTY[];
1643
1644 private:
1645 /// safety gap after the string end; for instance, UTF-8 Russian stemmer
1646 /// which treats strings as 16-bit word sequences needs this in some cases.
1647 /// note that this zero-filled gap does NOT include trailing C-string zero,
1648 /// and does NOT affect strlen() as well.
1649 static const int SAFETY_GAP = 4;
1650
1651 public:
CSphStringCSphString1652 CSphString ()
1653 : m_sValue ( NULL )
1654 {
1655 }
1656
1657 // take a note this is not an explicit constructor
1658 // so a lot of silent constructing and deleting of strings is possible
1659 // Example:
1660 // SmallStringHash_T<int> hHash;
1661 // ...
1662 // hHash.Exists ( "asdf" ); // implicit CSphString construction and deletion here
CSphStringCSphString1663 CSphString ( const CSphString & rhs )
1664 : m_sValue ( NULL )
1665 {
1666 *this = rhs;
1667 }
1668
~CSphStringCSphString1669 ~CSphString ()
1670 {
1671 if ( m_sValue!=EMPTY )
1672 SafeDeleteArray ( m_sValue );
1673 }
1674
cstrCSphString1675 const char * cstr () const
1676 {
1677 return m_sValue;
1678 }
1679
scstrCSphString1680 const char * scstr() const
1681 {
1682 return m_sValue ? m_sValue : EMPTY;
1683 }
1684
1685 inline bool operator == ( const char * t ) const
1686 {
1687 if ( !t || !m_sValue )
1688 return ( ( !t && !m_sValue ) || ( !t && m_sValue && !*m_sValue ) || ( !m_sValue && t && !*t ) );
1689 return strcmp ( m_sValue, t )==0;
1690 }
1691
1692 inline bool operator == ( const CSphString & t ) const
1693 {
1694 return operator==( t.cstr() );
1695 }
1696
1697 inline bool operator != ( const CSphString & t ) const
1698 {
1699 return !operator==( t );
1700 }
1701
1702 bool operator != ( const char * t ) const
1703 {
1704 return !operator==( t );
1705 }
1706
CSphStringCSphString1707 CSphString ( const char * sString ) // NOLINT
1708 {
1709 if ( sString )
1710 {
1711 if ( sString[0]=='\0' )
1712 {
1713 m_sValue = EMPTY;
1714 } else
1715 {
1716 int iLen = 1+strlen(sString);
1717 m_sValue = new char [ iLen+SAFETY_GAP ];
1718
1719 strcpy ( m_sValue, sString ); // NOLINT
1720 memset ( m_sValue+iLen, 0, SAFETY_GAP );
1721 }
1722 } else
1723 {
1724 m_sValue = NULL;
1725 }
1726 }
1727
CSphStringCSphString1728 CSphString ( const char * sValue, int iLen )
1729 : m_sValue ( NULL )
1730 {
1731 SetBinary ( sValue, iLen );
1732 }
1733
1734 const CSphString & operator = ( const CSphString & rhs )
1735 {
1736 if ( m_sValue==rhs.m_sValue )
1737 return *this;
1738 if ( m_sValue!=EMPTY )
1739 SafeDeleteArray ( m_sValue );
1740 if ( rhs.m_sValue )
1741 {
1742 if ( rhs.m_sValue[0]=='\0' )
1743 {
1744 m_sValue = EMPTY;
1745 } else
1746 {
1747 int iLen = 1+strlen(rhs.m_sValue);
1748 m_sValue = new char [ iLen+SAFETY_GAP ];
1749
1750 strcpy ( m_sValue, rhs.m_sValue ); // NOLINT
1751 memset ( m_sValue+iLen, 0, SAFETY_GAP );
1752 }
1753 }
1754 return *this;
1755 }
1756
SubStringCSphString1757 CSphString SubString ( int iStart, int iCount ) const
1758 {
1759 #ifndef NDEBUG
1760 int iLen = strlen(m_sValue);
1761 #endif
1762 assert ( iStart>=0 && iStart<iLen );
1763 assert ( iCount>0 );
1764 assert ( (iStart+iCount)>=0 && (iStart+iCount)<=iLen );
1765
1766 CSphString sRes;
1767 sRes.m_sValue = new char [ 1+SAFETY_GAP+iCount ];
1768 strncpy ( sRes.m_sValue, m_sValue+iStart, iCount );
1769 memset ( sRes.m_sValue+iCount, 0, 1+SAFETY_GAP );
1770 return sRes;
1771 }
1772
SetBinaryCSphString1773 void SetBinary ( const char * sValue, int iLen )
1774 {
1775 if ( m_sValue!=EMPTY )
1776 SafeDeleteArray ( m_sValue );
1777 if ( sValue )
1778 {
1779 if ( sValue[0]=='\0' )
1780 {
1781 m_sValue = EMPTY;
1782 } else
1783 {
1784 m_sValue = new char [ 1+SAFETY_GAP+iLen ];
1785 memcpy ( m_sValue, sValue, iLen );
1786 memset ( m_sValue+iLen, 0, 1+SAFETY_GAP );
1787 }
1788 }
1789 }
1790
ReserveCSphString1791 void Reserve ( int iLen )
1792 {
1793 if ( m_sValue!=EMPTY )
1794 SafeDeleteArray ( m_sValue );
1795 m_sValue = new char [ 1+SAFETY_GAP+iLen ];
1796 memset ( m_sValue, 0, 1+SAFETY_GAP+iLen );
1797 }
1798
SetSprintfCSphString1799 const CSphString & SetSprintf ( const char * sTemplate, ... ) __attribute__ ( ( format ( printf, 2, 3 ) ) )
1800 {
1801 char sBuf[1024];
1802 va_list ap;
1803
1804 va_start ( ap, sTemplate );
1805 vsnprintf ( sBuf, sizeof(sBuf), sTemplate, ap );
1806 va_end ( ap );
1807
1808 (*this) = sBuf;
1809 return (*this);
1810 }
1811
SetSprintfVaCSphString1812 const CSphString & SetSprintfVa ( const char * sTemplate, va_list ap )
1813 {
1814 char sBuf[1024];
1815 vsnprintf ( sBuf, sizeof(sBuf), sTemplate, ap );
1816
1817 (*this) = sBuf;
1818 return (*this);
1819 }
1820
IsEmptyCSphString1821 bool IsEmpty () const
1822 {
1823 if ( !m_sValue )
1824 return true;
1825 return ( (*m_sValue)=='\0' );
1826 }
1827
ToLowerCSphString1828 CSphString & ToLower ()
1829 {
1830 if ( m_sValue )
1831 for ( char * s=m_sValue; *s; s++ )
1832 *s = (char) tolower ( *s );
1833 return *this;
1834 }
1835
ToUpperCSphString1836 CSphString & ToUpper ()
1837 {
1838 if ( m_sValue )
1839 for ( char * s=m_sValue; *s; s++ )
1840 *s = (char) toupper ( *s );
1841 return *this;
1842 }
1843
SwapCSphString1844 void Swap ( CSphString & rhs )
1845 {
1846 ::Swap ( m_sValue, rhs.m_sValue );
1847 }
1848
BeginsCSphString1849 bool Begins ( const char * sPrefix ) const
1850 {
1851 if ( !m_sValue || !sPrefix )
1852 return false;
1853 return strncmp ( m_sValue, sPrefix, strlen(sPrefix) )==0;
1854 }
1855
EndsCSphString1856 bool Ends ( const char * sSuffix ) const
1857 {
1858 if ( !m_sValue || !sSuffix )
1859 return false;
1860
1861 int iVal = strlen ( m_sValue );
1862 int iSuffix = strlen ( sSuffix );
1863 if ( iVal<iSuffix )
1864 return false;
1865 return strncmp ( m_sValue+iVal-iSuffix, sSuffix, iSuffix )==0;
1866 }
1867
TrimCSphString1868 void Trim ()
1869 {
1870 if ( m_sValue )
1871 {
1872 const char * sStart = m_sValue;
1873 const char * sEnd = m_sValue + strlen(m_sValue) - 1;
1874 while ( sStart<=sEnd && isspace ( (unsigned char)*sStart ) ) sStart++;
1875 while ( sStart<=sEnd && isspace ( (unsigned char)*sEnd ) ) sEnd--;
1876 memmove ( m_sValue, sStart, sEnd-sStart+1 );
1877 m_sValue [ sEnd-sStart+1 ] = '\0';
1878 }
1879 }
1880
LengthCSphString1881 int Length () const
1882 {
1883 return m_sValue ? (int)strlen(m_sValue) : 0;
1884 }
1885
LeakCSphString1886 char * Leak ()
1887 {
1888 if ( m_sValue==EMPTY )
1889 {
1890 m_sValue = NULL;
1891 char * pBuf = new char[1];
1892 pBuf[0] = '\0';
1893 return pBuf;
1894 }
1895 char * pBuf = m_sValue;
1896 m_sValue = NULL;
1897 return pBuf;
1898 }
1899
1900 // opposite to Leak()
AdoptCSphString1901 void Adopt ( char ** sValue )
1902 {
1903 if ( m_sValue!=EMPTY )
1904 SafeDeleteArray ( m_sValue );
1905 m_sValue = *sValue;
1906 *sValue = NULL;
1907 }
1908
1909 bool operator < ( const CSphString & b ) const
1910 {
1911 if ( !m_sValue && !b.m_sValue )
1912 return false;
1913 if ( !m_sValue || !b.m_sValue )
1914 return !m_sValue;
1915 return strcmp ( m_sValue, b.m_sValue ) < 0;
1916 }
1917
UnquoteCSphString1918 void Unquote()
1919 {
1920 int l = Length();
1921 if ( l && m_sValue[0]=='\'' && m_sValue[l-1]=='\'' )
1922 {
1923 memmove ( m_sValue, m_sValue+1, l-2 );
1924 m_sValue[l-2] = '\0';
1925 }
1926 }
1927 };
1928
1929 /// string swapper
Swap(CSphString & v1,CSphString & v2)1930 inline void Swap ( CSphString & v1, CSphString & v2 )
1931 {
1932 v1.Swap ( v2 );
1933 }
1934
1935
1936 /// string builder
1937 /// somewhat quicker than a series of SetSprintf()s
1938 /// lets you build strings bigger than 1024 bytes, too
1939 class CSphStringBuilder
1940 {
1941 protected:
1942 char * m_sBuffer;
1943 int m_iSize;
1944 int m_iUsed;
1945
1946 public:
CSphStringBuilder()1947 CSphStringBuilder ()
1948 {
1949 Reset ();
1950 }
1951
~CSphStringBuilder()1952 ~CSphStringBuilder ()
1953 {
1954 SafeDeleteArray ( m_sBuffer );
1955 }
1956
Reset()1957 void Reset ()
1958 {
1959 m_iSize = 256;
1960 m_sBuffer = new char [ m_iSize ];
1961 Clear ();
1962 }
1963
Clear()1964 void Clear ()
1965 {
1966 m_sBuffer[0] = '\0';
1967 m_iUsed = 0;
1968 }
1969
Appendf(const char * sTemplate,...)1970 CSphStringBuilder & Appendf ( const char * sTemplate, ... ) __attribute__ ( ( format ( printf, 2, 3 ) ) )
1971 {
1972 assert ( m_sBuffer );
1973 assert ( m_iUsed<m_iSize );
1974
1975 for ( ;; )
1976 {
1977 int iLeft = m_iSize - m_iUsed;
1978
1979 // try to append
1980 va_list ap;
1981 va_start ( ap, sTemplate );
1982 int iPrinted = vsnprintf ( m_sBuffer+m_iUsed, iLeft, sTemplate, ap );
1983 va_end ( ap );
1984
1985 // success? bail
1986 // note that we check for strictly less, not less or equal
1987 // that is because vsnprintf does *not* count the trailing zero
1988 // meaning that if we had N bytes left, and N bytes w/o the zero were printed,
1989 // we do not have a trailing zero anymore, but vsnprintf succeeds anyway
1990 if ( iPrinted>=0 && iPrinted<iLeft )
1991 {
1992 m_iUsed += iPrinted;
1993 break;
1994 }
1995
1996 // we need more chars!
1997 // either 256 (happens on Windows; lets assume we need 256 more chars)
1998 // or get all the needed chars and 64 more for future calls
1999 Grow ( iPrinted<0 ? 256 : iPrinted - iLeft + 64 );
2000 }
2001 return *this;
2002 }
2003
cstr()2004 const char * cstr() const
2005 {
2006 return m_sBuffer;
2007 }
2008
Length()2009 int Length ()
2010 {
2011 return m_iUsed;
2012 }
2013
2014 const CSphStringBuilder & operator += ( const char * sText )
2015 {
2016 if ( !sText || *sText=='\0' )
2017 return *this;
2018
2019 int iLen = strlen ( sText );
2020 int iLeft = m_iSize - m_iUsed;
2021 if ( iLen>=iLeft )
2022 Grow ( iLen - iLeft + 64 );
2023
2024 memcpy ( m_sBuffer+m_iUsed, sText, iLen+1 );
2025 m_iUsed += iLen;
2026 return *this;
2027 }
2028
2029 const CSphStringBuilder & operator = ( const CSphStringBuilder & rhs )
2030 {
2031 if ( this!=&rhs )
2032 {
2033 m_iUsed = rhs.m_iUsed;
2034 m_iSize = rhs.m_iSize;
2035 SafeDeleteArray ( m_sBuffer );
2036 m_sBuffer = new char [ m_iSize ];
2037 memcpy ( m_sBuffer, rhs.m_sBuffer, m_iUsed+1 );
2038 }
2039 return *this;
2040 }
2041
2042 // FIXME? move escaping to another place
2043 void AppendEscaped ( const char * sText, bool bEscape=true, bool bFixupSpace=true )
2044 {
2045 if ( !sText || !*sText )
2046 return;
2047
2048 const char * pBuf = sText;
2049 int iEsc = 0;
2050 for ( ; *pBuf; )
2051 {
2052 char s = *pBuf++;
2053 iEsc = ( bEscape && ( s=='\\' || s=='\'' ) ) ? ( iEsc+1 ) : iEsc;
2054 }
2055
2056 int iLen = pBuf - sText + iEsc;
2057 int iLeft = m_iSize - m_iUsed;
2058 if ( iLen>=iLeft )
2059 Grow ( iLen - iLeft + 64 );
2060
2061 pBuf = sText;
2062 char * pCur = m_sBuffer+m_iUsed;
2063 for ( ; *pBuf; )
2064 {
2065 char s = *pBuf++;
2066 if ( bEscape && ( s=='\\' || s=='\'' ) )
2067 {
2068 *pCur++ = '\\';
2069 *pCur++ = s;
2070 } else if ( bFixupSpace && ( s==' ' || s=='\t' || s=='\n' || s=='\r' ) )
2071 {
2072 *pCur++ = ' ';
2073 } else
2074 {
2075 *pCur++ = s;
2076 }
2077 }
2078 *pCur = '\0';
2079 m_iUsed = pCur-m_sBuffer;
2080 }
2081
2082 private:
Grow(int iLen)2083 void Grow ( int iLen )
2084 {
2085 m_iSize += iLen;
2086 char * pNew = new char [ m_iSize ];
2087 memcpy ( pNew, m_sBuffer, m_iUsed+1 );
2088 Swap ( pNew, m_sBuffer );
2089 SafeDeleteArray ( pNew );
2090 }
2091 };
2092
2093 /////////////////////////////////////////////////////////////////////////////
2094
2095 /// immutable string/int/float variant list proxy
2096 /// used in config parsing
2097 struct CSphVariant
2098 {
2099 protected:
2100 CSphString m_sValue;
2101 int m_iValue;
2102 int64_t m_i64Value;
2103 float m_fValue;
2104
2105 public:
2106 CSphVariant * m_pNext;
2107 // tags are used for handling multiple same keys
2108 bool m_bTag; // 'true' means override - no multi-valued; 'false' means multi-valued - chain them
2109 int m_iTag; // stores order like in config file
2110
2111 public:
2112 /// default ctor
CSphVariantCSphVariant2113 CSphVariant ()
2114 : m_iValue ( 0 )
2115 , m_i64Value ( 0 )
2116 , m_fValue ( 0.0f )
2117 , m_pNext ( NULL )
2118 , m_bTag ( false )
2119 , m_iTag ( 0 )
2120 {
2121 }
2122
2123 /// ctor from C string
CSphVariantCSphVariant2124 CSphVariant ( const char * sString, int iTag )
2125 : m_sValue ( sString )
2126 , m_iValue ( sString ? atoi ( sString ) : 0 )
2127 , m_i64Value ( sString ? (int64_t)strtoull ( sString, NULL, 10 ) : 0 )
2128 , m_fValue ( sString ? (float)atof ( sString ) : 0.0f )
2129 , m_pNext ( NULL )
2130 , m_bTag ( false )
2131 , m_iTag ( iTag )
2132 {
2133 }
2134
2135 /// copy ctor
CSphVariantCSphVariant2136 CSphVariant ( const CSphVariant & rhs )
2137 {
2138 m_pNext = NULL;
2139 *this = rhs;
2140 }
2141
2142 /// default dtor
2143 /// WARNING: automatically frees linked items!
~CSphVariantCSphVariant2144 ~CSphVariant ()
2145 {
2146 SafeDelete ( m_pNext );
2147 }
2148
cstrCSphVariant2149 const char * cstr() const { return m_sValue.cstr(); }
2150
strvalCSphVariant2151 const CSphString & strval () const { return m_sValue; }
intvalCSphVariant2152 int intval () const { return m_iValue; }
int64valCSphVariant2153 int64_t int64val () const { return m_i64Value; }
floatvalCSphVariant2154 float floatval () const { return m_fValue; }
2155
2156 /// default copy operator
2157 const CSphVariant & operator = ( const CSphVariant & rhs )
2158 {
2159 assert ( !m_pNext );
2160 if ( rhs.m_pNext )
2161 m_pNext = new CSphVariant ( *rhs.m_pNext );
2162
2163 m_sValue = rhs.m_sValue;
2164 m_iValue = rhs.m_iValue;
2165 m_i64Value = rhs.m_i64Value;
2166 m_fValue = rhs.m_fValue;
2167 m_bTag = rhs.m_bTag;
2168 m_iTag = rhs.m_iTag;
2169
2170 return *this;
2171 }
2172
2173 bool operator== ( const char * s ) const { return m_sValue==s; }
2174 bool operator!= ( const char * s ) const { return m_sValue!=s; }
2175 };
2176
2177 //////////////////////////////////////////////////////////////////////////
2178
2179 /// name+int pair
2180 struct CSphNamedInt
2181 {
2182 CSphString m_sName;
2183 int m_iValue;
2184
CSphNamedIntCSphNamedInt2185 CSphNamedInt () : m_iValue ( 0 ) {}
2186 };
2187
Swap(CSphNamedInt & a,CSphNamedInt & b)2188 inline void Swap ( CSphNamedInt & a, CSphNamedInt & b )
2189 {
2190 a.m_sName.Swap ( b.m_sName );
2191 Swap ( a.m_iValue, b.m_iValue );
2192 }
2193
2194
2195 /////////////////////////////////////////////////////////////////////////////
2196
2197 /// string hash function
2198 struct CSphStrHashFunc
2199 {
2200 static int Hash ( const CSphString & sKey );
2201 };
2202
2203 /// small hash with string keys
2204 template < typename T >
2205 class SmallStringHash_T : public CSphOrderedHash < T, CSphString, CSphStrHashFunc, 256 > {};
2206
2207 //////////////////////////////////////////////////////////////////////////
2208
2209 /// pointer with automatic safe deletion when going out of scope
2210 template < typename T >
2211 class CSphScopedPtr : public ISphNoncopyable
2212 {
2213 public:
CSphScopedPtr(T * pPtr)2214 explicit CSphScopedPtr ( T * pPtr ) { m_pPtr = pPtr; }
~CSphScopedPtr()2215 ~CSphScopedPtr () { SafeDelete ( m_pPtr ); }
2216 T * operator -> () const { return m_pPtr; }
Ptr()2217 T * Ptr () const { return m_pPtr; }
2218 CSphScopedPtr & operator = ( T * pPtr ) { SafeDelete ( m_pPtr ); m_pPtr = pPtr; return *this; }
LeakPtr()2219 T * LeakPtr () { T * pPtr = m_pPtr; m_pPtr = NULL; return pPtr; }
Reset()2220 void Reset () { SafeDelete ( m_pPtr ); }
2221
2222 protected:
2223 T * m_pPtr;
2224 };
2225
2226 //////////////////////////////////////////////////////////////////////////
2227
2228 /// refcounted base
2229 /// WARNING, FOR SINGLE-THREADED USE ONLY
2230 struct ISphRefcounted : public ISphNoncopyable
2231 {
2232 protected:
ISphRefcountedISphRefcounted2233 ISphRefcounted () : m_iRefCount ( 1 ) {}
~ISphRefcountedISphRefcounted2234 virtual ~ISphRefcounted () {}
2235
2236 public:
AddRefISphRefcounted2237 void AddRef () const { m_iRefCount++; }
ReleaseISphRefcounted2238 void Release () const { --m_iRefCount; assert ( m_iRefCount>=0 ); if ( m_iRefCount==0 ) delete this; }
2239
2240 protected:
2241 mutable int m_iRefCount;
2242 };
2243
2244
2245 /// automatic pointer wrapper for refcounted objects
2246 /// construction from or assignment of a raw pointer takes over (!) the ownership
2247 template < typename T >
2248 class CSphRefcountedPtr
2249 {
2250 public:
CSphRefcountedPtr()2251 explicit CSphRefcountedPtr () { m_pPtr = NULL; } ///< default NULL wrapper construction (for vectors)
CSphRefcountedPtr(T * pPtr)2252 explicit CSphRefcountedPtr ( T * pPtr ) { m_pPtr = pPtr; } ///< construction from raw pointer, takes over ownership!
~CSphRefcountedPtr()2253 ~CSphRefcountedPtr () { if ( m_pPtr ) m_pPtr->Release(); }
2254
Ptr()2255 T * Ptr () const { return m_pPtr; }
2256 T * operator -> () const { return m_pPtr; }
2257 bool operator ! () const { return m_pPtr==NULL; }
2258
2259 public:
2260 /// assignment of a raw pointer, takes over ownership!
2261 CSphRefcountedPtr<T> & operator = ( T * pPtr )
2262 {
2263 if ( m_pPtr && m_pPtr!=pPtr )
2264 m_pPtr->Release();
2265 m_pPtr = pPtr;
2266 return *this;
2267 }
2268
2269 /// wrapper assignment, does automated reference tracking
2270 CSphRefcountedPtr<T> & operator = ( const CSphRefcountedPtr<T> & rhs )
2271 {
2272 if ( rhs.m_pPtr )
2273 rhs.m_pPtr->AddRef();
2274 if ( m_pPtr )
2275 m_pPtr->Release();
2276 m_pPtr = rhs.m_pPtr;
2277 return *this;
2278 }
2279
2280 protected:
2281 T * m_pPtr;
2282 };
2283
2284 //////////////////////////////////////////////////////////////////////////
2285
2286 // parent process for forked children
2287 extern bool g_bHeadProcess;
2288 void sphWarn ( const char *, ... ) __attribute__ ( ( format ( printf, 1, 2 ) ) );
2289 void SafeClose ( int & iFD );
2290
2291 /// open file for reading
2292 int sphOpenFile ( const char * sFile, CSphString & sError );
2293
2294 /// return size of file descriptor
2295 int64_t sphGetFileSize ( int iFD, CSphString & sError );
2296
2297
2298 /// buffer trait that neither own buffer nor clean-up it on destroy
2299 template < typename T >
2300 class CSphBufferTrait : public ISphNoncopyable
2301 {
2302 public:
2303 /// ctor
CSphBufferTrait()2304 CSphBufferTrait ()
2305 : m_pData ( NULL )
2306 , m_iCount ( 0 )
2307 { }
2308
2309 /// dtor
~CSphBufferTrait()2310 virtual ~CSphBufferTrait () {}
2311
2312 /// accessor
2313 inline const T & operator [] ( int64_t iIndex ) const
2314 {
2315 assert ( iIndex>=0 && iIndex<m_iCount );
2316 return m_pData[iIndex];
2317 }
2318
2319 /// get write address
GetWritePtr()2320 T * GetWritePtr () const
2321 {
2322 return m_pData;
2323 }
2324
2325 /// check if i'm empty
IsEmpty()2326 bool IsEmpty () const
2327 {
2328 return ( m_pData==NULL );
2329 }
2330
2331 /// get length in bytes
GetLengthBytes()2332 size_t GetLengthBytes () const
2333 {
2334 return sizeof(T) * (size_t)m_iCount;
2335 }
2336
2337 /// get length in entries
GetNumEntries()2338 int64_t GetNumEntries () const
2339 {
2340 return m_iCount;
2341 }
2342
Set(T * pData,int64_t iCount)2343 void Set ( T * pData, int64_t iCount )
2344 {
2345 m_pData = pData;
2346 m_iCount = iCount;
2347 }
2348
2349 protected:
2350 T * m_pData;
2351 int64_t m_iCount;
2352 };
2353
2354
2355 //////////////////////////////////////////////////////////////////////////
2356
2357 /// in-memory buffer shared between processes
2358 template < typename T >
2359 class CSphSharedBuffer : public CSphBufferTrait < T >
2360 {
2361 public:
2362 /// ctor
CSphSharedBuffer()2363 CSphSharedBuffer ()
2364 {
2365 m_bMlock = false;
2366 }
2367
2368 /// dtor
~CSphSharedBuffer()2369 virtual ~CSphSharedBuffer ()
2370 {
2371 Reset ();
2372 }
2373
2374 /// set locking mode for subsequent Alloc()s
SetMlock(bool bMlock)2375 void SetMlock ( bool bMlock )
2376 {
2377 m_bMlock = bMlock;
2378 }
2379
2380 public:
2381 /// allocate storage
2382 #if USE_WINDOWS
Alloc(int64_t iEntries,CSphString & sError,CSphString &)2383 bool Alloc ( int64_t iEntries, CSphString & sError, CSphString & )
2384 #else
2385 bool Alloc ( int64_t iEntries, CSphString & sError, CSphString & sWarning )
2386 #endif
2387 {
2388 assert ( !this->GetWritePtr() );
2389
2390 int64_t uCheck = sizeof(T);
2391 uCheck *= iEntries;
2392
2393 int64_t iLength = (size_t)uCheck;
2394 if ( uCheck!=iLength )
2395 {
2396 sError.SetSprintf ( "impossible to mmap() over 4 GB on 32-bit system" );
2397 return false;
2398 }
2399
2400 #if USE_WINDOWS
2401 T * pData = new T [ (size_t)iEntries ];
2402 #else
2403 T * pData = (T *) mmap ( NULL, iLength, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANON, -1, 0 );
2404 if ( pData==MAP_FAILED )
2405 {
2406 if ( iLength>(int64_t)0x7fffffffUL )
2407 sError.SetSprintf ( "mmap() failed: %s (length=" INT64_FMT " is over 2GB, impossible on some 32-bit systems)",
2408 strerror(errno), iLength );
2409 else
2410 sError.SetSprintf ( "mmap() failed: %s (length=" INT64_FMT ")", strerror(errno), iLength );
2411 return false;
2412 }
2413
2414 if ( m_bMlock )
2415 if ( -1==mlock ( pData, iLength ) )
2416 sWarning.SetSprintf ( "mlock() failed: %s", strerror(errno) );
2417
2418 #if SPH_ALLOCS_PROFILER
2419 sphMemStatMMapAdd ( iLength );
2420 #endif
2421
2422 #endif // USE_WINDOWS
2423
2424 assert ( pData );
2425 this->Set ( pData, iEntries );
2426 return true;
2427 }
2428
2429
2430 /// relock again (for daemonization only)
2431 #if USE_WINDOWS
Mlock(const char *,CSphString &)2432 bool Mlock ( const char *, CSphString & )
2433 {
2434 return true;
2435 }
2436 #else
Mlock(const char * sPrefix,CSphString & sError)2437 bool Mlock ( const char * sPrefix, CSphString & sError )
2438 {
2439 if ( !m_bMlock )
2440 return true;
2441
2442 if ( mlock ( this->GetWritePtr(), this->GetLengthBytes() )!=-1 )
2443 return true;
2444
2445 if ( sError.IsEmpty() )
2446 sError.SetSprintf ( "%s mlock() failed: bytes=" INT64_FMT ", error=%s", sPrefix, (int64_t)this->GetLengthBytes(), strerror(errno) );
2447 else
2448 sError.SetSprintf ( "%s; %s mlock() failed: bytes=" INT64_FMT ", error=%s", sError.cstr(), sPrefix, (int64_t)this->GetLengthBytes(), strerror(errno) );
2449 return false;
2450 }
2451 #endif
2452
2453
2454 /// deallocate storage
Reset()2455 void Reset ()
2456 {
2457 if ( !this->GetWritePtr() )
2458 return;
2459
2460 #if USE_WINDOWS
2461 delete [] this->GetWritePtr();
2462 #else
2463 int iRes = munmap ( this->GetWritePtr(), this->GetLengthBytes() );
2464 if ( iRes )
2465 sphWarn ( "munmap() failed: %s", strerror(errno) );
2466
2467 #if SPH_ALLOCS_PROFILER
2468 sphMemStatMMapDel ( this->GetLengthBytes() );
2469 #endif
2470
2471 #endif // USE_WINDOWS
2472
2473 this->Set ( NULL, 0 );
2474 }
2475
2476 public:
Swap(CSphSharedBuffer & tBuf)2477 void Swap ( CSphSharedBuffer & tBuf )
2478 {
2479 ::Swap ( this->m_pData, tBuf.m_pData );
2480 ::Swap ( this->m_iCount, tBuf.m_iCount );
2481 ::Swap ( m_bMlock, tBuf.m_bMlock );
2482 }
2483
2484 protected:
2485 bool m_bMlock; ///< whether to lock data in RAM
2486 };
2487
2488
2489 //////////////////////////////////////////////////////////////////////////
2490
2491 template < typename T >
2492 class CSphMappedBuffer : public CSphBufferTrait < T >
2493 {
2494 public:
2495 /// ctor
CSphMappedBuffer()2496 CSphMappedBuffer ()
2497 {
2498 #if USE_WINDOWS
2499 m_iFD = INVALID_HANDLE_VALUE;
2500 #else
2501 m_iFD = -1;
2502 #endif
2503 }
2504
2505 /// dtor
~CSphMappedBuffer()2506 virtual ~CSphMappedBuffer ()
2507 {
2508 Close();
2509 }
2510
Setup(const char * sFile,CSphString & sError)2511 bool Setup ( const char * sFile, CSphString & sError )
2512 {
2513 #if USE_WINDOWS
2514 assert ( m_iFD==INVALID_HANDLE_VALUE );
2515 #else
2516 assert ( m_iFD==-1 );
2517 #endif
2518 assert ( !this->GetWritePtr() && !this->GetNumEntries() );
2519
2520 T * pData = NULL;
2521 int64_t iCount = 0;
2522
2523 #if USE_WINDOWS
2524 HANDLE iFD = CreateFile ( sFile, GENERIC_READ, FILE_SHARE_READ, 0, OPEN_EXISTING, FILE_ATTRIBUTE_READONLY, 0 );
2525 if ( iFD==INVALID_HANDLE_VALUE )
2526 {
2527 sError.SetSprintf ( "failed to open file '%s' (errno %d)", sFile, ::GetLastError() );
2528 return false;
2529 }
2530 m_iFD = iFD;
2531
2532 LARGE_INTEGER tLen;
2533 if ( GetFileSizeEx ( iFD, &tLen )==0 )
2534 {
2535 sError.SetSprintf ( "failed to fstat file '%s' (errno %d)", sFile, ::GetLastError() );
2536 Close();
2537 return false;
2538 }
2539
2540 // FIXME!!! report abount tail, ie m_iLen*sizeof(T)!=tLen.QuadPart
2541 iCount = tLen.QuadPart / sizeof(T);
2542
2543 // mmap fails to map zero-size file
2544 if ( tLen.QuadPart>0 )
2545 {
2546 HANDLE hFile = ::CreateFileMapping ( iFD, NULL, PAGE_READONLY, 0, 0, NULL );
2547 pData = (T *)::MapViewOfFile ( hFile, FILE_MAP_READ, 0, 0, 0 );
2548 if ( !pData )
2549 {
2550 sError.SetSprintf ( "failed to map file '%s': (errno %d, length=" INT64_FMT ")", sFile, ::GetLastError(), (int64_t)tLen.QuadPart );
2551 Close();
2552 return false;
2553 }
2554 }
2555 #else
2556
2557 int iFD = sphOpenFile ( sFile, sError );
2558 if ( iFD<0 )
2559 return false;
2560 m_iFD = iFD;
2561
2562 int64_t iFileSize = sphGetFileSize ( iFD, sError );
2563 if ( iFileSize<0 )
2564 return false;
2565
2566 // FIXME!!! report abount tail, ie m_iLen*sizeof(T)!=st.st_size
2567 iCount = iFileSize / sizeof(T);
2568
2569 // mmap fails to map zero-size file
2570 if ( iFileSize>0 )
2571 {
2572 pData = (T *)mmap ( NULL, iFileSize, PROT_READ, MAP_PRIVATE, iFD, 0 );
2573 if ( pData==MAP_FAILED )
2574 {
2575 sError.SetSprintf ( "failed to mmap file '%s': %s (length=" INT64_FMT ")", sFile, strerror(errno), iFileSize );
2576 Close();
2577 return false;
2578 }
2579 }
2580 #endif
2581
2582 this->Set ( pData, iCount );
2583 return true;
2584 }
2585
Close()2586 void Close ()
2587 {
2588 #if USE_WINDOWS
2589 if ( this->GetWritePtr() )
2590 ::UnmapViewOfFile ( this->GetWritePtr() );
2591
2592 if ( m_iFD!=INVALID_HANDLE_VALUE )
2593 ::CloseHandle ( m_iFD );
2594
2595 m_iFD = INVALID_HANDLE_VALUE;
2596 #else
2597 if ( this->GetWritePtr() )
2598 ::munmap ( this->GetWritePtr(), this->GetLengthBytes() );
2599
2600 SafeClose ( m_iFD );
2601 #endif
2602
2603 this->Set ( NULL, 0 );
2604 }
2605
2606 private:
2607 #if USE_WINDOWS
2608 HANDLE m_iFD;
2609 #else
2610 int m_iFD;
2611 #endif
2612 };
2613
2614
2615 //////////////////////////////////////////////////////////////////////////
2616
2617 extern int g_iThreadStackSize;
2618
2619 /// my thread handle and thread func magic
2620 #if USE_WINDOWS
2621 typedef HANDLE SphThread_t;
2622 typedef DWORD SphThreadKey_t;
2623 #else
2624 typedef pthread_t SphThread_t;
2625 typedef pthread_key_t SphThreadKey_t;
2626 #endif
2627
2628 /// my threading initialize routine
2629 void * sphThreadInit ( bool bDetached=false );
2630
2631 /// my threading deinitialize routine
2632 void sphThreadDone ( int iFD );
2633
2634 /// my create thread wrapper
2635 bool sphThreadCreate ( SphThread_t * pThread, void (*fnThread)(void*), void * pArg, bool bDetached=false );
2636
2637 /// my join thread wrapper
2638 bool sphThreadJoin ( SphThread_t * pThread );
2639
2640 /// add (cleanup) callback to run on thread exit
2641 void sphThreadOnExit ( void (*fnCleanup)(void*), void * pArg );
2642
2643 /// alloc thread-local key
2644 bool sphThreadKeyCreate ( SphThreadKey_t * pKey );
2645
2646 /// free thread-local key
2647 void sphThreadKeyDelete ( SphThreadKey_t tKey );
2648
2649 /// get thread-local key value
2650 void * sphThreadGet ( SphThreadKey_t tKey );
2651
2652 /// get the pointer to my thread's stack
2653 void * sphMyStack ();
2654
2655 /// get size of used stack
2656 int64_t sphGetStackUsed();
2657
2658 /// set the size of my thread's stack
2659 void sphSetMyStackSize ( int iStackSize );
2660
2661 /// store the address in the TLS
2662 void MemorizeStack ( void* PStack );
2663
2664 /// set thread-local key value
2665 bool sphThreadSet ( SphThreadKey_t tKey, void * pValue );
2666
2667 #if !USE_WINDOWS
2668 /// what kind of threading lib do we have? The number of frames in the stack depends from it
2669 bool sphIsLtLib();
2670 #endif
2671
2672 //////////////////////////////////////////////////////////////////////////
2673
2674 /// mutex implementation
2675 class CSphMutex
2676 {
2677 public:
CSphMutex()2678 CSphMutex () : m_bInitialized ( false ) {}
~CSphMutex()2679 ~CSphMutex () { assert ( !m_bInitialized ); }
2680
2681 bool Init ();
2682 bool Done ();
2683 bool Lock ();
2684 bool Unlock ();
2685
2686 protected:
2687 bool m_bInitialized;
2688 #if USE_WINDOWS
2689 HANDLE m_hMutex;
2690 #else
2691 pthread_mutex_t m_tMutex;
2692 public:
GetInternalMutex()2693 inline pthread_mutex_t* GetInternalMutex()
2694 {
2695 return &m_tMutex;
2696 }
2697 #endif
2698 };
2699
2700 // event implementation
2701 class CSphAutoEvent
2702 {
2703 public:
CSphAutoEvent()2704 CSphAutoEvent () {}
~CSphAutoEvent()2705 ~CSphAutoEvent() {}
2706
2707 bool Init ( CSphMutex * pMutex );
2708 bool Done();
2709 void SetEvent();
2710 bool WaitEvent();
2711
2712 protected:
2713 bool m_bInitialized;
2714 bool m_bSent;
2715 #if USE_WINDOWS
2716 HANDLE m_hEvent;
2717 #else
2718 pthread_cond_t m_tCond;
2719 pthread_mutex_t* m_pMutex;
2720 #endif
2721 };
2722
2723
2724 /// static mutex (for globals)
2725 class CSphStaticMutex : private CSphMutex
2726 {
2727 public:
CSphStaticMutex()2728 CSphStaticMutex()
2729 {
2730 Verify ( Init() );
2731 }
2732
~CSphStaticMutex()2733 ~CSphStaticMutex()
2734 {
2735 Done();
2736 }
2737
Lock()2738 bool Lock ()
2739 {
2740 return CSphMutex::Lock();
2741 }
2742
Unlock()2743 bool Unlock ()
2744 {
2745 return CSphMutex::Unlock();
2746 }
2747 };
2748
2749
2750 /// scoped mutex lock
2751 template < typename T >
2752 class CSphScopedLock : ISphNoncopyable
2753 {
2754 public:
2755 /// lock on creation
CSphScopedLock(T & tMutex)2756 explicit CSphScopedLock ( T & tMutex )
2757 : m_tMutexRef ( tMutex )
2758 {
2759 m_tMutexRef.Lock();
2760 }
2761
2762 /// unlock on going out of scope
~CSphScopedLock()2763 ~CSphScopedLock ()
2764 {
2765 m_tMutexRef.Unlock ();
2766 }
2767
2768 protected:
2769 T & m_tMutexRef;
2770 };
2771
2772
2773 /// scoped locked shared variable
2774 template < typename LOCK >
2775 class CSphScopedLockedShare : public CSphScopedLock<LOCK>
2776 {
2777 public:
2778 /// lock on creation
CSphScopedLockedShare(LOCK & tMutex)2779 explicit CSphScopedLockedShare ( LOCK & tMutex )
2780 : CSphScopedLock<LOCK> ( tMutex )
2781 {}
2782
2783 template <typename T>
SharedValue()2784 inline T& SharedValue()
2785 {
2786 return *(T*)( this->m_tMutexRef.GetSharedData() );
2787 }
2788 };
2789
2790
2791 /// rwlock implementation
2792 class CSphRwlock : public ISphNoncopyable
2793 {
2794 public:
2795 CSphRwlock ();
~CSphRwlock()2796 ~CSphRwlock () {}
2797
2798 bool Init ( bool bProcessShared = false );
2799 bool Done ();
2800
2801 const char * GetError () const;
2802
2803 bool ReadLock ();
2804 bool WriteLock ();
2805 bool Unlock ();
2806
2807 private:
2808 bool m_bInitialized;
2809 CSphString m_sError;
2810 #if USE_WINDOWS
2811 HANDLE m_hWriteMutex;
2812 HANDLE m_hReadEvent;
2813 LONG m_iReaders;
2814 #else
2815 pthread_rwlock_t m_tLock;
2816 #endif
2817 };
2818
2819
2820 /// scoped RW lock
2821 class CSphScopedRWLock : ISphNoncopyable
2822 {
2823 public:
2824 /// lock on creation
CSphScopedRWLock(CSphRwlock & tLock,bool bRead)2825 CSphScopedRWLock ( CSphRwlock & tLock, bool bRead )
2826 : m_tLock ( tLock )
2827 {
2828 if ( bRead )
2829 m_tLock.ReadLock();
2830 else
2831 m_tLock.WriteLock();
2832 }
2833
2834 /// unlock on going out of scope
~CSphScopedRWLock()2835 ~CSphScopedRWLock ()
2836 {
2837 m_tLock.Unlock ();
2838 }
2839
2840 protected:
2841 CSphRwlock & m_tLock;
2842 };
2843
2844
2845 /// process-shared mutex that survives fork
2846 class CSphProcessSharedMutex
2847 {
2848 public:
2849 explicit CSphProcessSharedMutex ( int iExtraSize=0 );
2850 ~CSphProcessSharedMutex(); // not virtual for now.
2851 void Lock ();
2852 void Unlock ();
2853 bool TimedLock ( int tmSpin ) const; // wait at least tmSpin microseconds the lock will available
2854 const char * GetError () const;
2855 BYTE * GetSharedData() const;
2856
2857 protected:
2858 #if !USE_WINDOWS
2859 CSphSharedBuffer<BYTE> m_pStorage;
2860 #ifdef __FreeBSD__
2861 sem_t * m_pMutex;
2862 #else
2863 pthread_mutex_t * m_pMutex;
2864 #endif
2865 CSphString m_sError;
2866 #else
2867 CSphMutex m_tLock;
2868 #endif
2869 };
2870
2871 #if !USE_WINDOWS
2872 /// process-shared mutex variable that survives fork
2873 template < typename T > class CSphProcessSharedVariable : protected CSphProcessSharedMutex, public ISphNoncopyable
2874 {
2875 public:
2876
CSphProcessSharedVariable(const T & tInitValue)2877 explicit CSphProcessSharedVariable ( const T& tInitValue )
2878 : CSphProcessSharedMutex ( sizeof(T) )
2879 , m_pValue ( NULL )
2880 {
2881 if ( m_pMutex )
2882 {
2883 m_pValue = reinterpret_cast<T*> ( GetSharedData() );
2884 *m_pValue = tInitValue;
2885 }
2886 }
ReadValue()2887 T ReadValue()
2888 {
2889 if ( !m_pValue )
2890 return 0;
2891 Lock();
2892 T val = *m_pValue;
2893 Unlock();
2894 return val;
2895 }
WriteValue(const T & tNewValue)2896 void WriteValue ( const T& tNewValue )
2897 {
2898 if ( !m_pValue )
2899 return;
2900 Lock();
2901 *m_pValue = tNewValue;
2902 Unlock();
2903 }
2904
2905 protected:
2906 T * m_pValue;
2907 };
2908 #endif // #if !USE_WINDOWS
2909
2910
2911 #if USE_WINDOWS
2912 #pragma warning(push,1)
2913 #pragma warning(disable:4701)
2914 #endif
2915
2916 #if USE_WINDOWS
2917 #pragma warning(pop)
2918 #endif
2919
2920 //////////////////////////////////////////////////////////////////////////
2921
2922 /// generic dynamic bitvector
2923 /// with a preallocated part for small-size cases, and a dynamic route for big-size ones
2924 class CSphBitvec
2925 {
2926 protected:
2927 DWORD * m_pData;
2928 DWORD m_uStatic[4];
2929 int m_iElements;
2930
2931 public:
CSphBitvec()2932 CSphBitvec ()
2933 : m_pData ( NULL )
2934 , m_iElements ( 0 )
2935 {}
2936
CSphBitvec(int iElements)2937 explicit CSphBitvec ( int iElements )
2938 {
2939 Init ( iElements );
2940 }
2941
~CSphBitvec()2942 ~CSphBitvec ()
2943 {
2944 if ( m_pData!=m_uStatic )
2945 SafeDeleteArray ( m_pData );
2946 }
2947
2948 // huh, no copy ctor and operator= ?
2949
Init(int iElements)2950 void Init ( int iElements )
2951 {
2952 assert ( iElements>=0 );
2953 m_iElements = iElements;
2954 if ( iElements > int(sizeof(m_uStatic)*8) )
2955 {
2956 int iSize = GetSize();
2957 m_pData = new DWORD [ iSize ];
2958 } else
2959 {
2960 m_pData = m_uStatic;
2961 }
2962 Clear();
2963 }
2964
Clear()2965 void Clear ()
2966 {
2967 int iSize = GetSize();
2968 memset ( m_pData, 0, sizeof(DWORD)*iSize );
2969 }
2970
BitGet(int iIndex)2971 bool BitGet ( int iIndex ) const
2972 {
2973 assert ( m_pData );
2974 assert ( iIndex>=0 );
2975 assert ( iIndex<m_iElements );
2976 return ( m_pData [ iIndex>>5 ] & ( 1UL<<( iIndex&31 ) ) )!=0; // NOLINT
2977 }
2978
BitSet(int iIndex)2979 void BitSet ( int iIndex )
2980 {
2981 assert ( iIndex>=0 );
2982 assert ( iIndex<m_iElements );
2983 m_pData [ iIndex>>5 ] |= ( 1UL<<( iIndex&31 ) ); // NOLINT
2984 }
2985
BitClear(int iIndex)2986 void BitClear ( int iIndex )
2987 {
2988 assert ( iIndex>=0 );
2989 assert ( iIndex<m_iElements );
2990 m_pData [ iIndex>>5 ] &= ~( 1UL<<( iIndex&31 ) ); // NOLINT
2991 }
2992
Begin()2993 const DWORD * Begin () const
2994 {
2995 return m_pData;
2996 }
2997
Begin()2998 DWORD * Begin ()
2999 {
3000 return m_pData;
3001 }
3002
GetSize()3003 int GetSize() const
3004 {
3005 return (m_iElements+31)/32;
3006 }
3007
GetBits()3008 int GetBits() const
3009 {
3010 return m_iElements;
3011 }
3012
BitCount()3013 int BitCount () const
3014 {
3015 int iBitSet = 0;
3016 for ( int i=0; i<GetSize(); i++ )
3017 iBitSet += sphBitCount ( m_pData[i] );
3018
3019 return iBitSet;
3020 }
3021 };
3022
3023 //////////////////////////////////////////////////////////////////////////
3024
3025 #if USE_WINDOWS
3026 #define DISABLE_CONST_COND_CHECK \
3027 __pragma ( warning ( push ) ) \
3028 __pragma ( warning ( disable:4127 ) )
3029 #define ENABLE_CONST_COND_CHECK \
3030 __pragma ( warning ( pop ) )
3031 #else
3032 #define DISABLE_CONST_COND_CHECK
3033 #define ENABLE_CONST_COND_CHECK
3034 #endif
3035
3036 #define if_const(_arg) \
3037 DISABLE_CONST_COND_CHECK \
3038 if ( _arg ) \
3039 ENABLE_CONST_COND_CHECK
3040
3041 //////////////////////////////////////////////////////////////////////////
3042 // interlocked (atomic) operation
3043
3044 #if (USE_WINDOWS) || (HAVE_SYNC_FETCH)
3045 #define NO_ATOMIC 0
3046 #else
3047 #define NO_ATOMIC 1
3048 #endif
3049
3050 template < typename INT >
3051 class CSphAtomic : public ISphNoncopyable
3052 {
3053 volatile INT m_iValue;
3054 #if NO_ATOMIC
3055 CSphMutex m_tLock;
3056 #endif
3057
3058 public:
3059 CSphAtomic ( INT iValue=0 )
m_iValue(iValue)3060 : m_iValue ( iValue )
3061 {
3062 #if NO_ATOMIC
3063 m_tLock.Init();
3064 #endif
3065 }
3066
~CSphAtomic()3067 ~CSphAtomic ()
3068 {
3069 #if NO_ATOMIC
3070 m_tLock.Done();
3071 #endif
3072 }
3073
3074 #ifdef HAVE_SYNC_FETCH
INT()3075 operator INT()
3076 {
3077 return __sync_fetch_and_add ( &m_iValue, 0 );
3078 }
3079
3080 // return value here is original value, prior to operation took place
Inc()3081 inline INT Inc()
3082 {
3083 return __sync_fetch_and_add ( &m_iValue, 1 );
3084 }
Dec()3085 inline INT Dec()
3086 {
3087 return __sync_fetch_and_sub ( &m_iValue, 1 );
3088 }
3089 #elif USE_WINDOWS
3090 operator INT();
3091 INT Inc();
3092 INT Dec();
3093 #endif
3094
3095 #if NO_ATOMIC
INT()3096 operator INT()
3097 {
3098 CSphScopedLock<CSphMutex> tLock ( m_tLock );
3099 return m_iValue;
3100 }
Inc()3101 inline INT Inc()
3102 {
3103 CSphScopedLock<CSphMutex> tLock ( m_tLock );
3104 return m_iValue++;
3105 }
Dec()3106 inline INT Dec()
3107 {
3108 CSphScopedLock<CSphMutex> tLock ( m_tLock );
3109 return m_iValue--;
3110 }
3111 #endif
3112 };
3113
3114
3115
3116 /// MT-aware refcounted base (might be a mutex protected and slow)
3117 struct ISphRefcountedMT : public ISphNoncopyable
3118 {
3119 protected:
ISphRefcountedMTISphRefcountedMT3120 ISphRefcountedMT ()
3121 : m_iRefCount ( 1 )
3122 {}
3123
~ISphRefcountedMTISphRefcountedMT3124 virtual ~ISphRefcountedMT ()
3125 {}
3126
3127 public:
AddRefISphRefcountedMT3128 void AddRef () const
3129 {
3130 m_iRefCount.Inc();
3131 }
3132
ReleaseISphRefcountedMT3133 void Release () const
3134 {
3135 long uRefs = m_iRefCount.Dec();
3136 assert ( uRefs>=1 );
3137 if ( uRefs==1 )
3138 delete this;
3139 }
3140
3141 protected:
3142 mutable CSphAtomic<long> m_iRefCount;
3143 };
3144
3145
3146
3147 #endif // _sphinxstd_
3148
3149 //
3150 // $Id$
3151 //
3152