1 //
2 // $Id: sphinxstd.h 4113 2013-08-26 07:43:28Z deogar $
3 //
4
5 //
6 // Copyright (c) 2001-2013, Andrew Aksyonoff
7 // Copyright (c) 2008-2013, 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>=1000) && !defined(__midl) && defined(_PREFAST_)
25 typedef int __declspec("SAL_nokernel") __declspec("SAL_nodriver") __prefast_flag_kernel_driver_mode;
26 #endif
27
28 #if defined(_MSC_VER) && (_MSC_VER<1400)
29 #define vsnprintf _vsnprintf
30 #endif
31
32 #ifndef __GNUC__
33 #define __attribute__(x)
34 #endif
35
36 #if HAVE_CONFIG_H
37 #include "config.h"
38 #endif
39
40 #include <string.h>
41 #include <stdlib.h>
42 #include <stdio.h>
43 #include <assert.h>
44 #include <ctype.h>
45 #include <stdarg.h>
46
47 // for 64-bit types
48 #if HAVE_STDINT_H
49 #include <stdint.h>
50 #endif
51
52 #if HAVE_INTTYPES_H
53 #define __STDC_FORMAT_MACROS
54 #include <inttypes.h>
55 #endif
56
57 #if HAVE_SYS_TYPES_H
58 #include <sys/types.h>
59 #endif
60
61 #if !USE_WINDOWS
62 #include <sys/mman.h>
63 #include <errno.h>
64 #include <pthread.h>
65 #ifdef __FreeBSD__
66 #include <semaphore.h>
67 #endif
68 #endif
69
70 /////////////////////////////////////////////////////////////////////////////
71 // COMPILE-TIME CHECKS
72 /////////////////////////////////////////////////////////////////////////////
73
74 #define STATIC_ASSERT(_cond,_name) typedef char STATIC_ASSERT_FAILED_ ## _name [ (_cond) ? 1 : -1 ]
75 #define STATIC_SIZE_ASSERT(_type,_size) STATIC_ASSERT ( sizeof(_type)==_size, _type ## _MUST_BE_ ## _size ## _BYTES )
76
77
78 #ifndef __analysis_assume
79 #define __analysis_assume(_arg)
80 #endif
81
82 /////////////////////////////////////////////////////////////////////////////
83 // PORTABILITY
84 /////////////////////////////////////////////////////////////////////////////
85
86 #if _WIN32
87
88 #define WIN32_LEAN_AND_MEAN
89 #include <windows.h>
90
91 #define strcasecmp strcmpi
92 #define strncasecmp _strnicmp
93 #define snprintf _snprintf
94 #define strtoll _strtoi64
95 #define strtoull _strtoui64
96
97 #else
98
99 #if USE_ODBC
100 // UnixODBC compatible DWORD
101 #if defined(__alpha) || defined(__sparcv9) || defined(__LP64__) || (defined(__HOS_AIX__) && defined(_LP64)) || defined(__APPLE__)
102 typedef unsigned int DWORD;
103 #else
104 typedef unsigned long DWORD;
105 #endif
106 #else
107 // default DWORD
108 typedef unsigned int DWORD;
109 #endif // USE_ODBC
110
111 typedef unsigned short WORD;
112 typedef unsigned char BYTE;
113
114 #endif // _WIN32
115
116 /////////////////////////////////////////////////////////////////////////////
117 // 64-BIT INTEGER TYPES AND MACROS
118 /////////////////////////////////////////////////////////////////////////////
119
120 #if defined(U64C) || defined(I64C)
121 #error "Internal 64-bit integer macros already defined."
122 #endif
123
124 #if !HAVE_STDINT_H
125
126 #if defined(_MSC_VER)
127 typedef __int64 int64_t;
128 typedef unsigned __int64 uint64_t;
129 #define U64C(v) v ## UI64
130 #define I64C(v) v ## I64
131 #define PRIu64 "I64d"
132 #define PRIi64 "I64d"
133 #else // !defined(_MSC_VER)
134 typedef long long int64_t;
135 typedef unsigned long long uint64_t;
136 #endif // !defined(_MSC_VER)
137
138 #endif // no stdint.h
139
140 // if platform-specific macros were not supplied, use common defaults
141 #ifndef U64C
142 #define U64C(v) v ## ULL
143 #endif
144
145 #ifndef I64C
146 #define I64C(v) v ## LL
147 #endif
148
149 #ifndef PRIu64
150 #define PRIu64 "llu"
151 #endif
152
153 #ifndef PRIi64
154 #define PRIi64 "lld"
155 #endif
156
157 #define UINT64_FMT "%" PRIu64
158 #define INT64_FMT "%" PRIi64
159
160 #ifndef UINT64_MAX
161 #define UINT64_MAX U64C(0xffffffffffffffff)
162 #endif
163
164 #ifndef INT64_MAX
165 #define INT64_MAX I64C(0x7fffffffffffffff)
166 #endif
167
168 STATIC_SIZE_ASSERT ( uint64_t, 8 );
169 STATIC_SIZE_ASSERT ( int64_t, 8 );
170
171 /////////////////////////////////////////////////////////////////////////////
172 // MEMORY MANAGEMENT
173 /////////////////////////////////////////////////////////////////////////////
174
175 #define SPH_DEBUG_LEAKS 0
176 #define SPH_ALLOCS_PROFILER 0
177
178 #if SPH_DEBUG_LEAKS || SPH_ALLOCS_PROFILER
179
180 /// debug new that tracks memory leaks
181 void * operator new ( size_t iSize, const char * sFile, int iLine );
182
183 /// debug new that tracks memory leaks
184 void * operator new [] ( size_t iSize, const char * sFile, int iLine );
185
186 /// get current allocs count
187 int sphAllocsCount ();
188
189 /// total allocated bytes
190 int64_t sphAllocBytes ();
191
192 /// get last alloc id
193 int sphAllocsLastID ();
194
195 /// dump all allocs since given id
196 void sphAllocsDump ( int iFile, int iSinceID );
197
198 /// dump stats to stdout
199 void sphAllocsStats ();
200
201 /// check all existing allocs; raises assertion failure in cases of errors
202 void sphAllocsCheck ();
203
204 void sphMemStatDump ( int iFD );
205
206 void sphMemStatMMapAdd ( int64_t iSize );
207 void sphMemStatMMapDel ( int64_t iSize );
208
209 #undef new
210 #define new new(__FILE__,__LINE__)
211
212 /// delete for my new
213 void operator delete ( void * pPtr );
214
215 /// delete for my new
216 void operator delete [] ( void * pPtr );
217
218 #endif // SPH_DEBUG_LEAKS || SPH_ALLOCS_PROFILER
219
220 /////////////////////////////////////////////////////////////////////////////
221 // HELPERS
222 /////////////////////////////////////////////////////////////////////////////
223
sphBitCount(DWORD n)224 inline int sphBitCount ( DWORD n )
225 {
226 // MIT HACKMEM count
227 // works for 32-bit numbers only
228 // fix last line for 64-bit numbers
229 register DWORD tmp;
230 tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
231 return ( (tmp + (tmp >> 3) ) & 030707070707) % 63;
232 }
233
234 typedef bool ( *SphDieCallback_t ) ( const char * );
235
236 /// crash with an error message
237 void sphDie ( const char * sMessage, ... ) __attribute__ ( ( format ( printf, 1, 2 ) ) );
238
239 /// setup a callback function to call from sphDie() before exit
240 /// if callback returns false, sphDie() will not log to stdout
241 void sphSetDieCallback ( SphDieCallback_t pfDieCallback );
242
243 /// how much bits do we need for given int
sphLog2(uint64_t iValue)244 inline int sphLog2 ( uint64_t iValue )
245 {
246 int iBits = 0;
247 while ( iValue )
248 {
249 iValue >>= 1;
250 iBits++;
251 }
252 return iBits;
253 }
254
255 /// float vs dword conversion
sphF2DW(float f)256 inline DWORD sphF2DW ( float f ) { union { float f; DWORD d; } u; u.f = f; return u.d; }
257
258 /// dword vs float conversion
sphDW2F(DWORD d)259 inline float sphDW2F ( DWORD d ) { union { float f; DWORD d; } u; u.d = d; return u.f; }
260
261 //////////////////////////////////////////////////////////////////////////
262 // RANDOM NUMBERS GENERATOR
263 //////////////////////////////////////////////////////////////////////////
264
265 /// seed RNG
266 void sphSrand ( DWORD uSeed );
267
268 /// auto-seed RNG based on time and PID
269 void sphAutoSrand ();
270
271 /// generate another random
272 DWORD sphRand ();
273
274 /////////////////////////////////////////////////////////////////////////////
275 // DEBUGGING
276 /////////////////////////////////////////////////////////////////////////////
277
278 #if USE_WINDOWS
279 #ifndef NDEBUG
280
281 void sphAssert ( const char * sExpr, const char * sFile, int iLine );
282
283 #undef assert
284 #define assert(_expr) (void)( (_expr) || ( sphAssert ( #_expr, __FILE__, __LINE__ ), 0 ) )
285
286 #endif // !NDEBUG
287 #endif // USE_WINDOWS
288
289
290 #ifndef NDEBUG
291 #define Verify(_expr) assert(_expr)
292 #else
293 #define Verify(_expr) _expr
294 #endif
295
296 /////////////////////////////////////////////////////////////////////////////
297 // GENERICS
298 /////////////////////////////////////////////////////////////////////////////
299
300 #define Min(a,b) ((a)<(b)?(a):(b))
301 #define Max(a,b) ((a)>(b)?(a):(b))
302 #define SafeDelete(_x) { if (_x) { delete (_x); (_x) = NULL; } }
303 #define SafeDeleteArray(_x) { if (_x) { delete [] (_x); (_x) = NULL; } }
304 #define SafeRelease(_x) { if (_x) { (_x)->Release(); (_x) = NULL; } }
305
306 /// swap
Swap(T & v1,T & v2)307 template < typename T > inline void Swap ( T & v1, T & v2 )
308 {
309 T temp = v1;
310 v1 = v2;
311 v2 = temp;
312 }
313
314 /// prevent copy
315 class ISphNoncopyable
316 {
317 public:
ISphNoncopyable()318 ISphNoncopyable () {}
319
320 private:
ISphNoncopyable(const ISphNoncopyable &)321 ISphNoncopyable ( const ISphNoncopyable & ) {}
322 const ISphNoncopyable & operator = ( const ISphNoncopyable & ) { return *this; }
323 };
324
325 //////////////////////////////////////////////////////////////////////////////
326
327 /// generic comparator
328 template < typename T >
329 struct SphLess_T
330 {
IsLessSphLess_T331 inline bool IsLess ( const T & a, const T & b ) const
332 {
333 return a < b;
334 }
335 };
336
337
338 /// generic comparator
339 template < typename T >
340 struct SphGreater_T
341 {
IsLessSphGreater_T342 inline bool IsLess ( const T & a, const T & b ) const
343 {
344 return b < a;
345 }
346 };
347
348
349 /// generic comparator
350 template < typename T, typename C >
351 struct SphMemberLess_T
352 {
353 const T C::* m_pMember;
354
SphMemberLess_TSphMemberLess_T355 explicit SphMemberLess_T ( T C::* pMember )
356 : m_pMember ( pMember )
357 {}
358
IsLessSphMemberLess_T359 inline bool IsLess ( const C & a, const C & b ) const
360 {
361 return ( (&a)->*m_pMember ) < ( (&b)->*m_pMember );
362 }
363 };
364
365 template < typename T, typename C >
366 inline SphMemberLess_T<T,C>
sphMemberLess(T C::* pMember)367 sphMemberLess ( T C::* pMember )
368 {
369 return SphMemberLess_T<T,C> ( pMember );
370 }
371
372
373 /// generic accessor
374 template < typename T >
375 struct SphAccessor_T
376 {
377 typedef T MEDIAN_TYPE;
378
KeySphAccessor_T379 MEDIAN_TYPE & Key ( T * a ) const
380 {
381 return *a;
382 }
383
CopyKeySphAccessor_T384 void CopyKey ( MEDIAN_TYPE * pMed, T * pVal ) const
385 {
386 *pMed = Key(pVal);
387 }
388
SwapSphAccessor_T389 void Swap ( T * a, T * b ) const
390 {
391 ::Swap ( *a, *b );
392 }
393
AddSphAccessor_T394 T * Add ( T * p, int i ) const
395 {
396 return p+i;
397 }
398
SubSphAccessor_T399 int Sub ( T * b, T * a ) const
400 {
401 return (int)(b-a);
402 }
403 };
404
405
406 /// heap sort helper
407 template < typename T, typename U, typename V >
sphSiftDown(T * pData,int iStart,int iEnd,U COMP,V ACC)408 void sphSiftDown ( T * pData, int iStart, int iEnd, U COMP, V ACC )
409 {
410 for ( ;; )
411 {
412 int iChild = iStart*2+1;
413 if ( iChild>iEnd )
414 break;
415
416 int iChild1 = iChild+1;
417 if ( iChild1<=iEnd && COMP.IsLess ( ACC.Key ( ACC.Add ( pData, iChild ) ), ACC.Key ( ACC.Add ( pData, iChild1 ) ) ) )
418 iChild = iChild1;
419
420 if ( COMP.IsLess ( ACC.Key ( ACC.Add ( pData, iChild ) ), ACC.Key ( ACC.Add ( pData, iStart ) ) ) )
421 return;
422 ACC.Swap ( ACC.Add ( pData, iChild ), ACC.Add ( pData, iStart ) );
423 iStart = iChild;
424 }
425 }
426
427
428 /// heap sort
429 template < typename T, typename U, typename V >
sphHeapSort(T * pData,int iCount,U COMP,V ACC)430 void sphHeapSort ( T * pData, int iCount, U COMP, V ACC )
431 {
432 if ( !pData || iCount<=1 )
433 return;
434
435 // build a max-heap, so that the largest element is root
436 for ( int iStart=( iCount-2 )>>1; iStart>=0; iStart-- )
437 sphSiftDown ( pData, iStart, iCount-1, COMP, ACC );
438
439 // now keep popping root into the end of array
440 for ( int iEnd=iCount-1; iEnd>0; )
441 {
442 ACC.Swap ( pData, ACC.Add ( pData, iEnd ) );
443 sphSiftDown ( pData, 0, --iEnd, COMP, ACC );
444 }
445 }
446
447
448 /// generic sort
449 template < typename T, typename U, typename V >
sphSort(T * pData,int iCount,U COMP,V ACC)450 void sphSort ( T * pData, int iCount, U COMP, V ACC )
451 {
452 if ( iCount<2 )
453 return;
454
455 typedef T * P;
456 P st0[32], st1[32], a, b, i, j;
457 typename V::MEDIAN_TYPE x;
458 int k;
459
460 const int SMALL_THRESH = 32;
461 int iDepthLimit = sphLog2 ( iCount );
462 iDepthLimit = ( ( iDepthLimit<<2 ) + iDepthLimit ) >> 1; // x2.5
463
464 k = 1;
465 st0[0] = pData;
466 st1[0] = ACC.Add ( pData, iCount-1 );
467 while ( k )
468 {
469 k--;
470 i = a = st0[k];
471 j = b = st1[k];
472
473 // if quicksort fails on this data; switch to heapsort
474 if ( !k )
475 {
476 if ( !--iDepthLimit )
477 {
478 sphHeapSort ( a, ACC.Sub ( b, a )+1, COMP, ACC );
479 return;
480 }
481 }
482
483 // for tiny arrays, switch to insertion sort
484 int iLen = ACC.Sub ( b, a );
485 if ( iLen<=SMALL_THRESH )
486 {
487 for ( i=ACC.Add ( a, 1 ); i<=b; i=ACC.Add ( i, 1 ) )
488 {
489 for ( j=i; j>a; )
490 {
491 P j1 = ACC.Add ( j, -1 );
492 if ( COMP.IsLess ( ACC.Key(j1), ACC.Key(j) ) )
493 break;
494 ACC.Swap ( j, j1 );
495 j = j1;
496 }
497 }
498 continue;
499 }
500
501 ACC.CopyKey ( &x, ACC.Add ( a, iLen/2 ) );
502 while ( a<b )
503 {
504 while ( i<=j )
505 {
506 while ( COMP.IsLess ( ACC.Key(i), x ) )
507 i = ACC.Add ( i, 1 );
508 while ( COMP.IsLess ( x, ACC.Key(j) ) )
509 j = ACC.Add ( j, -1 );
510 if ( i<=j )
511 {
512 ACC.Swap ( i, j );
513 i = ACC.Add ( i, 1 );
514 j = ACC.Add ( j, -1 );
515 }
516 }
517
518 if ( ACC.Sub ( j, a )>=ACC.Sub ( b, i ) )
519 {
520 if ( a<j ) { st0[k] = a; st1[k] = j; k++; }
521 a = i;
522 } else
523 {
524 if ( i<b ) { st0[k] = i; st1[k] = b; k++; }
525 b = j;
526 }
527 }
528 }
529 }
530
531
532 template < typename T, typename U >
sphSort(T * pData,int iCount,U COMP)533 void sphSort ( T * pData, int iCount, U COMP )
534 {
535 sphSort ( pData, iCount, COMP, SphAccessor_T<T>() );
536 }
537
538
539 template < typename T >
sphSort(T * pData,int iCount)540 void sphSort ( T * pData, int iCount )
541 {
542 sphSort ( pData, iCount, SphLess_T<T>() );
543 }
544
545 //////////////////////////////////////////////////////////////////////////
546
547 /// member functor, wraps object member access
548 template < typename T, typename CLASS >
549 struct SphMemberFunctor_T
550 {
551 const T CLASS::* m_pMember;
552
SphMemberFunctor_TSphMemberFunctor_T553 explicit SphMemberFunctor_T ( T CLASS::* pMember ) : m_pMember ( pMember ) {}
operatorSphMemberFunctor_T554 const T & operator () ( const CLASS & arg ) const { return (&arg)->*m_pMember; }
555
IsLessSphMemberFunctor_T556 inline bool IsLess ( const CLASS & a, const CLASS & b ) const
557 {
558 return (&a)->*m_pMember < (&b)->*m_pMember;
559 }
560 };
561
562
563 /// handy member functor generator
564 template < typename T, typename CLASS >
565 inline SphMemberFunctor_T < T, CLASS >
bind(T CLASS::* ptr)566 bind ( T CLASS::* ptr )
567 {
568 return SphMemberFunctor_T < T, CLASS > ( ptr );
569 }
570
571
572 /// identity functor
573 template < typename T >
574 struct SphIdentityFunctor_T
575 {
operatorSphIdentityFunctor_T576 const T & operator () ( const T & arg ) const { return arg; }
577 };
578
579 //////////////////////////////////////////////////////////////////////////
580
581 /// generic binary search
582 template < typename T, typename U, typename PRED >
sphBinarySearch(T * pStart,T * pEnd,const PRED & tPred,U tRef)583 T * sphBinarySearch ( T * pStart, T * pEnd, const PRED & tPred, U tRef )
584 {
585 if ( !pStart || pEnd<pStart )
586 return NULL;
587
588 if ( tPred(*pStart)==tRef )
589 return pStart;
590
591 if ( tPred(*pEnd)==tRef )
592 return pEnd;
593
594 while ( pEnd-pStart>1 )
595 {
596 if ( tRef<tPred(*pStart) || tRef>tPred(*pEnd) )
597 break;
598 assert ( tRef>tPred(*pStart) );
599 assert ( tRef<tPred(*pEnd) );
600
601 T * pMid = pStart + (pEnd-pStart)/2;
602 if ( tRef==tPred(*pMid) )
603 return pMid;
604
605 if ( tRef<tPred(*pMid) )
606 pEnd = pMid;
607 else
608 pStart = pMid;
609 }
610 return NULL;
611 }
612
613
614 /// generic binary search
615 template < typename T >
sphBinarySearch(T * pStart,T * pEnd,T & tRef)616 T * sphBinarySearch ( T * pStart, T * pEnd, T & tRef )
617 {
618 return sphBinarySearch ( pStart, pEnd, SphIdentityFunctor_T<T>(), tRef );
619 }
620
621 //////////////////////////////////////////////////////////////////////////
622
623 /// default vector policy
624 /// grow 2x and copy using assignment operator on resize
625 template < typename T >
626 class CSphVectorPolicy
627 {
628 protected:
629 static const int MAGIC_INITIAL_LIMIT = 8;
630
631 public:
Copy(T * pNew,T * pData,int iLength)632 static inline void Copy ( T * pNew, T * pData, int iLength )
633 {
634 for ( int i=0; i<iLength; i++ )
635 pNew[i] = pData[i];
636 }
637
Relimit(int iLimit,int iNewLimit)638 static inline int Relimit ( int iLimit, int iNewLimit )
639 {
640 if ( !iLimit )
641 iLimit = MAGIC_INITIAL_LIMIT;
642 while ( iLimit<iNewLimit )
643 iLimit *= 2;
644 return iLimit;
645 }
646 };
647
648 /// generic vector
649 /// (don't even ask why it's not std::vector)
650 template < typename T, typename POLICY=CSphVectorPolicy<T> > class CSphVector
651 {
652 public:
653 /// ctor
CSphVector()654 CSphVector ()
655 : m_iLength ( 0 )
656 , m_iLimit ( 0 )
657 , m_pData ( NULL )
658 {
659 }
660
661 /// ctor with initial size
CSphVector(int iCount)662 CSphVector ( int iCount )
663 : m_iLength ( 0 )
664 , m_iLimit ( 0 )
665 , m_pData ( NULL )
666 {
667 Resize ( iCount );
668 }
669
670 /// copy ctor
CSphVector(const CSphVector<T> & rhs)671 CSphVector ( const CSphVector<T> & rhs )
672 {
673 m_iLength = 0;
674 m_iLimit = 0;
675 m_pData = NULL;
676 *this = rhs;
677 }
678
679 /// dtor
~CSphVector()680 ~CSphVector ()
681 {
682 Reset ();
683 }
684
685 /// add entry
Add()686 T & Add ()
687 {
688 if ( m_iLength>=m_iLimit )
689 Reserve ( 1+m_iLength );
690 return m_pData [ m_iLength++ ];
691 }
692
693 /// add entry
Add(const T & tValue)694 void Add ( const T & tValue )
695 {
696 assert ( (&tValue<m_pData || &tValue>=(m_pData+m_iLength)) && "inserting own value (like last()) by ref!" );
697 if ( m_iLength>=m_iLimit )
698 Reserve ( 1+m_iLength );
699 m_pData [ m_iLength++ ] = tValue;
700 }
701
702 /// add unique entry (ie. do not add if equal to last one)
AddUnique(const T & tValue)703 void AddUnique ( const T & tValue )
704 {
705 assert ( (&tValue<m_pData || &tValue>=(m_pData+m_iLength)) && "inserting own value (like last()) by ref!" );
706 if ( m_iLength>=m_iLimit )
707 Reserve ( 1+m_iLength );
708
709 if ( m_iLength==0 || m_pData[m_iLength-1]!=tValue )
710 m_pData [ m_iLength++ ] = tValue;
711 }
712
713 /// get first entry ptr
Begin()714 T * Begin ()
715 {
716 return m_iLength ? m_pData : NULL;
717 }
718
719 /// get first entry ptr
Begin()720 const T * Begin () const
721 {
722 return m_iLength ? m_pData : NULL;
723 }
724
725 /// get last entry
Last()726 T & Last ()
727 {
728 return (*this) [ m_iLength-1 ];
729 }
730
731 /// get last entry
Last()732 const T & Last () const
733 {
734 return (*this) [ m_iLength-1 ];
735 }
736
737 /// remove element by index
Remove(int iIndex)738 void Remove ( int iIndex )
739 {
740 assert ( iIndex>=0 && iIndex<m_iLength );
741
742 m_iLength--;
743 for ( int i=iIndex; i<m_iLength; i++ )
744 m_pData[i] = m_pData[i+1];
745 }
746
747 /// remove element by index, swapping it with the tail
RemoveFast(int iIndex)748 void RemoveFast ( int iIndex )
749 {
750 assert ( iIndex>=0 && iIndex<m_iLength );
751 if ( iIndex!=--m_iLength )
752 Swap ( m_pData[iIndex], m_pData[m_iLength] );
753 }
754
755 /// remove element by value (warning, linear O(n) search)
RemoveValue(T tValue)756 bool RemoveValue ( T tValue )
757 {
758 for ( int i=0; i<m_iLength; i++ )
759 {
760 if ( m_pData[i]==tValue )
761 {
762 Remove ( i );
763 return true;
764 }
765 }
766 return false;
767 }
768
769 /// pop last value
Pop()770 const T & Pop ()
771 {
772 assert ( m_iLength>0 );
773 return m_pData[--m_iLength];
774 }
775
776 public:
777 /// grow enough to hold that much entries, if needed, but do *not* change the length
Reserve(int iNewLimit)778 void Reserve ( int iNewLimit )
779 {
780 // check that we really need to be called
781 assert ( iNewLimit>=0 );
782 if ( iNewLimit<=m_iLimit )
783 return;
784
785 // calc new limit
786 m_iLimit = POLICY::Relimit ( m_iLimit, iNewLimit );
787
788 // realloc
789 // FIXME! optimize for POD case
790 T * pNew = new T [ m_iLimit ];
791 __analysis_assume ( m_iLength<=m_iLimit );
792
793 POLICY::Copy ( pNew, m_pData, m_iLength );
794 delete [] m_pData;
795
796 m_pData = pNew;
797 }
798
799 /// resize
Resize(int iNewLength)800 void Resize ( int iNewLength )
801 {
802 assert ( iNewLength>=0 );
803 if ( iNewLength>=m_iLength )
804 Reserve ( iNewLength );
805 m_iLength = iNewLength;
806 }
807
808 /// reset
Reset()809 void Reset ()
810 {
811 m_iLength = 0;
812 m_iLimit = 0;
813 SafeDeleteArray ( m_pData );
814 }
815
816 /// query current length
GetLength()817 inline int GetLength () const
818 {
819 return m_iLength;
820 }
821
822 /// query current reserved size
GetLimit()823 inline int GetLimit () const
824 {
825 return m_iLimit;
826 }
827
828 public:
829 /// filter unique
Uniq()830 void Uniq ()
831 {
832 if ( !m_iLength )
833 return;
834
835 Sort ();
836
837 int iSrc = 1, iDst = 1;
838 while ( iSrc<m_iLength )
839 {
840 if ( m_pData[iDst-1]==m_pData[iSrc] )
841 iSrc++;
842 else
843 m_pData[iDst++] = m_pData[iSrc++];
844 }
845
846 Resize ( iDst );
847 }
848
849 /// default sort
850 void Sort ( int iStart=0, int iEnd=-1 )
851 {
852 Sort ( SphLess_T<T>(), iStart, iEnd );
853 }
854
855 /// default reverse sort
856 void RSort ( int iStart=0, int iEnd=-1 )
857 {
858 Sort ( SphGreater_T<T>(), iStart, iEnd );
859 }
860
861 /// generic sort
862 template < typename F > void Sort ( F COMP, int iStart=0, int iEnd=-1 )
863 {
864 if ( m_iLength<2 ) return;
865 if ( iStart<0 ) iStart = m_iLength+iStart;
866 if ( iEnd<0 ) iEnd = m_iLength+iEnd;
867 assert ( iStart<=iEnd );
868
869 sphSort ( m_pData+iStart, iEnd-iStart+1, COMP );
870 }
871
872 /// accessor by forward index
873 const T & operator [] ( int iIndex ) const
874 {
875 assert ( iIndex>=0 && iIndex<m_iLength );
876 return m_pData [ iIndex ];
877 }
878
879 /// accessor by forward index
880 T & operator [] ( int iIndex )
881 {
882 assert ( iIndex>=0 && iIndex<m_iLength );
883 return m_pData [ iIndex ];
884 }
885
886 /// copy
887 const CSphVector<T> & operator = ( const CSphVector<T> & rhs )
888 {
889 Reset ();
890
891 m_iLength = rhs.m_iLength;
892 m_iLimit = rhs.m_iLimit;
893 m_pData = new T [ m_iLimit ];
894 __analysis_assume ( m_iLength<=m_iLimit );
895 for ( int i=0; i<rhs.m_iLength; i++ )
896 m_pData[i] = rhs.m_pData[i];
897
898 return *this;
899 }
900
901 /// swap
SwapData(CSphVector<T,POLICY> & rhs)902 void SwapData ( CSphVector<T, POLICY> & rhs )
903 {
904 Swap ( m_iLength, rhs.m_iLength );
905 Swap ( m_iLimit, rhs.m_iLimit );
906 Swap ( m_pData, rhs.m_pData );
907 }
908
909 /// leak
LeakData()910 T * LeakData ()
911 {
912 T * pData = m_pData;
913 m_pData = NULL;
914 Reset();
915 return pData;
916 }
917
918 /// generic binary search
919 /// assumes that the array is sorted in ascending order
920 template < typename U, typename PRED >
BinarySearch(const PRED & tPred,U tRef)921 const T * BinarySearch ( const PRED & tPred, U tRef ) const
922 {
923 return sphBinarySearch ( m_pData, m_pData+m_iLength-1, tPred, tRef );
924 }
925
926 /// generic binary search
927 /// assumes that the array is sorted in ascending order
BinarySearch(T tRef)928 const T * BinarySearch ( T tRef ) const
929 {
930 return sphBinarySearch ( m_pData, m_pData+m_iLength-1, tRef );
931 }
932
933 /// generic linear search
Contains(T tRef)934 bool Contains ( T tRef ) const
935 {
936 for ( int i=0; i<m_iLength; i++ )
937 if ( m_pData[i]==tRef )
938 return true;
939 return false;
940 }
941
942 /// fill with given value
Fill(const T & rhs)943 void Fill ( const T & rhs )
944 {
945 for ( int i=0; i<m_iLength; i++ )
946 m_pData[i] = rhs;
947 }
948
949 /// insert into a middle
Insert(int iIndex,const T & tValue)950 void Insert ( int iIndex, const T & tValue )
951 {
952 assert ( iIndex>=0 && iIndex<=m_iLength );
953
954 if ( m_iLength>=m_iLimit )
955 Reserve ( m_iLength+1 );
956
957 // FIXME! this will not work for SwapVector
958 for ( int i=m_iLength-1; i>=iIndex; i-- )
959 m_pData [ i+1 ] = m_pData[i];
960 m_pData[iIndex] = tValue;
961 m_iLength++;
962 }
963
964 protected:
965 int m_iLength; ///< entries actually used
966 int m_iLimit; ///< entries allocated
967 T * m_pData; ///< entries
968 };
969
970
971 #define ARRAY_FOREACH(_index,_array) \
972 for ( int _index=0; _index<_array.GetLength(); _index++ )
973
974 #define ARRAY_FOREACH_COND(_index,_array,_cond) \
975 for ( int _index=0; _index<_array.GetLength() && (_cond); _index++ )
976
977 #define ARRAY_ANY(_res,_array,_cond) \
978 false; \
979 for ( int _any=0; _any<_array.GetLength() && !_res; _any++ ) \
980 _res |= ( _cond ); \
981
982 #define ARRAY_ALL(_res,_array,_cond) \
983 true; \
984 for ( int _all=0; _all<_array.GetLength() && _res; _all++ ) \
985 _res &= ( _cond ); \
986
987 //////////////////////////////////////////////////////////////////////////
988
989 /// swap-vector policy (for non-copyable classes)
990 /// use Swap() instead of assignment on resize
991 template < typename T >
992 class CSphSwapVectorPolicy : public CSphVectorPolicy<T>
993 {
994 public:
Copy(T * pNew,T * pData,int iLength)995 static inline void Copy ( T * pNew, T * pData, int iLength )
996 {
997 for ( int i=0; i<iLength; i++ )
998 Swap ( pNew[i], pData[i] );
999 }
1000 };
1001
1002 /// tight-vector policy
1003 /// grow only 1.2x on resize (not 2x) starting from a certain threshold
1004 template < typename T >
1005 class CSphTightVectorPolicy : public CSphVectorPolicy<T>
1006 {
1007 protected:
1008 static const int SLOW_GROW_TRESHOLD = 1024;
1009
1010 public:
Relimit(int iLimit,int iNewLimit)1011 static inline int Relimit ( int iLimit, int iNewLimit )
1012 {
1013 if ( !iLimit )
1014 iLimit = CSphVectorPolicy<T>::MAGIC_INITIAL_LIMIT;
1015 while ( iLimit<iNewLimit && iLimit<SLOW_GROW_TRESHOLD )
1016 iLimit *= 2;
1017 while ( iLimit<iNewLimit )
1018 iLimit = (int)( iLimit*1.2f );
1019 return iLimit;
1020 }
1021 };
1022
1023 /// swap-vector
1024 template < typename T >
1025 class CSphSwapVector : public CSphVector < T, CSphSwapVectorPolicy<T> >
1026 {
1027 };
1028
1029 /// tight-vector
1030 template < typename T >
1031 class CSphTightVector : public CSphVector < T, CSphTightVectorPolicy<T> >
1032 {
1033 };
1034
1035 //////////////////////////////////////////////////////////////////////////
1036
1037 /// dynamically allocated fixed-size vector
1038 template < typename T >
1039 class CSphFixedVector : public ISphNoncopyable
1040 {
1041 protected:
1042 T * m_pData;
1043 int m_iSize;
1044
1045 public:
CSphFixedVector(int iSize)1046 explicit CSphFixedVector ( int iSize )
1047 : m_iSize ( iSize )
1048 {
1049 assert ( iSize>=0 );
1050 m_pData = ( iSize>0 ) ? new T [ iSize ] : NULL;
1051 }
1052
~CSphFixedVector()1053 ~CSphFixedVector ()
1054 {
1055 SafeDeleteArray ( m_pData );
1056 }
1057
1058 T & operator [] ( int iIndex ) const
1059 {
1060 assert ( iIndex>=0 && iIndex<m_iSize );
1061 return m_pData[iIndex];
1062 }
1063
Begin()1064 T * Begin () const
1065 {
1066 return m_pData;
1067 }
1068
Last()1069 T & Last () const
1070 {
1071 return (*this) [ m_iSize-1 ];
1072 }
1073
Reset(int iSize)1074 void Reset ( int iSize )
1075 {
1076 SafeDeleteArray ( m_pData );
1077 assert ( iSize>=0 );
1078 m_pData = ( iSize>0 ) ? new T [ iSize ] : NULL;
1079 m_iSize = iSize;
1080 }
1081
GetLength()1082 int GetLength() const
1083 {
1084 return m_iSize;
1085 }
1086 };
1087
1088 //////////////////////////////////////////////////////////////////////////
1089
1090 /// simple dynamic hash
1091 /// keeps the order, so Iterate() return the entries in the order they was inserted
1092 template < typename T, typename KEY, typename HASHFUNC, int LENGTH >
1093 class CSphOrderedHash
1094 {
1095 protected:
1096 struct HashEntry_t
1097 {
1098 KEY m_tKey; ///< key, owned by the hash
1099 T m_tValue; ///< data, owned by the hash
1100 HashEntry_t * m_pNextByHash; ///< next entry in hash list
1101 HashEntry_t * m_pPrevByOrder; ///< prev entry in the insertion order
1102 HashEntry_t * m_pNextByOrder; ///< next entry in the insertion order
1103 };
1104
1105
1106 protected:
1107 HashEntry_t * m_dHash [ LENGTH ]; ///< all the hash entries
1108 HashEntry_t * m_pFirstByOrder; ///< first entry in the insertion order
1109 HashEntry_t * m_pLastByOrder; ///< last entry in the insertion order
1110 int m_iLength; ///< entries count
1111
1112 protected:
1113 /// find entry by key
FindByKey(const KEY & tKey)1114 HashEntry_t * FindByKey ( const KEY & tKey ) const
1115 {
1116 unsigned int uHash = ( (unsigned int) HASHFUNC::Hash ( tKey ) ) % LENGTH;
1117 HashEntry_t * pEntry = m_dHash [ uHash ];
1118
1119 while ( pEntry )
1120 {
1121 if ( pEntry->m_tKey==tKey )
1122 return pEntry;
1123 pEntry = pEntry->m_pNextByHash;
1124 }
1125 return NULL;
1126 }
1127
1128 public:
1129 /// ctor
CSphOrderedHash()1130 CSphOrderedHash ()
1131 : m_pFirstByOrder ( NULL )
1132 , m_pLastByOrder ( NULL )
1133 , m_iLength ( 0 )
1134 , m_pIterator ( NULL )
1135 {
1136 for ( int i=0; i<LENGTH; i++ )
1137 m_dHash[i] = NULL;
1138 }
1139
1140 /// dtor
~CSphOrderedHash()1141 ~CSphOrderedHash ()
1142 {
1143 Reset ();
1144 }
1145
1146 /// reset
Reset()1147 void Reset ()
1148 {
1149 HashEntry_t * pKill = m_pFirstByOrder;
1150 while ( pKill )
1151 {
1152 HashEntry_t * pNext = pKill->m_pNextByOrder;
1153 SafeDelete ( pKill );
1154 pKill = pNext;
1155 }
1156
1157 for ( int i=0; i<LENGTH; i++ )
1158 m_dHash[i] = 0;
1159
1160 m_pFirstByOrder = NULL;
1161 m_pLastByOrder = NULL;
1162 m_pIterator = NULL;
1163 m_iLength = 0;
1164 }
1165
1166 /// add new entry
1167 /// returns true on success
1168 /// returns false if this key is already hashed
Add(const T & tValue,const KEY & tKey)1169 bool Add ( const T & tValue, const KEY & tKey )
1170 {
1171 unsigned int uHash = ( (unsigned int) HASHFUNC::Hash ( tKey ) ) % LENGTH;
1172
1173 // check if this key is already hashed
1174 HashEntry_t * pEntry = m_dHash [ uHash ];
1175 HashEntry_t ** ppEntry = &m_dHash [ uHash ];
1176 while ( pEntry )
1177 {
1178 if ( pEntry->m_tKey==tKey )
1179 return false;
1180
1181 ppEntry = &pEntry->m_pNextByHash;
1182 pEntry = pEntry->m_pNextByHash;
1183 }
1184
1185 // it's not; let's add the entry
1186 assert ( !pEntry );
1187 assert ( !*ppEntry );
1188
1189 pEntry = new HashEntry_t;
1190 pEntry->m_tKey = tKey;
1191 pEntry->m_tValue = tValue;
1192 pEntry->m_pNextByHash = NULL;
1193 pEntry->m_pPrevByOrder = NULL;
1194 pEntry->m_pNextByOrder = NULL;
1195
1196 *ppEntry = pEntry;
1197
1198 if ( !m_pFirstByOrder )
1199 m_pFirstByOrder = pEntry;
1200
1201 if ( m_pLastByOrder )
1202 {
1203 assert ( !m_pLastByOrder->m_pNextByOrder );
1204 assert ( !pEntry->m_pNextByOrder );
1205 m_pLastByOrder->m_pNextByOrder = pEntry;
1206 pEntry->m_pPrevByOrder = m_pLastByOrder;
1207 }
1208 m_pLastByOrder = pEntry;
1209
1210 m_iLength++;
1211 return true;
1212 }
1213
1214 /// add new entry
1215 /// returns the pointer to just inserted or previously cached (if dupe) value
AddUnique(const KEY & tKey)1216 T & AddUnique ( const KEY & tKey )
1217 {
1218 unsigned int uHash = ( (unsigned int) HASHFUNC::Hash ( tKey ) ) % LENGTH;
1219
1220 // check if this key is already hashed
1221 HashEntry_t * pEntry = m_dHash [ uHash ];
1222 HashEntry_t ** ppEntry = &m_dHash [ uHash ];
1223 while ( pEntry )
1224 {
1225 if ( pEntry->m_tKey==tKey )
1226 return pEntry->m_tValue;
1227
1228 ppEntry = &pEntry->m_pNextByHash;
1229 pEntry = pEntry->m_pNextByHash;
1230 }
1231
1232 // it's not; let's add the entry
1233 assert ( !pEntry );
1234 assert ( !*ppEntry );
1235
1236 pEntry = new HashEntry_t;
1237 pEntry->m_tKey = tKey;
1238 pEntry->m_pNextByHash = NULL;
1239 pEntry->m_pPrevByOrder = NULL;
1240 pEntry->m_pNextByOrder = NULL;
1241
1242 *ppEntry = pEntry;
1243
1244 if ( !m_pFirstByOrder )
1245 m_pFirstByOrder = pEntry;
1246
1247 if ( m_pLastByOrder )
1248 {
1249 assert ( !m_pLastByOrder->m_pNextByOrder );
1250 assert ( !pEntry->m_pNextByOrder );
1251 m_pLastByOrder->m_pNextByOrder = pEntry;
1252 pEntry->m_pPrevByOrder = m_pLastByOrder;
1253 }
1254 m_pLastByOrder = pEntry;
1255
1256 m_iLength++;
1257 return pEntry->m_tValue;
1258 }
1259
1260 /// delete an entry
Delete(const KEY & tKey)1261 bool Delete ( const KEY & tKey )
1262 {
1263 unsigned int uHash = ( (unsigned int) HASHFUNC::Hash ( tKey ) ) % LENGTH;
1264 HashEntry_t * pEntry = m_dHash [ uHash ];
1265
1266 HashEntry_t * pPrevEntry = NULL;
1267 HashEntry_t * pToDelete = NULL;
1268 while ( pEntry )
1269 {
1270 if ( pEntry->m_tKey==tKey )
1271 {
1272 pToDelete = pEntry;
1273 if ( pPrevEntry )
1274 pPrevEntry->m_pNextByHash = pEntry->m_pNextByHash;
1275 else
1276 m_dHash [ uHash ] = pEntry->m_pNextByHash;
1277
1278 break;
1279 }
1280
1281 pPrevEntry = pEntry;
1282 pEntry = pEntry->m_pNextByHash;
1283 }
1284
1285 if ( !pToDelete )
1286 return false;
1287
1288 if ( pToDelete->m_pPrevByOrder )
1289 pToDelete->m_pPrevByOrder->m_pNextByOrder = pToDelete->m_pNextByOrder;
1290 else
1291 m_pFirstByOrder = pToDelete->m_pNextByOrder;
1292
1293 if ( pToDelete->m_pNextByOrder )
1294 pToDelete->m_pNextByOrder->m_pPrevByOrder = pToDelete->m_pPrevByOrder;
1295 else
1296 m_pLastByOrder = pToDelete->m_pPrevByOrder;
1297
1298 // step the iterator one item back - to gracefully hold deletion in iteration cycle
1299 if ( pToDelete==m_pIterator )
1300 m_pIterator = pToDelete->m_pPrevByOrder;
1301
1302 SafeDelete ( pToDelete );
1303 --m_iLength;
1304
1305 return true;
1306 }
1307
1308 /// check if key exists
Exists(const KEY & tKey)1309 bool Exists ( const KEY & tKey ) const
1310 {
1311 return FindByKey ( tKey )!=NULL;
1312 }
1313
1314 /// get value pointer by key
operator()1315 T * operator () ( const KEY & tKey ) const
1316 {
1317 HashEntry_t * pEntry = FindByKey ( tKey );
1318 return pEntry ? &pEntry->m_tValue : NULL;
1319 }
1320
1321 /// get value reference by key, asserting that the key exists in hash
1322 T & operator [] ( const KEY & tKey ) const
1323 {
1324 HashEntry_t * pEntry = FindByKey ( tKey );
1325 assert ( pEntry && "hash missing value in operator []" );
1326
1327 return pEntry->m_tValue;
1328 }
1329
1330 /// get pointer to key storage
GetKeyPtr(const KEY & tKey)1331 const KEY * GetKeyPtr ( const KEY & tKey ) const
1332 {
1333 HashEntry_t * pEntry = FindByKey ( tKey );
1334 return pEntry ? &pEntry->m_tKey : NULL;
1335 }
1336
1337 /// copying
1338 const CSphOrderedHash<T,KEY,HASHFUNC,LENGTH> & operator = ( const CSphOrderedHash<T,KEY,HASHFUNC,LENGTH> & rhs )
1339 {
1340 if ( this!=&rhs )
1341 {
1342 Reset ();
1343
1344 rhs.IterateStart ();
1345 while ( rhs.IterateNext() )
1346 Add ( rhs.IterateGet(), rhs.IterateGetKey() );
1347 }
1348 return *this;
1349 }
1350
1351 /// copyint ctor
1352 CSphOrderedHash<T,KEY,HASHFUNC,LENGTH> ( const CSphOrderedHash<T,KEY,HASHFUNC,LENGTH> & rhs )
m_pFirstByOrder(NULL)1353 : m_pFirstByOrder ( NULL )
1354 , m_pLastByOrder ( NULL )
1355 , m_iLength ( 0 )
1356 , m_pIterator ( NULL )
1357 {
1358 for ( int i=0; i<LENGTH; i++ )
1359 m_dHash[i] = NULL;
1360 *this = rhs;
1361 }
1362
1363 /// length query
GetLength()1364 int GetLength () const
1365 {
1366 return m_iLength;
1367 }
1368
1369 public:
1370 /// start iterating
IterateStart()1371 void IterateStart () const
1372 {
1373 m_pIterator = NULL;
1374 }
1375
1376 /// start iterating from key element
IterateStart(const KEY & tKey)1377 bool IterateStart ( const KEY & tKey ) const
1378 {
1379 m_pIterator = FindByKey ( tKey );
1380 return m_pIterator!=NULL;
1381 }
1382
1383 /// go to next existing entry
IterateNext()1384 bool IterateNext () const
1385 {
1386 m_pIterator = m_pIterator ? m_pIterator->m_pNextByOrder : m_pFirstByOrder;
1387 return m_pIterator!=NULL;
1388 }
1389
1390 /// get entry value
IterateGet()1391 T & IterateGet () const
1392 {
1393 assert ( m_pIterator );
1394 return m_pIterator->m_tValue;
1395 }
1396
1397 /// get entry key
IterateGetKey()1398 const KEY & IterateGetKey () const
1399 {
1400 assert ( m_pIterator );
1401 return m_pIterator->m_tKey;
1402 }
1403
1404 /// go to next existing entry in terms of external independed iterator
IterateNext(void ** ppCookie)1405 bool IterateNext ( void ** ppCookie ) const
1406 {
1407 HashEntry_t ** ppIterator = reinterpret_cast < HashEntry_t** > ( ppCookie );
1408 *ppIterator = ( *ppIterator ) ? ( *ppIterator )->m_pNextByOrder : m_pFirstByOrder;
1409 return ( *ppIterator )!=NULL;
1410 }
1411
1412 /// get entry value in terms of external independed iterator
IterateGet(void ** ppCookie)1413 static T & IterateGet ( void ** ppCookie )
1414 {
1415 assert ( ppCookie );
1416 HashEntry_t ** ppIterator = reinterpret_cast < HashEntry_t** > ( ppCookie );
1417 assert ( *ppIterator );
1418 return ( *ppIterator )->m_tValue;
1419 }
1420
1421 /// get entry key in terms of external independed iterator
IterateGetKey(void ** ppCookie)1422 static const KEY & IterateGetKey ( void ** ppCookie )
1423 {
1424 assert ( ppCookie );
1425 HashEntry_t ** ppIterator = reinterpret_cast < HashEntry_t** > ( ppCookie );
1426 assert ( *ppIterator );
1427 return ( *ppIterator )->m_tKey;
1428 }
1429
1430
1431 private:
1432 /// current iterator
1433 mutable HashEntry_t * m_pIterator;
1434 };
1435
1436 /// very popular and so, moved here
1437 struct IdentityHash_fn
1438 {
1439 template <typename INT>
HashIdentityHash_fn1440 static inline INT Hash ( INT iValue ) { return iValue; }
1441 };
1442
1443 /////////////////////////////////////////////////////////////////////////////
1444
1445 /// immutable C string proxy
1446 struct CSphString
1447 {
1448 protected:
1449 char * m_sValue;
1450
1451 private:
1452 /// safety gap after the string end; for instance, UTF-8 Russian stemmer
1453 /// which treats strings as 16-bit word sequences needs this in some cases.
1454 /// note that this zero-filled gap does NOT include trailing C-string zero,
1455 /// and does NOT affect strlen() as well.
1456 static const int SAFETY_GAP = 4;
1457
1458 public:
CSphStringCSphString1459 CSphString ()
1460 : m_sValue ( NULL )
1461 {
1462 }
1463
CSphStringCSphString1464 CSphString ( const CSphString & rhs )
1465 : m_sValue ( NULL )
1466 {
1467 *this = rhs;
1468 }
1469
~CSphStringCSphString1470 virtual ~CSphString ()
1471 {
1472 SafeDeleteArray ( m_sValue );
1473 }
1474
cstrCSphString1475 const char * cstr () const
1476 {
1477 return m_sValue;
1478 }
1479
1480 inline bool operator == ( const char * t ) const
1481 {
1482 if ( !t || !m_sValue )
1483 return ( !t && !m_sValue );
1484 return strcmp ( m_sValue, t )==0;
1485 }
1486
1487 inline bool operator == ( const CSphString & t ) const
1488 {
1489 return operator==( t.cstr() );
1490 }
1491
1492 inline bool operator != ( const CSphString & t ) const
1493 {
1494 return !operator==( t );
1495 }
1496
1497 bool operator != ( const char * t ) const
1498 {
1499 return !operator==( t );
1500 }
1501
CSphStringCSphString1502 CSphString ( const char * sString ) // NOLINT
1503 {
1504 if ( sString )
1505 {
1506 int iLen = 1+strlen(sString);
1507 m_sValue = new char [ iLen+SAFETY_GAP ];
1508
1509 strcpy ( m_sValue, sString ); // NOLINT
1510 memset ( m_sValue+iLen, 0, SAFETY_GAP );
1511 } else
1512 {
1513 m_sValue = NULL;
1514 }
1515 }
1516
1517 const CSphString & operator = ( const CSphString & rhs )
1518 {
1519 if ( m_sValue==rhs.m_sValue )
1520 return *this;
1521 SafeDeleteArray ( m_sValue );
1522 if ( rhs.m_sValue )
1523 {
1524 int iLen = 1+strlen(rhs.m_sValue);
1525 m_sValue = new char [ iLen+SAFETY_GAP ];
1526
1527 strcpy ( m_sValue, rhs.m_sValue ); // NOLINT
1528 memset ( m_sValue+iLen, 0, SAFETY_GAP );
1529 }
1530 return *this;
1531 }
1532
SubStringCSphString1533 CSphString SubString ( int iStart, int iCount ) const
1534 {
1535 #ifndef NDEBUG
1536 int iLen = strlen(m_sValue);
1537 #endif
1538 assert ( iStart>=0 && iStart<iLen );
1539 assert ( iCount>0 );
1540 assert ( (iStart+iCount)>=0 && (iStart+iCount)<=iLen );
1541
1542 CSphString sRes;
1543 sRes.m_sValue = new char [ 1+SAFETY_GAP+iCount ];
1544 strncpy ( sRes.m_sValue, m_sValue+iStart, iCount );
1545 memset ( sRes.m_sValue+iCount, 0, 1+SAFETY_GAP );
1546 return sRes;
1547 }
1548
SetBinaryCSphString1549 void SetBinary ( const char * sValue, int iLen )
1550 {
1551 SafeDeleteArray ( m_sValue );
1552 if ( sValue )
1553 {
1554 m_sValue = new char [ 1+SAFETY_GAP+iLen ];
1555 memcpy ( m_sValue, sValue, iLen );
1556 memset ( m_sValue+iLen, 0, 1+SAFETY_GAP );
1557 }
1558 }
1559
ReserveCSphString1560 void Reserve ( int iLen )
1561 {
1562 SafeDeleteArray ( m_sValue );
1563 m_sValue = new char [ 1+SAFETY_GAP+iLen ];
1564 memset ( m_sValue, 0, 1+SAFETY_GAP+iLen );
1565 }
1566
SetSprintfCSphString1567 const CSphString & SetSprintf ( const char * sTemplate, ... ) __attribute__ ( ( format ( printf, 2, 3 ) ) )
1568 {
1569 char sBuf[1024];
1570 va_list ap;
1571
1572 va_start ( ap, sTemplate );
1573 vsnprintf ( sBuf, sizeof(sBuf), sTemplate, ap );
1574 va_end ( ap );
1575
1576 (*this) = sBuf;
1577 return (*this);
1578 }
1579
SetSprintfVaCSphString1580 const CSphString & SetSprintfVa ( const char * sTemplate, va_list ap )
1581 {
1582 char sBuf[1024];
1583 vsnprintf ( sBuf, sizeof(sBuf), sTemplate, ap );
1584
1585 (*this) = sBuf;
1586 return (*this);
1587 }
1588
IsEmptyCSphString1589 bool IsEmpty () const
1590 {
1591 if ( !m_sValue )
1592 return true;
1593 return ( (*m_sValue)=='\0' );
1594 }
1595
ToLowerCSphString1596 void ToLower ()
1597 {
1598 if ( m_sValue )
1599 for ( char * s=m_sValue; *s; s++ )
1600 *s = (char) tolower ( *s );
1601 }
1602
ToUpperCSphString1603 void ToUpper ()
1604 {
1605 if ( m_sValue )
1606 for ( char * s=m_sValue; *s; s++ )
1607 *s = (char) toupper ( *s );
1608 }
1609
SwapCSphString1610 void Swap ( CSphString & rhs )
1611 {
1612 ::Swap ( m_sValue, rhs.m_sValue );
1613 }
1614
BeginsCSphString1615 bool Begins ( const char * sPrefix ) const
1616 {
1617 if ( !m_sValue || !sPrefix )
1618 return false;
1619 return strncmp ( m_sValue, sPrefix, strlen(sPrefix) )==0;
1620 }
1621
EndsCSphString1622 bool Ends ( const char * sPrefix ) const
1623 {
1624 if ( !m_sValue || !sPrefix )
1625 return false;
1626
1627 int iVal = strlen ( m_sValue );
1628 int iPrefix = strlen ( sPrefix );
1629 if ( iVal<iPrefix )
1630 return false;
1631 return strncmp ( m_sValue+iVal-iPrefix, sPrefix, iPrefix )==0;
1632 }
1633
ChopCSphString1634 void Chop ()
1635 {
1636 if ( m_sValue )
1637 {
1638 const char * sStart = m_sValue;
1639 const char * sEnd = m_sValue + strlen(m_sValue) - 1;
1640 while ( sStart<=sEnd && isspace ( (unsigned char)*sStart ) ) sStart++;
1641 while ( sStart<=sEnd && isspace ( (unsigned char)*sEnd ) ) sEnd--;
1642 memmove ( m_sValue, sStart, sEnd-sStart+1 );
1643 m_sValue [ sEnd-sStart+1 ] = '\0';
1644 }
1645 }
1646
LengthCSphString1647 int Length () const
1648 {
1649 return m_sValue ? (int)strlen(m_sValue) : 0;
1650 }
1651
LeakCSphString1652 char * Leak ()
1653 {
1654 char * pBuf = m_sValue;
1655 m_sValue = NULL;
1656 return pBuf;
1657 }
1658
1659 bool operator < ( const CSphString & b ) const
1660 {
1661 if ( !m_sValue && !b.m_sValue )
1662 return false;
1663 if ( !m_sValue || !b.m_sValue )
1664 return !m_sValue;
1665 return strcmp ( m_sValue, b.m_sValue ) < 0;
1666 }
1667 };
1668
1669 /// string swapper
Swap(CSphString & v1,CSphString & v2)1670 inline void Swap ( CSphString & v1, CSphString & v2 )
1671 {
1672 v1.Swap ( v2 );
1673 }
1674
1675
1676 /// string builder
1677 /// somewhat quicker than a series of SetSprintf()s
1678 /// lets you build strings bigger than 1024 bytes, too
1679 class CSphStringBuilder
1680 {
1681 protected:
1682 char * m_sBuffer;
1683 int m_iSize;
1684 int m_iUsed;
1685 bool m_bFirstSeparator;
1686
1687 public:
CSphStringBuilder()1688 CSphStringBuilder ()
1689 {
1690 Reset ();
1691 }
1692
~CSphStringBuilder()1693 ~CSphStringBuilder ()
1694 {
1695 SafeDeleteArray ( m_sBuffer );
1696 }
1697
Reset()1698 void Reset ()
1699 {
1700 m_iSize = 256;
1701 m_iUsed = 0;
1702 m_sBuffer = new char [ m_iSize ];
1703 m_sBuffer[0] = '\0';
1704 m_bFirstSeparator = true;
1705 }
1706
Appendf(const char * sTemplate,...)1707 CSphStringBuilder & Appendf ( const char * sTemplate, ... ) __attribute__ ( ( format ( printf, 2, 3 ) ) )
1708 {
1709 assert ( m_sBuffer );
1710 assert ( m_iUsed<m_iSize );
1711
1712 for ( ;; )
1713 {
1714 int iLeft = m_iSize - m_iUsed;
1715
1716 // try to append
1717 va_list ap;
1718 va_start ( ap, sTemplate );
1719 int iPrinted = vsnprintf ( m_sBuffer+m_iUsed, iLeft, sTemplate, ap );
1720 va_end ( ap );
1721
1722 // success? bail
1723 // note that we check for strictly less, not less or equal
1724 // that is because vsnprintf does *not* count the trailing zero
1725 // meaning that if we had N bytes left, and N bytes w/o the zero were printed,
1726 // we do not have a trailing zero anymore, but vsnprintf succeeds anyway
1727 if ( iPrinted>=0 && iPrinted<iLeft )
1728 {
1729 m_iUsed += iPrinted;
1730 break;
1731 }
1732
1733 // we need more chars!
1734 // either 256 (happens on Windows; lets assume we need 256 more chars)
1735 // or get all the needed chars and 64 more for future calls
1736 Grow ( iPrinted<0 ? 256 : iPrinted - iLeft + 64 );
1737 }
1738 return *this;
1739 }
1740
ResetSeparator()1741 void ResetSeparator ()
1742 {
1743 m_bFirstSeparator = true;
1744 }
1745
AppendSeparator(const char * sSep)1746 CSphStringBuilder & AppendSeparator ( const char * sSep )
1747 {
1748 if ( !m_bFirstSeparator )
1749 *this += sSep;
1750 m_bFirstSeparator = false;
1751 return *this;
1752 }
1753
cstr()1754 const char * cstr() const
1755 {
1756 return m_sBuffer;
1757 }
1758
Length()1759 int Length ()
1760 {
1761 return m_iUsed;
1762 }
1763
1764 const CSphStringBuilder & operator += ( const char * sText )
1765 {
1766 if ( !sText || *sText=='\0' )
1767 return *this;
1768
1769 int iLen = strlen ( sText );
1770 int iLeft = m_iSize - m_iUsed;
1771 if ( iLen>=iLeft )
1772 Grow ( iLen - iLeft + 64 );
1773
1774 memcpy ( m_sBuffer+m_iUsed, sText, iLen+1 );
1775 m_iUsed += iLen;
1776 return *this;
1777 }
1778
1779 const CSphStringBuilder & operator = ( const CSphStringBuilder & rhs )
1780 {
1781 if ( this!=&rhs )
1782 {
1783 m_iUsed = rhs.m_iUsed;
1784 m_iSize = rhs.m_iSize;
1785 m_bFirstSeparator = rhs.m_bFirstSeparator;
1786 SafeDeleteArray ( m_sBuffer );
1787 m_sBuffer = new char [ m_iSize ];
1788 memcpy ( m_sBuffer, rhs.m_sBuffer, m_iUsed+1 );
1789 }
1790 return *this;
1791 }
1792
1793 void AppendEscaped ( const char * sText, bool bEscape=true, bool bFixupSpace=true )
1794 {
1795 if ( !sText || !*sText )
1796 return;
1797
1798 const char * pBuf = sText;
1799 int iEsc = 0;
1800 for ( ; *pBuf; )
1801 {
1802 char s = *pBuf++;
1803 iEsc = ( bEscape && ( s=='\\' || s=='\'' ) ) ? ( iEsc+1 ) : iEsc;
1804 }
1805
1806 int iLen = pBuf - sText + iEsc;
1807 int iLeft = m_iSize - m_iUsed;
1808 if ( iLen>=iLeft )
1809 Grow ( iLen - iLeft + 64 );
1810
1811 pBuf = sText;
1812 char * pCur = m_sBuffer+m_iUsed;
1813 for ( ; *pBuf; )
1814 {
1815 char s = *pBuf++;
1816 if ( bEscape && ( s=='\\' || s=='\'' ) )
1817 {
1818 *pCur++ = '\\';
1819 *pCur++ = s;
1820 } else if ( bFixupSpace && ( s==' ' || s=='\t' || s=='\n' || s=='\r' ) )
1821 {
1822 *pCur++ = ' ';
1823 } else
1824 {
1825 *pCur++ = s;
1826 }
1827 }
1828 *pCur = '\0';
1829 m_iUsed = pCur-m_sBuffer;
1830 }
1831
1832 private:
Grow(int iLen)1833 void Grow ( int iLen )
1834 {
1835 m_iSize += iLen;
1836 char * pNew = new char [ m_iSize ];
1837 memcpy ( pNew, m_sBuffer, m_iUsed+1 );
1838 Swap ( pNew, m_sBuffer );
1839 SafeDeleteArray ( pNew );
1840 }
1841 };
1842
1843 /////////////////////////////////////////////////////////////////////////////
1844
1845 /// immutable string/int/float variant list proxy
1846 struct CSphVariant : public CSphString
1847 {
1848 protected:
1849 int m_iValue;
1850 int64_t m_i64Value;
1851 float m_fValue;
1852
1853 public:
1854 CSphVariant * m_pNext;
1855 bool m_bTag;
1856
1857 public:
1858 /// default ctor
CSphVariantCSphVariant1859 CSphVariant ()
1860 : CSphString ()
1861 , m_iValue ( 0 )
1862 , m_i64Value ( 0 )
1863 , m_fValue ( 0.0f )
1864 , m_pNext ( NULL )
1865 , m_bTag ( false )
1866 {
1867 }
1868
1869 /// ctor from C string
CSphVariantCSphVariant1870 CSphVariant ( const char * sString ) // NOLINT desired implicit conversion
1871 : CSphString ( sString )
1872 , m_iValue ( m_sValue ? atoi ( m_sValue ) : 0 )
1873 , m_i64Value ( m_sValue ? (int64_t)strtoull ( m_sValue, NULL, 10 ) : 0 )
1874 , m_fValue ( m_sValue ? (float)atof ( m_sValue ) : 0.0f )
1875 , m_pNext ( NULL )
1876 {
1877 }
1878
1879 /// copy ctor
CSphVariantCSphVariant1880 CSphVariant ( const CSphVariant & rhs )
1881 : CSphString ()
1882 , m_iValue ( 0 )
1883 , m_i64Value ( 0 )
1884 , m_fValue ( 0.0f )
1885 , m_pNext ( NULL )
1886 {
1887 *this = rhs;
1888 }
1889
1890 /// default dtor
1891 /// WARNING: automatically frees linked items!
~CSphVariantCSphVariant1892 virtual ~CSphVariant ()
1893 {
1894 SafeDelete ( m_pNext );
1895 }
1896
1897 /// int value getter
intvalCSphVariant1898 int intval () const
1899 {
1900 return m_iValue;
1901 }
1902
1903 /// int64_t value getter
int64valCSphVariant1904 int64_t int64val () const
1905 {
1906 return m_i64Value;
1907 }
1908
1909 /// float value getter
floatvalCSphVariant1910 float floatval () const
1911 {
1912 return m_fValue;
1913 }
1914
1915 /// default copy operator
1916 const CSphVariant & operator = ( const CSphVariant & rhs )
1917 {
1918 assert ( !m_pNext );
1919 if ( rhs.m_pNext )
1920 m_pNext = new CSphVariant ( *rhs.m_pNext );
1921
1922 CSphString::operator = ( rhs );
1923 m_iValue = rhs.m_iValue;
1924 m_i64Value = rhs.m_i64Value;
1925 m_fValue = rhs.m_fValue;
1926
1927 return *this;
1928 }
1929 };
1930
1931
1932 /////////////////////////////////////////////////////////////////////////////
1933
1934 /// string hash function
1935 struct CSphStrHashFunc
1936 {
1937 static int Hash ( const CSphString & sKey );
1938 };
1939
1940 /// small hash with string keys
1941 template < typename T >
1942 class SmallStringHash_T : public CSphOrderedHash < T, CSphString, CSphStrHashFunc, 256 > {};
1943
1944 //////////////////////////////////////////////////////////////////////////
1945
1946 /// pointer with automatic safe deletion when going out of scope
1947 template < typename T >
1948 class CSphScopedPtr : public ISphNoncopyable
1949 {
1950 public:
CSphScopedPtr(T * pPtr)1951 explicit CSphScopedPtr ( T * pPtr ) { m_pPtr = pPtr; }
~CSphScopedPtr()1952 ~CSphScopedPtr () { SafeDelete ( m_pPtr ); }
1953 T * operator -> () const { return m_pPtr; }
Ptr()1954 T * Ptr () const { return m_pPtr; }
1955 CSphScopedPtr & operator = ( T * pPtr ) { SafeDelete ( m_pPtr ); m_pPtr = pPtr; return *this; }
LeakPtr()1956 T * LeakPtr () { T * pPtr = m_pPtr; m_pPtr = NULL; return pPtr; }
Reset()1957 void Reset () { SafeDelete ( m_pPtr ); }
1958
1959 protected:
1960 T * m_pPtr;
1961 };
1962
1963 //////////////////////////////////////////////////////////////////////////
1964
1965 /// refcounted base
1966 /// WARNING, FOR SINGLE-THREADED USE ONLY
1967 struct ISphRefcounted : public ISphNoncopyable
1968 {
1969 protected:
ISphRefcountedISphRefcounted1970 ISphRefcounted () : m_iRefCount ( 1 ) {}
~ISphRefcountedISphRefcounted1971 virtual ~ISphRefcounted () {}
1972
1973 public:
AddRefISphRefcounted1974 void AddRef () const { m_iRefCount++; }
ReleaseISphRefcounted1975 void Release () const { --m_iRefCount; assert ( m_iRefCount>=0 ); if ( m_iRefCount==0 ) delete this; }
1976
1977 protected:
1978 mutable int m_iRefCount;
1979 };
1980
1981
1982 /// automatic pointer wrapper for refcounted objects
1983 /// construction from or assignment of a raw pointer takes over (!) the ownership
1984 template < typename T >
1985 class CSphRefcountedPtr
1986 {
1987 public:
CSphRefcountedPtr()1988 explicit CSphRefcountedPtr () { m_pPtr = NULL; } ///< default NULL wrapper construction (for vectors)
CSphRefcountedPtr(T * pPtr)1989 explicit CSphRefcountedPtr ( T * pPtr ) { m_pPtr = pPtr; } ///< construction from raw pointer, takes over ownership!
~CSphRefcountedPtr()1990 ~CSphRefcountedPtr () { if ( m_pPtr ) m_pPtr->Release(); }
1991
Ptr()1992 T * Ptr () const { return m_pPtr; }
1993 T * operator -> () const { return m_pPtr; }
1994 bool operator ! () const { return m_pPtr==NULL; }
1995
1996 public:
1997 /// assignment of a raw pointer, takes over ownership!
1998 CSphRefcountedPtr<T> & operator = ( T * pPtr )
1999 {
2000 if ( m_pPtr && m_pPtr!=pPtr )
2001 m_pPtr->Release();
2002 m_pPtr = pPtr;
2003 return *this;
2004 }
2005
2006 /// wrapper assignment, does automated reference tracking
2007 CSphRefcountedPtr<T> & operator = ( const CSphRefcountedPtr<T> & rhs )
2008 {
2009 if ( rhs.m_pPtr )
2010 rhs.m_pPtr->AddRef();
2011 if ( m_pPtr )
2012 m_pPtr->Release();
2013 m_pPtr = rhs.m_pPtr;
2014 return *this;
2015 }
2016
2017 protected:
2018 T * m_pPtr;
2019 };
2020
2021 //////////////////////////////////////////////////////////////////////////
2022
2023 extern bool g_bHeadProcess;
2024 void sphWarn ( const char *, ... ) __attribute__ ( ( format ( printf, 1, 2 ) ) );
2025
2026 /// in-memory buffer shared between processes
2027 template < typename T > class CSphSharedBuffer
2028 {
2029 public:
2030 /// ctor
CSphSharedBuffer()2031 CSphSharedBuffer ()
2032 : m_pData ( NULL )
2033 , m_iLength ( 0 )
2034 , m_iEntries ( 0 )
2035 , m_bMlock ( false )
2036 {}
2037
2038 /// dtor
~CSphSharedBuffer()2039 ~CSphSharedBuffer ()
2040 {
2041 Reset ();
2042 }
2043
2044 /// set locking mode for subsequent Alloc()s
SetMlock(bool bMlock)2045 void SetMlock ( bool bMlock )
2046 {
2047 m_bMlock = bMlock;
2048 }
2049
2050 public:
2051 /// allocate storage
2052 #if USE_WINDOWS
Alloc(int64_t iEntries,CSphString & sError,CSphString &)2053 bool Alloc ( int64_t iEntries, CSphString & sError, CSphString & )
2054 #else
2055 bool Alloc ( int64_t iEntries, CSphString & sError, CSphString & sWarning )
2056 #endif
2057 {
2058 assert ( !m_pData );
2059
2060 int64_t uCheck = sizeof(T);
2061 uCheck *= iEntries;
2062
2063 m_iLength = (size_t)uCheck;
2064 if ( uCheck!=(int64_t)m_iLength )
2065 {
2066 sError.SetSprintf ( "impossible to mmap() over 4 GB on 32-bit system" );
2067 m_iLength = 0;
2068 return false;
2069 }
2070
2071 #if USE_WINDOWS
2072 m_pData = new T [ (size_t)iEntries ];
2073 #else
2074 m_pData = (T *) mmap ( NULL, m_iLength, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANON, -1, 0 );
2075 if ( m_pData==MAP_FAILED )
2076 {
2077 if ( m_iLength>0x7fffffffUL )
2078 sError.SetSprintf ( "mmap() failed: %s (length="INT64_FMT" is over 2GB, impossible on some 32-bit systems)", strerror(errno), (int64_t)m_iLength );
2079 else
2080 sError.SetSprintf ( "mmap() failed: %s (length="INT64_FMT")", strerror(errno), (int64_t)m_iLength );
2081 m_iLength = 0;
2082 return false;
2083 }
2084
2085 if ( m_bMlock )
2086 if ( -1==mlock ( m_pData, m_iLength ) )
2087 sWarning.SetSprintf ( "mlock() failed: %s", strerror(errno) );
2088
2089 #if SPH_ALLOCS_PROFILER
2090 sphMemStatMMapAdd ( m_iLength );
2091 #endif
2092
2093 #endif // USE_WINDOWS
2094
2095 assert ( m_pData );
2096 m_iEntries = (size_t)iEntries;
2097 return true;
2098 }
2099
2100
2101 /// relock again (for daemonization only)
2102 #if USE_WINDOWS
Mlock(const char *,CSphString &)2103 bool Mlock ( const char *, CSphString & )
2104 {
2105 return true;
2106 }
2107 #else
Mlock(const char * sPrefix,CSphString & sError)2108 bool Mlock ( const char * sPrefix, CSphString & sError )
2109 {
2110 if ( !m_bMlock )
2111 return true;
2112
2113 if ( mlock ( m_pData, m_iLength )!=-1 )
2114 return true;
2115
2116 if ( sError.IsEmpty() )
2117 sError.SetSprintf ( "%s mlock() failed: bytes="INT64_FMT", error=%s", sPrefix, (int64_t)m_iLength, strerror(errno) );
2118 else
2119 sError.SetSprintf ( "%s; %s mlock() failed: bytes="INT64_FMT", error=%s", sError.cstr(), sPrefix, (int64_t)m_iLength, strerror(errno) );
2120 return false;
2121 }
2122 #endif
2123
2124
2125 /// deallocate storage
Reset()2126 void Reset ()
2127 {
2128 if ( !m_pData )
2129 return;
2130
2131 #if USE_WINDOWS
2132 delete [] m_pData;
2133 #else
2134 if ( g_bHeadProcess )
2135 {
2136 int iRes = munmap ( m_pData, m_iLength );
2137 if ( iRes )
2138 sphWarn ( "munmap() failed: %s", strerror(errno) );
2139
2140 #if SPH_ALLOCS_PROFILER
2141 sphMemStatMMapDel ( m_iLength );
2142 #endif
2143 }
2144 #endif // USE_WINDOWS
2145
2146 m_pData = NULL;
2147 m_iLength = 0;
2148 m_iEntries = 0;
2149 }
2150
2151 public:
2152 /// accessor
2153 inline const T & operator [] ( int64_t iIndex ) const
2154 {
2155 assert ( iIndex>=0 && iIndex<(int64_t)m_iEntries );
2156 return m_pData[iIndex];
2157 }
2158
2159 /// get write address
GetWritePtr()2160 T * GetWritePtr () const
2161 {
2162 return m_pData;
2163 }
2164
2165 /// check if i'm empty
IsEmpty()2166 bool IsEmpty () const
2167 {
2168 return m_pData==NULL;
2169 }
2170
2171 /// get length in bytes
GetLength()2172 size_t GetLength () const
2173 {
2174 return m_iLength;
2175 }
2176
2177 /// get length in entries
GetNumEntries()2178 size_t GetNumEntries () const
2179 {
2180 return m_iEntries;
2181 }
2182
2183 protected:
2184 T * m_pData; ///< data storage
2185 size_t m_iLength; ///< data length, bytes
2186 size_t m_iEntries; ///< data length, entries
2187 bool m_bMlock; ///< whether to lock data in RAM
2188 };
2189
2190 //////////////////////////////////////////////////////////////////////////
2191
2192 /// process-shared mutex that survives fork
2193 class CSphProcessSharedMutex
2194 {
2195 public:
2196 explicit CSphProcessSharedMutex ( int iExtraSize=0 );
2197 ~CSphProcessSharedMutex(); // not virtual for now.
2198 void Lock () const;
2199 void Unlock () const;
2200 bool TimedLock ( int tmSpin ) const; // wait at least tmSpin microseconds the lock will available
2201 const char * GetError () const;
2202
2203 protected:
2204 #if !USE_WINDOWS
2205 CSphSharedBuffer<BYTE> m_pStorage;
2206 #ifdef __FreeBSD__
2207 sem_t * m_pMutex;
2208 #else
2209 pthread_mutex_t * m_pMutex;
2210 #endif
2211 CSphString m_sError;
2212 #endif
2213 };
2214
2215
2216 #if !USE_WINDOWS
2217 /// process-shared mutex variable that survives fork
2218 template < typename T > class CSphProcessSharedVariable : protected CSphProcessSharedMutex, public ISphNoncopyable
2219 {
2220 public:
2221
CSphProcessSharedVariable(const T & tInitValue)2222 explicit CSphProcessSharedVariable ( const T& tInitValue )
2223 : CSphProcessSharedMutex ( sizeof(T) )
2224 , m_pValue ( NULL )
2225 {
2226 if ( m_pMutex )
2227 {
2228 #ifdef __FreeBSD__
2229 m_pValue = reinterpret_cast<T*> ( m_pStorage.GetWritePtr () + sizeof ( sem_t ) );
2230 #else
2231 m_pValue = reinterpret_cast<T*> ( m_pStorage.GetWritePtr () + sizeof ( pthread_mutex_t ) );
2232 #endif
2233 *m_pValue = tInitValue;
2234 }
2235 }
ReadValue()2236 T ReadValue() const
2237 {
2238 if ( !m_pValue )
2239 return 0;
2240 Lock();
2241 T val = *m_pValue;
2242 Unlock();
2243 return val;
2244 }
WriteValue(const T & tNewValue)2245 void WriteValue ( const T& tNewValue )
2246 {
2247 if ( !m_pValue )
2248 return;
2249 Lock();
2250 *m_pValue = tNewValue;
2251 Unlock();
2252 }
2253
2254 protected:
2255 T * m_pValue;
2256 };
2257 #endif // #if !USE_WINDOWS
2258
2259 //////////////////////////////////////////////////////////////////////////
2260
2261 extern int g_iThreadStackSize;
2262
2263 /// my thread handle and thread func magic
2264 #if USE_WINDOWS
2265 typedef HANDLE SphThread_t;
2266 typedef DWORD SphThreadKey_t;
2267 #else
2268 typedef pthread_t SphThread_t;
2269 typedef pthread_key_t SphThreadKey_t;
2270 #endif
2271
2272 /// my threading initialize routine
2273 void * sphThreadInit ( bool bDetached=false );
2274
2275 /// my threading deinitialize routine
2276 void sphThreadDone ( int iFD );
2277
2278 /// my create thread wrapper
2279 bool sphThreadCreate ( SphThread_t * pThread, void (*fnThread)(void*), void * pArg, bool bDetached=false );
2280
2281 /// my join thread wrapper
2282 bool sphThreadJoin ( SphThread_t * pThread );
2283
2284 /// add (cleanup) callback to run on thread exit
2285 void sphThreadOnExit ( void (*fnCleanup)(void*), void * pArg );
2286
2287 /// alloc thread-local key
2288 bool sphThreadKeyCreate ( SphThreadKey_t * pKey );
2289
2290 /// free thread-local key
2291 void sphThreadKeyDelete ( SphThreadKey_t tKey );
2292
2293 /// get thread-local key value
2294 void * sphThreadGet ( SphThreadKey_t tKey );
2295
2296 /// get the pointer to my thread's stack
2297 void * sphMyStack ();
2298
2299 /// get size of used stack
2300 int64_t sphGetStackUsed();
2301
2302 /// set the size of my thread's stack
2303 void sphSetMyStackSize ( int iStackSize );
2304
2305 /// store the address in the TLS
2306 void MemorizeStack ( void* PStack );
2307
2308 /// set thread-local key value
2309 bool sphThreadSet ( SphThreadKey_t tKey, void * pValue );
2310
2311 #if !USE_WINDOWS
2312 /// what kind of threading lib do we have? The number of frames in the stack depends from it
2313 bool sphIsLtLib();
2314 #endif
2315
2316 //////////////////////////////////////////////////////////////////////////
2317
2318 /// mutex implementation
2319 class CSphMutex
2320 {
2321 public:
CSphMutex()2322 CSphMutex () : m_bInitialized ( false ) {}
~CSphMutex()2323 ~CSphMutex () { assert ( !m_bInitialized ); }
2324
2325 bool Init ();
2326 bool Done ();
2327 bool Lock ();
2328 bool Unlock ();
2329
2330 protected:
2331 bool m_bInitialized;
2332 #if USE_WINDOWS
2333 HANDLE m_hMutex;
2334 #else
2335 pthread_mutex_t m_tMutex;
2336 #endif
2337 };
2338
2339
2340 /// static mutex (for globals)
2341 class CSphStaticMutex : private CSphMutex
2342 {
2343 public:
CSphStaticMutex()2344 CSphStaticMutex()
2345 {
2346 Verify ( Init() );
2347 }
2348
~CSphStaticMutex()2349 ~CSphStaticMutex()
2350 {
2351 Done();
2352 }
2353
Lock()2354 bool Lock ()
2355 {
2356 return CSphMutex::Lock();
2357 }
2358
Unlock()2359 bool Unlock ()
2360 {
2361 return CSphMutex::Unlock();
2362 }
2363 };
2364
2365
2366 /// scoped mutex lock
2367 template < typename T >
2368 class CSphScopedLock : ISphNoncopyable
2369 {
2370 public:
2371 /// lock on creation
CSphScopedLock(T & tMutex)2372 explicit CSphScopedLock ( T & tMutex )
2373 : m_tMutexRef ( tMutex )
2374 {
2375 m_tMutexRef.Lock();
2376 }
2377
2378 /// unlock on going out of scope
~CSphScopedLock()2379 ~CSphScopedLock ()
2380 {
2381 m_tMutexRef.Unlock ();
2382 }
2383
2384 protected:
2385 T & m_tMutexRef;
2386 };
2387
2388
2389 /// MT-aware refcounted base
2390 /// mutex protected, might be slow
2391 struct ISphRefcountedMT : public ISphNoncopyable
2392 {
2393 protected:
ISphRefcountedMTISphRefcountedMT2394 ISphRefcountedMT ()
2395 : m_iRefCount ( 1 )
2396 {
2397 m_tLock.Init();
2398 }
2399
~ISphRefcountedMTISphRefcountedMT2400 virtual ~ISphRefcountedMT ()
2401 {
2402 m_tLock.Done();
2403 }
2404
2405 public:
AddRefISphRefcountedMT2406 void AddRef () const
2407 {
2408 m_tLock.Lock();
2409 m_iRefCount++;
2410 m_tLock.Unlock();
2411 }
2412
ReleaseISphRefcountedMT2413 void Release () const
2414 {
2415 m_tLock.Lock();
2416 int iRefs = --m_iRefCount;
2417 assert ( iRefs>=0 );
2418 m_tLock.Unlock();
2419 if ( iRefs==0 )
2420 delete this;
2421 }
2422
2423 protected:
2424 mutable int m_iRefCount;
2425 mutable CSphMutex m_tLock;
2426 };
2427
2428
2429 /// rwlock implementation
2430 class CSphRwlock : public ISphNoncopyable
2431 {
2432 public:
2433 CSphRwlock ();
~CSphRwlock()2434 ~CSphRwlock () {}
2435
2436 bool Init ();
2437 bool Done ();
2438
2439 bool ReadLock ();
2440 bool WriteLock ();
2441 bool Unlock ();
2442
2443 private:
2444 bool m_bInitialized;
2445 #if USE_WINDOWS
2446 HANDLE m_hWriteMutex;
2447 HANDLE m_hReadEvent;
2448 LONG m_iReaders;
2449 #else
2450 pthread_rwlock_t m_tLock;
2451 #endif
2452 };
2453
2454 // small bitvector of 256 elements.
2455 class CSphSmallBitvec
2456 {
2457 public:
2458 static const int iTOTALBITS = 256;
2459
2460 private:
2461 static const int iELEMBITS = sizeof(DWORD) * 8;
2462 static const int iBYTESIZE = iTOTALBITS / 8;
2463 static const int IELEMENTS = iTOTALBITS / iELEMBITS;
2464 static const DWORD uALLBITS = (DWORD)(~(0UL));
2465
2466 STATIC_ASSERT ( IELEMENTS>=1, 8_BITS_MINIMAL_SIZE_OF_VECTOR );
2467
2468 public:
2469 DWORD m_dFieldsMask[IELEMENTS];
2470
2471 public:
2472 // no custom cstr and d-tor - to be usable from inside unions
2473 // deep copy for it is ok - so, no explicit copying constructor and operator=
2474
2475 // old-fashion layer to work with DWORD (32-bit) mask.
2476 // all bits above 32 assumed to be unset.
Assign32(DWORD uMask)2477 void Assign32 ( DWORD uMask )
2478 {
2479 Unset();
2480 m_dFieldsMask[0] = uMask;
2481 }
2482
GetMask32()2483 DWORD GetMask32 () const
2484 {
2485 return (DWORD) ( m_dFieldsMask[0] & 0xFFFFFFFFUL );
2486 }
2487
2488 // set n-th bit, or all
2489 void Set ( int iIdx=-1 )
2490 {
2491 assert ( iIdx < iTOTALBITS );
2492 if ( iIdx<0 )
2493 for ( int i=0; i<IELEMENTS; i++ )
2494 m_dFieldsMask[i] = uALLBITS;
2495 else
2496 m_dFieldsMask[iIdx/iELEMBITS] |= 1UL << ( iIdx & ( iELEMBITS-1 ) );
2497 }
2498
2499 // unset n-th bit, or all
2500 void Unset ( int iIdx=-1 )
2501 {
2502 assert ( iIdx < iTOTALBITS );
2503 if ( iIdx<0 )
2504 for ( int i=0; i<IELEMENTS; i++ )
2505 m_dFieldsMask[i] = 0UL;
2506 else
2507 m_dFieldsMask[iIdx/iELEMBITS] &= ~(1UL << ( iIdx & ( iELEMBITS-1 ) ));
2508 }
2509
2510 // test if n-th bit is set
Test(int iIdx)2511 bool Test ( int iIdx ) const
2512 {
2513 assert ( iIdx>=0 && iIdx<iTOTALBITS );
2514 return ( m_dFieldsMask[iIdx/iELEMBITS] & ( 1UL << ( iIdx & ( iELEMBITS-1 ) ) ) )!=0;
2515 }
2516
2517 // test the given mask (with &-operator)
Test(const CSphSmallBitvec & dParam)2518 bool Test ( const CSphSmallBitvec& dParam ) const
2519 {
2520 for ( int i=0; i<IELEMENTS; i++ )
2521 if ( m_dFieldsMask[i] & dParam.m_dFieldsMask[i] )
2522 return true;
2523 return false;
2524 }
2525
2526 // test if all bits are set or unset
TestAll(bool bSet)2527 bool TestAll ( bool bSet ) const
2528 {
2529 DWORD uTest = bSet?uALLBITS:0;
2530 for ( int i=0; i<IELEMENTS; i++ )
2531 if ( m_dFieldsMask[i]!=uTest )
2532 return false;
2533 return true;
2534 }
2535
2536 friend CSphSmallBitvec operator & ( const CSphSmallBitvec& dFirst, const CSphSmallBitvec& dSecond );
2537 friend CSphSmallBitvec operator | ( const CSphSmallBitvec& dFirst, const CSphSmallBitvec& dSecond );
2538 friend bool operator == ( const CSphSmallBitvec& dFirst, const CSphSmallBitvec& dSecond );
2539 CSphSmallBitvec& operator |= ( const CSphSmallBitvec& dSecond )
2540 {
2541 if ( &dSecond!=this )
2542 for ( int i=0; i<IELEMENTS; i++ )
2543 m_dFieldsMask[i] |= dSecond.m_dFieldsMask[i];
2544 return *this;
2545 }
2546
2547 // cut out all the bits over given number
LimitBits(int iBits)2548 void LimitBits ( int iBits )
2549 {
2550 if ( iBits>=iTOTALBITS )
2551 return;
2552
2553 int iMaskPos = iBits / iELEMBITS;
2554 DWORD uMask = ( 1UL << ( iBits % iELEMBITS ) ) - 1;
2555 m_dFieldsMask[iMaskPos++] &= uMask;
2556 for ( ; iMaskPos < IELEMENTS; iMaskPos++ )
2557 m_dFieldsMask[iMaskPos] = 0UL;
2558 }
2559
Negate()2560 void Negate()
2561 {
2562 for ( int i=0; i<IELEMENTS; i++ )
2563 m_dFieldsMask[i] = ~m_dFieldsMask[i];
2564 }
2565 };
2566
2567 #if USE_WINDOWS
2568 #pragma warning(push,1)
2569 #pragma warning(disable:4701)
2570 #endif
2571
2572 inline CSphSmallBitvec operator & ( const CSphSmallBitvec& dFirst, const CSphSmallBitvec& dSecond )
2573 {
2574 if ( &dFirst==&dSecond )
2575 return dFirst;
2576
2577 CSphSmallBitvec dResult;
2578 for ( int i=0; i<CSphSmallBitvec::IELEMENTS; i++ )
2579 dResult.m_dFieldsMask[i] = dFirst.m_dFieldsMask[i] & dSecond.m_dFieldsMask[i];
2580 return dResult;
2581 }
2582
2583 inline CSphSmallBitvec operator | ( const CSphSmallBitvec& dFirst, const CSphSmallBitvec& dSecond )
2584 {
2585 if ( &dFirst==&dSecond )
2586 return dFirst;
2587
2588 CSphSmallBitvec dResult;
2589 for ( int i=0; i<CSphSmallBitvec::IELEMENTS; i++ )
2590 dResult.m_dFieldsMask[i] = dFirst.m_dFieldsMask[i] | dSecond.m_dFieldsMask[i];
2591 return dResult;
2592 }
2593
2594 inline bool operator == ( const CSphSmallBitvec& dFirst, const CSphSmallBitvec& dSecond )
2595 {
2596 if ( &dFirst==&dSecond )
2597 return true;
2598
2599 return !memcmp ( &dFirst.m_dFieldsMask, &dSecond.m_dFieldsMask, CSphSmallBitvec::iBYTESIZE );
2600 }
2601
2602 inline bool operator != ( const CSphSmallBitvec& dFirst, const CSphSmallBitvec& dSecond )
2603 {
2604 return !( dFirst==dSecond );
2605 }
2606
2607 #if USE_WINDOWS
2608 #pragma warning(pop)
2609 #endif
2610
2611 //////////////////////////////////////////////////////////////////////////
2612
2613 /// generic dynamic bitvector
2614 /// with a preallocated part for small-size cases, and a dynamic route for big-size ones
2615 class CSphBitvec
2616 {
2617 protected:
2618 DWORD * m_pData;
2619 DWORD m_uStatic[4];
2620 int m_iElements;
2621
2622 public:
CSphBitvec()2623 CSphBitvec ()
2624 : m_pData ( NULL )
2625 , m_iElements ( 0 )
2626 {}
2627
~CSphBitvec()2628 ~CSphBitvec ()
2629 {
2630 if ( m_pData && m_pData!=m_uStatic )
2631 SafeDeleteArray ( m_pData );
2632 }
2633
Init(int iElements)2634 void Init ( int iElements )
2635 {
2636 assert ( iElements>0 );
2637 m_iElements = iElements;
2638 if ( iElements > int(sizeof(m_uStatic)*8) )
2639 {
2640 int iSize = (m_iElements+31)/32;
2641 m_pData = new DWORD [ iSize ];
2642 memset ( m_pData, 0, sizeof(DWORD)*iSize );
2643 } else
2644 {
2645 m_pData = m_uStatic;
2646 for ( int i=0; i<int(sizeof(m_uStatic)/sizeof(m_uStatic[0])); i++ )
2647 m_uStatic[i] = 0;
2648 }
2649 }
2650
BitGet(int iIndex)2651 bool BitGet ( int iIndex ) const
2652 {
2653 assert ( m_pData );
2654 assert ( iIndex>=0 );
2655 assert ( iIndex<m_iElements );
2656 return ( m_pData [ iIndex>>5 ] & ( 1UL<<( iIndex&31 ) ) )!=0; // NOLINT
2657 }
2658
BitSet(int iIndex)2659 void BitSet ( int iIndex )
2660 {
2661 assert ( iIndex>=0 );
2662 assert ( iIndex<m_iElements );
2663 m_pData [ iIndex>>5 ] |= ( 1UL<<( iIndex&31 ) ); // NOLINT
2664 }
2665 };
2666
2667 #endif // _sphinxstd_
2668
2669 //
2670 // $Id: sphinxstd.h 4113 2013-08-26 07:43:28Z deogar $
2671 //
2672