![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to _arr_map.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / cfront / libC / new|
Return to _arr_map.c CVS log | Up to [Research Unix] / researchv10no / cmd / cfront / libC / new |
1.1 root 1: /*ident "@(#)C++env:lib/new/_arr_map.c 1.3" */
2: /**************************************************************************
3: Copyright (c) 1984 AT&T
4: All Rights Reserved
5:
6: THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T
7:
8: The copyright notice above does not evidence any
9: actual or intended publication of such source code.
10:
11: *****************************************************************************/
12:
13:
14: // manage the global table of array pointers and counts
15: #include <values.h>
16: #include <new.h>
17:
18: // !!!! only works if sizeof(long) >= sizeof(void*) !!!!
19:
20: typedef void* KEYTYP; // generic array address
21: void __insert_new_array(KEYTYP key, int count);
22: // key is a pointer to a new array. It must
23: // be non-zero
24: // not already be in the table
25: // count is the number of elements in the array. May be zero
26: int __remove_old_array(KEYTYP key);
27: // removes an old array from the table. Returns the count or -1 if not found
28:
29: // choose 2 <= DIGIT_SIZE <= 6
30: // smaller numbers waste less space and are slower, larger numbers waste more
31: // space and are faster
32:
33: // control the size of blocks grabbed from the free store (and frequency of
34: // allocations) with RECORDS_BLOCK_COUNT and NODES_BLOCK_COUNT
35:
36: // a trie based on groups of DIGIT_SIZE bits from the key
37: #define DIGIT_SIZE 5
38: // each node contains 2 ** DIGIT_SIZE entries
39: #define NODE_SIZE (1 << DIGIT_SIZE)
40: #define MASK_BITS (1 << DIGIT_SIZE) - 1
41: // a few low order bits are uninteresting and are rotated around to the top
42: #define LOW_BITS 2
43: #define LOW_MASK ((1 << LOW_BITS) - 1)
44: // the number of groups in a word
45: #define POSITIONS ((BITS(long) - 1) / DIGIT_SIZE + 1)
46: // control the size of blocks grabbed from new
47: #define RECORDS_BLOCK_COUNT 150
48: #define NODES_BLOCK_COUNT 10
49:
50: // avoid name space clashes
51: #define pnd __pnd
52: #define Node_Pool __Node_Pool
53: #define Record_Pool __Record_Pool
54: #define pnd_internal_node __pnd_internal_node
55:
56: class pnd;
57: class pnd_internal_node;
58:
59: class RECORD {
60: friend pnd;
61: friend void __insert_new_array(KEYTYP addr, int count);
62: inline void* operator new(size_t);
63: inline void operator delete(void* p, size_t);
64: inline RECORD(unsigned long k, int cnt);
65: inline ~RECORD();
66: unsigned long key; // rotated address of array
67: int count; // number of elements of array
68: };
69:
70: class Record_Pool;
71:
72: class Record_shell {
73: friend Record_Pool;
74: Record_shell* next;
75: char dummy[sizeof(RECORD) - sizeof(Record_shell*)];
76: };
77:
78: class Record_Pool {
79: friend RECORD;
80: static Record_shell* top;
81: Record_Pool();
82: Record_shell slot[RECORDS_BLOCK_COUNT];
83: static void* alloc() {
84: if (top == 0)
85: new Record_Pool;
86: void* ans = top;
87: top = top->next;
88: return ans;
89: }
90: static void free(Record_shell* p) {
91: p->next = top;
92: top = p;
93: }
94: };
95:
96: inline void*
97: RECORD::operator new(size_t)
98: {
99: return Record_Pool::alloc();
100: }
101: inline void
102: RECORD::operator delete(void* p, size_t)
103: {
104: Record_Pool::free((Record_shell*)p);
105: }
106:
107: inline
108: RECORD::RECORD(unsigned long k, int cnt)
109: : key(k), count(cnt)
110: {}
111:
112: inline RECORD::~RECORD() {}
113:
114: class pnd_internal_item {
115: friend pnd;
116: friend pnd_internal_node;
117: union {
118: RECORD* ext_leaf;
119: pnd_internal_node* nodep;
120: };
121: int this_is_leaf;
122: int is_node() { return !this_is_leaf && nodep; }
123: int is_leaf() { return this_is_leaf; }
124: int is_null() { return !nodep; }
125: pnd_internal_node* next_node() { return nodep; }
126: RECORD* external_leaf() { return ext_leaf; }
127: void make_leaf(RECORD* p) { this_is_leaf = 1; ext_leaf = p; }
128: void make_node(pnd_internal_node* cp) { this_is_leaf = 0; nodep = cp; }
129: void make_null() {this_is_leaf = 0; nodep = 0; }
130: };
131:
132: class Node_Pool;
133:
134: class pnd_internal_node {
135: friend pnd;
136: friend void __insert_new_array(KEYTYP key, int count);
137: inline void* operator new(size_t i);
138: inline void operator delete(void* p, size_t i);
139: pnd_internal_node();
140: inline ~pnd_internal_node();
141: pnd_internal_item item[NODE_SIZE];
142: int busy_count;
143: };
144:
145: class Node_shell {
146: friend Node_Pool;
147: Node_shell* next;
148: char dummy[sizeof(pnd_internal_node) - sizeof(Node_shell*)];
149: };
150:
151: class Node_Pool {
152: friend pnd_internal_node;
153: static Node_shell* top;
154: Node_Pool();
155: Node_shell slot[NODES_BLOCK_COUNT];
156: static void* alloc() {
157: if (top == 0)
158: new Node_Pool;
159: void* ans = top;
160: top = top->next;
161: return ans;
162: }
163: static void free(void* p) {
164: ((Node_shell*)p)->next = top;
165: top = (Node_shell*)p;
166: }
167: };
168:
169: inline void*
170: pnd_internal_node::operator new(size_t)
171: {
172: return Node_Pool::alloc();
173: }
174: inline void
175: pnd_internal_node::operator delete(void* p, size_t)
176: {
177: Node_Pool::free(p);
178: }
179:
180: inline pnd_internal_node::~pnd_internal_node() {}
181:
182: class pnd {
183: friend void __insert_new_array(KEYTYP key, int count);
184: friend int __remove_old_array(KEYTYP key);
185: static pnd* the_table;
186: pnd_internal_item contents;
187: // int sze;
188: pnd();
189: static void initialize();
190: void insert(KEYTYP, int);
191: int remove(KEYTYP); // returns count or -1 if not found
192: };
193:
194: void
195: __insert_new_array(KEYTYP key, int count)
196: {
197: if (pnd::the_table == 0)
198: pnd::initialize();
199: pnd::the_table->insert(key, count);
200: }
201:
202: int
203: __remove_old_array(KEYTYP key)
204: {
205: return pnd::the_table->remove(key);
206: }
207:
208: pnd_internal_node::pnd_internal_node()
209: {
210: register pnd_internal_item* itemp = &item[0];
211: register int i = NODE_SIZE;
212: while (i--)
213: (itemp++)->make_null();
214: busy_count = 0;
215: }
216:
217: void
218: pnd::insert(KEYTYP addr, int cnt)
219: {
220: register unsigned long mask = MASK_BITS;
221: register unsigned long key = (unsigned long)addr & LOW_MASK;
222: if (key)
223: key <<= BITS(long) - LOW_BITS;
224: key |= (unsigned long)addr >> LOW_BITS;
225: RECORD* new_rec = new RECORD(key, cnt);
226: register int unshift = 0;
227: register pnd_internal_item* itemp = &contents;
228: register pnd_internal_node* nodep = 0;
229: for (;; mask <<= DIGIT_SIZE, unshift += DIGIT_SIZE) {
230: if (itemp->is_null())
231: break;
232: if (itemp->is_leaf()) {
233: if (itemp->external_leaf()->key == key){
234: itemp->external_leaf()->count = cnt;
235: delete new_rec; // didn't need it after all
236: return; // should rarely happen
237: }
238: break;
239: }
240: nodep = itemp->next_node();
241: // assert(nodep);
242: itemp = &nodep->item[(key & mask) >> unshift];
243: }
244: // sze++;
245: if (itemp->is_null()) {
246: itemp->make_leaf(new_rec);
247: if (nodep)
248: nodep->busy_count++;
249: return;
250: }
251: // assert(itemp->is_leaf());
252: RECORD* temp = itemp->external_leaf();
253: unsigned long other_key = temp->key;
254: // assert(other_key != key);
255: unsigned long ind1, ind2;
256: for (;; mask <<= DIGIT_SIZE, unshift += DIGIT_SIZE) {
257: itemp->make_node(nodep = new pnd_internal_node);
258: // assert(pos.curr_depth < POSITIONS);
259: ind1 = (other_key & mask) >> unshift;
260: ind2 = (key & mask) >> unshift;
261: if (ind1 != ind2) break; // I hope so!
262: nodep->busy_count = 1;
263: itemp = &nodep->item[ind1];
264: }
265: nodep->item[ind1].make_leaf(temp);
266: nodep->item[ind2].make_leaf(new_rec);
267: nodep->busy_count = 2;
268: return;
269: }
270:
271: int
272: pnd::remove(KEYTYP addr)
273: {
274: pnd_internal_item* curr_pos[POSITIONS];
275: int curr_depth;
276: if (addr == 0) return -1;
277: register unsigned long mask = MASK_BITS;
278: register unsigned long key = (unsigned long)addr & LOW_MASK;
279: if (key)
280: key <<= BITS(long) - LOW_BITS;
281: key |= (unsigned long)addr >> LOW_BITS;
282: register int unshift = 0;
283: register pnd_internal_item* itemp = &contents;
284: register pnd_internal_node* nodep = 0;
285: for (curr_depth = -1;; mask <<= DIGIT_SIZE, unshift += DIGIT_SIZE) {
286: // assert(curr_depth < POSITIONS);
287: if (itemp->is_null())
288: return -1;
289: if (itemp->is_leaf())
290: if (itemp->external_leaf()->key == key)
291: break;
292: else
293: return -1;
294: nodep = itemp->next_node();
295: // assert(nodep);
296: curr_pos[++curr_depth] = itemp =
297: &nodep->item[(key & mask) >> unshift];
298: }
299: // assert(itemp->is_leaf());
300: // assert(itemp->external_leaf()->key == key);
301: RECORD* old_p = itemp->external_leaf();
302: // sze--;
303: int ans = old_p->count;
304: delete old_p;
305: itemp->make_null();
306: if (curr_depth == -1 || // it was a singleton set
307: --(nodep->busy_count) > 1) // easy case
308: return ans;
309: // assert(nodep->busy_count == 1);
310: register pnd_internal_item* itp = &nodep->item[0];
311: while (itp->is_null() || itp == itemp) itp++;
312: if (!itp->is_leaf()) // unfortunate case
313: return ans;
314: RECORD* temp = itp->external_leaf();
315: // assert(temp->key != key);
316: for (;;) {
317: delete nodep;
318: if (curr_depth-- == 0) {
319: // assert(sze == 1);
320: contents.make_leaf(temp);
321: return ans;
322: }
323: nodep = curr_depth == 0 ? contents.next_node() :
324: curr_pos[curr_depth-1]->next_node();
325: if (nodep->busy_count > 1) {
326: curr_pos[curr_depth]->make_leaf(temp);
327: return ans;
328: }
329: // assert(nodep->busy_count == 1);
330: }
331: }
332:
333: pnd::pnd()
334: /* : sze(0) */
335: {
336: contents.make_null();
337: }
338:
339: void
340: pnd::initialize()
341: {
342: the_table = new pnd;
343: }
344:
345: Record_Pool::Record_Pool()
346: {
347: register int i = RECORDS_BLOCK_COUNT;
348: register Record_shell* p = slot;
349: register Record_shell* q;
350: while (--i) {
351: q = p++;
352: q->next = p;
353: }
354: p->next = top;
355: top = slot;
356: }
357:
358: Node_Pool::Node_Pool()
359: {
360: register int i = NODES_BLOCK_COUNT;
361: register Node_shell* p = slot;
362: register Node_shell* q;
363: while (--i) {
364: q = p++;
365: q->next = p;
366: }
367: p->next = top;
368: top = slot;
369: }
370:
371:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.