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