tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

SpanningCellSorter.cpp (4893B)

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