1 /*
2 * Copyright (c) 2001, 2013, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
105
106 friend class RSHashTableIter;
107
108 enum SomePrivateConstants {
109 NullEntry = -1
110 };
111
112 size_t _capacity;
113 size_t _capacity_mask;
114 size_t _occupied_entries;
115 size_t _occupied_cards;
116
117 SparsePRTEntry* _entries;
118 int* _buckets;
119 int _free_region;
120 int _free_list;
121
122 // Requires that the caller hold a lock preventing parallel modifying
123 // operations, and that the the table be less than completely full. If
124 // an entry for "region_ind" is already in the table, finds it and
125 // returns its address; otherwise returns "NULL."
126 SparsePRTEntry* entry_for_region_ind(RegionIdx_t region_ind) const;
127
128 // Requires that the caller hold a lock preventing parallel modifying
129 // operations, and that the the table be less than completely full. If
130 // an entry for "region_ind" is already in the table, finds it and
131 // returns its address; otherwise allocates, initializes, inserts and
132 // returns a new entry for "region_ind".
133 SparsePRTEntry* entry_for_region_ind_create(RegionIdx_t region_ind);
134
135 // Returns the index of the next free entry in "_entries".
136 int alloc_entry();
137 // Declares the entry "fi" to be free. (It must have already been
138 // deleted from any bucket lists.
139 void free_entry(int fi);
140
141 public:
142 RSHashTable(size_t capacity);
143 ~RSHashTable();
144
145 // Attempts to ensure that the given card_index in the given region is in
146 // the sparse table. If successful (because the card was already
147 // present, or because it was successfully added) returns "true".
148 // Otherwise, returns "false" to indicate that the addition would
149 // overflow the entry for the region. The caller must transfer these
150 // entries to a larger-capacity representation.
151 bool add_card(RegionIdx_t region_id, CardIdx_t card_index);
152
153 bool get_cards(RegionIdx_t region_id, CardIdx_t* cards);
154
155 bool delete_entry(RegionIdx_t region_id);
156
157 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const;
158
159 void add_entry(SparsePRTEntry* e);
160
161 SparsePRTEntry* get_entry(RegionIdx_t region_id);
162
163 void clear();
164
165 size_t capacity() const { return _capacity; }
166 size_t capacity_mask() const { return _capacity_mask; }
167 size_t occupied_entries() const { return _occupied_entries; }
168 size_t occupied_cards() const { return _occupied_cards; }
169 size_t mem_size() const;
170
171 SparsePRTEntry* entry(int i) const { return (SparsePRTEntry*)((char*)_entries + SparsePRTEntry::size() * i); }
172
173 void print();
174 };
175
176 // ValueObj because will be embedded in HRRS iterator.
177 class RSHashTableIter VALUE_OBJ_CLASS_SPEC {
178 int _tbl_ind; // [-1, 0.._rsht->_capacity)
179 int _bl_ind; // [-1, 0.._rsht->_capacity)
180 short _card_ind; // [0..SparsePRTEntry::cards_num())
181 RSHashTable* _rsht;
|
1 /*
2 * Copyright (c) 2001, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
105
106 friend class RSHashTableIter;
107
108 enum SomePrivateConstants {
109 NullEntry = -1
110 };
111
112 size_t _capacity;
113 size_t _capacity_mask;
114 size_t _occupied_entries;
115 size_t _occupied_cards;
116
117 SparsePRTEntry* _entries;
118 int* _buckets;
119 int _free_region;
120 int _free_list;
121
122 // Requires that the caller hold a lock preventing parallel modifying
123 // operations, and that the the table be less than completely full. If
124 // an entry for "region_ind" is already in the table, finds it and
125 // returns its address; otherwise allocates, initializes, inserts and
126 // returns a new entry for "region_ind".
127 SparsePRTEntry* entry_for_region_ind_create(RegionIdx_t region_ind);
128
129 // Returns the index of the next free entry in "_entries".
130 int alloc_entry();
131 // Declares the entry "fi" to be free. (It must have already been
132 // deleted from any bucket lists.
133 void free_entry(int fi);
134
135 public:
136 RSHashTable(size_t capacity);
137 ~RSHashTable();
138
139 // Attempts to ensure that the given card_index in the given region is in
140 // the sparse table. If successful (because the card was already
141 // present, or because it was successfully added) returns "true".
142 // Otherwise, returns "false" to indicate that the addition would
143 // overflow the entry for the region. The caller must transfer these
144 // entries to a larger-capacity representation.
145 bool add_card(RegionIdx_t region_id, CardIdx_t card_index);
146
147 bool get_cards(RegionIdx_t region_id, CardIdx_t* cards);
148
149 bool delete_entry(RegionIdx_t region_id);
150
151 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const;
152
153 void add_entry(SparsePRTEntry* e);
154
155 SparsePRTEntry* get_entry(RegionIdx_t region_id) const;
156
157 void clear();
158
159 size_t capacity() const { return _capacity; }
160 size_t capacity_mask() const { return _capacity_mask; }
161 size_t occupied_entries() const { return _occupied_entries; }
162 size_t occupied_cards() const { return _occupied_cards; }
163 size_t mem_size() const;
164
165 SparsePRTEntry* entry(int i) const { return (SparsePRTEntry*)((char*)_entries + SparsePRTEntry::size() * i); }
166
167 void print();
168 };
169
170 // ValueObj because will be embedded in HRRS iterator.
171 class RSHashTableIter VALUE_OBJ_CLASS_SPEC {
172 int _tbl_ind; // [-1, 0.._rsht->_capacity)
173 int _bl_ind; // [-1, 0.._rsht->_capacity)
174 short _card_ind; // [0..SparsePRTEntry::cards_num())
175 RSHashTable* _rsht;
|