LEFT | RIGHT |
(no file at all) | |
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 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 /* A hash table. | 5 /* A hash table. |
6 Example, hashing nul-terminated char*s: | 6 Example, hashing nul-terminated char*s: |
7 hash_hash_t str_hash (void *v) { | 7 hash_hash_t str_hash (void *v) { |
8 char *s; | 8 char *s; |
9 hash_hash_t hash = 0; | 9 hash_hash_t hash = 0; |
10 for (s = *(char **)v; *s != 0; s++) { | 10 for (s = *(char **)v; *s != 0; s++) { |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
63 } | 63 } |
64 */ | 64 */ |
65 | 65 |
66 #define malloc runtime·mal | 66 #define malloc runtime·mal |
67 #define memset(a,b,c) runtime·memclr((byte*)(a), (uint32)(c)) | 67 #define memset(a,b,c) runtime·memclr((byte*)(a), (uint32)(c)) |
68 #define memcpy(a,b,c) runtime·mcpy((byte*)(a),(byte*)(b),(uint32)(c)) | 68 #define memcpy(a,b,c) runtime·mcpy((byte*)(a),(byte*)(b),(uint32)(c)) |
69 #define assert(a) if(!(a)) runtime·throw("assert") | 69 #define assert(a) if(!(a)) runtime·throw("assert") |
70 #define free(x) runtime·free(x) | 70 #define free(x) runtime·free(x) |
71 #define memmove(a,b,c) runtime·memmove(a, b, c) | 71 #define memmove(a,b,c) runtime·memmove(a, b, c) |
72 | 72 |
73 struct hash;» » /* opaque */ | 73 struct Hmap;» » /* opaque */ |
74 struct hash_subtable; /* opaque */ | 74 struct hash_subtable; /* opaque */ |
75 struct hash_entry; /* opaque */ | 75 struct hash_entry; /* opaque */ |
76 | 76 |
77 typedef uintptr uintptr_t; | 77 typedef uintptr uintptr_t; |
78 typedef uintptr_t hash_hash_t; | 78 typedef uintptr_t hash_hash_t; |
79 | 79 |
80 struct hash_iter { | 80 struct hash_iter { |
81 uint8* data; /* returned from next */ | 81 uint8* data; /* returned from next */ |
82 int32 elemsize; /* size of elements in table */ | 82 int32 elemsize; /* size of elements in table */ |
83 int32 changes; /* number of changes observed last time */ | 83 int32 changes; /* number of changes observed last time */ |
84 int32 i; /* stack pointer in subtable_state */ | 84 int32 i; /* stack pointer in subtable_state */ |
85 hash_hash_t last_hash; /* last hash value returned */ | 85 hash_hash_t last_hash; /* last hash value returned */ |
86 » struct hash *h;»» /* the hash table */ | 86 » struct Hmap *h;»» /* the hash table */ |
87 struct hash_iter_sub { | 87 struct hash_iter_sub { |
88 struct hash_entry *e; /* pointer into subtable */ | 88 struct hash_entry *e; /* pointer into subtable */ |
89 struct hash_entry *start; /* start of subtable */ | 89 struct hash_entry *start; /* start of subtable */ |
90 struct hash_entry *end; /* end of subtable */ | 90 struct hash_entry *end; /* end of subtable */ |
91 } subtable_state[4]; /* Should be large enough unless the hashing is | 91 } subtable_state[4]; /* Should be large enough unless the hashing is |
92 so bad that many distinct data values hash | 92 so bad that many distinct data values hash |
93 to the same hash value. */ | 93 to the same hash value. */ |
94 }; | 94 }; |
95 | 95 |
96 /* Return a hashtable h 2**init_power empty entries, each with | 96 /* Return a hashtable h 2**init_power empty entries, each with |
(...skipping 53 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
150 // void hash_iter_init (struct hash *h, struct hash_iter *it); | 150 // void hash_iter_init (struct hash *h, struct hash_iter *it); |
151 | 151 |
152 /* Return the next used entry in the table which which *it was initialized. */ | 152 /* Return the next used entry in the table which which *it was initialized. */ |
153 // void *hash_next (struct hash_iter *it); | 153 // void *hash_next (struct hash_iter *it); |
154 | 154 |
155 /*---- test interface ----*/ | 155 /*---- test interface ----*/ |
156 /* Call (*data_visit) (arg, level, data) for every data entry in the table, | 156 /* Call (*data_visit) (arg, level, data) for every data entry in the table, |
157 whether used or not. "level" is the subtable level, 0 means first level. */ | 157 whether used or not. "level" is the subtable level, 0 means first level. */ |
158 /* TESTING ONLY: DO NOT USE THIS ROUTINE IN NORMAL CODE */ | 158 /* TESTING ONLY: DO NOT USE THIS ROUTINE IN NORMAL CODE */ |
159 // void hash_visit (struct hash *h, void (*data_visit) (void *arg, int32 level,
void *data), void *arg); | 159 // void hash_visit (struct hash *h, void (*data_visit) (void *arg, int32 level,
void *data), void *arg); |
LEFT | RIGHT |