1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/layout/tables/SpanningCellSorter.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,187 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
1.5 +// vim:cindent:ts=4:et:sw=4:
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/*
1.11 + * Code to sort cells by their colspan, used by BasicTableLayoutStrategy.
1.12 + */
1.13 +
1.14 +#include "SpanningCellSorter.h"
1.15 +#include "nsQuickSort.h"
1.16 +#include "nsIPresShell.h"
1.17 +
1.18 +//#define DEBUG_SPANNING_CELL_SORTER
1.19 +
1.20 +SpanningCellSorter::SpanningCellSorter()
1.21 + : mState(ADDING)
1.22 + , mSortedHashTable(nullptr)
1.23 +{
1.24 + memset(mArray, 0, sizeof(mArray));
1.25 + mHashTable.entryCount = 0;
1.26 +}
1.27 +
1.28 +SpanningCellSorter::~SpanningCellSorter()
1.29 +{
1.30 + if (mHashTable.entryCount) {
1.31 + PL_DHashTableFinish(&mHashTable);
1.32 + mHashTable.entryCount = 0;
1.33 + }
1.34 + delete [] mSortedHashTable;
1.35 +}
1.36 +
1.37 +/* static */ const PLDHashTableOps
1.38 +SpanningCellSorter::HashTableOps = {
1.39 + PL_DHashAllocTable,
1.40 + PL_DHashFreeTable,
1.41 + HashTableHashKey,
1.42 + HashTableMatchEntry,
1.43 + PL_DHashMoveEntryStub,
1.44 + PL_DHashClearEntryStub,
1.45 + PL_DHashFinalizeStub,
1.46 + nullptr
1.47 +};
1.48 +
1.49 +/* static */ PLDHashNumber
1.50 +SpanningCellSorter::HashTableHashKey(PLDHashTable *table, const void *key)
1.51 +{
1.52 + return NS_PTR_TO_INT32(key);
1.53 +}
1.54 +
1.55 +/* static */ bool
1.56 +SpanningCellSorter::HashTableMatchEntry(PLDHashTable *table,
1.57 + const PLDHashEntryHdr *hdr,
1.58 + const void *key)
1.59 +{
1.60 + const HashTableEntry *entry = static_cast<const HashTableEntry*>(hdr);
1.61 + return NS_PTR_TO_INT32(key) == entry->mColSpan;
1.62 +}
1.63 +
1.64 +bool
1.65 +SpanningCellSorter::AddCell(int32_t aColSpan, int32_t aRow, int32_t aCol)
1.66 +{
1.67 + NS_ASSERTION(mState == ADDING, "cannot call AddCell after GetNext");
1.68 + NS_ASSERTION(aColSpan >= ARRAY_BASE, "cannot add cells with colspan<2");
1.69 +
1.70 + Item *i = (Item*) mozilla::AutoStackArena::Allocate(sizeof(Item));
1.71 + NS_ENSURE_TRUE(i != nullptr, false);
1.72 +
1.73 + i->row = aRow;
1.74 + i->col = aCol;
1.75 +
1.76 + if (UseArrayForSpan(aColSpan)) {
1.77 + int32_t index = SpanToIndex(aColSpan);
1.78 + i->next = mArray[index];
1.79 + mArray[index] = i;
1.80 + } else {
1.81 + if (!mHashTable.entryCount) {
1.82 + PL_DHashTableInit(&mHashTable, &HashTableOps, nullptr,
1.83 + sizeof(HashTableEntry), PL_DHASH_MIN_SIZE);
1.84 + }
1.85 + HashTableEntry *entry = static_cast<HashTableEntry*>
1.86 + (PL_DHashTableOperate(&mHashTable, NS_INT32_TO_PTR(aColSpan),
1.87 + PL_DHASH_ADD));
1.88 + NS_ENSURE_TRUE(entry, false);
1.89 +
1.90 + NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan,
1.91 + "wrong entry");
1.92 + NS_ASSERTION((entry->mColSpan == 0) == (entry->mItems == nullptr),
1.93 + "entry should be either new or properly initialized");
1.94 + entry->mColSpan = aColSpan;
1.95 +
1.96 + i->next = entry->mItems;
1.97 + entry->mItems = i;
1.98 + }
1.99 +
1.100 + return true;
1.101 +}
1.102 +
1.103 +/* static */ PLDHashOperator
1.104 +SpanningCellSorter::FillSortedArray(PLDHashTable *table, PLDHashEntryHdr *hdr,
1.105 + uint32_t number, void *arg)
1.106 +{
1.107 + HashTableEntry *entry = static_cast<HashTableEntry*>(hdr);
1.108 + HashTableEntry **sh = static_cast<HashTableEntry**>(arg);
1.109 +
1.110 + sh[number] = entry;
1.111 +
1.112 + return PL_DHASH_NEXT;
1.113 +}
1.114 +
1.115 +/* static */ int
1.116 +SpanningCellSorter::SortArray(const void *a, const void *b, void *closure)
1.117 +{
1.118 + int32_t spanA = (*static_cast<HashTableEntry*const*>(a))->mColSpan;
1.119 + int32_t spanB = (*static_cast<HashTableEntry*const*>(b))->mColSpan;
1.120 +
1.121 + if (spanA < spanB)
1.122 + return -1;
1.123 + if (spanA == spanB)
1.124 + return 0;
1.125 + return 1;
1.126 +}
1.127 +
1.128 +SpanningCellSorter::Item*
1.129 +SpanningCellSorter::GetNext(int32_t *aColSpan)
1.130 +{
1.131 + NS_ASSERTION(mState != DONE, "done enumerating, stop calling");
1.132 +
1.133 + switch (mState) {
1.134 + case ADDING:
1.135 + /* prepare to enumerate the array */
1.136 + mState = ENUMERATING_ARRAY;
1.137 + mEnumerationIndex = 0;
1.138 + /* fall through */
1.139 + case ENUMERATING_ARRAY:
1.140 + while (mEnumerationIndex < ARRAY_SIZE && !mArray[mEnumerationIndex])
1.141 + ++mEnumerationIndex;
1.142 + if (mEnumerationIndex < ARRAY_SIZE) {
1.143 + Item *result = mArray[mEnumerationIndex];
1.144 + *aColSpan = IndexToSpan(mEnumerationIndex);
1.145 + NS_ASSERTION(result, "logic error");
1.146 +#ifdef DEBUG_SPANNING_CELL_SORTER
1.147 + printf("SpanningCellSorter[%p]:"
1.148 + " returning list for colspan=%d from array\n",
1.149 + static_cast<void*>(this), *aColSpan);
1.150 +#endif
1.151 + ++mEnumerationIndex;
1.152 + return result;
1.153 + }
1.154 + /* prepare to enumerate the hash */
1.155 + mState = ENUMERATING_HASH;
1.156 + mEnumerationIndex = 0;
1.157 + if (mHashTable.entryCount) {
1.158 + HashTableEntry **sh =
1.159 + new HashTableEntry*[mHashTable.entryCount];
1.160 + if (!sh) {
1.161 + // give up
1.162 + mState = DONE;
1.163 + return nullptr;
1.164 + }
1.165 + PL_DHashTableEnumerate(&mHashTable, FillSortedArray, sh);
1.166 + NS_QuickSort(sh, mHashTable.entryCount, sizeof(sh[0]),
1.167 + SortArray, nullptr);
1.168 + mSortedHashTable = sh;
1.169 + }
1.170 + /* fall through */
1.171 + case ENUMERATING_HASH:
1.172 + if (mEnumerationIndex < mHashTable.entryCount) {
1.173 + Item *result = mSortedHashTable[mEnumerationIndex]->mItems;
1.174 + *aColSpan = mSortedHashTable[mEnumerationIndex]->mColSpan;
1.175 + NS_ASSERTION(result, "holes in hash table");
1.176 +#ifdef DEBUG_SPANNING_CELL_SORTER
1.177 + printf("SpanningCellSorter[%p]:"
1.178 + " returning list for colspan=%d from hash\n",
1.179 + static_cast<void*>(this), *aColSpan);
1.180 +#endif
1.181 + ++mEnumerationIndex;
1.182 + return result;
1.183 + }
1.184 + mState = DONE;
1.185 + /* fall through */
1.186 + case DONE:
1.187 + ;
1.188 + }
1.189 + return nullptr;
1.190 +}
