The Tor Browser / annotate

layout/tables/SpanningCellSorter.cpp@7e26c7da4463 (annotated)

layout/tables/SpanningCellSorter.cpp

Wed, 31 Dec 2014 06:55:50 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Wed, 31 Dec 2014 06:55:50 +0100
changeset 2
7e26c7da4463
permissions
-rw-r--r--

Added tag UPSTREAM_283F7C6 for changeset ca08bd8f51b2

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial