Line data    Source code

       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             : #include "mozilla/HashFunctions.h"
      15             : 
      16             : //#define DEBUG_SPANNING_CELL_SORTER
      17             : 
      18           0 : SpanningCellSorter::SpanningCellSorter()
      19             :   : mState(ADDING)
      20             :   , mHashTable(&HashTableOps, sizeof(HashTableEntry))
      21           0 :   , mSortedHashTable(nullptr)
      22             : {
      23           0 :     memset(mArray, 0, sizeof(mArray));
      24           0 : }
      25             : 
      26           0 : SpanningCellSorter::~SpanningCellSorter()
      27             : {
      28           0 :     delete [] mSortedHashTable;
      29           0 : }
      30             : 
      31             : /* static */ const PLDHashTableOps
      32             : SpanningCellSorter::HashTableOps = {
      33             :     HashTableHashKey,
      34             :     HashTableMatchEntry,
      35             :     PLDHashTable::MoveEntryStub,
      36             :     PLDHashTable::ClearEntryStub,
      37             :     nullptr
      38             : };
      39             : 
      40             : /* static */ PLDHashNumber
      41           0 : SpanningCellSorter::HashTableHashKey(const void *key)
      42             : {
      43           0 :     return HashGeneric(key);
      44             : }
      45             : 
      46             : /* static */ bool
      47           0 : SpanningCellSorter::HashTableMatchEntry(const PLDHashEntryHdr *hdr,
      48             :                                         const void *key)
      49             : {
      50           0 :     const HashTableEntry *entry = static_cast<const HashTableEntry*>(hdr);
      51           0 :     return NS_PTR_TO_INT32(key) == entry->mColSpan;
      52             : }
      53             : 
      54             : bool
      55           0 : SpanningCellSorter::AddCell(int32_t aColSpan, int32_t aRow, int32_t aCol)
      56             : {
      57           0 :     NS_ASSERTION(mState == ADDING, "cannot call AddCell after GetNext");
      58           0 :     NS_ASSERTION(aColSpan >= ARRAY_BASE, "cannot add cells with colspan<2");
      59             : 
      60           0 :     Item *i = (Item*) mozilla::AutoStackArena::Allocate(sizeof(Item));
      61           0 :     NS_ENSURE_TRUE(i != nullptr, false);
      62             : 
      63           0 :     i->row = aRow;
      64           0 :     i->col = aCol;
      65             : 
      66           0 :     if (UseArrayForSpan(aColSpan)) {
      67           0 :         int32_t index = SpanToIndex(aColSpan);
      68           0 :         i->next = mArray[index];
      69           0 :         mArray[index] = i;
      70             :     } else {
      71             :         auto entry = static_cast<HashTableEntry*>
      72           0 :             (mHashTable.Add(NS_INT32_TO_PTR(aColSpan), fallible));
      73           0 :         NS_ENSURE_TRUE(entry, false);
      74             : 
      75           0 :         NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan,
      76             :                      "wrong entry");
      77           0 :         NS_ASSERTION((entry->mColSpan == 0) == (entry->mItems == nullptr),
      78             :                      "entry should be either new or properly initialized");
      79           0 :         entry->mColSpan = aColSpan;
      80             : 
      81           0 :         i->next = entry->mItems;
      82           0 :         entry->mItems = i;
      83             :     }
      84             : 
      85           0 :     return true;
      86             : }
      87             : 
      88             : /* static */ int
      89           0 : SpanningCellSorter::SortArray(const void *a, const void *b, void *closure)
      90             : {
      91           0 :     int32_t spanA = (*static_cast<HashTableEntry*const*>(a))->mColSpan;
      92           0 :     int32_t spanB = (*static_cast<HashTableEntry*const*>(b))->mColSpan;
      93             : 
      94           0 :     if (spanA < spanB)
      95           0 :         return -1;
      96           0 :     if (spanA == spanB)
      97           0 :         return 0;
      98           0 :     return 1;
      99             : }
     100             : 
     101             : SpanningCellSorter::Item*
     102           0 : SpanningCellSorter::GetNext(int32_t *aColSpan)
     103             : {
     104           0 :     NS_ASSERTION(mState != DONE, "done enumerating, stop calling");
     105             : 
     106           0 :     switch (mState) {
     107             :         case ADDING:
     108             :             /* prepare to enumerate the array */
     109           0 :             mState = ENUMERATING_ARRAY;
     110           0 :             mEnumerationIndex = 0;
     111             :             MOZ_FALLTHROUGH;
     112             :         case ENUMERATING_ARRAY:
     113           0 :             while (mEnumerationIndex < ARRAY_SIZE && !mArray[mEnumerationIndex])
     114           0 :                 ++mEnumerationIndex;
     115           0 :             if (mEnumerationIndex < ARRAY_SIZE) {
     116           0 :                 Item *result = mArray[mEnumerationIndex];
     117           0 :                 *aColSpan = IndexToSpan(mEnumerationIndex);
     118           0 :                 NS_ASSERTION(result, "logic error");
     119             : #ifdef DEBUG_SPANNING_CELL_SORTER
     120             :                 printf("SpanningCellSorter[%p]:"
     121             :                        " returning list for colspan=%d from array\n",
     122             :                        static_cast<void*>(this), *aColSpan);
     123             : #endif
     124           0 :                 ++mEnumerationIndex;
     125           0 :                 return result;
     126             :             }
     127             :             /* prepare to enumerate the hash */
     128           0 :             mState = ENUMERATING_HASH;
     129           0 :             mEnumerationIndex = 0;
     130           0 :             if (mHashTable.EntryCount() > 0) {
     131             :                 HashTableEntry **sh =
     132           0 :                     new HashTableEntry*[mHashTable.EntryCount()];
     133           0 :                 int32_t j = 0;
     134           0 :                 for (auto iter = mHashTable.Iter(); !iter.Done(); iter.Next()) {
     135           0 :                     sh[j++] = static_cast<HashTableEntry*>(iter.Get());
     136             :                 }
     137           0 :                 NS_QuickSort(sh, mHashTable.EntryCount(), sizeof(sh[0]),
     138           0 :                              SortArray, nullptr);
     139           0 :                 mSortedHashTable = sh;
     140             :             }
     141             :             MOZ_FALLTHROUGH;
     142             :         case ENUMERATING_HASH:
     143           0 :             if (mEnumerationIndex < mHashTable.EntryCount()) {
     144           0 :                 Item *result = mSortedHashTable[mEnumerationIndex]->mItems;
     145           0 :                 *aColSpan = mSortedHashTable[mEnumerationIndex]->mColSpan;
     146           0 :                 NS_ASSERTION(result, "holes in hash table");
     147             : #ifdef DEBUG_SPANNING_CELL_SORTER
     148             :                 printf("SpanningCellSorter[%p]:"
     149             :                        " returning list for colspan=%d from hash\n",
     150             :                        static_cast<void*>(this), *aColSpan);
     151             : #endif
     152           0 :                 ++mEnumerationIndex;
     153           0 :                 return result;
     154             :             }
     155           0 :             mState = DONE;
     156             :             MOZ_FALLTHROUGH;
     157             :         case DONE:
     158             :             ;
     159             :     }
     160           0 :     return nullptr;
     161             : }