--- a/accessible/base/ARIAMap.cpp
+++ b/accessible/base/ARIAMap.cpp
@@ -10,16 +10,18 @@
#include "nsAccUtils.h"
#include "nsCoreUtils.h"
#include "Role.h"
#include "States.h"
#include "nsAttrName.h"
#include "nsWhitespaceTokenizer.h"
+#include "mozilla/BinarySearch.h"
+
using namespace mozilla;
using namespace mozilla::a11y;
using namespace mozilla::a11y::aria;
static const uint32_t kGenericAccType = 0;
/**
* This list of WAI-defined roles are currently hardcoded.
@@ -727,44 +729,49 @@ static const AttrCharacteristics gWAIUni
{&nsGkAtoms::aria_setsize, ATTR_BYPASSOBJ }, /* handled via groupPosition */
{&nsGkAtoms::aria_sort, ATTR_VALTOKEN },
{&nsGkAtoms::aria_valuenow, ATTR_BYPASSOBJ },
{&nsGkAtoms::aria_valuemin, ATTR_BYPASSOBJ },
{&nsGkAtoms::aria_valuemax, ATTR_BYPASSOBJ },
{&nsGkAtoms::aria_valuetext, ATTR_BYPASSOBJ }
};
+namespace {
+
+struct RoleComparator
+{
+ const nsDependentSubstring& mRole;
+ RoleComparator(const nsDependentSubstring& aRole) : mRole(aRole) {}
+ int operator()(const nsRoleMapEntry& aEntry) const {
+ return Compare(mRole, aEntry.ARIARoleString());
+ }
+};
+
+}
+
nsRoleMapEntry*
aria::GetRoleMap(nsINode* aNode)
{
nsIContent* content = nsCoreUtils::GetRoleContent(aNode);
nsAutoString roles;
if (!content ||
!content->GetAttr(kNameSpaceID_None, nsGkAtoms::role, roles) ||
roles.IsEmpty()) {
// We treat role="" as if the role attribute is absent (per aria spec:8.1.1)
return nullptr;
}
nsWhitespaceTokenizer tokenizer(roles);
while (tokenizer.hasMoreTokens()) {
// Do a binary search through table for the next role in role list
const nsDependentSubstring role = tokenizer.nextToken();
- uint32_t low = 0;
- uint32_t high = ArrayLength(sWAIRoleMaps);
- while (low < high) {
- uint32_t idx = (low + high) / 2;
- int32_t compare = Compare(role, sWAIRoleMaps[idx].ARIARoleString());
- if (compare == 0)
- return sWAIRoleMaps + idx;
-
- if (compare < 0)
- high = idx;
- else
- low = idx + 1;
+ size_t idx;
+ if (BinarySearchIf(sWAIRoleMaps, 0, ArrayLength(sWAIRoleMaps),
+ RoleComparator(role), &idx)) {
+ return sWAIRoleMaps + idx;
}
}
// Always use some entry if there is a non-empty role string
// To ensure an accessible object is created
return &sLandmarkRoleMap;
}
--- a/accessible/generic/HyperTextAccessible.cpp
+++ b/accessible/generic/HyperTextAccessible.cpp
@@ -26,16 +26,17 @@
#include "nsFrameSelection.h"
#include "nsILineIterator.h"
#include "nsIInterfaceRequestorUtils.h"
#include "nsIPersistentProperties2.h"
#include "nsIScrollableFrame.h"
#include "nsIServiceManager.h"
#include "nsITextControlElement.h"
#include "nsTextFragment.h"
+#include "mozilla/BinarySearch.h"
#include "mozilla/dom/Element.h"
#include "mozilla/EventStates.h"
#include "mozilla/dom/Selection.h"
#include "mozilla/MathAlgorithms.h"
#include "gfxSkipChars.h"
#include <algorithm>
using namespace mozilla;
@@ -1846,35 +1847,27 @@ HyperTextAccessible::GetChildOffset(uint
return mOffsets[aChildIndex - 1];
}
int32_t
HyperTextAccessible::GetChildIndexAtOffset(uint32_t aOffset) const
{
uint32_t lastOffset = 0;
- uint32_t offsetCount = mOffsets.Length();
+ const uint32_t offsetCount = mOffsets.Length();
+
if (offsetCount > 0) {
lastOffset = mOffsets[offsetCount - 1];
if (aOffset < lastOffset) {
- uint32_t low = 0, high = offsetCount;
- while (high > low) {
- uint32_t mid = (high + low) >> 1;
- if (mOffsets[mid] == aOffset)
- return mid < offsetCount - 1 ? mid + 1 : mid;
+ size_t index;
+ if (BinarySearch(mOffsets, 0, offsetCount, aOffset, &index)) {
+ return (index < (offsetCount - 1)) ? index + 1 : index;
+ }
- if (mOffsets[mid] < aOffset)
- low = mid + 1;
- else
- high = mid;
- }
- if (high == offsetCount)
- return -1;
-
- return low;
+ return (index == offsetCount) ? -1 : index;
}
}
uint32_t childCount = ChildCount();
while (mOffsets.Length() < childCount) {
Accessible* child = GetChildAt(mOffsets.Length());
lastOffset += nsAccUtils::TextLength(child);
mOffsets.AppendElement(lastOffset);
--- a/content/base/src/nsDocument.cpp
+++ b/content/base/src/nsDocument.cpp
@@ -7,16 +7,17 @@
/*
* Base class for all our document implementations.
*/
#include "nsDocument.h"
#include "mozilla/ArrayUtils.h"
#include "mozilla/AutoRestore.h"
+#include "mozilla/BinarySearch.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/Likely.h"
#include <algorithm>
#ifdef MOZ_LOGGING
// so we can get logging even in release builds
#define FORCE_PR_LOG 1
@@ -544,16 +545,36 @@ nsIdentifierMapEntry::FireChangeCallback
{
if (!mChangeCallbacks)
return;
FireChangeArgs args = { aOldElement, aNewElement, aImageOnly, !!mImageElement };
mChangeCallbacks->EnumerateEntries(FireChangeEnumerator, &args);
}
+namespace {
+
+struct PositionComparator
+{
+ Element* const mElement;
+ PositionComparator(Element* const aElement) : mElement(aElement) {}
+
+ int operator()(void* aElement) const {
+ Element* curElement = static_cast<Element*>(aElement);
+ if (mElement == curElement) {
+ return 0;
+ }
+ if (nsContentUtils::PositionIsBefore(mElement, curElement)) {
+ return -1;
+ }
+ return 1;
+ }
+};
+} // namespace
+
bool
nsIdentifierMapEntry::AddIdElement(Element* aElement)
{
NS_PRECONDITION(aElement, "Must have element");
NS_PRECONDITION(mIdContentList.IndexOf(nullptr) < 0,
"Why is null in our list?");
#ifdef DEBUG
@@ -567,43 +588,30 @@ nsIdentifierMapEntry::AddIdElement(Eleme
return false;
NS_ASSERTION(currentElement == nullptr, "How did that happen?");
FireChangeCallbacks(nullptr, aElement);
return true;
}
// We seem to have multiple content nodes for the same id, or XUL is messing
// with us. Search for the right place to insert the content.
- int32_t start = 0;
- int32_t end = mIdContentList.Count();
- do {
- NS_ASSERTION(start < end, "Bogus start/end");
-
- int32_t cur = (start + end) / 2;
- NS_ASSERTION(cur >= start && cur < end, "What happened here?");
-
- Element* curElement = static_cast<Element*>(mIdContentList[cur]);
- if (curElement == aElement) {
- // Already in the list, so already in the right spot. Get out of here.
- // XXXbz this only happens because XUL does all sorts of random
- // UpdateIdTableEntry calls. Hate, hate, hate!
- return true;
- }
-
- if (nsContentUtils::PositionIsBefore(aElement, curElement)) {
- end = cur;
- } else {
- start = cur + 1;
- }
- } while (start != end);
-
- if (!mIdContentList.InsertElementAt(aElement, start))
+
+ size_t idx;
+ if (BinarySearchIf(mIdContentList, 0, mIdContentList.Count(),
+ PositionComparator(aElement), &idx)) {
+ // Already in the list, so already in the right spot. Get out of here.
+ // XXXbz this only happens because XUL does all sorts of random
+ // UpdateIdTableEntry calls. Hate, hate, hate!
+ return true;
+ }
+
+ if (!mIdContentList.InsertElementAt(aElement, idx))
return false;
- if (start == 0) {
+ if (idx == 0) {
Element* oldElement =
static_cast<Element*>(mIdContentList.SafeElementAt(1));
NS_ASSERTION(currentElement == oldElement, "How did that happen?");
FireChangeCallbacks(oldElement, aElement);
}
return true;
}
--- a/content/base/src/nsPlainTextSerializer.cpp
+++ b/content/base/src/nsPlainTextSerializer.cpp
@@ -16,16 +16,17 @@
#include "nsNameSpaceManager.h"
#include "nsTextFragment.h"
#include "nsContentUtils.h"
#include "nsReadableUtils.h"
#include "nsUnicharUtils.h"
#include "nsCRT.h"
#include "mozilla/dom/Element.h"
#include "mozilla/Preferences.h"
+#include "mozilla/BinarySearch.h"
using namespace mozilla;
using namespace mozilla::dom;
#define PREF_STRUCTS "converter.html2txt.structs"
#define PREF_HEADER_STRATEGY "converter.html2txt.header_strategy"
static const int32_t kTabSize=4;
@@ -1856,23 +1857,46 @@ int32_t HeaderLevel(nsIAtom* aTag)
* - All remaining characters (including all printable
* ISO 8859-1 and WGL4 characters, Unicode control characters,
* etc.) have a column width of 1.
*
* This implementation assumes that wchar_t characters are encoded
* in ISO 10646.
*/
+namespace {
+
+struct interval
+{
+ uint16_t first;
+ uint16_t last;
+};
+
+struct CombiningComparator
+{
+ const char16_t mUcs;
+ CombiningComparator(char16_t ucs) : mUcs(ucs) {}
+ int operator()(const interval& combining) const {
+ if (mUcs > combining.last)
+ return 1;
+ if (mUcs < combining.first)
+ return -1;
+
+ MOZ_ASSERT(combining.first <= mUcs);
+ MOZ_ASSERT(mUcs <= combining.last);
+ return 0;
+ }
+};
+
+} // namespace
+
int32_t GetUnicharWidth(char16_t ucs)
{
/* sorted list of non-overlapping intervals of non-spacing characters */
- static const struct interval {
- uint16_t first;
- uint16_t last;
- } combining[] = {
+ static const interval combining[] = {
{ 0x0300, 0x034E }, { 0x0360, 0x0362 }, { 0x0483, 0x0486 },
{ 0x0488, 0x0489 }, { 0x0591, 0x05A1 }, { 0x05A3, 0x05B9 },
{ 0x05BB, 0x05BD }, { 0x05BF, 0x05BF }, { 0x05C1, 0x05C2 },
{ 0x05C4, 0x05C4 }, { 0x064B, 0x0655 }, { 0x0670, 0x0670 },
{ 0x06D6, 0x06E4 }, { 0x06E7, 0x06E8 }, { 0x06EA, 0x06ED },
{ 0x0711, 0x0711 }, { 0x0730, 0x074A }, { 0x07A6, 0x07B0 },
{ 0x0901, 0x0902 }, { 0x093C, 0x093C }, { 0x0941, 0x0948 },
{ 0x094D, 0x094D }, { 0x0951, 0x0954 }, { 0x0962, 0x0963 },
@@ -1895,39 +1919,32 @@ int32_t GetUnicharWidth(char16_t ucs)
{ 0x0F71, 0x0F7E }, { 0x0F80, 0x0F84 }, { 0x0F86, 0x0F87 },
{ 0x0F90, 0x0F97 }, { 0x0F99, 0x0FBC }, { 0x0FC6, 0x0FC6 },
{ 0x102D, 0x1030 }, { 0x1032, 0x1032 }, { 0x1036, 0x1037 },
{ 0x1039, 0x1039 }, { 0x1058, 0x1059 }, { 0x17B7, 0x17BD },
{ 0x17C6, 0x17C6 }, { 0x17C9, 0x17D3 }, { 0x18A9, 0x18A9 },
{ 0x20D0, 0x20E3 }, { 0x302A, 0x302F }, { 0x3099, 0x309A },
{ 0xFB1E, 0xFB1E }, { 0xFE20, 0xFE23 }
};
- int32_t min = 0;
- int32_t max = sizeof(combining) / sizeof(struct interval) - 1;
- int32_t mid;
/* test for 8-bit control characters */
if (ucs == 0)
return 0;
if (ucs < 32 || (ucs >= 0x7f && ucs < 0xa0))
return -1;
/* first quick check for Latin-1 etc. characters */
if (ucs < combining[0].first)
return 1;
/* binary search in table of non-spacing characters */
- while (max >= min) {
- mid = (min + max) / 2;
- if (combining[mid].last < ucs)
- min = mid + 1;
- else if (combining[mid].first > ucs)
- max = mid - 1;
- else if (combining[mid].first <= ucs && combining[mid].last >= ucs)
- return 0;
+ size_t idx;
+ if (BinarySearchIf(combining, 0, ArrayLength(combining),
+ CombiningComparator(ucs), &idx)) {
+ return 0;
}
/* if we arrive here, ucs is not a combining or C0/C1 control character */
/* fast test for majority of non-wide scripts */
if (ucs < 0x1100)
return 1;
--- a/content/html/content/src/HTMLFormElement.cpp
+++ b/content/html/content/src/HTMLFormElement.cpp
@@ -25,16 +25,17 @@
#include "nsContentUtils.h"
#include "nsInterfaceHashtable.h"
#include "nsContentList.h"
#include "nsCOMArray.h"
#include "nsAutoPtr.h"
#include "nsTArray.h"
#include "nsIMutableArray.h"
#include "nsIFormAutofillContentService.h"
+#include "mozilla/BinarySearch.h"
// form submission
#include "nsIFormSubmitObserver.h"
#include "nsIObserverService.h"
#include "nsICategoryManager.h"
#include "nsCategoryManagerUtils.h"
#include "nsISimpleEnumerator.h"
#include "nsRange.h"
@@ -1066,27 +1067,42 @@ HTMLFormElement::PostPasswordEvent()
}
mFormPasswordEventDispatcher =
new FormPasswordEventDispatcher(this,
NS_LITERAL_STRING("DOMFormHasPassword"));
mFormPasswordEventDispatcher->PostDOMEvent();
}
+namespace {
+
+struct FormComparator
+{
+ Element* const mChild;
+ HTMLFormElement* const mForm;
+ FormComparator(Element* aChild, HTMLFormElement* aForm)
+ : mChild(aChild), mForm(aForm) {}
+ int operator()(Element* aElement) const {
+ return HTMLFormElement::CompareFormControlPosition(mChild, aElement, mForm);
+ }
+};
+
+} // namespace
+
// This function return true if the element, once appended, is the last one in
// the array.
template<typename ElementType>
static bool
AddElementToList(nsTArray<ElementType*>& aList, ElementType* aChild,
HTMLFormElement* aForm)
{
NS_ASSERTION(aList.IndexOf(aChild) == aList.NoIndex,
"aChild already in aList");
- uint32_t count = aList.Length();
+ const uint32_t count = aList.Length();
ElementType* element;
bool lastElement = false;
// Optimize most common case where we insert at the end.
int32_t position = -1;
if (count > 0) {
element = aList[count - 1];
position =
@@ -1097,33 +1113,21 @@ AddElementToList(nsTArray<ElementType*>&
// empty, we append to the end. Otherwise, we do a binary search to
// determine where the element should go.
if (position >= 0 || count == 0) {
// WEAK - don't addref
aList.AppendElement(aChild);
lastElement = true;
}
else {
- int32_t low = 0, mid, high;
- high = count - 1;
-
- while (low <= high) {
- mid = (low + high) / 2;
-
- element = aList[mid];
- position =
- HTMLFormElement::CompareFormControlPosition(aChild, element, aForm);
- if (position >= 0)
- low = mid + 1;
- else
- high = mid - 1;
- }
+ size_t idx;
+ BinarySearchIf(aList, 0, count, FormComparator(aChild, aForm), &idx);
// WEAK - don't addref
- aList.InsertElementAt(low, aChild);
+ aList.InsertElementAt(idx, aChild);
}
return lastElement;
}
nsresult
HTMLFormElement::AddElement(nsGenericHTMLFormElement* aChild,
bool aUpdateValidity, bool aNotify)
@@ -2229,16 +2233,45 @@ HTMLFormElement::Clear()
for (int32_t i = mImageElements.Length() - 1; i >= 0; i--) {
mImageElements[i]->ClearForm(false);
}
mImageElements.Clear();
mImageNameLookupTable.Clear();
mPastNameLookupTable.Clear();
}
+namespace {
+
+struct PositionComparator
+{
+ nsIContent* const mElement;
+ PositionComparator(nsIContent* const element) : mElement(element) {}
+
+ int operator()(nsIContent* aElement) const {
+ if (mElement == aElement) {
+ return 0;
+ }
+ if (nsContentUtils::PositionIsBefore(mElement, aElement)) {
+ return -1;
+ }
+ return 1;
+ }
+};
+
+struct NodeListAdaptor
+{
+ nsINodeList* const mList;
+ NodeListAdaptor(nsINodeList* aList) : mList(aList) {}
+ nsIContent* operator[](size_t aIdx) const {
+ return mList->Item(aIdx);
+ }
+};
+
+} // namespace
+
nsresult
HTMLFormElement::AddElementToTableInternal(
nsInterfaceHashtable<nsStringHashKey,nsISupports>& aTable,
nsIContent* aChild, const nsAString& aName)
{
nsCOMPtr<nsISupports> supports;
aTable.Get(aName, getter_AddRefs(supports));
@@ -2300,34 +2333,23 @@ HTMLFormElement::AddElementToTableIntern
return NS_OK;
}
// If a control has a name equal to its id, it could be in the
// list already.
if (list->IndexOf(aChild) != -1) {
return NS_OK;
}
-
- // first is the first possible insertion index, last is the last possible
- // insertion index
- uint32_t first = 0;
- uint32_t last = list->Length() - 1;
- uint32_t mid;
-
- // Stop when there is only one index in our range
- while (last != first) {
- mid = (first + last) / 2;
-
- if (nsContentUtils::PositionIsBefore(aChild, list->Item(mid)))
- last = mid;
- else
- first = mid + 1;
- }
- list->InsertElementAt(aChild, first);
+ size_t idx;
+ DebugOnly<bool> found = BinarySearchIf(NodeListAdaptor(list), 0, list->Length(),
+ PositionComparator(aChild), &idx);
+ MOZ_ASSERT(!found, "should not have found an element");
+
+ list->InsertElementAt(aChild, idx);
}
}
return NS_OK;
}
nsresult
HTMLFormElement::AddImageElement(HTMLImageElement* aChild)
--- a/content/xul/templates/src/nsXULTreeBuilder.cpp
+++ b/content/xul/templates/src/nsXULTreeBuilder.cpp
@@ -26,16 +26,17 @@
#include "nsIXULSortService.h"
#include "nsTArray.h"
#include "nsUnicharUtils.h"
#include "nsNameSpaceManager.h"
#include "nsDOMClassInfoID.h"
#include "nsWhitespaceTokenizer.h"
#include "nsTreeContentView.h"
#include "nsIXULStore.h"
+#include "mozilla/BinarySearch.h"
// For security check
#include "nsIDocument.h"
/**
* A XUL template builder that serves as an tree view, allowing
* (pretty much) arbitrary RDF to be presented in an tree.
*/
@@ -58,16 +59,18 @@ public:
// nsIMutationObserver
NS_DECL_NSIMUTATIONOBSERVER_NODEWILLBEDESTROYED
protected:
friend nsresult
NS_NewXULTreeBuilder(nsISupports* aOuter, REFNSIID aIID, void** aResult);
+ friend struct ResultComparator;
+
nsXULTreeBuilder();
~nsXULTreeBuilder();
/**
* Uninitialize the template builder
*/
virtual void Uninit(bool aIsFinal);
@@ -1062,16 +1065,27 @@ nsXULTreeBuilder::GetInsertionLocations(
nsTreeRows::iterator iter = mRows.FindByResource(container);
if (iter == mRows.Last())
return false;
return (iter->mContainerState == nsTreeRows::eContainerState_Open);
}
+struct ResultComparator
+{
+ nsXULTreeBuilder* const mTreebuilder;
+ nsIXULTemplateResult* const mResult;
+ ResultComparator(nsXULTreeBuilder* aTreebuilder, nsIXULTemplateResult* aResult)
+ : mTreebuilder(aTreebuilder), mResult(aResult) {}
+ int operator()(const nsTreeRows::Row& aSubtree) const {
+ return mTreebuilder->CompareResults(mResult, aSubtree.mMatch->mResult);
+ }
+};
+
nsresult
nsXULTreeBuilder::ReplaceMatch(nsIXULTemplateResult* aOldResult,
nsTemplateMatch* aNewMatch,
nsTemplateRule* aNewMatchRule,
void *aLocation)
{
if (! mBoxObject)
return NS_OK;
@@ -1160,34 +1174,23 @@ nsXULTreeBuilder::ReplaceMatch(nsIXULTem
else {
parent = mRows.GetRoot();
}
if (parent) {
// If we get here, then we're inserting into an open
// container. By default, place the new element at the
// end of the container
- int32_t index = parent->Count();
+ size_t index = parent->Count();
if (mSortVariable) {
- // Figure out where to put the new element by doing an
- // insertion sort.
- int32_t left = 0;
- int32_t right = index;
-
- while (left < right) {
- index = (left + right) / 2;
- int32_t cmp = CompareResults((*parent)[index].mMatch->mResult, result);
- if (cmp < 0)
- left = ++index;
- else if (cmp > 0)
- right = index;
- else
- break;
- }
+ // Figure out where to put the new element through
+ // binary search.
+ mozilla::BinarySearchIf(*parent, 0, parent->Count(),
+ ResultComparator(this, result), &index);
}
nsTreeRows::iterator iter =
mRows.InsertRowAt(aNewMatch, parent, index);
mBoxObject->RowCountChanged(iter.GetRowIndex(), +1);
// See if this newly added row is open; in which case,
--- a/extensions/spellcheck/src/mozInlineSpellWordUtil.cpp
+++ b/extensions/spellcheck/src/mozInlineSpellWordUtil.cpp
@@ -18,16 +18,17 @@
#include "nsServiceManagerUtils.h"
#include "nsIContent.h"
#include "nsTextFragment.h"
#include "mozilla/dom/Element.h"
#include "nsRange.h"
#include "nsContentUtils.h"
#include "nsIFrame.h"
#include <algorithm>
+#include "mozilla/BinarySearch.h"
using namespace mozilla;
// IsIgnorableCharacter
//
// These characters are ones that we should ignore in input.
inline bool IsIgnorableCharacter(char16_t ch)
@@ -653,115 +654,134 @@ mozInlineSpellWordUtil::MapDOMPositionTo
offsetInContributedString <= map.mLength)
return map.mSoftTextOffset + offsetInContributedString;
return -1;
}
}
return -1;
}
+namespace {
+
+template<class T>
+class FirstLargerOffset
+{
+ int32_t mSoftTextOffset;
+
+public:
+ FirstLargerOffset(int32_t aSoftTextOffset) : mSoftTextOffset(aSoftTextOffset) {}
+ int operator()(const T& t) const {
+ // We want the first larger offset, so never return 0 (which would
+ // short-circuit evaluation before finding the last such offset).
+ return mSoftTextOffset < t.mSoftTextOffset ? -1 : 1;
+ }
+};
+
+template<class T>
+bool
+FindLastNongreaterOffset(const nsTArray<T>& aContainer, int32_t aSoftTextOffset, size_t* aIndex)
+{
+ if (aContainer.Length() == 0) {
+ return false;
+ }
+
+ BinarySearchIf(aContainer, 0, aContainer.Length(),
+ FirstLargerOffset<T>(aSoftTextOffset), aIndex);
+ if (*aIndex > 0) {
+ // There was at least one mapping with offset <= aSoftTextOffset. Step back
+ // to find the last element with |mSoftTextOffset <= aSoftTextOffset|.
+ *aIndex -= 1;
+ } else {
+ // Every mapping had offset greater than aSoftTextOffset.
+ MOZ_ASSERT(aContainer[*aIndex].mSoftTextOffset > aSoftTextOffset);
+ }
+ return true;
+}
+
+} // namespace
+
mozInlineSpellWordUtil::NodeOffset
mozInlineSpellWordUtil::MapSoftTextOffsetToDOMPosition(int32_t aSoftTextOffset,
DOMMapHint aHint)
{
NS_ASSERTION(mSoftTextValid, "Soft text must be valid if we're to map out of it");
if (!mSoftTextValid)
return NodeOffset(nullptr, -1);
-
- // The invariant is that the range start..end includes the last mapping,
- // if any, such that mSoftTextOffset <= aSoftTextOffset
- int32_t start = 0;
- int32_t end = mSoftTextDOMMapping.Length();
- while (end - start >= 2) {
- int32_t mid = (start + end)/2;
- const DOMTextMapping& map = mSoftTextDOMMapping[mid];
- if (map.mSoftTextOffset > aSoftTextOffset) {
- end = mid;
- } else {
- start = mid;
- }
+
+ // Find the last mapping, if any, such that mSoftTextOffset <= aSoftTextOffset
+ size_t index;
+ bool found = FindLastNongreaterOffset(mSoftTextDOMMapping, aSoftTextOffset, &index);
+ if (!found) {
+ return NodeOffset(nullptr, -1);
}
-
- if (start >= end)
- return NodeOffset(nullptr, -1);
- // 'start' is now the last mapping, if any, such that
+ // 'index' is now the last mapping, if any, such that
// mSoftTextOffset <= aSoftTextOffset.
// If we're doing HINT_END, then we may want to return the end of the
// the previous mapping instead of the start of this mapping
- if (aHint == HINT_END && start > 0) {
- const DOMTextMapping& map = mSoftTextDOMMapping[start - 1];
+ if (aHint == HINT_END && index > 0) {
+ const DOMTextMapping& map = mSoftTextDOMMapping[index - 1];
if (map.mSoftTextOffset + map.mLength == aSoftTextOffset)
return NodeOffset(map.mNodeOffset.mNode, map.mNodeOffset.mOffset + map.mLength);
}
-
+
// We allow ourselves to return the end of this mapping even if we're
// doing HINT_START. This will only happen if there is no mapping which this
// point is the start of. I'm not 100% sure this is OK...
- const DOMTextMapping& map = mSoftTextDOMMapping[start];
+ const DOMTextMapping& map = mSoftTextDOMMapping[index];
int32_t offset = aSoftTextOffset - map.mSoftTextOffset;
if (offset >= 0 && offset <= map.mLength)
return NodeOffset(map.mNodeOffset.mNode, map.mNodeOffset.mOffset + offset);
-
+
return NodeOffset(nullptr, -1);
}
int32_t
mozInlineSpellWordUtil::FindRealWordContaining(int32_t aSoftTextOffset,
DOMMapHint aHint, bool aSearchForward)
{
NS_ASSERTION(mSoftTextValid, "Soft text must be valid if we're to map out of it");
if (!mSoftTextValid)
return -1;
- // The invariant is that the range start..end includes the last word,
- // if any, such that mSoftTextOffset <= aSoftTextOffset
- int32_t start = 0;
- int32_t end = mRealWords.Length();
- while (end - start >= 2) {
- int32_t mid = (start + end)/2;
- const RealWord& word = mRealWords[mid];
- if (word.mSoftTextOffset > aSoftTextOffset) {
- end = mid;
- } else {
- start = mid;
- }
+ // Find the last word, if any, such that mSoftTextOffset <= aSoftTextOffset
+ size_t index;
+ bool found = FindLastNongreaterOffset(mRealWords, aSoftTextOffset, &index);
+ if (!found) {
+ return -1;
}
-
- if (start >= end)
- return -1;
- // 'start' is now the last word, if any, such that
+ // 'index' is now the last word, if any, such that
// mSoftTextOffset <= aSoftTextOffset.
// If we're doing HINT_END, then we may want to return the end of the
// the previous word instead of the start of this word
- if (aHint == HINT_END && start > 0) {
- const RealWord& word = mRealWords[start - 1];
+ if (aHint == HINT_END && index > 0) {
+ const RealWord& word = mRealWords[index - 1];
if (word.mSoftTextOffset + word.mLength == aSoftTextOffset)
- return start - 1;
+ return index - 1;
}
-
+
// We allow ourselves to return the end of this word even if we're
// doing HINT_START. This will only happen if there is no word which this
// point is the start of. I'm not 100% sure this is OK...
- const RealWord& word = mRealWords[start];
+ const RealWord& word = mRealWords[index];
int32_t offset = aSoftTextOffset - word.mSoftTextOffset;
if (offset >= 0 && offset <= word.mLength)
- return start;
+ return index;
if (aSearchForward) {
if (mRealWords[0].mSoftTextOffset > aSoftTextOffset) {
// All words have mSoftTextOffset > aSoftTextOffset
return 0;
}
- // 'start' is the last word such that mSoftTextOffset <= aSoftTextOffset.
- // Word start+1, if it exists, will be the first with
+ // 'index' is the last word such that mSoftTextOffset <= aSoftTextOffset.
+ // Word index+1, if it exists, will be the first with
// mSoftTextOffset > aSoftTextOffset.
- if (start + 1 < int32_t(mRealWords.Length()))
- return start + 1;
+ if (index + 1 < mRealWords.Length())
+ return index + 1;
}
return -1;
}
/*********** Word Splitting ************/
// classifies a given character in the DOM word
--- a/gfx/thebes/gfxFont.cpp
+++ b/gfx/thebes/gfxFont.cpp
@@ -1,13 +1,14 @@
/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+#include "mozilla/BinarySearch.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/MathAlgorithms.h"
#ifdef MOZ_LOGGING
#define FORCE_PR_LOG /* Allow logging in the release build */
#endif
#include "prlog.h"
--- a/gfx/thebes/gfxFontUtils.cpp
+++ b/gfx/thebes/gfxFontUtils.cpp
@@ -4,25 +4,27 @@
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#ifdef MOZ_LOGGING
#define FORCE_PR_LOG /* Allow logging in the release build */
#include "prlog.h"
#endif
#include "mozilla/ArrayUtils.h"
+#include "mozilla/BinarySearch.h"
#include "gfxFontUtils.h"
#include "gfxColor.h"
#include "nsServiceManagerUtils.h"
#include "mozilla/dom/EncodingUtils.h"
#include "mozilla/Preferences.h"
#include "mozilla/Services.h"
+#include "mozilla/BinarySearch.h"
#include "nsCOMPtr.h"
#include "nsIUUIDGenerator.h"
#include "nsIUnicodeDecoder.h"
#include "harfbuzz/hb.h"
#include "plbase64.h"
@@ -699,59 +701,57 @@ gfxFontUtils::MapCharToGlyphFormat12(con
if (startCharCode <= aCh && groups[range].endCharCode >= aCh) {
return groups[range].startGlyphId + aCh - startCharCode;
}
// Else it's not present, so return the .notdef glyph
return 0;
}
+namespace {
+
+struct Format14CmapWrapper
+{
+ const Format14Cmap& mCmap14;
+ Format14CmapWrapper(const Format14Cmap& cmap14) : mCmap14(cmap14) {}
+ uint32_t operator[](size_t index) const {
+ return mCmap14.varSelectorRecords[index].varSelector;
+ }
+};
+
+struct NonDefUVSTableWrapper
+{
+ const NonDefUVSTable& mTable;
+ NonDefUVSTableWrapper(const NonDefUVSTable& table) : mTable(table) {}
+ uint32_t operator[](size_t index) const {
+ return mTable.uvsMappings[index].unicodeValue;
+ }
+};
+
+} // namespace
+
uint16_t
gfxFontUtils::MapUVSToGlyphFormat14(const uint8_t *aBuf, uint32_t aCh, uint32_t aVS)
{
+ using mozilla::BinarySearch;
const Format14Cmap *cmap14 = reinterpret_cast<const Format14Cmap*>(aBuf);
- // binary search in varSelectorRecords
- uint32_t min = 0;
- uint32_t max = cmap14->numVarSelectorRecords;
- uint32_t nonDefUVSOffset = 0;
- while (min < max) {
- uint32_t index = (min + max) >> 1;
- uint32_t varSelector = cmap14->varSelectorRecords[index].varSelector;
- if (aVS == varSelector) {
- nonDefUVSOffset = cmap14->varSelectorRecords[index].nonDefaultUVSOffset;
- break;
- }
- if (aVS < varSelector) {
- max = index;
- } else {
- min = index + 1;
- }
- }
- if (!nonDefUVSOffset) {
+ size_t index;
+ if (!BinarySearch(Format14CmapWrapper(*cmap14),
+ 0, cmap14->numVarSelectorRecords, aVS, &index)) {
return 0;
}
+ const uint32_t nonDefUVSOffset = cmap14->varSelectorRecords[index].nonDefaultUVSOffset;
const NonDefUVSTable *table = reinterpret_cast<const NonDefUVSTable*>
(aBuf + nonDefUVSOffset);
- // binary search in uvsMappings
- min = 0;
- max = table->numUVSMappings;
- while (min < max) {
- uint32_t index = (min + max) >> 1;
- uint32_t unicodeValue = table->uvsMappings[index].unicodeValue;
- if (aCh == unicodeValue) {
- return table->uvsMappings[index].glyphID;
- }
- if (aCh < unicodeValue) {
- max = index;
- } else {
- min = index + 1;
- }
+ if (BinarySearch(NonDefUVSTableWrapper(*table), 0, table->numUVSMappings,
+ aCh, &index)) {
+ return table->uvsMappings[index].glyphID;
}
return 0;
}
uint32_t
gfxFontUtils::MapCharToGlyph(const uint8_t *aCmapBuf, uint32_t aBufLength,
uint32_t aUnicode, uint32_t aVarSelector)
@@ -1329,52 +1329,57 @@ const char* gfxFontUtils::gMSFontNameCha
/* [5] ENCODING_ID_MICROSOFT_WANSUNG */ nullptr ,
/* [6] ENCODING_ID_MICROSOFT_JOHAB */ nullptr ,
/* [7] reserved */ nullptr ,
/* [8] reserved */ nullptr ,
/* [9] reserved */ nullptr ,
/*[10] ENCODING_ID_MICROSOFT_UNICODEFULL */ ""
};
+struct MacCharsetMappingComparator
+{
+ typedef gfxFontUtils::MacFontNameCharsetMapping MacFontNameCharsetMapping;
+ const MacFontNameCharsetMapping& mSearchValue;
+ MacCharsetMappingComparator(const MacFontNameCharsetMapping& aSearchValue)
+ : mSearchValue(aSearchValue) {}
+ int operator()(const MacFontNameCharsetMapping& aEntry) const {
+ if (mSearchValue < aEntry) {
+ return -1;
+ }
+ if (aEntry < mSearchValue) {
+ return 1;
+ }
+ return 0;
+ }
+};
+
// Return the name of the charset we should use to decode a font name
// given the name table attributes.
// Special return values:
// "" charset is UTF16BE, no need for a converter
// nullptr unknown charset, do not attempt conversion
const char*
gfxFontUtils::GetCharsetForFontName(uint16_t aPlatform, uint16_t aScript, uint16_t aLanguage)
{
switch (aPlatform)
{
case PLATFORM_ID_UNICODE:
return "";
case PLATFORM_ID_MAC:
{
- uint32_t lo = 0, hi = ArrayLength(gMacFontNameCharsets);
MacFontNameCharsetMapping searchValue = { aScript, aLanguage, nullptr };
for (uint32_t i = 0; i < 2; ++i) {
- // binary search; if not found, set language to ANY and try again
- while (lo < hi) {
- uint32_t mid = (lo + hi) / 2;
- const MacFontNameCharsetMapping& entry = gMacFontNameCharsets[mid];
- if (entry < searchValue) {
- lo = mid + 1;
- continue;
- }
- if (searchValue < entry) {
- hi = mid;
- continue;
- }
- // found a match
- return entry.mCharsetName;
+ size_t idx;
+ if (BinarySearchIf(gMacFontNameCharsets, 0, ArrayLength(gMacFontNameCharsets),
+ MacCharsetMappingComparator(searchValue), &idx)) {
+ return gMacFontNameCharsets[idx].mCharsetName;
}
- // no match, so reset high bound for search and re-try
- hi = ArrayLength(gMacFontNameCharsets);
+ // no match, so try again finding one in any language
searchValue.mLanguage = ANY;
}
}
break;
case PLATFORM_ID_ISO:
if (aScript < ArrayLength(gISOFontNameCharsets)) {
return gISOFontNameCharsets[aScript];
--- a/gfx/thebes/gfxFontUtils.h
+++ b/gfx/thebes/gfxFontUtils.h
@@ -962,16 +962,18 @@ public:
static bool ValidateColorGlyphs(hb_blob_t* aCOLR, hb_blob_t* aCPAL);
static bool GetColorGlyphLayers(hb_blob_t* aCOLR,
hb_blob_t* aCPAL,
uint32_t aGlyphId,
nsTArray<uint16_t> &aGlyphs,
nsTArray<mozilla::gfx::Color> &aColors);
protected:
+ friend struct MacCharsetMappingComparator;
+
static nsresult
ReadNames(const char *aNameData, uint32_t aDataLen, uint32_t aNameID,
int32_t aLangID, int32_t aPlatformID, nsTArray<nsString>& aNames);
// convert opentype name-table platform/encoding/language values to a charset name
// we can use to convert the name data to unicode, or "" if data is UTF16BE
static const char*
GetCharsetForFontName(uint16_t aPlatform, uint16_t aScript, uint16_t aLanguage);
--- a/gfx/thebes/gfxMathTable.cpp
+++ b/gfx/thebes/gfxMathTable.cpp
@@ -1,16 +1,17 @@
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#include "gfxMathTable.h"
#include "MathTableStructures.h"
#include "harfbuzz/hb.h"
+#include "mozilla/BinarySearch.h"
#include <algorithm>
using namespace mozilla;
gfxMathTable::gfxMathTable(hb_blob_t* aMathTable)
: mMathTable(aMathTable)
, mGlyphConstruction(nullptr)
, mGlyphID(-1)
@@ -350,64 +351,80 @@ gfxMathTable::GetGlyphAssembly(uint32_t
// Verify the validity of the GlyphAssembly and return it.
if (!ValidStructure(start, sizeof(GlyphAssembly))) {
return nullptr;
}
return reinterpret_cast<const GlyphAssembly*>(start);
}
+namespace {
+
+struct GlyphArrayWrapper
+{
+ const GlyphID* const mGlyphArray;
+ GlyphArrayWrapper(const GlyphID* const aGlyphArray) : mGlyphArray(aGlyphArray)
+ {}
+ uint16_t operator[](size_t index) const {
+ return mGlyphArray[index];
+ }
+};
+
+struct RangeRecordComparator
+{
+ const uint32_t mGlyph;
+ RangeRecordComparator(uint32_t aGlyph) : mGlyph(aGlyph) {}
+ int operator()(const RangeRecord& aRecord) const {
+ if (mGlyph < static_cast<uint16_t>(aRecord.mStart)) {
+ return -1;
+ }
+ if (mGlyph > static_cast<uint16_t>(aRecord.mEnd)) {
+ return 1;
+ }
+ return 0;
+ }
+};
+
+} // namespace
+
int32_t
gfxMathTable::GetCoverageIndex(const Coverage* aCoverage, uint32_t aGlyph)
{
+ using mozilla::BinarySearch;
+ using mozilla::BinarySearchIf;
+
if (uint16_t(aCoverage->mFormat) == 1) {
// Coverage Format 1: list of individual glyph indices in the glyph set.
const CoverageFormat1* table =
reinterpret_cast<const CoverageFormat1*>(aCoverage);
- uint16_t count = table->mGlyphCount;
+ const uint16_t count = table->mGlyphCount;
const char* start = reinterpret_cast<const char*>(table + 1);
if (ValidStructure(start, count * sizeof(GlyphID))) {
- const GlyphID* glyphArray =
- reinterpret_cast<const GlyphID*>(start);
- uint32_t imin = 0, imax = count;
- while (imin < imax) {
- uint32_t imid = (imin + imax) >> 1;
- uint16_t glyphMid = glyphArray[imid];
- if (glyphMid == aGlyph) {
- return imid;
- }
- if (glyphMid < aGlyph) {
- imin = imid + 1;
- } else {
- imax = imid;
- }
+ const GlyphID* glyphArray = reinterpret_cast<const GlyphID*>(start);
+ size_t index;
+
+ if (BinarySearch(GlyphArrayWrapper(glyphArray), 0, count, aGlyph, &index)) {
+ return index;
}
}
} else if (uint16_t(aCoverage->mFormat) == 2) {
// Coverage Format 2: ranges of consecutive indices.
const CoverageFormat2* table =
reinterpret_cast<const CoverageFormat2*>(aCoverage);
- uint16_t count = table->mRangeCount;
+ const uint16_t count = table->mRangeCount;
const char* start = reinterpret_cast<const char*>(table + 1);
if (ValidStructure(start, count * sizeof(RangeRecord))) {
- const RangeRecord* rangeArray =
- reinterpret_cast<const RangeRecord*>(start);
- uint32_t imin = 0, imax = count;
- while (imin < imax) {
- uint32_t imid = (imin + imax) >> 1;
- uint16_t rStart = rangeArray[imid].mStart;
- uint16_t rEnd = rangeArray[imid].mEnd;
- if (rEnd < aGlyph) {
- imin = imid + 1;
- } else if (aGlyph < rStart) {
- imax = imid;
- } else {
- return (uint16_t(rangeArray[imid].mStartCoverageIndex) +
- aGlyph - rStart);
- }
+ const RangeRecord* rangeArray = reinterpret_cast<const RangeRecord*>(start);
+ size_t index;
+
+ if (BinarySearchIf(rangeArray, 0, count, RangeRecordComparator(aGlyph),
+ &index)) {
+ uint16_t rStart = rangeArray[index].mStart;
+ uint16_t startCoverageIndex = rangeArray[index].mStartCoverageIndex;
+ return (startCoverageIndex + aGlyph - rStart);
}
}
}
return -1;
}
void
gfxMathTable::SelectGlyphConstruction(uint32_t aGlyphID, bool aVertical)
--- a/gfx/thebes/gfxSkipChars.cpp
+++ b/gfx/thebes/gfxSkipChars.cpp
@@ -1,71 +1,85 @@
/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*-
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#include "gfxSkipChars.h"
+#include "mozilla/BinarySearch.h"
+
+struct SkippedRangeStartComparator
+{
+ const uint32_t mOffset;
+ SkippedRangeStartComparator(const uint32_t aOffset) : mOffset(aOffset) {}
+ int operator()(const gfxSkipChars::SkippedRange& aRange) const {
+ return (mOffset < aRange.Start()) ? -1 : 1;
+ }
+};
void
gfxSkipCharsIterator::SetOriginalOffset(int32_t aOffset)
{
aOffset += mOriginalStringToSkipCharsOffset;
NS_ASSERTION(uint32_t(aOffset) <= mSkipChars->mCharCount,
"Invalid offset");
mOriginalStringOffset = aOffset;
- uint32_t rangeCount = mSkipChars->mRanges.Length();
+ const uint32_t rangeCount = mSkipChars->mRanges.Length();
if (rangeCount == 0) {
mSkippedStringOffset = aOffset;
return;
}
// at start of string?
if (aOffset == 0) {
mSkippedStringOffset = 0;
mCurrentRangeIndex =
rangeCount && mSkipChars->mRanges[0].Start() == 0 ? 0 : -1;
return;
}
// find the range that includes or precedes aOffset
- uint32_t lo = 0, hi = rangeCount;
- const gfxSkipChars::SkippedRange* ranges = mSkipChars->mRanges.Elements();
- while (lo < hi) {
- uint32_t mid = (lo + hi) / 2;
- if (uint32_t(aOffset) < ranges[mid].Start()) {
- hi = mid;
- } else {
- lo = mid + 1;
- }
- }
+ const nsTArray<gfxSkipChars::SkippedRange>& ranges = mSkipChars->mRanges;
+ size_t idx;
+ mozilla::BinarySearchIf(ranges, 0, rangeCount,
+ SkippedRangeStartComparator(aOffset),
+ &idx);
- if (lo == rangeCount) {
+ if (idx == rangeCount) {
mCurrentRangeIndex = rangeCount - 1;
- } else if (uint32_t(aOffset) < ranges[lo].Start()) {
- mCurrentRangeIndex = lo - 1;
+ } else if (uint32_t(aOffset) < ranges[idx].Start()) {
+ mCurrentRangeIndex = idx - 1;
if (mCurrentRangeIndex == -1) {
mSkippedStringOffset = aOffset;
return;
}
} else {
- mCurrentRangeIndex = lo;
+ mCurrentRangeIndex = idx;
}
const gfxSkipChars::SkippedRange& r = ranges[mCurrentRangeIndex];
if (uint32_t(aOffset) < r.End()) {
mSkippedStringOffset = r.SkippedOffset();
return;
}
mSkippedStringOffset = aOffset - r.NextDelta();
}
+struct SkippedRangeOffsetComparator
+{
+ const uint32_t mOffset;
+ SkippedRangeOffsetComparator(const uint32_t aOffset) : mOffset(aOffset) {}
+ int operator()(const gfxSkipChars::SkippedRange& aRange) const {
+ return (mOffset < aRange.SkippedOffset()) ? -1 : 1;
+ }
+};
+
void
gfxSkipCharsIterator::SetSkippedOffset(uint32_t aOffset)
{
NS_ASSERTION((mSkipChars->mRanges.IsEmpty() &&
aOffset <= mSkipChars->mCharCount) ||
(aOffset <= mSkipChars->LastRange().SkippedOffset() +
mSkipChars->mCharCount -
mSkipChars->LastRange().End()),
@@ -73,37 +87,32 @@ gfxSkipCharsIterator::SetSkippedOffset(u
mSkippedStringOffset = aOffset;
uint32_t rangeCount = mSkipChars->mRanges.Length();
if (rangeCount == 0) {
mOriginalStringOffset = aOffset;
return;
}
- uint32_t lo = 0, hi = rangeCount;
- const gfxSkipChars::SkippedRange* ranges = mSkipChars->mRanges.Elements();
- while (lo < hi) {
- uint32_t mid = (lo + hi) / 2;
- if (aOffset < ranges[mid].SkippedOffset()) {
- hi = mid;
- } else {
- lo = mid + 1;
- }
- }
+ const nsTArray<gfxSkipChars::SkippedRange>& ranges = mSkipChars->mRanges;
+ size_t idx;
+ mozilla::BinarySearchIf(ranges, 0, rangeCount,
+ SkippedRangeOffsetComparator(aOffset),
+ &idx);
- if (lo == rangeCount) {
+ if (idx == rangeCount) {
mCurrentRangeIndex = rangeCount - 1;
- } else if (aOffset < ranges[lo].SkippedOffset()) {
- mCurrentRangeIndex = lo - 1;
+ } else if (aOffset < ranges[idx].SkippedOffset()) {
+ mCurrentRangeIndex = idx - 1;
if (mCurrentRangeIndex == -1) {
mOriginalStringOffset = aOffset;
return;
}
} else {
- mCurrentRangeIndex = lo;
+ mCurrentRangeIndex = idx;
}
const gfxSkipChars::SkippedRange& r = ranges[mCurrentRangeIndex];
mOriginalStringOffset = r.End() + aOffset - r.SkippedOffset();
}
bool
gfxSkipCharsIterator::IsOriginalCharSkipped(int32_t* aRunLength) const
--- a/gfx/thebes/gfxSkipChars.h
+++ b/gfx/thebes/gfxSkipChars.h
@@ -20,16 +20,19 @@
/**
* The gfxSkipChars is represented as a sorted array of skipped ranges.
*
* A freshly-created gfxSkipChars means "all chars kept".
*/
class gfxSkipChars
{
+ friend struct SkippedRangeStartComparator;
+ friend struct SkippedRangeOffsetComparator;
+
private:
class SkippedRange
{
public:
SkippedRange(uint32_t aOffset, uint32_t aLength, uint32_t aDelta)
: mOffset(aOffset), mLength(aLength), mDelta(aDelta)
{ }
--- a/intl/locale/nsUConvPropertySearch.cpp
+++ b/intl/locale/nsUConvPropertySearch.cpp
@@ -1,35 +1,44 @@
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#include "nsUConvPropertySearch.h"
#include "nsCRT.h"
#include "nsString.h"
+#include "mozilla/BinarySearch.h"
+
+namespace {
+
+struct PropertyComparator
+{
+ const nsCString& mKey;
+ PropertyComparator(const nsCString& aKey) : mKey(aKey) {}
+ int operator()(const char* (&aProperty)[3]) const {
+ return mKey.Compare(aProperty[0]);
+ }
+};
+
+}
// static
nsresult
nsUConvPropertySearch::SearchPropertyValue(const char* aProperties[][3],
int32_t aNumberOfProperties,
const nsACString& aKey,
nsACString& aValue)
{
- const char* key = PromiseFlatCString(aKey).get();
- int32_t lo = 0;
- int32_t hi = aNumberOfProperties - 1;
- while (lo <= hi) {
- uint32_t mid = (lo + hi) / 2;
- int32_t comp = nsCRT::strcmp(aProperties[mid][0], key);
- if (comp > 0) {
- hi = mid - 1;
- } else if (comp < 0) {
- lo = mid + 1;
- } else {
- nsDependentCString val(aProperties[mid][1],
- NS_PTR_TO_UINT32(aProperties[mid][2]));
- aValue.Assign(val);
- return NS_OK;
- }
+ using mozilla::BinarySearchIf;
+
+ const nsCString& flat = PromiseFlatCString(aKey);
+ size_t index;
+ if (BinarySearchIf(aProperties, 0, aNumberOfProperties,
+ PropertyComparator(flat), &index)) {
+ nsDependentCString val(aProperties[index][1],
+ NS_PTR_TO_UINT32(aProperties[index][2]));
+ aValue.Assign(val);
+ return NS_OK;
}
+
aValue.Truncate();
return NS_ERROR_FAILURE;
}
--- a/intl/unicharutil/nsUnicodeNormalizer.cpp
+++ b/intl/unicharutil/nsUnicodeNormalizer.cpp
@@ -51,16 +51,17 @@
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
*/
#include <string.h>
#include "nsMemory.h"
#include "nsUnicodeNormalizer.h"
#include "nsString.h"
+#include "mozilla/BinarySearch.h"
NS_IMPL_ISUPPORTS(nsUnicodeNormalizer, nsIUnicodeNormalizer)
nsUnicodeNormalizer::nsUnicodeNormalizer()
{
}
@@ -231,21 +232,33 @@ mdn__unicode_iscompositecandidate(uint32
* composition candidate.
*/
if (compose_char(c, &dummy) == 0)
return (0);
else
return (1);
}
+namespace {
+
+struct SequenceAdaptor
+{
+ const composition* const mSequence;
+ SequenceAdaptor(const composition* aSequence) : mSequence(aSequence) {}
+ uint32_t operator[](size_t aIdx) const {
+ return mSequence[aIdx].c2;
+ }
+};
+
+} // namespace
+
static nsresult
mdn__unicode_compose(uint32_t c1, uint32_t c2, uint32_t *compp)
{
int32_t n;
- int32_t lo, hi;
const struct composition *cseq;
//assert(compp != nullptr);
/*
* Check for Hangul.
*/
if (LBase <= c1 && c1 < LBase + LCount &&
@@ -274,30 +287,22 @@ mdn__unicode_compose(uint32_t c1, uint32
*/
if ((n = compose_char(c1, &cseq)) == 0)
return (NS_SUCCESS_UNORM_NOTFOUND);
/*
* The composite sequences are sorted by the 2nd character 'c2'.
* So we can use binary search.
*/
- lo = 0;
- hi = n - 1;
- while (lo <= hi) {
- int32_t mid = (lo + hi) / 2;
+ size_t idx;
+ if (mozilla::BinarySearch(SequenceAdaptor(cseq), 0, n, c2, &idx)) {
+ *compp = cseq[idx].comp;
+ return (NS_OK);
+ }
- if (cseq[mid].c2 < c2) {
- lo = mid + 1;
- } else if (cseq[mid].c2 > c2) {
- hi = mid - 1;
- } else {
- *compp = cseq[mid].comp;
- return (NS_OK);
- }
- }
return (NS_SUCCESS_UNORM_NOTFOUND);
}
#define WORKBUF_SIZE 128
#define WORKBUF_SIZE_MAX 10000
typedef struct {
--- a/layout/generic/MathMLTextRunFactory.cpp
+++ b/layout/generic/MathMLTextRunFactory.cpp
@@ -1,17 +1,18 @@
/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#include "MathMLTextRunFactory.h"
#include "mozilla/ArrayUtils.h"
-
+#include "mozilla/BinarySearch.h"
+
#include "nsStyleConsts.h"
#include "nsStyleContext.h"
#include "nsTextFrameUtils.h"
#include "nsFontMetrics.h"
#include "nsDeviceContext.h"
using namespace mozilla;
@@ -184,34 +185,39 @@ static const MathVarMapping gLatinExcept
{ 0x1D53F, 0x210D },
{ 0x1D545, 0x2115 },
{ 0x1D547, 0x2119 },
{ 0x1D548, 0x211A },
{ 0x1D549, 0x211D },
{ 0x1D551, 0x2124 }
};
+namespace {
+
+struct MathVarMappingWrapper
+{
+ const MathVarMapping* const mTable;
+ MathVarMappingWrapper(const MathVarMapping* aTable) : mTable(aTable) {}
+ uint32_t operator[](size_t index) const {
+ return mTable[index].mKey;
+ }
+};
+
+} // namespace
+
// Finds a MathVarMapping struct with the specified key (aKey) within aTable.
// aTable must be an array, whose length is specified by aNumElements
static uint32_t
MathvarMappingSearch(uint32_t aKey, const MathVarMapping* aTable, uint32_t aNumElements)
{
- uint32_t low = 0;
- uint32_t high = aNumElements;
- while (high > low) {
- uint32_t midPoint = (low+high) >> 1;
- if (aKey == aTable[midPoint].mKey) {
- return aTable[midPoint].mReplacement;
- }
- if (aKey > aTable[midPoint].mKey) {
- low = midPoint + 1;
- } else {
- high = midPoint;
- }
+ size_t index;
+ if (BinarySearch(MathVarMappingWrapper(aTable), 0, aNumElements, aKey, &index)) {
+ return aTable[index].mReplacement;
}
+
return 0;
}
#define GREEK_UPPER_THETA 0x03F4
#define HOLE_GREEK_UPPER_THETA 0x03A2
#define NABLA 0x2207
#define PARTIAL_DIFFERENTIAL 0x2202
#define GREEK_UPPER_ALPHA 0x0391
--- a/layout/generic/nsTextFrame.cpp
+++ b/layout/generic/nsTextFrame.cpp
@@ -7,16 +7,17 @@
#include "nsTextFrame.h"
#include "mozilla/Attributes.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/Likely.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/TextEvents.h"
+#include "mozilla/BinarySearch.h"
#include "nsCOMPtr.h"
#include "nsBlockFrame.h"
#include "nsCRT.h"
#include "nsSplittableFrame.h"
#include "nsLineLayout.h"
#include "nsString.h"
#include "nsUnicharUtils.h"
@@ -115,49 +116,43 @@ struct TabWidthStore {
// Need to recalc tab offsets if frame content offset differs from this.
int32_t mValidForContentOffset;
// A TabWidth record for each tab character measured so far.
nsTArray<TabWidth> mWidths;
};
+namespace {
+
+struct TabwidthAdaptor
+{
+ const nsTArray<TabWidth>& mWidths;
+ TabwidthAdaptor(const nsTArray<TabWidth>& aWidths)
+ : mWidths(aWidths) {}
+ uint32_t operator[](size_t aIdx) const {
+ return mWidths[aIdx].mOffset;
+ }
+};
+
+} // namespace
+
void
TabWidthStore::ApplySpacing(gfxTextRun::PropertyProvider::Spacing *aSpacing,
uint32_t aOffset, uint32_t aLength)
{
- uint32_t i = 0, len = mWidths.Length();
+ size_t i = 0;
+ const size_t len = mWidths.Length();
// If aOffset is non-zero, do a binary search to find where to start
// processing the tab widths, in case the list is really long. (See bug
// 953247.)
// We need to start from the first entry where mOffset >= aOffset.
if (aOffset > 0) {
- uint32_t lo = 0, hi = len;
- while (lo < hi) {
- i = (lo + hi) / 2;
- const TabWidth& tw = mWidths[i];
- if (tw.mOffset < aOffset) {
- // mWidths[i] precedes the target range; new search range
- // will be [i+1, hi)
- lo = ++i;
- continue;
- }
- if (tw.mOffset > aOffset) {
- // mWidths[i] is within (or beyond) the target range;
- // new search range is [lo, i). If it turns out that
- // mWidths[i] was the first entry within the range,
- // we'll never move hi any further, and end up exiting
- // when i == lo == this value of hi.
- hi = i;
- continue;
- }
- // Found an exact match for aOffset, so end search now
- break;
- }
+ mozilla::BinarySearch(TabwidthAdaptor(mWidths), 0, len, aOffset, &i);
}
uint32_t limit = aOffset + aLength;
while (i < len) {
const TabWidth& tw = mWidths[i];
if (tw.mOffset >= limit) {
break;
}
--- a/parser/html/jArray.h
+++ b/parser/html/jArray.h
@@ -19,39 +19,30 @@
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
*/
#ifndef jArray_h
#define jArray_h
#include "mozilla/Attributes.h"
+#include "mozilla/BinarySearch.h"
#include "mozilla/NullPtr.h"
#include "nsDebug.h"
template<class T, class L>
struct staticJArray {
const T* arr;
const L length;
operator T*() { return arr; }
T& operator[] (L const index) { return ((T*)arr)[index]; }
L binarySearch(T const elem) {
- L lo = 0;
- L hi = length - 1;
- while (lo <= hi) {
- L mid = (lo + hi) / 2;
- if (arr[mid] > elem) {
- hi = mid - 1;
- } else if (arr[mid] < elem) {
- lo = mid + 1;
- } else {
- return mid;
- }
- }
- return -1;
+ size_t idx;
+ bool found = mozilla::BinarySearch(arr, 0, length, elem, &idx);
+ return found ? idx : -1;
}
};
template<class T, class L>
struct jArray {
T* arr;
L length;
static jArray<T,L> newJArray(L const len) {
--- a/parser/htmlparser/nsParser.cpp
+++ b/parser/htmlparser/nsParser.cpp
@@ -37,16 +37,17 @@
#include "mozilla/Mutex.h"
#include "nsParserConstants.h"
#include "nsCharsetSource.h"
#include "nsContentUtils.h"
#include "nsThreadUtils.h"
#include "nsIHTMLContentSink.h"
#include "mozilla/dom/EncodingUtils.h"
+#include "mozilla/BinarySearch.h"
using namespace mozilla;
using mozilla::dom::EncodingUtils;
#define NS_PARSER_FLAG_PARSER_ENABLED 0x00000002
#define NS_PARSER_FLAG_OBSERVERS_ENABLED 0x00000004
#define NS_PARSER_FLAG_PENDING_CONTINUE_EVENT 0x00000008
#define NS_PARSER_FLAG_FLUSH_TOKENS 0x00000020
@@ -632,16 +633,30 @@ VerifyPublicIDs()
NS_NOTREACHED("doctype not lower case");
printf("Doctype %s not lower case.\n", kPublicIDs[i].name);
}
}
}
}
#endif
+namespace {
+
+struct PublicIdComparator
+{
+ const nsAutoCString& mPublicId;
+ PublicIdComparator(const nsAutoCString& aPublicId)
+ : mPublicId(aPublicId) {}
+ int operator()(const PubIDInfo& aInfo) const {
+ return nsCRT::strcmp(mPublicId.get(), aInfo.name);
+ }
+};
+
+} // namespace
+
static void
DetermineHTMLParseMode(const nsString& aBuffer,
nsDTDMode& aParseMode,
eParserDocType& aDocType)
{
#ifdef DEBUG
VerifyPublicIDs();
#endif
@@ -672,39 +687,25 @@ DetermineHTMLParseMode(const nsString& a
// Yes, we want UCS2 to ASCII lossy conversion.
nsAutoCString publicID;
publicID.AssignWithConversion(publicIDUCS2);
// See comment above definition of kPublicIDs about case
// sensitivity.
ToLowerCase(publicID);
- // Binary search to see if we can find the correct public ID
- // These must be signed since maximum can go below zero and we'll
- // crash if it's unsigned.
- int32_t minimum = 0;
- int32_t maximum = ELEMENTS_OF(kPublicIDs) - 1;
- int32_t index;
- for (;;) {
- index = (minimum + maximum) / 2;
- int32_t comparison =
- nsCRT::strcmp(publicID.get(), kPublicIDs[index].name);
- if (comparison == 0)
- break;
- if (comparison < 0)
- maximum = index - 1;
- else
- minimum = index + 1;
-
- if (maximum < minimum) {
- // The DOCTYPE is not in our list, so it must be full_standards.
- aParseMode = eDTDMode_full_standards;
- aDocType = eHTML_Strict;
- return;
- }
+ // Binary search to see if we can find the correct public ID.
+ size_t index;
+ bool found = BinarySearchIf(kPublicIDs, 0, ArrayLength(kPublicIDs),
+ PublicIdComparator(publicID), &index);
+ if (!found) {
+ // The DOCTYPE is not in our list, so it must be full_standards.
+ aParseMode = eDTDMode_full_standards;
+ aDocType = eHTML_Strict;
+ return;
}
switch ((resultFlags & PARSE_DTD_HAVE_SYSTEM_ID)
? kPublicIDs[index].mode_if_sysid
: kPublicIDs[index].mode_if_no_sysid)
{
case PubIDInfo::eQuirks:
aParseMode = eDTDMode_quirks;
--- a/xpcom/glue/nsTArray.h
+++ b/xpcom/glue/nsTArray.h
@@ -5,16 +5,17 @@
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
#ifndef nsTArray_h__
#define nsTArray_h__
#include "nsTArrayForwardDeclare.h"
#include "mozilla/Alignment.h"
#include "mozilla/Assertions.h"
+#include "mozilla/BinarySearch.h"
#include "mozilla/MemoryReporting.h"
#include "mozilla/Move.h"
#include "mozilla/TypeTraits.h"
#include <string.h>
#include "nsCycleCollectionNoteChild.h"
#include "nsAlgorithm.h"
@@ -692,16 +693,39 @@ struct nsTArray_TypedBase<JS::Heap<E>, D
operator const FallibleTArray<E>&()
{
Derived* self = static_cast<Derived*>(this);
return *reinterpret_cast<FallibleTArray<E> *>(self);
}
};
+namespace detail {
+
+template<class Item, class Comparator>
+struct ItemComparator
+{
+ const Item& mItem;
+ const Comparator& mComp;
+ ItemComparator(const Item& aItem, const Comparator& aComp)
+ : mItem(aItem)
+ , mComp(aComp)
+ {}
+ template<class T>
+ int operator()(const T& aElement) const {
+ if (mComp.LessThan(aElement, mItem) ||
+ mComp.Equals(aElement, mItem)) {
+ return 1;
+ } else {
+ return -1;
+ }
+ }
+};
+
+} // namespace detail
//
// nsTArray_Impl contains most of the guts supporting nsTArray, FallibleTArray,
// nsAutoTArray, and AutoFallibleTArray.
//
// The only situation in which you might need to use nsTArray_Impl in your code
// is if you're writing code which mutates a TArray which may or may not be
// infallible.
@@ -1221,33 +1245,22 @@ public:
// @param aItem The item to search for.
// @param aComp The Comparator used.
// @return The index of greatest element <= to |aItem|
// @precondition The array is sorted
template<class Item, class Comparator>
index_type IndexOfFirstElementGt(const Item& aItem,
const Comparator& aComp) const
{
- // invariant: low <= [idx] <= high
- index_type low = 0, high = Length();
- while (high > low) {
- index_type mid = (high + low) >> 1;
- // Comparators are not required to provide a LessThan(Item&, elem_type),
- // so we can't do aComp.LessThan(aItem, ElementAt(mid)).
- if (aComp.LessThan(ElementAt(mid), aItem) ||
- aComp.Equals(ElementAt(mid), aItem)) {
- // aItem >= ElementAt(mid), so our desired index is at least mid+1.
- low = mid + 1;
- } else {
- // aItem < ElementAt(mid). Our desired index is therefore at most mid.
- high = mid;
- }
- }
- MOZ_ASSERT(high == low);
- return low;
+ using mozilla::BinarySearchIf;
+ typedef ::detail::ItemComparator<Item, Comparator> Cmp;
+
+ size_t index;
+ BinarySearchIf(*this, 0, Length(), Cmp(aItem, aComp), &index);
+ return index;
}
// A variation on the IndexOfFirstElementGt method defined above.
template<class Item>
index_type
IndexOfFirstElementGt(const Item& aItem) const
{
return IndexOfFirstElementGt(aItem, nsDefaultComparator<elem_type, Item>());
--- a/xpcom/threads/TimerThread.cpp
+++ b/xpcom/threads/TimerThread.cpp
@@ -10,16 +10,17 @@
#include "nsThreadUtils.h"
#include "pratom.h"
#include "nsIObserverService.h"
#include "nsIServiceManager.h"
#include "mozilla/Services.h"
#include "mozilla/ChaosMode.h"
#include "mozilla/ArrayUtils.h"
+#include "mozilla/BinarySearch.h"
#include <math.h>
using namespace mozilla;
NS_IMPL_ISUPPORTS(TimerThread, nsIRunnable, nsIObserver)
TimerThread::TimerThread() :
@@ -169,16 +170,34 @@ TimerThread::Shutdown()
PR_LOG(GetTimerLog(), PR_LOG_DEBUG, ("TimerThread::Shutdown end\n"));
return NS_OK;
}
#ifdef MOZ_NUWA_PROCESS
#include "ipc/Nuwa.h"
#endif
+namespace {
+
+struct MicrosecondsToInterval
+{
+ PRIntervalTime operator[](size_t aMs) const {
+ return PR_MicrosecondsToInterval(aMs);
+ }
+};
+
+struct IntervalComparator
+{
+ int operator()(PRIntervalTime aInterval) const {
+ return (0 < aInterval) ? -1 : 1;
+ }
+};
+
+} // namespace
+
/* void Run(); */
NS_IMETHODIMP
TimerThread::Run()
{
PR_SetCurrentThreadName("Timer");
#ifdef MOZ_NUWA_PROCESS
if (IsNuwaProcess()) {
@@ -186,38 +205,32 @@ TimerThread::Run()
"NuwaMarkCurrentThread is undefined!");
NuwaMarkCurrentThread(nullptr, nullptr);
}
#endif
MonitorAutoLock lock(mMonitor);
// We need to know how many microseconds give a positive PRIntervalTime. This
- // is platform-dependent, we calculate it at runtime now.
- // First we find a value such that PR_MicrosecondsToInterval(high) = 1
- int32_t low = 0, high = 1;
- while (PR_MicrosecondsToInterval(high) == 0) {
- high <<= 1;
+ // is platform-dependent and we calculate it at runtime, finding a value |v|
+ // such that |PR_MicrosecondsToInterval(v) > 0| and then binary-searching in
+ // the range [0, v) to find the ms-to-interval scale.
+ uint32_t usForPosInterval = 1;
+ while (PR_MicrosecondsToInterval(usForPosInterval) == 0) {
+ usForPosInterval <<= 1;
}
- // We now have
- // PR_MicrosecondsToInterval(low) = 0
- // PR_MicrosecondsToInterval(high) = 1
- // and we can proceed to find the critical value using binary search
- while (high - low > 1) {
- int32_t mid = (high + low) >> 1;
- if (PR_MicrosecondsToInterval(mid) == 0) {
- low = mid;
- } else {
- high = mid;
- }
- }
+
+ size_t usIntervalResolution;
+ BinarySearchIf(MicrosecondsToInterval(), 0, usForPosInterval, IntervalComparator(), &usIntervalResolution);
+ MOZ_ASSERT(PR_MicrosecondsToInterval(usIntervalResolution - 1) == 0);
+ MOZ_ASSERT(PR_MicrosecondsToInterval(usIntervalResolution) == 1);
// Half of the amount of microseconds needed to get positive PRIntervalTime.
// We use this to decide how to round our wait times later
- int32_t halfMicrosecondsIntervalResolution = high >> 1;
+ int32_t halfMicrosecondsIntervalResolution = usIntervalResolution / 2;
bool forceRunNextTimer = false;
while (!mShutdown) {
// Have to use PRIntervalTime here, since PR_WaitCondVar takes it
PRIntervalTime waitFor;
bool forceRunThisTimer = forceRunNextTimer;
forceRunNextTimer = false;
