layout/tables/SpanningCellSorter.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   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 "nsTArray.h"
  13 #include "mozilla/HashFunctions.h"
  14
  15 using namespace mozilla;
  16
  17 // #define DEBUG_SPANNING_CELL_SORTER
  18
  19 SpanningCellSorter::SpanningCellSorter()
  20     : mState(ADDING), mHashTable(&HashTableOps, sizeof(HashTableEntry)) {
  21   memset(mArray, 0, sizeof(mArray));
  22 }
  23
  24 SpanningCellSorter::~SpanningCellSorter() = default;
  25
  26 /* static */ const PLDHashTableOps SpanningCellSorter::HashTableOps = {
  27     HashTableHashKey, HashTableMatchEntry, PLDHashTable::MoveEntryStub,
  28     PLDHashTable::ClearEntryStub, nullptr};
  29
  30 /* static */
  31 PLDHashNumber SpanningCellSorter::HashTableHashKey(const void* key) {
  32   return HashGeneric(key);
  33 }
  34
  35 /* static */
  36 bool SpanningCellSorter::HashTableMatchEntry(const PLDHashEntryHdr* hdr,
  37                                              const void* key) {
  38   const HashTableEntry* entry = static_cast<const HashTableEntry*>(hdr);
  39   return NS_PTR_TO_INT32(key) == entry->mColSpan;
  40 }
  41
  42 bool SpanningCellSorter::AddCell(int32_t aColSpan, int32_t aRow, int32_t aCol) {
  43   NS_ASSERTION(mState == ADDING, "cannot call AddCell after GetNext");
  44   NS_ASSERTION(aColSpan >= ARRAY_BASE, "cannot add cells with colspan<2");
  45
  46   Item* i = (Item*)mozilla::AutoStackArena::Allocate(sizeof(Item));
  47   NS_ENSURE_TRUE(i != nullptr, false);
  48
  49   i->row = aRow;
  50   i->col = aCol;
  51
  52   if (UseArrayForSpan(aColSpan)) {
  53     int32_t index = SpanToIndex(aColSpan);
  54     i->next = mArray[index];
  55     mArray[index] = i;
  56   } else {
  57     auto entry = static_cast<HashTableEntry*>(
  58         mHashTable.Add(NS_INT32_TO_PTR(aColSpan), fallible));
  59     NS_ENSURE_TRUE(entry, false);
  60
  61     NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan,
  62                  "wrong entry");
  63     NS_ASSERTION((entry->mColSpan == 0) == (entry->mItems == nullptr),
  64                  "entry should be either new or properly initialized");
  65     entry->mColSpan = aColSpan;
  66
  67     i->next = entry->mItems;
  68     entry->mItems = i;
  69   }
  70
  71   return true;
  72 }
  73
  74 SpanningCellSorter::Item* SpanningCellSorter::GetNext(int32_t* aColSpan) {
  75   NS_ASSERTION(mState != DONE, "done enumerating, stop calling");
  76
  77   // Our comparator needs the SpanningCellSorter private HashTableEntry
  78   class HashTableEntryComparator {
  79    public:
  80     bool Equals(HashTableEntry* left, HashTableEntry* right) const {
  81       return left->mColSpan == right->mColSpan;
  82     }
  83     bool LessThan(HashTableEntry* left, HashTableEntry* right) const {
  84       return left->mColSpan < right->mColSpan;
  85     }
  86   };
  87
  88   switch (mState) {
  89     case ADDING:
  90       /* prepare to enumerate the array */
  91       mState = ENUMERATING_ARRAY;
  92       mEnumerationIndex = 0;
  93       [[fallthrough]];
  94     case ENUMERATING_ARRAY:
  95       while (mEnumerationIndex < ARRAY_SIZE && !mArray[mEnumerationIndex])
  96         ++mEnumerationIndex;
  97       if (mEnumerationIndex < ARRAY_SIZE) {
  98         Item* result = mArray[mEnumerationIndex];
  99         *aColSpan = IndexToSpan(mEnumerationIndex);
 100         NS_ASSERTION(result, "logic error");
 101 #ifdef DEBUG_SPANNING_CELL_SORTER
 102         printf(
 103             "SpanningCellSorter[%p]:"
 104             " returning list for colspan=%d from array\n",
 105             static_cast<void*>(this), *aColSpan);
 106 #endif
 107         ++mEnumerationIndex;
 108         return result;
 109       }
 110       /* prepare to enumerate the hash */
 111       mState = ENUMERATING_HASH;
 112       mEnumerationIndex = 0;
 113       if (mHashTable.EntryCount() > 0) {
 114         // This clear is a no-op if the array is empty and it makes us
 115         // resilient against re-entrance.
 116         mSortedHashTable.ClearAndRetainStorage();
 117         mSortedHashTable.SetCapacity(mHashTable.EntryCount());
 118         for (auto iter = mHashTable.ConstIter(); !iter.Done(); iter.Next()) {
 119           mSortedHashTable.AppendElement(
 120               static_cast<HashTableEntry*>(iter.Get()));
 121         }
 122         mSortedHashTable.Sort(HashTableEntryComparator());
 123       }
 124       [[fallthrough]];
 125     case ENUMERATING_HASH:
 126       if (mEnumerationIndex < mHashTable.EntryCount()) {
 127         Item* result = mSortedHashTable[mEnumerationIndex]->mItems;
 128         *aColSpan = mSortedHashTable[mEnumerationIndex]->mColSpan;
 129         NS_ASSERTION(result, "holes in hash table");
 130 #ifdef DEBUG_SPANNING_CELL_SORTER
 131         printf(
 132             "SpanningCellSorter[%p]:"
 133             " returning list for colspan=%d from hash\n",
 134             static_cast<void*>(this), *aColSpan);
 135 #endif
 136         ++mEnumerationIndex;
 137         return result;
 138       }
 139       mState = DONE;
 140       [[fallthrough]];
 141     case DONE:;
 142   }
 143   return nullptr;
 144 }