michael@0: /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
michael@0: // vim:cindent:ts=4:et:sw=4:
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0:  * Code to sort cells by their colspan, used by BasicTableLayoutStrategy.
michael@0:  */
michael@0: 
michael@0: #include "SpanningCellSorter.h"
michael@0: #include "nsQuickSort.h"
michael@0: #include "nsIPresShell.h"
michael@0: 
michael@0: //#define DEBUG_SPANNING_CELL_SORTER
michael@0: 
michael@0: SpanningCellSorter::SpanningCellSorter()
michael@0:   : mState(ADDING)
michael@0:   , mSortedHashTable(nullptr)
michael@0: {
michael@0:     memset(mArray, 0, sizeof(mArray));
michael@0:     mHashTable.entryCount = 0;
michael@0: }
michael@0: 
michael@0: SpanningCellSorter::~SpanningCellSorter()
michael@0: {
michael@0:     if (mHashTable.entryCount) {
michael@0:         PL_DHashTableFinish(&mHashTable);
michael@0:         mHashTable.entryCount = 0;
michael@0:     }
michael@0:     delete [] mSortedHashTable;
michael@0: }
michael@0: 
michael@0: /* static */ const PLDHashTableOps
michael@0: SpanningCellSorter::HashTableOps = {
michael@0:     PL_DHashAllocTable,
michael@0:     PL_DHashFreeTable,
michael@0:     HashTableHashKey,
michael@0:     HashTableMatchEntry,
michael@0:     PL_DHashMoveEntryStub,
michael@0:     PL_DHashClearEntryStub,
michael@0:     PL_DHashFinalizeStub,
michael@0:     nullptr
michael@0: };
michael@0: 
michael@0: /* static */ PLDHashNumber
michael@0: SpanningCellSorter::HashTableHashKey(PLDHashTable *table, const void *key)
michael@0: {
michael@0:     return NS_PTR_TO_INT32(key);
michael@0: }
michael@0: 
michael@0: /* static */ bool
michael@0: SpanningCellSorter::HashTableMatchEntry(PLDHashTable *table,
michael@0:                                         const PLDHashEntryHdr *hdr,
michael@0:                                         const void *key)
michael@0: {
michael@0:     const HashTableEntry *entry = static_cast<const HashTableEntry*>(hdr);
michael@0:     return NS_PTR_TO_INT32(key) == entry->mColSpan;
michael@0: }
michael@0: 
michael@0: bool
michael@0: SpanningCellSorter::AddCell(int32_t aColSpan, int32_t aRow, int32_t aCol)
michael@0: {
michael@0:     NS_ASSERTION(mState == ADDING, "cannot call AddCell after GetNext");
michael@0:     NS_ASSERTION(aColSpan >= ARRAY_BASE, "cannot add cells with colspan<2");
michael@0: 
michael@0:     Item *i = (Item*) mozilla::AutoStackArena::Allocate(sizeof(Item));
michael@0:     NS_ENSURE_TRUE(i != nullptr, false);
michael@0: 
michael@0:     i->row = aRow;
michael@0:     i->col = aCol;
michael@0: 
michael@0:     if (UseArrayForSpan(aColSpan)) {
michael@0:         int32_t index = SpanToIndex(aColSpan);
michael@0:         i->next = mArray[index];
michael@0:         mArray[index] = i;
michael@0:     } else {
michael@0:         if (!mHashTable.entryCount) {
michael@0:             PL_DHashTableInit(&mHashTable, &HashTableOps, nullptr,
michael@0:                               sizeof(HashTableEntry), PL_DHASH_MIN_SIZE);
michael@0:         }
michael@0:         HashTableEntry *entry = static_cast<HashTableEntry*>
michael@0:                                            (PL_DHashTableOperate(&mHashTable, NS_INT32_TO_PTR(aColSpan),
michael@0:                                  PL_DHASH_ADD));
michael@0:         NS_ENSURE_TRUE(entry, false);
michael@0: 
michael@0:         NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan,
michael@0:                      "wrong entry");
michael@0:         NS_ASSERTION((entry->mColSpan == 0) == (entry->mItems == nullptr),
michael@0:                      "entry should be either new or properly initialized");
michael@0:         entry->mColSpan = aColSpan;
michael@0: 
michael@0:         i->next = entry->mItems;
michael@0:         entry->mItems = i;
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: /* static */ PLDHashOperator
michael@0: SpanningCellSorter::FillSortedArray(PLDHashTable *table, PLDHashEntryHdr *hdr,
michael@0:                                     uint32_t number, void *arg)
michael@0: {
michael@0:     HashTableEntry *entry = static_cast<HashTableEntry*>(hdr);
michael@0:     HashTableEntry **sh = static_cast<HashTableEntry**>(arg);
michael@0: 
michael@0:     sh[number] = entry;
michael@0: 
michael@0:     return PL_DHASH_NEXT;
michael@0: }
michael@0: 
michael@0: /* static */ int
michael@0: SpanningCellSorter::SortArray(const void *a, const void *b, void *closure)
michael@0: {
michael@0:     int32_t spanA = (*static_cast<HashTableEntry*const*>(a))->mColSpan;
michael@0:     int32_t spanB = (*static_cast<HashTableEntry*const*>(b))->mColSpan;
michael@0: 
michael@0:     if (spanA < spanB)
michael@0:         return -1;
michael@0:     if (spanA == spanB)
michael@0:         return 0;
michael@0:     return 1;
michael@0: }
michael@0: 
michael@0: SpanningCellSorter::Item*
michael@0: SpanningCellSorter::GetNext(int32_t *aColSpan)
michael@0: {
michael@0:     NS_ASSERTION(mState != DONE, "done enumerating, stop calling");
michael@0: 
michael@0:     switch (mState) {
michael@0:         case ADDING:
michael@0:             /* prepare to enumerate the array */
michael@0:             mState = ENUMERATING_ARRAY;
michael@0:             mEnumerationIndex = 0;
michael@0:             /* fall through */
michael@0:         case ENUMERATING_ARRAY:
michael@0:             while (mEnumerationIndex < ARRAY_SIZE && !mArray[mEnumerationIndex])
michael@0:                 ++mEnumerationIndex;
michael@0:             if (mEnumerationIndex < ARRAY_SIZE) {
michael@0:                 Item *result = mArray[mEnumerationIndex];
michael@0:                 *aColSpan = IndexToSpan(mEnumerationIndex);
michael@0:                 NS_ASSERTION(result, "logic error");
michael@0: #ifdef DEBUG_SPANNING_CELL_SORTER
michael@0:                 printf("SpanningCellSorter[%p]:"
michael@0:                        " returning list for colspan=%d from array\n",
michael@0:                        static_cast<void*>(this), *aColSpan);
michael@0: #endif
michael@0:                 ++mEnumerationIndex;
michael@0:                 return result;
michael@0:             }
michael@0:             /* prepare to enumerate the hash */
michael@0:             mState = ENUMERATING_HASH;
michael@0:             mEnumerationIndex = 0;
michael@0:             if (mHashTable.entryCount) {
michael@0:                 HashTableEntry **sh =
michael@0:                     new HashTableEntry*[mHashTable.entryCount];
michael@0:                 if (!sh) {
michael@0:                     // give up
michael@0:                     mState = DONE;
michael@0:                     return nullptr;
michael@0:                 }
michael@0:                 PL_DHashTableEnumerate(&mHashTable, FillSortedArray, sh);
michael@0:                 NS_QuickSort(sh, mHashTable.entryCount, sizeof(sh[0]),
michael@0:                              SortArray, nullptr);
michael@0:                 mSortedHashTable = sh;
michael@0:             }
michael@0:             /* fall through */
michael@0:         case ENUMERATING_HASH:
michael@0:             if (mEnumerationIndex < mHashTable.entryCount) {
michael@0:                 Item *result = mSortedHashTable[mEnumerationIndex]->mItems;
michael@0:                 *aColSpan = mSortedHashTable[mEnumerationIndex]->mColSpan;
michael@0:                 NS_ASSERTION(result, "holes in hash table");
michael@0: #ifdef DEBUG_SPANNING_CELL_SORTER
michael@0:                 printf("SpanningCellSorter[%p]:"
michael@0:                        " returning list for colspan=%d from hash\n",
michael@0:                        static_cast<void*>(this), *aColSpan);
michael@0: #endif
michael@0:                 ++mEnumerationIndex;
michael@0:                 return result;
michael@0:             }
michael@0:             mState = DONE;
michael@0:             /* fall through */
michael@0:         case DONE:
michael@0:             ;
michael@0:     }
michael@0:     return nullptr;
michael@0: }