xref: /aoo4110/main/svl/source/memtools/svarray.cxx (revision b1cdbd2c)
1 /**************************************************************
2  *
3  * Licensed to the Apache Software Foundation (ASF) under one
4  * or more contributor license agreements.  See the NOTICE file
5  * distributed with this work for additional information
6  * regarding copyright ownership.  The ASF licenses this file
7  * to you under the Apache License, Version 2.0 (the
8  * "License"); you may not use this file except in compliance
9  * with the License.  You may obtain a copy of the License at
10  *
11  *   http://www.apache.org/licenses/LICENSE-2.0
12  *
13  * Unless required by applicable law or agreed to in writing,
14  * software distributed under the License is distributed on an
15  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16  * KIND, either express or implied.  See the License for the
17  * specific language governing permissions and limitations
18  * under the License.
19  *
20  *************************************************************/
21 
22 
23 
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_svl.hxx"
26 
27 #define _SVARRAY_CXX
28 
29 #define _SVSTDARR_BOOLS
30 #define _SVSTDARR_BYTES
31 #define _SVSTDARR_ULONGS
32 #define _SVSTDARR_ULONGSSORT
33 #define _SVSTDARR_USHORTS
34 #define _SVSTDARR_LONGS
35 #define _SVSTDARR_LONGSSORT
36 #define _SVSTDARR_SHORTS
37 #define _SVSTDARR_STRINGS
38 #define _SVSTDARR_STRINGSDTOR
39 #define _SVSTDARR_STRINGSSORT
40 #define _SVSTDARR_STRINGSSORTDTOR
41 #define _SVSTDARR_STRINGSISORT
42 #define _SVSTDARR_STRINGSISORTDTOR
43 #define _SVSTDARR_USHORTSSORT
44 
45 #define _SVSTDARR_BYTESTRINGS
46 #define _SVSTDARR_BYTESTRINGSDTOR
47 #define _SVSTDARR_BYTESTRINGSSORT
48 #define _SVSTDARR_BYTESTRINGSSORTDTOR
49 #define _SVSTDARR_BYTESTRINGSISORT
50 #define _SVSTDARR_BYTESTRINGSISORTDTOR
51 
52 #define _SVSTDARR_XUB_STRLEN
53 #define _SVSTDARR_XUB_STRLENSORT
54 
55 #include <svl/svstdarr.hxx>
56 #include <tools/string.hxx>
57 #include <tools/debug.hxx>
58 
SV_IMPL_VARARR(SvPtrarr,VoidPtr)59 SV_IMPL_VARARR(SvPtrarr,VoidPtr)
60 
61 sal_uInt16 SvPtrarr::GetPos( const VoidPtr& aElement ) const
62 {	sal_uInt16 n;
63 	for( n=0; n < nA && *(GetData()+n) != aElement; ) n++;
64 	return ( n >= nA ? USHRT_MAX : n );
65 }
66 
SV_IMPL_VARARR(SvULongs,sal_uLong)67 SV_IMPL_VARARR( SvULongs, sal_uLong )
68 SV_IMPL_VARARR( SvUShorts, sal_uInt16 )
69 SV_IMPL_VARARR( SvLongs, long)
70 
71 SV_IMPL_VARARR_SORT( SvULongsSort, sal_uLong )
72 SV_IMPL_VARARR_SORT( SvLongsSort, long )
73 
74 SV_IMPL_PTRARR( SvStrings, StringPtr )
75 SV_IMPL_PTRARR( SvStringsDtor, StringPtr )
76 SV_IMPL_OP_PTRARR_SORT( SvStringsSort, StringPtr )
77 SV_IMPL_OP_PTRARR_SORT( SvStringsSortDtor, StringPtr )
78 
79 SV_IMPL_PTRARR( SvByteStrings, ByteStringPtr )
80 SV_IMPL_PTRARR( SvByteStringsDtor, ByteStringPtr )
81 SV_IMPL_OP_PTRARR_SORT( SvByteStringsSort, ByteStringPtr )
82 SV_IMPL_OP_PTRARR_SORT( SvByteStringsSortDtor, ByteStringPtr )
83 
84 
85 
86 // ---------------- strings -------------------------------------
87 
88 // Array mit anderer Seek-Methode!
89 _SV_IMPL_SORTAR_ALG( SvStringsISort, StringPtr )
90 void SvStringsISort::DeleteAndDestroy( sal_uInt16 nP, sal_uInt16 nL )
91 {
92 	if( nL )
93 	{
94 		DBG_ASSERT( nP < nA && nP + nL <= nA, "ERR_VAR_DEL" );
95 		for( sal_uInt16 n=nP; n < nP + nL; n++ )
96 			delete *((StringPtr*)pData+n);
97 		SvPtrarr::Remove( nP, nL );
98 	}
99 }
Seek_Entry(const StringPtr aE,sal_uInt16 * pP) const100 sal_Bool SvStringsISort::Seek_Entry( const StringPtr aE, sal_uInt16* pP ) const
101 {
102 	register sal_uInt16 nO  = SvStringsISort_SAR::Count(),
103 			nM,
104 			nU = 0;
105 	if( nO > 0 )
106 	{
107 		nO--;
108 		while( nU <= nO )
109 		{
110 			nM = nU + ( nO - nU ) / 2;
111 			StringCompare eCmp = (*((StringPtr*)pData + nM))->
112 										CompareIgnoreCaseToAscii( *(aE) );
113 			if( COMPARE_EQUAL == eCmp )
114 			{
115 				if( pP ) *pP = nM;
116 				return sal_True;
117 			}
118 			else if( COMPARE_LESS == eCmp )
119 				nU = nM + 1;
120 			else if( nM == 0 )
121 			{
122 				if( pP ) *pP = nU;
123 				return sal_False;
124 			}
125 			else
126 				nO = nM - 1;
127 		}
128 	}
129 	if( pP ) *pP = nU;
130 	return sal_False;
131 }
132 
133 // ---------------- strings -------------------------------------
134 
135 // Array mit anderer Seek-Methode!
_SV_IMPL_SORTAR_ALG(SvStringsISortDtor,StringPtr)136 _SV_IMPL_SORTAR_ALG( SvStringsISortDtor, StringPtr )
137 void SvStringsISortDtor::DeleteAndDestroy( sal_uInt16 nP, sal_uInt16 nL )
138 {
139 	if( nL )
140 	{
141 		DBG_ASSERT( nP < nA && nP + nL <= nA, "ERR_VAR_DEL" );
142 		for( sal_uInt16 n=nP; n < nP + nL; n++ )
143 			delete *((StringPtr*)pData+n);
144 		SvPtrarr::Remove( nP, nL );
145 	}
146 }
Seek_Entry(const StringPtr aE,sal_uInt16 * pP) const147 sal_Bool SvStringsISortDtor::Seek_Entry( const StringPtr aE, sal_uInt16* pP ) const
148 {
149 	register sal_uInt16 nO  = SvStringsISortDtor_SAR::Count(),
150 			nM,
151 			nU = 0;
152 	if( nO > 0 )
153 	{
154 		nO--;
155 		while( nU <= nO )
156 		{
157 			nM = nU + ( nO - nU ) / 2;
158 			StringCompare eCmp = (*((StringPtr*)pData + nM))->
159 									CompareIgnoreCaseToAscii( *(aE) );
160 			if( COMPARE_EQUAL == eCmp )
161 			{
162 				if( pP ) *pP = nM;
163 				return sal_True;
164 			}
165 			else if( COMPARE_LESS == eCmp )
166 				nU = nM + 1;
167 			else if( nM == 0 )
168 			{
169 				if( pP ) *pP = nU;
170 				return sal_False;
171 			}
172 			else
173 				nO = nM - 1;
174 		}
175 	}
176 	if( pP ) *pP = nU;
177 	return sal_False;
178 }
179 
180 // ---------------- Ushorts -------------------------------------
181 
182 /* SortArray fuer UShorts */
Seek_Entry(const sal_uInt16 aE,sal_uInt16 * pP) const183 sal_Bool SvUShortsSort::Seek_Entry( const sal_uInt16 aE, sal_uInt16* pP ) const
184 {
185 	register sal_uInt16 nO  = SvUShorts::Count(),
186 			nM,
187 			nU = 0;
188 	if( nO > 0 )
189 	{
190 		nO--;
191 		while( nU <= nO )
192 		{
193 			nM = nU + ( nO - nU ) / 2;
194 			if( *(pData + nM) == aE )
195 			{
196 				if( pP ) *pP = nM;
197 				return sal_True;
198 			}
199 			else if( *(pData + nM) < aE )
200 				nU = nM + 1;
201 			else if( nM == 0 )
202 			{
203 				if( pP ) *pP = nU;
204 				return sal_False;
205 			}
206 			else
207 				nO = nM - 1;
208 		}
209 	}
210 	if( pP ) *pP = nU;
211 	return sal_False;
212 }
213 
Insert(const SvUShortsSort * pI,sal_uInt16 nS,sal_uInt16 nE)214 void SvUShortsSort::Insert( const SvUShortsSort * pI, sal_uInt16 nS, sal_uInt16 nE )
215 {
216 	if( USHRT_MAX == nE )
217 		nE = pI->Count();
218 	sal_uInt16 nP;
219 	const sal_uInt16 * pIArr = pI->GetData();
220 	for( ; nS < nE; ++nS )
221 	{
222 		if( ! Seek_Entry( *(pIArr+nS), &nP) )
223 				SvUShorts::Insert( *(pIArr+nS), nP );
224 		if( ++nP >= Count() )
225 		{
226 			SvUShorts::Insert( pI, nP, nS+1, nE );
227 			nS = nE;
228 		}
229 	}
230 }
231 
Insert(const sal_uInt16 aE)232 sal_Bool SvUShortsSort::Insert( const sal_uInt16 aE )
233 {
234 	sal_uInt16 nP;
235 	sal_Bool bExist = Seek_Entry( aE, &nP );
236 	if( !bExist )
237 		SvUShorts::Insert( aE, nP );
238 	return !bExist;
239 }
240 
Insert(const sal_uInt16 aE,sal_uInt16 & rP)241 sal_Bool SvUShortsSort::Insert( const sal_uInt16 aE, sal_uInt16& rP )
242 {
243 	sal_Bool bExist = Seek_Entry( aE, &rP );
244 	if( !bExist )
245 		SvUShorts::Insert( aE, rP );
246 	return !bExist;
247 }
248 
Insert(const sal_uInt16 * pE,sal_uInt16 nL)249 void SvUShortsSort::Insert( const sal_uInt16* pE, sal_uInt16 nL)
250 {
251 	sal_uInt16 nP;
252 	for( sal_uInt16 n = 0; n < nL; ++n )
253 		if( ! Seek_Entry( *(pE+n), &nP ))
254 			SvUShorts::Insert( *(pE+n), nP );
255 }
256 
257 // remove ab Pos
RemoveAt(const sal_uInt16 nP,sal_uInt16 nL)258 void SvUShortsSort::RemoveAt( const sal_uInt16 nP, sal_uInt16 nL )
259 {
260 	if( nL )
261 		SvUShorts::Remove( nP, nL);
262 }
263 
264 // remove ab dem Eintrag
Remove(const sal_uInt16 aE,sal_uInt16 nL)265 void SvUShortsSort::Remove( const sal_uInt16 aE, sal_uInt16 nL )
266 {
267 	sal_uInt16 nP;
268 	if( nL && Seek_Entry( aE, &nP ) )
269 		SvUShorts::Remove( nP, nL);
270 }
271 
272 // ---------------- bytestrings -------------------------------------
273 
274 // Array mit anderer Seek-Methode!
_SV_IMPL_SORTAR_ALG(SvByteStringsISort,ByteStringPtr)275 _SV_IMPL_SORTAR_ALG( SvByteStringsISort, ByteStringPtr )
276 void SvByteStringsISort::DeleteAndDestroy( sal_uInt16 nP, sal_uInt16 nL )
277 {
278 	if( nL )
279 	{
280 		DBG_ASSERT( nP < nA && nP + nL <= nA, "ERR_VAR_DEL" );
281 		for( sal_uInt16 n=nP; n < nP + nL; n++ )
282 			delete *((ByteStringPtr*)pData+n);
283 		SvPtrarr::Remove( nP, nL );
284 	}
285 }
Seek_Entry(const ByteStringPtr aE,sal_uInt16 * pP) const286 sal_Bool SvByteStringsISort::Seek_Entry( const ByteStringPtr aE, sal_uInt16* pP ) const
287 {
288 	register sal_uInt16 nO  = SvByteStringsISort_SAR::Count(),
289 			nM,
290 			nU = 0;
291 	if( nO > 0 )
292 	{
293 		nO--;
294 		while( nU <= nO )
295 		{
296 			nM = nU + ( nO - nU ) / 2;
297 			StringCompare eCmp = (*((ByteStringPtr*)pData + nM))->
298 						CompareIgnoreCaseToAscii( *(aE) );
299 			if( COMPARE_EQUAL == eCmp )
300 			{
301 				if( pP ) *pP = nM;
302 				return sal_True;
303 			}
304 			else if( COMPARE_LESS == eCmp )
305 				nU = nM + 1;
306 			else if( nM == 0 )
307 			{
308 				if( pP ) *pP = nU;
309 				return sal_False;
310 			}
311 			else
312 				nO = nM - 1;
313 		}
314 	}
315 	if( pP ) *pP = nU;
316 	return sal_False;
317 }
318 
319 
320 // Array mit anderer Seek-Methode!
_SV_IMPL_SORTAR_ALG(SvByteStringsISortDtor,ByteStringPtr)321 _SV_IMPL_SORTAR_ALG( SvByteStringsISortDtor, ByteStringPtr )
322 void SvByteStringsISortDtor::DeleteAndDestroy( sal_uInt16 nP, sal_uInt16 nL )
323 {
324 	if( nL )
325 	{
326 		DBG_ASSERT( nP < nA && nP + nL <= nA, "ERR_VAR_DEL" );
327 		for( sal_uInt16 n=nP; n < nP + nL; n++ )
328 			delete *((ByteStringPtr*)pData+n);
329 		SvPtrarr::Remove( nP, nL );
330 	}
331 }
Seek_Entry(const ByteStringPtr aE,sal_uInt16 * pP) const332 sal_Bool SvByteStringsISortDtor::Seek_Entry( const ByteStringPtr aE, sal_uInt16* pP ) const
333 {
334 	register sal_uInt16 nO  = SvByteStringsISortDtor_SAR::Count(),
335 			nM,
336 			nU = 0;
337 	if( nO > 0 )
338 	{
339 		nO--;
340 		while( nU <= nO )
341 		{
342 			nM = nU + ( nO - nU ) / 2;
343 			StringCompare eCmp = (*((ByteStringPtr*)pData + nM))->
344 									CompareIgnoreCaseToAscii( *(aE) );
345 			if( COMPARE_EQUAL == eCmp )
346 			{
347 				if( pP ) *pP = nM;
348 				return sal_True;
349 			}
350 			else if( COMPARE_LESS == eCmp )
351 				nU = nM + 1;
352 			else if( nM == 0 )
353 			{
354 				if( pP ) *pP = nU;
355 				return sal_False;
356 			}
357 			else
358 				nO = nM - 1;
359 		}
360 	}
361 	if( pP ) *pP = nU;
362 	return sal_False;
363 }
364 
365