The Tor Browser: layout/tables/SpanningCellSorter.cpp@7e26c7da4463

     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/. */

     7 /*

     8  * Code to sort cells by their colspan, used by BasicTableLayoutStrategy.

     9  */

    11 #include "SpanningCellSorter.h"

    12 #include "nsQuickSort.h"

    13 #include "nsIPresShell.h"

    15 //#define DEBUG_SPANNING_CELL_SORTER

    17 SpanningCellSorter::SpanningCellSorter()

    18   : mState(ADDING)

    19   , mSortedHashTable(nullptr)

    20 {

    21     memset(mArray, 0, sizeof(mArray));

    22     mHashTable.entryCount = 0;

    23 }

    25 SpanningCellSorter::~SpanningCellSorter()

    26 {

    27     if (mHashTable.entryCount) {

    28         PL_DHashTableFinish(&mHashTable);

    29         mHashTable.entryCount = 0;

    30     }

    31     delete [] mSortedHashTable;

    32 }

    34 /* static */ const PLDHashTableOps

    35 SpanningCellSorter::HashTableOps = {

    36     PL_DHashAllocTable,

    37     PL_DHashFreeTable,

    38     HashTableHashKey,

    39     HashTableMatchEntry,

    40     PL_DHashMoveEntryStub,

    41     PL_DHashClearEntryStub,

    42     PL_DHashFinalizeStub,

    43     nullptr

    44 };

    46 /* static */ PLDHashNumber

    47 SpanningCellSorter::HashTableHashKey(PLDHashTable *table, const void *key)

    48 {

    49     return NS_PTR_TO_INT32(key);

    50 }

    52 /* static */ bool

    53 SpanningCellSorter::HashTableMatchEntry(PLDHashTable *table,

    54                                         const PLDHashEntryHdr *hdr,

    55                                         const void *key)

    56 {

    57     const HashTableEntry *entry = static_cast<const HashTableEntry*>(hdr);

    58     return NS_PTR_TO_INT32(key) == entry->mColSpan;

    59 }

    61 bool

    62 SpanningCellSorter::AddCell(int32_t aColSpan, int32_t aRow, int32_t aCol)

    63 {

    64     NS_ASSERTION(mState == ADDING, "cannot call AddCell after GetNext");

    65     NS_ASSERTION(aColSpan >= ARRAY_BASE, "cannot add cells with colspan<2");

    67     Item *i = (Item*) mozilla::AutoStackArena::Allocate(sizeof(Item));

    68     NS_ENSURE_TRUE(i != nullptr, false);

    70     i->row = aRow;

    71     i->col = aCol;

    73     if (UseArrayForSpan(aColSpan)) {

    74         int32_t index = SpanToIndex(aColSpan);

    75         i->next = mArray[index];

    76         mArray[index] = i;

    77     } else {

    78         if (!mHashTable.entryCount) {

    79             PL_DHashTableInit(&mHashTable, &HashTableOps, nullptr,

    80                               sizeof(HashTableEntry), PL_DHASH_MIN_SIZE);

    81         }

    82         HashTableEntry *entry = static_cast<HashTableEntry*>

    83                                            (PL_DHashTableOperate(&mHashTable, NS_INT32_TO_PTR(aColSpan),

    84                                  PL_DHASH_ADD));

    85         NS_ENSURE_TRUE(entry, false);

    87         NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan,

    88                      "wrong entry");

    89         NS_ASSERTION((entry->mColSpan == 0) == (entry->mItems == nullptr),

    90                      "entry should be either new or properly initialized");

    91         entry->mColSpan = aColSpan;

    93         i->next = entry->mItems;

    94         entry->mItems = i;

    95     }

    97     return true;

    98 }

   100 /* static */ PLDHashOperator

   101 SpanningCellSorter::FillSortedArray(PLDHashTable *table, PLDHashEntryHdr *hdr,

   102                                     uint32_t number, void *arg)

   103 {

   104     HashTableEntry *entry = static_cast<HashTableEntry*>(hdr);

   105     HashTableEntry **sh = static_cast<HashTableEntry**>(arg);

   107     sh[number] = entry;

   109     return PL_DHASH_NEXT;

   110 }

   112 /* static */ int

   113 SpanningCellSorter::SortArray(const void *a, const void *b, void *closure)

   114 {

   115     int32_t spanA = (*static_cast<HashTableEntry*const*>(a))->mColSpan;

   116     int32_t spanB = (*static_cast<HashTableEntry*const*>(b))->mColSpan;

   118     if (spanA < spanB)

   119         return -1;

   120     if (spanA == spanB)

   121         return 0;

   122     return 1;

   123 }

   125 SpanningCellSorter::Item*

   126 SpanningCellSorter::GetNext(int32_t *aColSpan)

   127 {

   128     NS_ASSERTION(mState != DONE, "done enumerating, stop calling");

   130     switch (mState) {

   131         case ADDING:

   132             /* prepare to enumerate the array */

   133             mState = ENUMERATING_ARRAY;

   134             mEnumerationIndex = 0;

   135             /* fall through */

   136         case ENUMERATING_ARRAY:

   137             while (mEnumerationIndex < ARRAY_SIZE && !mArray[mEnumerationIndex])

   138                 ++mEnumerationIndex;

   139             if (mEnumerationIndex < ARRAY_SIZE) {

   140                 Item *result = mArray[mEnumerationIndex];

   141                 *aColSpan = IndexToSpan(mEnumerationIndex);

   142                 NS_ASSERTION(result, "logic error");

   143 #ifdef DEBUG_SPANNING_CELL_SORTER

   144                 printf("SpanningCellSorter[%p]:"

   145                        " returning list for colspan=%d from array\n",

   146                        static_cast<void*>(this), *aColSpan);

   147 #endif

   148                 ++mEnumerationIndex;

   149                 return result;

   150             }

   151             /* prepare to enumerate the hash */

   152             mState = ENUMERATING_HASH;

   153             mEnumerationIndex = 0;

   154             if (mHashTable.entryCount) {

   155                 HashTableEntry **sh =

   156                     new HashTableEntry*[mHashTable.entryCount];

   157                 if (!sh) {

   158                     // give up

   159                     mState = DONE;

   160                     return nullptr;

   161                 }

   162                 PL_DHashTableEnumerate(&mHashTable, FillSortedArray, sh);

   163                 NS_QuickSort(sh, mHashTable.entryCount, sizeof(sh[0]),

   164                              SortArray, nullptr);

   165                 mSortedHashTable = sh;

   166             }

   167             /* fall through */

   168         case ENUMERATING_HASH:

   169             if (mEnumerationIndex < mHashTable.entryCount) {

   170                 Item *result = mSortedHashTable[mEnumerationIndex]->mItems;

   171                 *aColSpan = mSortedHashTable[mEnumerationIndex]->mColSpan;

   172                 NS_ASSERTION(result, "holes in hash table");

   173 #ifdef DEBUG_SPANNING_CELL_SORTER

   174                 printf("SpanningCellSorter[%p]:"

   175                        " returning list for colspan=%d from hash\n",

   176                        static_cast<void*>(this), *aColSpan);

   177 #endif

   178                 ++mEnumerationIndex;

   179                 return result;

   180             }

   181             mState = DONE;

   182             /* fall through */

   183         case DONE:

   184             ;

   185     }

   186     return nullptr;

   187 }

The Tor Browser / file revision