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 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is Mozilla's table layout code.
  17  *
  18  * The Initial Developer of the Original Code is the Mozilla Foundation.
  19  * Portions created by the Initial Developer are Copyright (C) 2006
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *   L. David Baron <dbaron@dbaron.org> (original author)
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either the GNU General Public License Version 2 or later (the "GPL"), or
  27  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 /*
  40  * Code to sort cells by their colspan, used by BasicTableLayoutStrategy.
  41  */
  42
  43 #include "SpanningCellSorter.h"
  44 #include "nsQuickSort.h"
  45
  46 //#define DEBUG_SPANNING_CELL_SORTER
  47
  48 SpanningCellSorter::SpanningCellSorter(nsIPresShell *aPresShell)
  49   : mPresShell(aPresShell)
  50   , mState(ADDING)
  51   , mSortedHashTable(nsnull)
  52 {
  53     memset(mArray, 0, sizeof(mArray));
  54     mHashTable.entryCount = 0;
  55     mPresShell->PushStackMemory();
  56 }
  57
  58 SpanningCellSorter::~SpanningCellSorter()
  59 {
  60     if (mHashTable.entryCount) {
  61         PL_DHashTableFinish(&mHashTable);
  62         mHashTable.entryCount = 0;
  63     }
  64     delete [] mSortedHashTable;
  65     mPresShell->PopStackMemory();
  66 }
  67
  68 /* static */ PLDHashTableOps
  69 SpanningCellSorter::HashTableOps = {
  70     PL_DHashAllocTable,
  71     PL_DHashFreeTable,
  72     HashTableHashKey,
  73     HashTableMatchEntry,
  74     PL_DHashMoveEntryStub,
  75     PL_DHashClearEntryStub,
  76     PL_DHashFinalizeStub,
  77     nsnull
  78 };
  79
  80 /* static */ PLDHashNumber
  81 SpanningCellSorter::HashTableHashKey(PLDHashTable *table, const void *key)
  82 {
  83     return NS_PTR_TO_INT32(key);
  84 }
  85
  86 /* static */ PRBool
  87 SpanningCellSorter::HashTableMatchEntry(PLDHashTable *table,
  88                                         const PLDHashEntryHdr *hdr,
  89                                         const void *key)
  90 {
  91     const HashTableEntry *entry = static_cast<const HashTableEntry*>(hdr);
  92     return NS_PTR_TO_INT32(key) == entry->mColSpan;
  93 }
  94
  95 PRBool
  96 SpanningCellSorter::AddCell(PRInt32 aColSpan, PRInt32 aRow, PRInt32 aCol)
  97 {
  98     NS_ASSERTION(mState == ADDING, "cannot call AddCell after GetNext");
  99     NS_ASSERTION(aColSpan >= ARRAY_BASE, "cannot add cells with colspan<2");
 100
 101     Item *i = (Item*) mPresShell->AllocateStackMemory(sizeof(Item));
 102     NS_ENSURE_TRUE(i != nsnull, PR_FALSE);
 103
 104     i->row = aRow;
 105     i->col = aCol;
 106
 107     if (UseArrayForSpan(aColSpan)) {
 108         PRInt32 index = SpanToIndex(aColSpan);
 109         i->next = mArray[index];
 110         mArray[index] = i;
 111     } else {
 112         if (!mHashTable.entryCount &&
 113             !PL_DHashTableInit(&mHashTable, &HashTableOps, nsnull,
 114                                sizeof(HashTableEntry), PL_DHASH_MIN_SIZE)) {
 115             NS_NOTREACHED("table init failed");
 116             mHashTable.entryCount = 0;
 117             return PR_FALSE;
 118         }
 119         HashTableEntry *entry = static_cast<HashTableEntry*>
 120                                            (PL_DHashTableOperate(&mHashTable, NS_INT32_TO_PTR(aColSpan),
 121                                  PL_DHASH_ADD));
 122         NS_ENSURE_TRUE(entry, PR_FALSE);
 123
 124         NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan,
 125                      "wrong entry");
 126         NS_ASSERTION((entry->mColSpan == 0) == (entry->mItems == nsnull),
 127                      "entry should be either new or properly initialized");
 128         entry->mColSpan = aColSpan;
 129
 130         i->next = entry->mItems;
 131         entry->mItems = i;
 132     }
 133
 134     return PR_TRUE;
 135 }
 136
 137 /* static */ PLDHashOperator
 138 SpanningCellSorter::FillSortedArray(PLDHashTable *table, PLDHashEntryHdr *hdr,
 139                                     PRUint32 number, void *arg)
 140 {
 141     HashTableEntry *entry = static_cast<HashTableEntry*>(hdr);
 142     HashTableEntry **sh = static_cast<HashTableEntry**>(arg);
 143
 144     sh[number] = entry;
 145
 146     return PL_DHASH_NEXT;
 147 }
 148
 149 /* static */ int
 150 SpanningCellSorter::SortArray(const void *a, const void *b, void *closure)
 151 {
 152     PRInt32 spanA = (*static_cast<HashTableEntry*const*>(a))->mColSpan;
 153     PRInt32 spanB = (*static_cast<HashTableEntry*const*>(b))->mColSpan;
 154
 155     if (spanA < spanB)
 156         return -1;
 157     if (spanA == spanB)
 158         return 0;
 159     return 1;
 160 }
 161
 162 SpanningCellSorter::Item*
 163 SpanningCellSorter::GetNext(PRInt32 *aColSpan)
 164 {
 165     NS_ASSERTION(mState != DONE, "done enumerating, stop calling");
 166
 167     switch (mState) {
 168         case ADDING:
 169             /* prepare to enumerate the array */
 170             mState = ENUMERATING_ARRAY;
 171             mEnumerationIndex = 0;
 172             /* fall through */
 173         case ENUMERATING_ARRAY:
 174             while (mEnumerationIndex < ARRAY_SIZE && !mArray[mEnumerationIndex])
 175                 ++mEnumerationIndex;
 176             if (mEnumerationIndex < ARRAY_SIZE) {
 177                 Item *result = mArray[mEnumerationIndex];
 178                 *aColSpan = IndexToSpan(mEnumerationIndex);
 179                 NS_ASSERTION(result, "logic error");
 180 #ifdef DEBUG_SPANNING_CELL_SORTER
 181                 printf("SpanningCellSorter[%p]:"
 182                        " returning list for colspan=%d from array\n",
 183                        static_cast<void*>(this), *aColSpan);
 184 #endif
 185                 ++mEnumerationIndex;
 186                 return result;
 187             }
 188             /* prepare to enumerate the hash */
 189             mState = ENUMERATING_HASH;
 190             mEnumerationIndex = 0;
 191             if (mHashTable.entryCount) {
 192                 HashTableEntry **sh =
 193                     new HashTableEntry*[mHashTable.entryCount];
 194                 if (!sh) {
 195                     // give up
 196                     mState = DONE;
 197                     return nsnull;
 198                 }
 199                 PL_DHashTableEnumerate(&mHashTable, FillSortedArray, sh);
 200                 NS_QuickSort(sh, mHashTable.entryCount, sizeof(sh[0]),
 201                              SortArray, nsnull);
 202                 mSortedHashTable = sh;
 203             }
 204             /* fall through */
 205         case ENUMERATING_HASH:
 206             if (mEnumerationIndex < mHashTable.entryCount) {
 207                 Item *result = mSortedHashTable[mEnumerationIndex]->mItems;
 208                 *aColSpan = mSortedHashTable[mEnumerationIndex]->mColSpan;
 209                 NS_ASSERTION(result, "holes in hash table");
 210 #ifdef DEBUG_SPANNING_CELL_SORTER
 211                 printf("SpanningCellSorter[%p]:"
 212                        " returning list for colspan=%d from hash\n",
 213                        static_cast<void*>(this), *aColSpan);
 214 #endif
 215                 ++mEnumerationIndex;
 216                 return result;
 217             }
 218             mState = DONE;
 219             /* fall through */
 220         case DONE:
 221             ;
 222     }
 223     return nsnull;
 224 }