LEFT | RIGHT |
1 // Copyright 2010 The Go Authors. All rights reserved. | 1 // Copyright 2010 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 #include "runtime.h" | 5 #include "runtime.h" |
6 #include "malloc.h" | 6 #include "malloc.h" |
7 | 7 |
8 // Finalizer hash table. Direct hash, linear scan, at most 3/4 full. | 8 // Finalizer hash table. Direct hash, linear scan, at most 3/4 full. |
9 // Table size is power of 3 so that hash can be key % max. | 9 // Table size is power of 3 so that hash can be key % max. |
10 // Key[i] == (void*)-1 denotes free but formerly occupied entry | 10 // Key[i] == (void*)-1 denotes free but formerly occupied entry |
11 // (doesn't stop the linear scan). | 11 // (doesn't stop the linear scan). |
12 // Key and val are separate tables because the garbage collector | 12 // Key and val are separate tables because the garbage collector |
13 // must be instructed to ignore the pointers in key but follow the | 13 // must be instructed to ignore the pointers in key but follow the |
14 // pointers in val. | 14 // pointers in val. |
15 typedef struct Fintab Fintab; | 15 typedef struct Fintab Fintab; |
16 struct Fintab | 16 struct Fintab |
17 { | 17 { |
18 void **key; | 18 void **key; |
19 » void **val; | 19 » struct { |
| 20 » » void *fn; |
| 21 » » int32 nret; |
| 22 » } *val; |
20 int32 nkey; // number of non-nil entries in key | 23 int32 nkey; // number of non-nil entries in key |
21 int32 ndead; // number of dead (-1) entries in key | 24 int32 ndead; // number of dead (-1) entries in key |
22 int32 max; // size of key, val allocations | 25 int32 max; // size of key, val allocations |
23 }; | 26 }; |
24 | 27 |
25 static void | 28 static void |
26 addfintab(Fintab *t, void *k, void *v) | 29 addfintab(Fintab *t, void *k, void *fn, int32 nret) |
27 { | 30 { |
28 int32 i, j; | 31 int32 i, j; |
29 ········ | 32 ········ |
30 i = (uintptr)k % (uintptr)t->max; | 33 i = (uintptr)k % (uintptr)t->max; |
31 for(j=0; j<t->max; j++) { | 34 for(j=0; j<t->max; j++) { |
32 if(t->key[i] == nil) { | 35 if(t->key[i] == nil) { |
33 t->nkey++; | 36 t->nkey++; |
34 goto ret; | 37 goto ret; |
35 } | 38 } |
36 if(t->key[i] == (void*)-1) { | 39 if(t->key[i] == (void*)-1) { |
37 t->ndead--; | 40 t->ndead--; |
38 goto ret; | 41 goto ret; |
39 } | 42 } |
40 if(++i == t->max) | 43 if(++i == t->max) |
41 i = 0; | 44 i = 0; |
42 } | 45 } |
43 | 46 |
44 // cannot happen - table is known to be non-full | 47 // cannot happen - table is known to be non-full |
45 throw("finalizer table inconsistent"); | 48 throw("finalizer table inconsistent"); |
46 | 49 |
47 ret: | 50 ret: |
48 t->key[i] = k; | 51 t->key[i] = k; |
49 » t->val[i] = v; | 52 » t->val[i].fn = fn; |
| 53 » t->val[i].nret = nret; |
50 } | 54 } |
51 | 55 |
52 static void* | 56 static void* |
53 lookfintab(Fintab *t, void *k, bool del) | 57 lookfintab(Fintab *t, void *k, bool del, int32 *nret) |
54 { | 58 { |
55 int32 i, j; | 59 int32 i, j; |
56 void *v; | 60 void *v; |
57 ········ | 61 ········ |
58 if(t->max == 0) | 62 if(t->max == 0) |
59 return nil; | 63 return nil; |
60 i = (uintptr)k % (uintptr)t->max; | 64 i = (uintptr)k % (uintptr)t->max; |
61 for(j=0; j<t->max; j++) { | 65 for(j=0; j<t->max; j++) { |
62 if(t->key[i] == nil) | 66 if(t->key[i] == nil) |
63 return nil; | 67 return nil; |
64 if(t->key[i] == k) { | 68 if(t->key[i] == k) { |
65 » » » v = t->val[i]; | 69 » » » v = t->val[i].fn; |
| 70 » » » if(nret) |
| 71 » » » » *nret = t->val[i].nret; |
66 if(del) { | 72 if(del) { |
67 t->key[i] = (void*)-1; | 73 t->key[i] = (void*)-1; |
68 » » » » t->val[i] = nil; | 74 » » » » t->val[i].fn = nil; |
| 75 » » » » t->val[i].nret = 0; |
69 t->ndead++; | 76 t->ndead++; |
70 } | 77 } |
71 return v; | 78 return v; |
72 } | 79 } |
73 if(++i == t->max) | 80 if(++i == t->max) |
74 i = 0; | 81 i = 0; |
75 } | 82 } |
76 | 83 |
77 // cannot happen - table is known to be non-full | 84 // cannot happen - table is known to be non-full |
78 throw("finalizer table inconsistent"); | 85 throw("finalizer table inconsistent"); |
79 return nil; | 86 return nil; |
80 } | 87 } |
81 | 88 |
82 static Fintab fintab; | 89 static Fintab fintab; |
83 | 90 |
84 // add finalizer; caller is responsible for making sure not already in table | 91 // add finalizer; caller is responsible for making sure not already in table |
85 void | 92 void |
86 addfinalizer(void *p, void (*f)(void*)) | 93 addfinalizer(void *p, void (*f)(void*), int32 nret) |
87 { | 94 { |
88 Fintab newtab; | 95 Fintab newtab; |
89 int32 i; | 96 int32 i; |
90 | 97 |
91 if(fintab.nkey >= fintab.max/2+fintab.max/4) { | 98 if(fintab.nkey >= fintab.max/2+fintab.max/4) { |
92 // keep table at most 3/4 full: | 99 // keep table at most 3/4 full: |
93 // allocate new table and rehash. | 100 // allocate new table and rehash. |
94 ················ | 101 ················ |
95 runtime_memclr((byte*)&newtab, sizeof newtab); | 102 runtime_memclr((byte*)&newtab, sizeof newtab); |
96 newtab.max = fintab.max; | 103 newtab.max = fintab.max; |
97 if(newtab.max == 0) | 104 if(newtab.max == 0) |
98 newtab.max = 3*3*3; | 105 newtab.max = 3*3*3; |
99 else if(fintab.ndead < fintab.nkey/2) { | 106 else if(fintab.ndead < fintab.nkey/2) { |
100 // grow table if not many dead values. | 107 // grow table if not many dead values. |
101 // otherwise just rehash into table of same size. | 108 // otherwise just rehash into table of same size. |
102 newtab.max *= 3; | 109 newtab.max *= 3; |
103 } | 110 } |
104 ················ | 111 ················ |
105 newtab.key = mallocgc(newtab.max*sizeof newtab.key[0], RefNoPoin
ters, 0); | 112 newtab.key = mallocgc(newtab.max*sizeof newtab.key[0], RefNoPoin
ters, 0); |
106 newtab.val = mallocgc(newtab.max*sizeof newtab.val[0], 0, 0); | 113 newtab.val = mallocgc(newtab.max*sizeof newtab.val[0], 0, 0); |
107 ················ | 114 ················ |
108 for(i=0; i<fintab.max; i++) { | 115 for(i=0; i<fintab.max; i++) { |
109 void *k; | 116 void *k; |
110 ························ | 117 ························ |
111 k = fintab.key[i]; | 118 k = fintab.key[i]; |
112 if(k != nil && k != (void*)-1) | 119 if(k != nil && k != (void*)-1) |
113 » » » » addfintab(&newtab, k, fintab.val[i]); | 120 » » » » addfintab(&newtab, k, fintab.val[i].fn, fintab.v
al[i].nret); |
114 } | 121 } |
115 free(fintab.key); | 122 free(fintab.key); |
116 free(fintab.val); | 123 free(fintab.val); |
117 fintab = newtab; | 124 fintab = newtab; |
118 } | 125 } |
119 ········ | 126 ········ |
120 » addfintab(&fintab, p, f);» »······· | 127 » addfintab(&fintab, p, f, nret);»»······· |
121 } | 128 } |
122 | 129 |
123 void* | 130 void* |
124 getfinalizer(void *p, bool del) | 131 getfinalizer(void *p, bool del, int32 *nret) |
125 { | 132 { |
126 » return lookfintab(&fintab, p, del); | 133 » return lookfintab(&fintab, p, del, nret); |
127 } | 134 } |
LEFT | RIGHT |