From 85d5c4af4a9546970b34dd413c473d10fef8534b Mon Sep 17 00:00:00 2001 From: Tom Sepez Date: Tue, 18 Aug 2015 09:20:29 -0700 Subject: FX_CMapDwordToDword considered harmful. Lookups are log(n), but random insertions could result in n^2 behaviour. Replace with maps and sets. R=thestig@chromium.org Review URL: https://codereview.chromium.org/1289703003 . --- core/src/fxcrt/fx_basic_maps.cpp | 68 ---------------------------------------- 1 file changed, 68 deletions(-) (limited to 'core/src/fxcrt') diff --git a/core/src/fxcrt/fx_basic_maps.cpp b/core/src/fxcrt/fx_basic_maps.cpp index 6bcb91546a..380beb6f89 100644 --- a/core/src/fxcrt/fx_basic_maps.cpp +++ b/core/src/fxcrt/fx_basic_maps.cpp @@ -348,71 +348,3 @@ int CFX_CMapByteStringToPtr::GetCount() const { } return count; } -extern "C" { -static int _CompareDWord(const void* p1, const void* p2) { - return (*(FX_DWORD*)p1) - (*(FX_DWORD*)p2); -} -}; -struct _DWordPair { - FX_DWORD key; - FX_DWORD value; -}; -FX_BOOL CFX_CMapDWordToDWord::Lookup(FX_DWORD key, FX_DWORD& value) const { - void* pResult = FXSYS_bsearch(&key, m_Buffer.GetBuffer(), - m_Buffer.GetSize() / sizeof(_DWordPair), - sizeof(_DWordPair), _CompareDWord); - if (pResult == NULL) { - return FALSE; - } - value = ((FX_DWORD*)pResult)[1]; - return TRUE; -} -FX_POSITION CFX_CMapDWordToDWord::GetStartPosition() const { - FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); - if (count == 0) { - return NULL; - } - return (FX_POSITION)1; -} -void CFX_CMapDWordToDWord::GetNextAssoc(FX_POSITION& pos, - FX_DWORD& key, - FX_DWORD& value) const { - if (pos == 0) { - return; - } - FX_DWORD index = ((FX_DWORD)(uintptr_t)pos) - 1; - FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); - _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer(); - key = buf[index].key; - value = buf[index].value; - if (index == count - 1) { - pos = 0; - } else { - pos = (FX_POSITION)((uintptr_t)pos + 1); - } -} -void CFX_CMapDWordToDWord::SetAt(FX_DWORD key, FX_DWORD value) { - FX_DWORD count = m_Buffer.GetSize() / sizeof(_DWordPair); - _DWordPair* buf = (_DWordPair*)m_Buffer.GetBuffer(); - _DWordPair pair = {key, value}; - if (count == 0 || key > buf[count - 1].key) { - m_Buffer.AppendBlock(&pair, sizeof(_DWordPair)); - return; - } - int low = 0, high = count - 1; - while (low <= high) { - int mid = (low + high) / 2; - if (buf[mid].key < key) { - low = mid + 1; - } else if (buf[mid].key > key) { - high = mid - 1; - } else { - buf[mid].value = value; - return; - } - } - m_Buffer.InsertBlock(low * sizeof(_DWordPair), &pair, sizeof(_DWordPair)); -} -void CFX_CMapDWordToDWord::EstimateSize(FX_DWORD size, FX_DWORD grow_by) { - m_Buffer.EstimateSize(size, grow_by); -} -- cgit v1.2.3