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