layout/tables/SpanningCellSorter.cpp

   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
  15 //#define DEBUG_SPANNING_CELL_SORTER
  16
  17 SpanningCellSorter::SpanningCellSorter()
  18   : mState(ADDING)
  19   , mSortedHashTable(nullptr)
  20 {
  21     memset(mArray, 0, sizeof(mArray));
  22     mHashTable.entryCount = 0;
  23 }
  24
  25 SpanningCellSorter::~SpanningCellSorter()
  26 {
  27     if (mHashTable.entryCount) {
  28         PL_DHashTableFinish(&mHashTable);
  29         mHashTable.entryCount = 0;
  30     }
  31     delete [] mSortedHashTable;
  32 }
  33
  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 };
  45
  46 /* static */ PLDHashNumber
  47 SpanningCellSorter::HashTableHashKey(PLDHashTable *table, const void *key)
  48 {
  49     return NS_PTR_TO_INT32(key);
  50 }
  51
  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 }
  60
  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");
  66
  67     Item *i = (Item*) mozilla::AutoStackArena::Allocate(sizeof(Item));
  68     NS_ENSURE_TRUE(i != nullptr, false);
  69
  70     i->row = aRow;
  71     i->col = aCol;
  72
  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             NS_NOTREACHED("table init failed");
  82             mHashTable.entryCount = 0;
  83             return false;
  84         }
  85         HashTableEntry *entry = static_cast<HashTableEntry*>
  86                                            (PL_DHashTableOperate(&mHashTable, NS_INT32_TO_PTR(aColSpan),
  87                                  PL_DHASH_ADD));
  88         NS_ENSURE_TRUE(entry, false);
  89
  90         NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan,
  91                      "wrong entry");
  92         NS_ASSERTION((entry->mColSpan == 0) == (entry->mItems == nullptr),
  93                      "entry should be either new or properly initialized");
  94         entry->mColSpan = aColSpan;
  95
  96         i->next = entry->mItems;
  97         entry->mItems = i;
  98     }
  99
 100     return true;
 101 }
 102
 103 /* static */ PLDHashOperator
 104 SpanningCellSorter::FillSortedArray(PLDHashTable *table, PLDHashEntryHdr *hdr,
 105                                     uint32_t number, void *arg)
 106 {
 107     HashTableEntry *entry = static_cast<HashTableEntry*>(hdr);
 108     HashTableEntry **sh = static_cast<HashTableEntry**>(arg);
 109
 110     sh[number] = entry;
 111
 112     return PL_DHASH_NEXT;
 113 }
 114
 115 /* static */ int
 116 SpanningCellSorter::SortArray(const void *a, const void *b, void *closure)
 117 {
 118     int32_t spanA = (*static_cast<HashTableEntry*const*>(a))->mColSpan;
 119     int32_t spanB = (*static_cast<HashTableEntry*const*>(b))->mColSpan;
 120
 121     if (spanA < spanB)
 122         return -1;
 123     if (spanA == spanB)
 124         return 0;
 125     return 1;
 126 }
 127
 128 SpanningCellSorter::Item*
 129 SpanningCellSorter::GetNext(int32_t *aColSpan)
 130 {
 131     NS_ASSERTION(mState != DONE, "done enumerating, stop calling");
 132
 133     switch (mState) {
 134         case ADDING:
 135             /* prepare to enumerate the array */
 136             mState = ENUMERATING_ARRAY;
 137             mEnumerationIndex = 0;
 138             /* fall through */
 139         case ENUMERATING_ARRAY:
 140             while (mEnumerationIndex < ARRAY_SIZE && !mArray[mEnumerationIndex])
 141                 ++mEnumerationIndex;
 142             if (mEnumerationIndex < ARRAY_SIZE) {
 143                 Item *result = mArray[mEnumerationIndex];
 144                 *aColSpan = IndexToSpan(mEnumerationIndex);
 145                 NS_ASSERTION(result, "logic error");
 146 #ifdef DEBUG_SPANNING_CELL_SORTER
 147                 printf("SpanningCellSorter[%p]:"
 148                        " returning list for colspan=%d from array\n",
 149                        static_cast<void*>(this), *aColSpan);
 150 #endif
 151                 ++mEnumerationIndex;
 152                 return result;
 153             }
 154             /* prepare to enumerate the hash */
 155             mState = ENUMERATING_HASH;
 156             mEnumerationIndex = 0;
 157             if (mHashTable.entryCount) {
 158                 HashTableEntry **sh =
 159                     new HashTableEntry*[mHashTable.entryCount];
 160                 if (!sh) {
 161                     // give up
 162                     mState = DONE;
 163                     return nullptr;
 164                 }
 165                 PL_DHashTableEnumerate(&mHashTable, FillSortedArray, sh);
 166                 NS_QuickSort(sh, mHashTable.entryCount, sizeof(sh[0]),
 167                              SortArray, nullptr);
 168                 mSortedHashTable = sh;
 169             }
 170             /* fall through */
 171         case ENUMERATING_HASH:
 172             if (mEnumerationIndex < mHashTable.entryCount) {
 173                 Item *result = mSortedHashTable[mEnumerationIndex]->mItems;
 174                 *aColSpan = mSortedHashTable[mEnumerationIndex]->mColSpan;
 175                 NS_ASSERTION(result, "holes in hash table");
 176 #ifdef DEBUG_SPANNING_CELL_SORTER
 177                 printf("SpanningCellSorter[%p]:"
 178                        " returning list for colspan=%d from hash\n",
 179                        static_cast<void*>(this), *aColSpan);
 180 #endif
 181                 ++mEnumerationIndex;
 182                 return result;
 183             }
 184             mState = DONE;
 185             /* fall through */
 186         case DONE:
 187             ;
 188     }
 189     return nullptr;
 190 }