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_tools.hxx" 26 27 #define _TOOLS_TABLE_CXX 28 29 // ----------------------------------------------------------------------- 30 #include <tools/debug.hxx> 31 #include <impcont.hxx> 32 #include <tools/table.hxx> 33 34 // ======================================================================= 35 36 sal_uIntPtr Table::ImplGetIndex( sal_uIntPtr nKey, sal_uIntPtr* pIndex ) const 37 { 38 // Abpruefen, ob der erste Key groesser als der Vergleichskey ist 39 if ( !nCount || (nKey < (sal_uIntPtr)Container::ImpGetObject(0)) ) 40 return TABLE_ENTRY_NOTFOUND; 41 42 sal_uIntPtr nLow; 43 sal_uIntPtr nHigh; 44 sal_uIntPtr nMid; 45 sal_uIntPtr nCompareKey; 46 void** pNodes = Container::ImpGetOnlyNodes(); 47 48 // Binaeres Suchen 49 nLow = 0; 50 nHigh = nCount-1; 51 if ( pNodes ) 52 { 53 do 54 { 55 nMid = (nLow + nHigh) / 2; 56 nCompareKey = (sal_uIntPtr)pNodes[nMid*2]; 57 if ( nKey < nCompareKey ) 58 nHigh = nMid-1; 59 else 60 { 61 if ( nKey > nCompareKey ) 62 nLow = nMid + 1; 63 else 64 return nMid*2; 65 } 66 } 67 while ( nLow <= nHigh ); 68 } 69 else 70 { 71 do 72 { 73 nMid = (nLow + nHigh) / 2; 74 nCompareKey = (sal_uIntPtr)Container::ImpGetObject( nMid*2 ); 75 if ( nKey < nCompareKey ) 76 nHigh = nMid-1; 77 else 78 { 79 if ( nKey > nCompareKey ) 80 nLow = nMid + 1; 81 else 82 return nMid*2; 83 } 84 } 85 while ( nLow <= nHigh ); 86 } 87 88 if ( pIndex ) 89 { 90 if ( nKey > nCompareKey ) 91 *pIndex = (nMid+1)*2; 92 else 93 *pIndex = nMid*2; 94 } 95 96 return TABLE_ENTRY_NOTFOUND; 97 } 98 99 // ======================================================================= 100 101 Table::Table( sal_uInt16 _nInitSize, sal_uInt16 _nReSize ) : 102 Container( CONTAINER_MAXBLOCKSIZE, _nInitSize*2, _nReSize*2 ) 103 { 104 DBG_ASSERT( _nInitSize <= 32767, "Table::Table(): InitSize > 32767" ); 105 DBG_ASSERT( _nReSize <= 32767, "Table::Table(): ReSize > 32767" ); 106 nCount = 0; 107 } 108 109 // ----------------------------------------------------------------------- 110 111 sal_Bool Table::Insert( sal_uIntPtr nKey, void* p ) 112 { 113 // Tabellenelement einsortieren 114 sal_uIntPtr i; 115 if ( nCount ) 116 { 117 if ( nCount <= 24 ) 118 { 119 sal_uInt16 n = 0; 120 sal_uInt16 nTempCount = (sal_uInt16)nCount * 2; 121 //<!--Modified by PengYunQuan for resolving a NULL pointer access 122 123 if( void** pNodes = Container::ImpGetOnlyNodes() ) 124 { 125 sal_uIntPtr nCompareKey = (sal_uIntPtr)(*pNodes); 126 while ( nKey > nCompareKey ) 127 { 128 n += 2; 129 pNodes += 2; 130 if ( n < nTempCount ) 131 nCompareKey = (sal_uIntPtr)(*pNodes); 132 else 133 { 134 nCompareKey = 0; 135 break; 136 } 137 } 138 139 // Testen, ob sich der Key schon in der Tabelle befindet 140 if ( nKey == nCompareKey ) 141 return sal_False; 142 143 i = n; 144 } 145 else 146 { 147 i = 0; 148 if ( ImplGetIndex( nKey, &i ) != TABLE_ENTRY_NOTFOUND ) 149 return sal_False; 150 } 151 //-->Modified by PengYunQuan for resolving a NULL pointer access 152 } 153 else 154 { 155 i = 0; 156 if ( ImplGetIndex( nKey, &i ) != TABLE_ENTRY_NOTFOUND ) 157 return sal_False; 158 } 159 } 160 else 161 i = 0; 162 163 // Eintrag einfuegen (Key vor Pointer) 164 Container::Insert( (void*)nKey, i ); 165 Container::Insert( p, i+1 ); 166 167 // Ein neuer Eintrag 168 nCount++; 169 170 return sal_True; 171 } 172 173 // ----------------------------------------------------------------------- 174 175 void* Table::Remove( sal_uIntPtr nKey ) 176 { 177 // Index besorgen 178 sal_uIntPtr nIndex = ImplGetIndex( nKey ); 179 180 // Testen, ob sich der Key in der Tabelle befindet 181 if ( nIndex == TABLE_ENTRY_NOTFOUND ) 182 return NULL; 183 184 // Itemanzahl erniedrigen 185 nCount--; 186 187 // Key entfernen 188 Container::Remove( nIndex ); 189 190 // Pointer entfernen und zurueckgeben 191 return Container::Remove( nIndex ); 192 } 193 194 // ----------------------------------------------------------------------- 195 196 void* Table::Replace( sal_uIntPtr nKey, void* p ) 197 { 198 // Index abfragen 199 sal_uIntPtr nIndex = ImplGetIndex( nKey ); 200 201 // Existiert kein Eintrag mit dem Schluessel 202 if ( nIndex == TABLE_ENTRY_NOTFOUND ) 203 return NULL; 204 else 205 return Container::Replace( p, nIndex+1 ); 206 } 207 208 // ----------------------------------------------------------------------- 209 210 void* Table::Get( sal_uIntPtr nKey ) const 211 { 212 // Index besorgen 213 sal_uIntPtr nIndex = ImplGetIndex( nKey ); 214 215 // Testen, ob sich der Key in der Tabelle befindet 216 if ( nIndex == TABLE_ENTRY_NOTFOUND ) 217 return NULL; 218 else 219 return Container::ImpGetObject( nIndex+1 ); 220 } 221 222 // ----------------------------------------------------------------------- 223 224 void* Table::GetCurObject() const 225 { 226 return Container::ImpGetObject( Container::GetCurPos()+1 ); 227 } 228 229 // ----------------------------------------------------------------------- 230 231 sal_uIntPtr Table::GetKey( const void* p ) const 232 { 233 sal_uIntPtr nIndex = 0; 234 235 // Solange noch Eintraege Vorhanden sind 236 while ( nIndex < nCount ) 237 { 238 // Stimmt der Pointer ueberein, wird der Key zurueckgegeben 239 if ( p == Container::ImpGetObject( (nIndex*2)+1 ) ) 240 return (sal_uIntPtr)Container::ImpGetObject( nIndex*2 ); 241 242 nIndex++; 243 } 244 245 return TABLE_ENTRY_NOTFOUND; 246 } 247 248 // ----------------------------------------------------------------------- 249 250 sal_Bool Table::IsKeyValid( sal_uIntPtr nKey ) const 251 { 252 return (ImplGetIndex( nKey ) != TABLE_ENTRY_NOTFOUND) ? sal_True : sal_False; 253 } 254 255 // ----------------------------------------------------------------------- 256 257 sal_uIntPtr Table::GetUniqueKey( sal_uIntPtr nStartKey ) const 258 { 259 DBG_ASSERT( (nStartKey > 1) && (nStartKey < 0xFFFFFFFF), 260 "Table::GetUniqueKey() - nStartKey == 0 or nStartKey >= 0xFFFFFFFF" ); 261 262 if ( !nCount ) 263 return nStartKey; 264 265 sal_uIntPtr nLastKey = (sal_uIntPtr)Container::GetObject( (nCount*2)-2 ); 266 if ( nLastKey < nStartKey ) 267 return nStartKey; 268 else 269 { 270 if ( nLastKey < 0xFFFFFFFE ) 271 return nLastKey+1; 272 else 273 { 274 sal_uIntPtr nPos; 275 sal_uIntPtr nTempPos = ImplGetIndex( nStartKey, &nPos ); 276 if ( nTempPos != TABLE_ENTRY_NOTFOUND ) 277 nPos = nTempPos; 278 nLastKey = (sal_uIntPtr)Container::GetObject( nPos ); 279 if ( nStartKey < nLastKey ) 280 return nStartKey; 281 while ( nLastKey < 0xFFFFFFFE ) 282 { 283 nPos += 2; 284 nLastKey++; 285 if ( nLastKey != (sal_uIntPtr)Container::GetObject( nPos ) ) 286 return nLastKey; 287 } 288 } 289 } 290 291 return 0; 292 } 293 294 // ----------------------------------------------------------------------- 295 296 sal_uIntPtr Table::SearchKey( sal_uIntPtr nKey, sal_uIntPtr* pPos ) const 297 { 298 *pPos = 0; 299 sal_uIntPtr nPos = ImplGetIndex( nKey, pPos ); 300 if ( nPos != TABLE_ENTRY_NOTFOUND ) 301 { 302 nPos /= 2; 303 *pPos = nPos; 304 } 305 else 306 *pPos /= 2; 307 return nPos; 308 } 309 310 // ----------------------------------------------------------------------- 311 312 void* Table::Seek( sal_uIntPtr nKey ) 313 { 314 // Testen, ob ein Eintrag vorhanden ist 315 if ( nCount ) 316 { 317 sal_uIntPtr nIndex = ImplGetIndex( nKey ); 318 319 // Ist Key nicht enthalten 320 if ( nIndex == TABLE_ENTRY_NOTFOUND ) 321 return NULL; 322 else 323 { 324 // Index setzen 325 Container::Seek( nIndex ); 326 327 // Pointer zurueckgeben 328 return Container::ImpGetObject( Container::GetCurPos() + 1 ); 329 } 330 } 331 else 332 return NULL; 333 } 334 335 // ----------------------------------------------------------------------- 336 337 void* Table::Seek( void* p ) 338 { 339 sal_uIntPtr nKey = GetKey( p ); 340 341 // Ist Key vorhanden, dann als aktuellen Eintrag setzen 342 if ( nKey != TABLE_ENTRY_NOTFOUND ) 343 return Seek( nKey ); 344 else 345 return NULL; 346 } 347 348 // ----------------------------------------------------------------------- 349 350 void* Table::First() 351 { 352 // Testen, ob ein Eintrag vorhanden ist 353 if ( nCount ) 354 { 355 // Auf ersten Eintag setzen 356 Container::First(); 357 358 // Pointer zurueckgeben 359 return Container::ImpGetObject( 1 ); 360 } 361 else 362 return NULL; 363 } 364 365 // ----------------------------------------------------------------------- 366 367 void* Table::Last() 368 { 369 // Testen, ob ein Eintrag vorhanden ist 370 if ( nCount ) 371 { 372 // Last auf letzten Eintrag setzen 373 void* p = Container::Last(); 374 Container::Prev(); 375 376 // Pointer zurueckgeben 377 return p; 378 } 379 else 380 return NULL; 381 } 382 383 // ----------------------------------------------------------------------- 384 385 void* Table::Next() 386 { 387 // Ueber den Pointer weiterschalten 388 Container::Next(); 389 390 // Nachsten Eintag 391 Container::Next(); 392 393 // Pointer vom naechsten Key zurueckgeben 394 return Container::ImpGetObject( Container::GetCurPos() + 1 ); 395 } 396 397 // ----------------------------------------------------------------------- 398 399 void* Table::Prev() 400 { 401 // Ueber den Pointer weiterschalten 402 void* p = Container::Prev(); 403 404 // Nachsten Eintag 405 Container::Prev(); 406 407 // Pointer vom vorherigen Key zurueckgeben 408 return p; 409 } 410