← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/content/xul/templates/src/nsConflictSet.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
mozilla/content/xul/templates/src/nsConflictSet.cpp
 
1
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
 
2
/* ***** BEGIN LICENSE BLOCK *****
 
3
 * Version: NPL 1.1/GPL 2.0/LGPL 2.1
 
4
 *
 
5
 * The contents of this file are subject to the Netscape Public License
 
6
 * Version 1.1 (the "License"); you may not use this file except in
 
7
 * compliance with the License. You may obtain a copy of the License at
 
8
 * http://www.mozilla.org/NPL/
 
9
 *
 
10
 * Software distributed under the License is distributed on an "AS IS" basis,
 
11
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 
12
 * for the specific language governing rights and limitations under the
 
13
 * License.
 
14
 *
 
15
 * The Original Code is Mozilla Communicator client code.
 
16
 *
 
17
 * The Initial Developer of the Original Code is 
 
18
 * Netscape Communications Corporation.
 
19
 * Portions created by the Initial Developer are Copyright (C) 1998
 
20
 * the Initial Developer. All Rights Reserved.
 
21
 *
 
22
 * Contributor(s):
 
23
 *   Chris Waterson <waterson@netscape.com>
 
24
 *
 
25
 *
 
26
 * Alternatively, the contents of this file may be used under the terms of
 
27
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 
28
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 
29
 * in which case the provisions of the GPL or the LGPL are applicable instead
 
30
 * of those above. If you wish to allow use of your version of this file only
 
31
 * under the terms of either the GPL or the LGPL, and not to allow others to
 
32
 * use your version of this file under the terms of the NPL, indicate your
 
33
 * decision by deleting the provisions above and replace them with the notice
 
34
 * and other provisions required by the GPL or the LGPL. If you do not delete
 
35
 * the provisions above, a recipient may use your version of this file under
 
36
 * the terms of any one of the NPL, the GPL or the LGPL.
 
37
 *
 
38
 * ***** END LICENSE BLOCK ***** */
 
39
 
 
40
#include "nsConflictSet.h"
 
41
#include "nsTemplateRule.h"
 
42
 
 
43
#ifdef PR_LOGGING
 
44
PRLogModule* nsConflictSet::gLog;
 
45
#endif
 
46
 
 
47
// Allocation operations for the cluster table
 
48
PLHashAllocOps nsConflictSet::gClusterAllocOps = {
 
49
    AllocClusterTable, FreeClusterTable, AllocClusterEntry, FreeClusterEntry };
 
50
 
 
51
// Allocation operations for the support table
 
52
PLHashAllocOps nsConflictSet::gSupportAllocOps = {
 
53
    AllocSupportTable, FreeSupportTable, AllocSupportEntry, FreeSupportEntry };
 
54
 
 
55
// Allocation operations for the binding table
 
56
PLHashAllocOps nsConflictSet::gBindingAllocOps = {
 
57
    AllocBindingTable, FreeBindingTable, AllocBindingEntry, FreeBindingEntry };
 
58
 
 
59
 
 
60
nsresult
 
61
nsConflictSet::Init()
 
62
{
 
63
#ifdef PR_LOGGING
 
64
    if (! gLog)
 
65
        gLog = PR_NewLogModule("nsConflictSet");
 
66
#endif
 
67
 
 
68
    static const size_t kBucketSizes[] = {
 
69
        sizeof(ClusterEntry),
 
70
        sizeof(SupportEntry),
 
71
        sizeof(BindingEntry),
 
72
    };
 
73
 
 
74
    static const PRInt32 kNumBuckets = sizeof(kBucketSizes) / sizeof(size_t);
 
75
 
 
76
    static const PRInt32 kNumResourceElements = 64;
 
77
 
 
78
    // Per news://news.mozilla.org/39BEC105.5090206%40netscape.com
 
79
    static const PRInt32 kInitialSize = 256;
 
80
 
 
81
    mPool.Init("nsConflictSet", kBucketSizes, kNumBuckets, kInitialSize);
 
82
 
 
83
    mClusters =
 
84
        PL_NewHashTable(kNumResourceElements /* XXXwaterson we need a way to give a hint? */,
 
85
                        nsClusterKey::HashClusterKey,
 
86
                        nsClusterKey::CompareClusterKeys,
 
87
                        PL_CompareValues,
 
88
                        &gClusterAllocOps,
 
89
                        &mPool);
 
90
 
 
91
    mSupport =
 
92
        PL_NewHashTable(kNumResourceElements, /* XXXwaterson need hint */
 
93
                        HashMemoryElement,
 
94
                        CompareMemoryElements,
 
95
                        PL_CompareValues,
 
96
                        &gSupportAllocOps,
 
97
                        &mPool);
 
98
 
 
99
    mBindingDependencies =
 
100
        PL_NewHashTable(kNumResourceElements /* XXX arbitrary */,
 
101
                        HashBindingElement,
 
102
                        CompareBindingElements,
 
103
                        PL_CompareValues,
 
104
                        &gBindingAllocOps,
 
105
                        &mPool);
 
106
 
 
107
    return NS_OK;
 
108
}
 
109
 
 
110
 
 
111
nsresult
 
112
nsConflictSet::Destroy()
 
113
{
 
114
    PL_HashTableDestroy(mSupport);
 
115
    PL_HashTableDestroy(mClusters);
 
116
    PL_HashTableDestroy(mBindingDependencies);
 
117
    return NS_OK;
 
118
}
 
119
 
 
120
nsresult
 
121
nsConflictSet::Add(nsTemplateMatch* aMatch)
 
122
{
 
123
    // Add a match to the conflict set. This involves adding it to
 
124
    // the cluster table, the support table, and the binding table.
 
125
 
 
126
    // add the match to a table indexed by instantiation key
 
127
    {
 
128
        nsClusterKey key(aMatch->mInstantiation, aMatch->mRule);
 
129
 
 
130
        PLHashNumber hash = key.Hash();
 
131
        PLHashEntry** hep = PL_HashTableRawLookup(mClusters, hash, &key);
 
132
 
 
133
        MatchCluster* cluster;
 
134
 
 
135
        if (hep && *hep) {
 
136
            cluster = NS_REINTERPRET_CAST(MatchCluster*, (*hep)->value);
 
137
        }
 
138
        else {
 
139
            PLHashEntry* he = PL_HashTableRawAdd(mClusters, hep, hash, &key, nsnull);
 
140
            if (! he)
 
141
                return NS_ERROR_OUT_OF_MEMORY;
 
142
 
 
143
            ClusterEntry* entry = NS_REINTERPRET_CAST(ClusterEntry*, he);
 
144
 
 
145
            // Fixup the key in the hashentry to point to the value
 
146
            // that the specially-allocated entry contains (rather
 
147
            // than the value on the stack). Do the same for its
 
148
            // value.
 
149
            entry->mHashEntry.key   = &entry->mKey;
 
150
            entry->mHashEntry.value = cluster = &entry->mCluster;
 
151
        }
 
152
 
 
153
        nsTemplateMatchRefSet& set = cluster->mMatches;
 
154
        if (! set.Contains(aMatch))
 
155
            set.Add(aMatch);
 
156
    }
 
157
 
 
158
 
 
159
    // Add the match to a table indexed by supporting MemoryElement
 
160
    {
 
161
        MemoryElementSet::ConstIterator last = aMatch->mInstantiation.mSupport.Last();
 
162
        for (MemoryElementSet::ConstIterator element = aMatch->mInstantiation.mSupport.First(); element != last; ++element) {
 
163
            PLHashNumber hash = element->Hash();
 
164
            PLHashEntry** hep = PL_HashTableRawLookup(mSupport, hash, element.operator->());
 
165
 
 
166
            nsTemplateMatchRefSet* set;
 
167
 
 
168
            if (hep && *hep) {
 
169
                set = NS_STATIC_CAST(nsTemplateMatchRefSet*, (*hep)->value);
 
170
            }
 
171
            else {
 
172
                PLHashEntry* he = PL_HashTableRawAdd(mSupport, hep, hash, element.operator->(), nsnull);
 
173
 
 
174
                SupportEntry* entry = NS_REINTERPRET_CAST(SupportEntry*, he);
 
175
                if (! entry)
 
176
                    return NS_ERROR_OUT_OF_MEMORY;
 
177
 
 
178
                // Fixup the key and value.
 
179
                entry->mHashEntry.key   = entry->mElement;
 
180
                entry->mHashEntry.value = &entry->mMatchSet;
 
181
 
 
182
                set = &entry->mMatchSet;
 
183
            }
 
184
 
 
185
            if (! set->Contains(aMatch)) {
 
186
                set->Add(aMatch);
 
187
                aMatch->AddRef();
 
188
            }
 
189
        }
 
190
    }
 
191
 
 
192
    // Add the match to a table indexed by bound MemoryElement
 
193
    nsResourceSet::ConstIterator last = aMatch->mBindingDependencies.Last();
 
194
    for (nsResourceSet::ConstIterator dep = aMatch->mBindingDependencies.First(); dep != last; ++dep)
 
195
        AddBindingDependency(aMatch, *dep);
 
196
 
 
197
    return NS_OK;
 
198
}
 
199
 
 
200
 
 
201
nsConflictSet::MatchCluster*
 
202
nsConflictSet::GetMatchesForClusterKey(const nsClusterKey& aKey)
 
203
{
 
204
    // Retrieve all the matches in a cluster
 
205
    return NS_STATIC_CAST(MatchCluster*, PL_HashTableLookup(mClusters, &aKey));
 
206
}
 
207
 
 
208
 
 
209
nsTemplateMatch*
 
210
nsConflictSet::GetMatchWithHighestPriority(const MatchCluster* aMatchCluster) const
 
211
{
 
212
    // Find the rule with the "highest priority"; i.e., the rule with
 
213
    // the lowest value for GetPriority().
 
214
    //
 
215
    // XXX if people start writing more than a few matches, we should
 
216
    // rewrite this to maintain the matches in sorted order, and then
 
217
    // just pluck the match off the top of the list.
 
218
    nsTemplateMatch* result = nsnull;
 
219
    PRInt32 max = PRInt32(PR_BIT(31) - 1);
 
220
 
 
221
    const nsTemplateMatchRefSet& set = aMatchCluster->mMatches;
 
222
    nsTemplateMatchRefSet::ConstIterator last = set.Last();
 
223
 
 
224
    for (nsTemplateMatchRefSet::ConstIterator match = set.First(); match != last; ++match) {
 
225
        PRInt32 priority = match->mRule->GetPriority();
 
226
        if (priority < max) {
 
227
            result = NS_CONST_CAST(nsTemplateMatch*, match.operator->());
 
228
            max = priority;
 
229
        }
 
230
    }
 
231
 
 
232
    return result;
 
233
}
 
234
 
 
235
const nsTemplateMatchRefSet*
 
236
nsConflictSet::GetMatchesWithBindingDependency(nsIRDFResource* aResource)
 
237
{
 
238
    // Retrieve all the matches whose bindings depend on the specified resource
 
239
    return NS_STATIC_CAST(nsTemplateMatchRefSet*, PL_HashTableLookup(mBindingDependencies, aResource));
 
240
}
 
241
 
 
242
 
 
243
void
 
244
nsConflictSet::Remove(const MemoryElement& aMemoryElement,
 
245
                      nsTemplateMatchSet& aNewMatches,
 
246
                      nsTemplateMatchSet& aRetractedMatches)
 
247
{
 
248
    // Use the memory-element-to-match map to figure out what matches
 
249
    // will be affected.
 
250
    PLHashEntry** hep = PL_HashTableRawLookup(mSupport, aMemoryElement.Hash(), &aMemoryElement);
 
251
 
 
252
    if (!hep || !*hep)
 
253
        return;
 
254
 
 
255
    // 'set' gets the set of all matches containing the first binding.
 
256
    nsTemplateMatchRefSet* set =
 
257
        NS_STATIC_CAST(nsTemplateMatchRefSet*, (*hep)->value);
 
258
 
 
259
    // We'll iterate through these matches, only paying attention to
 
260
    // matches that strictly contain the MemoryElement we're about to
 
261
    // remove.
 
262
    nsTemplateMatchRefSet::ConstIterator last = set->Last();
 
263
    for (nsTemplateMatchRefSet::ConstIterator match = set->First(); match != last; ++match) {
 
264
        // Note the retraction, so we can compute new matches, later.
 
265
        aRetractedMatches.Add(match.operator->());
 
266
 
 
267
        // Keep the bindings table in sync, as well. Since this match
 
268
        // is getting nuked, we need to nuke its bindings as well.
 
269
        nsResourceSet::ConstIterator last = match->mBindingDependencies.Last();
 
270
        for (nsResourceSet::ConstIterator dep = match->mBindingDependencies.First(); dep != last; ++dep)
 
271
            RemoveBindingDependency(match.operator->(), *dep);
 
272
    }
 
273
 
 
274
    // Unhash it
 
275
    PL_HashTableRawRemove(mSupport, hep, *hep);
 
276
 
 
277
    // Update the key-to-match map, and see if any new rules have been
 
278
    // fired as a result of the retraction.
 
279
    ComputeNewMatches(aNewMatches, aRetractedMatches);
 
280
}
 
281
 
 
282
nsresult
 
283
nsConflictSet::AddBindingDependency(nsTemplateMatch* aMatch, nsIRDFResource* aResource)
 
284
{
 
285
    // Note a match's dependency on a source resource
 
286
    PLHashNumber hash = HashBindingElement(aResource);
 
287
    PLHashEntry** hep = PL_HashTableRawLookup(mBindingDependencies, hash, aResource);
 
288
 
 
289
    nsTemplateMatchRefSet* set;
 
290
 
 
291
    if (hep && *hep) {
 
292
        set = NS_STATIC_CAST(nsTemplateMatchRefSet*, (*hep)->value);
 
293
    }
 
294
    else {
 
295
        PLHashEntry* he = PL_HashTableRawAdd(mBindingDependencies, hep, hash, aResource, nsnull);
 
296
 
 
297
        BindingEntry* entry = NS_REINTERPRET_CAST(BindingEntry*, he);
 
298
        if (! entry)
 
299
            return NS_ERROR_OUT_OF_MEMORY;
 
300
 
 
301
        // Fixup the value.
 
302
        entry->mHashEntry.value = set = &entry->mMatchSet;
 
303
        
 
304
    }
 
305
 
 
306
    if (! set->Contains(aMatch))
 
307
        set->Add(aMatch);
 
308
 
 
309
    return NS_OK;
 
310
}
 
311
 
 
312
nsresult
 
313
nsConflictSet::RemoveBindingDependency(nsTemplateMatch* aMatch, nsIRDFResource* aResource)
 
314
{
 
315
    // Remove a match's dependency on a source resource
 
316
    PLHashNumber hash = HashBindingElement(aResource);
 
317
    PLHashEntry** hep = PL_HashTableRawLookup(mBindingDependencies, hash, aResource);
 
318
 
 
319
    if (hep && *hep) {
 
320
        nsTemplateMatchRefSet* set = NS_STATIC_CAST(nsTemplateMatchRefSet*, (*hep)->value);
 
321
 
 
322
        set->Remove(aMatch);
 
323
 
 
324
        if (set->Empty())
 
325
            PL_HashTableRawRemove(mBindingDependencies, hep, *hep);
 
326
    }
 
327
 
 
328
    return NS_OK;
 
329
}
 
330
 
 
331
nsresult
 
332
nsConflictSet::ComputeNewMatches(nsTemplateMatchSet& aNewMatches,
 
333
                                 nsTemplateMatchSet& aRetractedMatches)
 
334
{
 
335
    // Given a set of just-retracted matches, compute the set of new
 
336
    // matches that have been revealed, updating the key-to-match map
 
337
    // as we go.
 
338
    nsTemplateMatchSet::ConstIterator last = aRetractedMatches.Last();
 
339
    for (nsTemplateMatchSet::ConstIterator retraction = aRetractedMatches.First();
 
340
         retraction != last;
 
341
         ++retraction) {
 
342
        nsClusterKey key(retraction->mInstantiation, retraction->mRule);
 
343
        PLHashEntry** hep = PL_HashTableRawLookup(mClusters, key.Hash(), &key);
 
344
 
 
345
        // XXXwaterson I'd managed to convince myself that this was really
 
346
        // okay, but now I can't remember why.
 
347
        //NS_ASSERTION(hep && *hep, "mClusters corrupted");
 
348
        if (!hep || !*hep)
 
349
            continue;
 
350
 
 
351
        MatchCluster* cluster = NS_REINTERPRET_CAST(MatchCluster*, (*hep)->value);
 
352
        nsTemplateMatchRefSet& set = cluster->mMatches;
 
353
 
 
354
        nsTemplateMatchRefSet::ConstIterator last = set.Last();
 
355
        for (nsTemplateMatchRefSet::ConstIterator match = set.First(); match != last; ++match) {
 
356
            if (match->mRule == retraction->mRule) {
 
357
                set.Remove(match.operator->()); // N.B., iterator no longer valid!
 
358
 
 
359
                // See if we've revealed another rule that's applicable
 
360
                nsTemplateMatch* newmatch =
 
361
                    GetMatchWithHighestPriority(cluster);
 
362
 
 
363
                if (newmatch)
 
364
                    aNewMatches.Add(newmatch);
 
365
 
 
366
                break;
 
367
            }
 
368
        }
 
369
 
 
370
        if (set.Empty())
 
371
            PL_HashTableRawRemove(mClusters, hep, *hep);
 
372
    }
 
373
 
 
374
    return NS_OK;
 
375
}
 
376
 
 
377
 
 
378
void
 
379
nsConflictSet::Clear()
 
380
{
 
381
    Destroy();
 
382
    Init();
 
383
}
 
384
 
 
385
PLHashNumber PR_CALLBACK
 
386
nsConflictSet::HashMemoryElement(const void* aMemoryElement)
 
387
{
 
388
    const MemoryElement* element =
 
389
        NS_STATIC_CAST(const MemoryElement*, aMemoryElement);
 
390
 
 
391
    return element->Hash();
 
392
}
 
393
 
 
394
PRIntn PR_CALLBACK
 
395
nsConflictSet::CompareMemoryElements(const void* aLeft, const void* aRight)
 
396
{
 
397
    const MemoryElement* left =
 
398
        NS_STATIC_CAST(const MemoryElement*, aLeft);
 
399
 
 
400
    const MemoryElement* right =
 
401
        NS_STATIC_CAST(const MemoryElement*, aRight);
 
402
 
 
403
    return *left == *right;
 
404
}
 
405
 
 
406
//----------------------------------------------------------------------
 
407
//
 
408
 
 
409
void
 
410
nsConflictSet::SupportEntry::Destroy(nsFixedSizeAllocator& aPool, SupportEntry* aEntry)
 
411
{
 
412
    // We need to Release() the matches here, because this is where
 
413
    // we've got access to the pool from which they were
 
414
    // allocated. Since SupportEntry's dtor is protected, nobody else
 
415
    // can be creating SupportEntry objects (e.g., on the stack).
 
416
    nsTemplateMatchRefSet::ConstIterator last = aEntry->mMatchSet.Last();
 
417
    for (nsTemplateMatchRefSet::ConstIterator iter = aEntry->mMatchSet.First();
 
418
         iter != last;
 
419
         ++iter)
 
420
        iter->Release(aPool);
 
421
 
 
422
    aEntry->~SupportEntry();
 
423
    aPool.Free(aEntry, sizeof(*aEntry));
 
424
}