2.2. 類型哈希表的初始化
完成辨別符哈希表的初始化後，general_init調用init_ttree來初始化類型哈希表。
116 void
117 init_ttree (void) in tree.c
118 {
119
120 type_hash_table = htab_create_ggc (TYPE_HASH_INITIAL_SIZE, type_hash_hash,
121 type_hash_eq, 0);
122 }
注意，這個哈希表指定了哈希函數及比較函數。
2.2.1. 哈希表的定義
該哈希表的對象是type_hash_table。它的定義如下。
94
100
101 static GTY ((if_marked ("type_hash_marked_p"), param_is (struct type_hash)))
102 htab_t type_hash_table;
type_hash_table的類型是htab_t，它是指向htab的指針。
90 struct htab GTY(()) in hashtab.h
91 {
92
93 htab_hash hash_f;
94
95
96 htab_eq eq_f;
97
98
99 htab_del del_f;
100
101
102 PTR * GTY ((use_param (""), length ("%h.size"))) entries;
103
104
105 size_t size;
106
107
108 size_t n_elements;
109
110
111 size_t n_deleted;
112
113
115 unsigned int searches;
116
117
119 unsigned int collisions;
120
121
122 htab_alloc alloc_f;
123 htab_free free_f;
124
125
126 PTR GTY((skip (""))) alloc_arg;
127 htab_alloc_with_arg alloc_with_arg_f;
128 htab_free_with_arg free_with_arg_f;
129 };
130
131 typedef struct htab *htab_t;
哈希表的建立函數htab_create_ggc的定義如下。
236 #define htab_create_ggc(SIZE, HASH, EQ, DEL) / in ggc.h
237 htab_create_alloc (SIZE, HASH, EQ, DEL, ggc_calloc, NULL)
ggc_alloc是由GC（垃圾收集器）提供的方法。它負責配置設定由GC管理的對象。上面126行的PTR是void*或char*。
167 htab_t
168 htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f) in hashtab.c
169 size_t size;
170 htab_hash hash_f;
171 htab_eq eq_f;
172 htab_del del_f;
173 htab_alloc alloc_f;
174 htab_free free_f;
175 {
176 htab_t result;
177
178 size = higher_prime_number (size);
179 result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
180 if (result == NULL)
181 return NULL;
182 result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
183 if (result->entries == NULL)
184 {
185 if (free_f != NULL)
186 (*free_f) (result);
187 return NULL;
188 }
189 result->size = size;
190 result->hash_f = hash_f;
191 result->eq_f = eq_f;
192 result->del_f = del_f;
193 result->alloc_f = alloc_f;
194 result->free_f = free_f;
195 return result;
196 }
上面178行，higher_prime_number傳回比size大而又小于比size大的最小2的指數的質數。目的為了減少哈希碰撞。
2.2.2. 哈希表的元素
在上面102行雖然這個表被聲明為void*，它的元素實際上是type_hash類型。
85 struct type_hash GTY(()) in tree.c
86 {
87 unsigned long hash;
88 tree type;
89 };
type_hash的type域實際是tree_type類型。
2.2.3. 查找哈希表
在這個哈希表中的查找是由函數type_hash_lookup執行，函數的type參數也是tree_type類型。
3008 tree
3009 type_hash_lookup (unsigned int hashcode, tree type) in tree.c
3010 {
3011 struct type_hash *h, in;
3012
3013
3015 layout_type (type);
3016
3017 in.hash = hashcode;
3018 in.type = type;
3019
3020 h = htab_find_with_hash (type_hash_table, &in, hashcode);
3021 if (h)
3022 return h->type;
3023 return NULL_TREE;
3024 }
htab_find_with_hash不能用于添加或删除元素，它隻能傳回與hashcode比對的表項，這表項可以為空。
2.2.3.1. 為新類型填寫資訊
2.2.3.1.1. 整數類型的資訊
參考内建類型的樹節點。
2.2.3.1.2. 實數和複數類型資訊
實數和複數類型所要求的資訊與整數類型相同。見如下代碼片段。
layout_type (continue)
1552 case REAL_TYPE:
1553 TYPE_MODE (type) = mode_for_size (TYPE_PRECISION (type), MODE_FLOAT, 0);
1554 TYPE_SIZE (type) = bitsize_int (GET_MODE_BITSIZE (TYPE_MODE (type)));
1555 TYPE_SIZE_UNIT (type) = size_int (GET_MODE_SIZE (TYPE_MODE (type)));
1556 break;
1557
1558 case COMPLEX_TYPE:
1559 TREE_UNSIGNED (type) = TREE_UNSIGNED (TREE_TYPE (type));
1560 TYPE_MODE (type)
1561 = mode_for_size (2 * TYPE_PRECISION (TREE_TYPE (type)),
1562 (TREE_CODE (TTREE_TYPE (type)) == INTEGER_TYPE
1563 ? MODE_COMPLEX_INT : MODE_COMPLEX_FLOAT),
1564 0);
1565 TYPE_SIZE (type) = bitsize_int (GET_MODE_BITSIZE (TYPE_MODE (type)));
1566 TYPE_SIZE_UNIT (type) = size_int (GET_MODE_SIZE (TYPE_MODE (type)));
1567 break;
函數mode_for_size和smallest_mode_for_size相似，它傳回對應有size比特的非标量的機器模式。這個模式必須是參數class指定的類别，而且确實具有那麼多有效比特位，它可能還包含有填充位。如果參數limit非零，不能使用比MAX_FIXED_MODE_SIZE更寬的模式。
211 enum machine_mode
212 mode_for_size (unsigned int size, enum mode_class class, int limit) in stor_layout.c
213 {
214 enum machine_mode mode;
215
216 if (limit && size > MAX_FIXED_MODE_SIZE)
217 return BLKmode;
218
219
220 for (mode = GET_CLASS_NARROWEST_MODE (class); mode != VOIDmode;
221 mode = GET_MODE_WIDER_MODE (mode))
222 if (GET_MODE_PRECISION (mode) == size)
223 return mode;
224
225 return BLKmode;
226 }
在沒有合适的固定模式（fixed mode）時，隻能選用BLKmode。它是用于結構或數組等的模式。
2.2.3.1.3. 其他簡單類型的資訊
以x86系統為例，系統提供SSE或MMX寄存器用于操作64位或更多位資料。是以數個總大小不超過特定尺寸的同型的整型或浮點型資料可以被存入這類寄存器。這組整數或浮點數就被定義為VECTOR_TYPE（向量類型）。
layout_type (continue)
1569 case VECTOR_TYPE:
1570 {
1571 tree subtype;
1572
1573 subtype = TREE_TYPE (type);
1574 TREE_UNSIGNED (type) = TREE_UNSIGNED (subtype);
1575 TYPE_SIZE (type) = bitsize_int (GET_MODE_BITSIZE (TYPE_MODE (type)));
1576 TYPE_SIZE_UNIT (type) = size_int (GET_MODE_SIZE (TYPE_MODE (type)));
1577 }
1578 break;
1579
1580 case VOID_TYPE:
1581
1582 TYPE_ALIGN (type) = 1;
1583 TYPE_USER_ALIGN (type) = 0;
1584 TYPE_MODE (type) = VOIDmode;
1585 break;
1586
1587 case OFFSET_TYPE:
1588 TYPE_SIZE (type) = bitsize_int (POINTER_SIZE);
1589 TYPE_SIZE_UNIT (type) = size_int (POINTER_SIZE / BITS_PER_UNIT);
1590
1592 TYPE_MODE (type) = mode_for_size (POINTER_SIZE, MODE_INT, 0);
1593 break;
1594
1595 case FUNCTION_TYPE:
1596 case METHOD_TYPE:
1597 TYPE_MODE (type) = mode_for_size (2 * POINTER_SIZE, MODE_INT, 0);
1598 TYPE_SIZE (type) = bitsize_int (2 * POINTER_SIZE);
1599 TYPE_SIZE_UNIT (type) = size_int ((2 * POINTER_SIZE) / BITS_PER_UNIT);
1600 break;
1601
1602 case POINTER_TYPE:
1603 case REFERENCE_TYPE:
1604 {
1605
1606 enum machine_mode mode = ((TREE_CODE (type) == REFERENCE_TYPE
1607 && reference_types_internal)
1608 ? Pmode : TYPE_MODE (type));
1609
1610 int nbits = GET_MODE_BITSIZE (mode);
1611
1612 TYPE_SIZE (type) = bitsize_int (nbits);
1613 TYPE_SIZE_UNIT (type) = size_int (GET_MODE_SIZE (mode));
1614 TREE_UNSIGNED (type) = 1;
1615 TYPE_PRECISION (type) = nbits;
1616 }
1617 break;
對于VECTOR_TYPE，注意到在其tree_common域，其中的type域是單個資料（元素）本身的類型。而元素類型的細節也被儲存入這個向量類型。向量類型所包含的元素個數由其機器模式決定。
2.2.3.1.4. 數組類型的資訊
參考建立數組類型節點
![DB2表壓縮功能[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)