1
2/*
3 * Copyright 2008 The Android Open Source Project
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9
10#ifndef SkPtrSet_DEFINED
11#define SkPtrSet_DEFINED
12
13#include "SkRefCnt.h"
14#include "SkTDArray.h"
15
16/**
17 *  Maintains a set of ptrs, assigning each a unique ID [1...N]. Duplicate ptrs
18 *  return the same ID (since its a set). Subclasses can override inPtr()
19 *  and decPtr(). incPtr() is called each time a unique ptr is added ot the
20 *  set. decPtr() is called on each ptr when the set is destroyed or reset.
21 */
22class SkPtrSet : public SkRefCnt {
23public:
24    /**
25     *  Search for the specified ptr in the set. If it is found, return its
26     *  32bit ID [1..N], or if not found, return 0. Always returns 0 for NULL.
27     */
28    uint32_t find(void*) const;
29
30    /**
31     *  Add the specified ptr to the set, returning a unique 32bit ID for it
32     *  [1...N]. Duplicate ptrs will return the same ID.
33     *
34     *  If the ptr is NULL, it is not added, and 0 is returned.
35     */
36    uint32_t add(void*);
37
38    /**
39     *  Return the number of (non-null) ptrs in the set.
40     */
41    int count() const { return fList.count(); }
42
43    /**
44     *  Copy the ptrs in the set into the specified array (allocated by the
45     *  caller). The ptrs are assgined to the array based on their corresponding
46     *  ID. e.g. array[ptr.ID - 1] = ptr.
47     *
48     *  incPtr() and decPtr() are not called during this operation.
49     */
50    void copyToArray(void* array[]) const;
51
52    /**
53     *  Call decPtr() on each ptr in the set, and the reset the size of the set
54     *  to 0.
55     */
56    void reset();
57
58protected:
59    virtual void incPtr(void* ptr) {}
60    virtual void decPtr(void* ptr) {}
61
62private:
63    struct Pair {
64        void*       fPtr;   // never NULL
65        uint32_t    fIndex; // 1...N
66    };
67
68    // we store the ptrs in sorted-order (using Cmp) so that we can efficiently
69    // detect duplicates when add() is called. Hence we need to store the
70    // ptr and its ID/fIndex explicitly, since the ptr's position in the array
71    // is not related to its "index".
72    SkTDArray<Pair>  fList;
73
74    static int Cmp(const Pair& a, const Pair& b);
75
76    typedef SkRefCnt INHERITED;
77};
78
79/**
80 *  Templated wrapper for SkPtrSet, just meant to automate typecasting
81 *  parameters to and from void* (which the base class expects).
82 */
83template <typename T> class SkTPtrSet : public SkPtrSet {
84public:
85    uint32_t find(T ptr) {
86        return this->INHERITED::find((void*)ptr);
87    }
88    uint32_t add(T ptr) {
89        return this->INHERITED::add((void*)ptr);
90    }
91
92    void copyToArray(T* array) const {
93        this->INHERITED::copyToArray((void**)array);
94    }
95
96private:
97    typedef SkPtrSet INHERITED;
98};
99
100#endif
101