The Tor Browser / file comparison
comparison: layout/tables/SpanningCellSorter.cpp
layout/tables/SpanningCellSorter.cpp
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
equal
deleted
inserted
replaced
| -1:000000000000 | 0:d5fa72e3d489 |
|---|---|
| 1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ | |
| 2 // vim:cindent:ts=4:et:sw=4: | |
| 3 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 4 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 6 | |
| 7 /* | |
| 8 * Code to sort cells by their colspan, used by BasicTableLayoutStrategy. | |
| 9 */ | |
| 10 | |
| 11 #include "SpanningCellSorter.h" | |
| 12 #include "nsQuickSort.h" | |
| 13 #include "nsIPresShell.h" | |
| 14 | |
| 15 //#define DEBUG_SPANNING_CELL_SORTER | |
| 16 | |
| 17 SpanningCellSorter::SpanningCellSorter() | |
| 18 : mState(ADDING) | |
| 19 , mSortedHashTable(nullptr) | |
| 20 { | |
| 21 memset(mArray, 0, sizeof(mArray)); | |
| 22 mHashTable.entryCount = 0; | |
| 23 } | |
| 24 | |
| 25 SpanningCellSorter::~SpanningCellSorter() | |
| 26 { | |
| 27 if (mHashTable.entryCount) { | |
| 28 PL_DHashTableFinish(&mHashTable); | |
| 29 mHashTable.entryCount = 0; | |
| 30 } | |
| 31 delete [] mSortedHashTable; | |
| 32 } | |
| 33 | |
| 34 /* static */ const PLDHashTableOps | |
| 35 SpanningCellSorter::HashTableOps = { | |
| 36 PL_DHashAllocTable, | |
| 37 PL_DHashFreeTable, | |
| 38 HashTableHashKey, | |
| 39 HashTableMatchEntry, | |
| 40 PL_DHashMoveEntryStub, | |
| 41 PL_DHashClearEntryStub, | |
| 42 PL_DHashFinalizeStub, | |
| 43 nullptr | |
| 44 }; | |
| 45 | |
| 46 /* static */ PLDHashNumber | |
| 47 SpanningCellSorter::HashTableHashKey(PLDHashTable *table, const void *key) | |
| 48 { | |
| 49 return NS_PTR_TO_INT32(key); | |
| 50 } | |
| 51 | |
| 52 /* static */ bool | |
| 53 SpanningCellSorter::HashTableMatchEntry(PLDHashTable *table, | |
| 54 const PLDHashEntryHdr *hdr, | |
| 55 const void *key) | |
| 56 { | |
| 57 const HashTableEntry *entry = static_cast<const HashTableEntry*>(hdr); | |
| 58 return NS_PTR_TO_INT32(key) == entry->mColSpan; | |
| 59 } | |
| 60 | |
| 61 bool | |
| 62 SpanningCellSorter::AddCell(int32_t aColSpan, int32_t aRow, int32_t aCol) | |
| 63 { | |
| 64 NS_ASSERTION(mState == ADDING, "cannot call AddCell after GetNext"); | |
| 65 NS_ASSERTION(aColSpan >= ARRAY_BASE, "cannot add cells with colspan<2"); | |
| 66 | |
| 67 Item *i = (Item*) mozilla::AutoStackArena::Allocate(sizeof(Item)); | |
| 68 NS_ENSURE_TRUE(i != nullptr, false); | |
| 69 | |
| 70 i->row = aRow; | |
| 71 i->col = aCol; | |
| 72 | |
| 73 if (UseArrayForSpan(aColSpan)) { | |
| 74 int32_t index = SpanToIndex(aColSpan); | |
| 75 i->next = mArray[index]; | |
| 76 mArray[index] = i; | |
| 77 } else { | |
| 78 if (!mHashTable.entryCount) { | |
| 79 PL_DHashTableInit(&mHashTable, &HashTableOps, nullptr, | |
| 80 sizeof(HashTableEntry), PL_DHASH_MIN_SIZE); | |
| 81 } | |
| 82 HashTableEntry *entry = static_cast<HashTableEntry*> | |
| 83 (PL_DHashTableOperate(&mHashTable, NS_INT32_TO_PTR(aColSpan), | |
| 84 PL_DHASH_ADD)); | |
| 85 NS_ENSURE_TRUE(entry, false); | |
| 86 | |
| 87 NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan, | |
| 88 "wrong entry"); | |
| 89 NS_ASSERTION((entry->mColSpan == 0) == (entry->mItems == nullptr), | |
| 90 "entry should be either new or properly initialized"); | |
| 91 entry->mColSpan = aColSpan; | |
| 92 | |
| 93 i->next = entry->mItems; | |
| 94 entry->mItems = i; | |
| 95 } | |
| 96 | |
| 97 return true; | |
| 98 } | |
| 99 | |
| 100 /* static */ PLDHashOperator | |
| 101 SpanningCellSorter::FillSortedArray(PLDHashTable *table, PLDHashEntryHdr *hdr, | |
| 102 uint32_t number, void *arg) | |
| 103 { | |
| 104 HashTableEntry *entry = static_cast<HashTableEntry*>(hdr); | |
| 105 HashTableEntry **sh = static_cast<HashTableEntry**>(arg); | |
| 106 | |
| 107 sh[number] = entry; | |
| 108 | |
| 109 return PL_DHASH_NEXT; | |
| 110 } | |
| 111 | |
| 112 /* static */ int | |
| 113 SpanningCellSorter::SortArray(const void *a, const void *b, void *closure) | |
| 114 { | |
| 115 int32_t spanA = (*static_cast<HashTableEntry*const*>(a))->mColSpan; | |
| 116 int32_t spanB = (*static_cast<HashTableEntry*const*>(b))->mColSpan; | |
| 117 | |
| 118 if (spanA < spanB) | |
| 119 return -1; | |
| 120 if (spanA == spanB) | |
| 121 return 0; | |
| 122 return 1; | |
| 123 } | |
| 124 | |
| 125 SpanningCellSorter::Item* | |
| 126 SpanningCellSorter::GetNext(int32_t *aColSpan) | |
| 127 { | |
| 128 NS_ASSERTION(mState != DONE, "done enumerating, stop calling"); | |
| 129 | |
| 130 switch (mState) { | |
| 131 case ADDING: | |
| 132 /* prepare to enumerate the array */ | |
| 133 mState = ENUMERATING_ARRAY; | |
| 134 mEnumerationIndex = 0; | |
| 135 /* fall through */ | |
| 136 case ENUMERATING_ARRAY: | |
| 137 while (mEnumerationIndex < ARRAY_SIZE && !mArray[mEnumerationIndex]) | |
| 138 ++mEnumerationIndex; | |
| 139 if (mEnumerationIndex < ARRAY_SIZE) { | |
| 140 Item *result = mArray[mEnumerationIndex]; | |
| 141 *aColSpan = IndexToSpan(mEnumerationIndex); | |
| 142 NS_ASSERTION(result, "logic error"); | |
| 143 #ifdef DEBUG_SPANNING_CELL_SORTER | |
| 144 printf("SpanningCellSorter[%p]:" | |
| 145 " returning list for colspan=%d from array\n", | |
| 146 static_cast<void*>(this), *aColSpan); | |
| 147 #endif | |
| 148 ++mEnumerationIndex; | |
| 149 return result; | |
| 150 } | |
| 151 /* prepare to enumerate the hash */ | |
| 152 mState = ENUMERATING_HASH; | |
| 153 mEnumerationIndex = 0; | |
| 154 if (mHashTable.entryCount) { | |
| 155 HashTableEntry **sh = | |
| 156 new HashTableEntry*[mHashTable.entryCount]; | |
| 157 if (!sh) { | |
| 158 // give up | |
| 159 mState = DONE; | |
| 160 return nullptr; | |
| 161 } | |
| 162 PL_DHashTableEnumerate(&mHashTable, FillSortedArray, sh); | |
| 163 NS_QuickSort(sh, mHashTable.entryCount, sizeof(sh[0]), | |
| 164 SortArray, nullptr); | |
| 165 mSortedHashTable = sh; | |
| 166 } | |
| 167 /* fall through */ | |
| 168 case ENUMERATING_HASH: | |
| 169 if (mEnumerationIndex < mHashTable.entryCount) { | |
| 170 Item *result = mSortedHashTable[mEnumerationIndex]->mItems; | |
| 171 *aColSpan = mSortedHashTable[mEnumerationIndex]->mColSpan; | |
| 172 NS_ASSERTION(result, "holes in hash table"); | |
| 173 #ifdef DEBUG_SPANNING_CELL_SORTER | |
| 174 printf("SpanningCellSorter[%p]:" | |
| 175 " returning list for colspan=%d from hash\n", | |
| 176 static_cast<void*>(this), *aColSpan); | |
| 177 #endif | |
| 178 ++mEnumerationIndex; | |
| 179 return result; | |
| 180 } | |
| 181 mState = DONE; | |
| 182 /* fall through */ | |
| 183 case DONE: | |
| 184 ; | |
| 185 } | |
| 186 return nullptr; | |
| 187 } |
