2 Copyright (C) 2000, 2001, 2003, 2004, 2008, 2009
3 Free Software Foundation, Inc.
5 This program is free software; you can redistribute it and/or modify it
6 under the terms of the GNU General Public License as published by the
7 Free Software Foundation; either version 3, or (at your option) any
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; see the file COPYING3. If not see
17 <http://www.gnu.org/licenses/>.
19 In other words, you are welcome to use, share and improve this program.
20 You are forbidden to forbid anyone else to use, share and improve
21 what you give them. Help stamp out software-hoarding! */
28 /* The code below is a specialization of Vladimir Makarov's expandable
29 hash tables (see libiberty/hashtab.c). The abstraction penalty was
30 too high to continue using the generic form. This code knows
31 intrinsically how to calculate a hash value, and how to compare an
32 existing entry with a potential new one. */
34 static void ht_expand (hash_table
*);
35 static double approx_sqrt (double);
37 /* A deleted entry. */
38 #define DELETED ((hashnode) -1)
40 /* Calculate the hash of the string STR of length LEN. */
43 ht_calc_hash (const unsigned char *str
, size_t len
)
49 r
= HT_HASHSTEP (r
, *str
++);
51 return HT_HASHFINISH (r
, len
);
54 /* Initialize an identifier hashtable. */
57 ht_create (unsigned int order
)
59 unsigned int nslots
= 1 << order
;
62 table
= XCNEW (hash_table
);
64 /* Strings need no alignment. */
65 _obstack_begin (&table
->stack
, 0, 0,
66 (void *(*) (long)) xmalloc
,
67 (void (*) (void *)) free
);
69 obstack_alignment_mask (&table
->stack
) = 0;
71 table
->entries
= XCNEWVEC (hashnode
, nslots
);
72 table
->entries_owned
= true;
73 table
->nslots
= nslots
;
77 /* Frees all memory associated with a hash table. */
80 ht_destroy (hash_table
*table
)
82 obstack_free (&table
->stack
, NULL
);
83 if (table
->entries_owned
)
84 free (table
->entries
);
88 /* Returns the hash entry for the a STR of length LEN. If that string
89 already exists in the table, returns the existing entry. If the
90 identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
91 returns NULL. Otherwise insert and returns a new entry. A new
92 string is allocated. */
94 ht_lookup (hash_table
*table
, const unsigned char *str
, size_t len
,
95 enum ht_lookup_option insert
)
97 return ht_lookup_with_hash (table
, str
, len
, ht_calc_hash (str
, len
),
102 ht_lookup_with_hash (hash_table
*table
, const unsigned char *str
,
103 size_t len
, unsigned int hash
,
104 enum ht_lookup_option insert
)
108 unsigned int deleted_index
= table
->nslots
;
112 sizemask
= table
->nslots
- 1;
113 index
= hash
& sizemask
;
116 node
= table
->entries
[index
];
121 deleted_index
= index
;
122 else if (node
->hash_value
== hash
123 && HT_LEN (node
) == (unsigned int) len
124 && !memcmp (HT_STR (node
), str
, len
))
127 /* hash2 must be odd, so we're guaranteed to visit every possible
128 location in the table during rehashing. */
129 hash2
= ((hash
* 17) & sizemask
) | 1;
134 index
= (index
+ hash2
) & sizemask
;
135 node
= table
->entries
[index
];
141 if (deleted_index
!= table
->nslots
)
142 deleted_index
= index
;
144 else if (node
->hash_value
== hash
145 && HT_LEN (node
) == (unsigned int) len
146 && !memcmp (HT_STR (node
), str
, len
))
151 if (insert
== HT_NO_INSERT
)
154 /* We prefer to overwrite the first deleted slot we saw. */
155 if (deleted_index
!= table
->nslots
)
156 index
= deleted_index
;
158 node
= (*table
->alloc_node
) (table
);
159 table
->entries
[index
] = node
;
161 HT_LEN (node
) = (unsigned int) len
;
162 node
->hash_value
= hash
;
164 if (table
->alloc_subobject
)
166 char *chars
= (char *) table
->alloc_subobject (len
+ 1);
167 memcpy (chars
, str
, len
);
169 HT_STR (node
) = (const unsigned char *) chars
;
172 HT_STR (node
) = (const unsigned char *) obstack_copy0 (&table
->stack
,
175 if (++table
->nelements
* 4 >= table
->nslots
* 3)
176 /* Must expand the string table. */
182 /* Double the size of a hash table, re-hashing existing entries. */
185 ht_expand (hash_table
*table
)
187 hashnode
*nentries
, *p
, *limit
;
188 unsigned int size
, sizemask
;
190 size
= table
->nslots
* 2;
191 nentries
= XCNEWVEC (hashnode
, size
);
195 limit
= p
+ table
->nslots
;
197 if (*p
&& *p
!= DELETED
)
199 unsigned int index
, hash
, hash2
;
201 hash
= (*p
)->hash_value
;
202 index
= hash
& sizemask
;
206 hash2
= ((hash
* 17) & sizemask
) | 1;
209 index
= (index
+ hash2
) & sizemask
;
211 while (nentries
[index
]);
213 nentries
[index
] = *p
;
217 if (table
->entries_owned
)
218 free (table
->entries
);
219 table
->entries_owned
= true;
220 table
->entries
= nentries
;
221 table
->nslots
= size
;
224 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
227 ht_forall (hash_table
*table
, ht_cb cb
, const void *v
)
232 limit
= p
+ table
->nslots
;
234 if (*p
&& *p
!= DELETED
)
236 if ((*cb
) (table
->pfile
, *p
, v
) == 0)
242 /* Like ht_forall, but a nonzero return from the callback means that
243 the entry should be removed from the table. */
245 ht_purge (hash_table
*table
, ht_cb cb
, const void *v
)
250 limit
= p
+ table
->nslots
;
252 if (*p
&& *p
!= DELETED
)
254 if ((*cb
) (table
->pfile
, *p
, v
))
260 /* Restore the hash table. */
262 ht_load (hash_table
*ht
, hashnode
*entries
,
263 unsigned int nslots
, unsigned int nelements
,
266 if (ht
->entries_owned
)
268 ht
->entries
= entries
;
270 ht
->nelements
= nelements
;
271 ht
->entries_owned
= own
;
274 /* Dump allocation statistics to stderr. */
277 ht_dump_statistics (hash_table
*table
)
279 size_t nelts
, nids
, overhead
, headers
;
280 size_t total_bytes
, longest
, deleted
= 0;
281 double sum_of_squares
, exp_len
, exp_len2
, exp2_len
;
284 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
286 : ((x) < 1024*1024*10 \
288 : (x) / (1024*1024))))
289 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
291 total_bytes
= longest
= sum_of_squares
= nids
= 0;
293 limit
= p
+ table
->nslots
;
299 size_t n
= HT_LEN (*p
);
302 sum_of_squares
+= (double) n
* n
;
309 nelts
= table
->nelements
;
310 overhead
= obstack_memory_used (&table
->stack
) - total_bytes
;
311 headers
= table
->nslots
* sizeof (hashnode
);
313 fprintf (stderr
, "\nString pool\nentries\t\t%lu\n",
314 (unsigned long) nelts
);
315 fprintf (stderr
, "identifiers\t%lu (%.2f%%)\n",
316 (unsigned long) nids
, nids
* 100.0 / nelts
);
317 fprintf (stderr
, "slots\t\t%lu\n",
318 (unsigned long) table
->nslots
);
319 fprintf (stderr
, "deleted\t\t%lu\n",
320 (unsigned long) deleted
);
321 fprintf (stderr
, "bytes\t\t%lu%c (%lu%c overhead)\n",
322 SCALE (total_bytes
), LABEL (total_bytes
),
323 SCALE (overhead
), LABEL (overhead
));
324 fprintf (stderr
, "table size\t%lu%c\n",
325 SCALE (headers
), LABEL (headers
));
327 exp_len
= (double)total_bytes
/ (double)nelts
;
328 exp2_len
= exp_len
* exp_len
;
329 exp_len2
= (double) sum_of_squares
/ (double) nelts
;
331 fprintf (stderr
, "coll/search\t%.4f\n",
332 (double) table
->collisions
/ (double) table
->searches
);
333 fprintf (stderr
, "ins/search\t%.4f\n",
334 (double) nelts
/ (double) table
->searches
);
335 fprintf (stderr
, "avg. entry\t%.2f bytes (+/- %.2f)\n",
336 exp_len
, approx_sqrt (exp_len2
- exp2_len
));
337 fprintf (stderr
, "longest entry\t%lu\n",
338 (unsigned long) longest
);
343 /* Return the approximate positive square root of a number N. This is for
344 statistical reports, not code generation. */
346 approx_sqrt (double x
)
358 d
= (s
* s
- x
) / (2 * s
);
366 /* Lookaside Identifier Hash Table */
368 /* This table is implemented as an extensible linear open hash table.
369 See http://en.wikipedia.org/wiki/Open_addressing. */
372 /* Exchange the DESIRED lookaside table with the existing table in the
373 READER. This operation is an information-preserving assignment. */
376 cpp_lt_exchange (cpp_reader
*reader
, cpp_lookaside
*desired
)
378 cpp_lookaside
*current
= reader
->lookaside_table
;
379 reader
->lookaside_table
= desired
;
383 /* Clear the lookaside TABLE statistics. */
386 lt_clear_stats (struct cpp_lookaside
*table
)
389 table
->comparisons
= 0;
391 table
->collisions
= 0;
393 table
->insertions
= 0;
394 table
->macrovalue
= 0;
397 table
->iterations
= 0;
401 /* Create a lookaside table of pow(2,ORDER) entries and set the DEBUG
402 level. This function is a constructor. */
405 cpp_lt_create (unsigned int order
, unsigned int debug
)
407 unsigned int slots
= 1 << order
;
408 cpp_lookaside
*table
= XCNEW (cpp_lookaside
);
409 table
->entries
= XCNEWVEC (struct lae
, slots
);
410 table
->order
= order
;
411 table
->sticky_order
= order
;
414 table
->max_length
= 0;
415 table
->strings
= XCNEW (struct obstack
);
416 /* Strings need no alignment. */
417 _obstack_begin (table
->strings
, 0, 0,
418 (void *(*) (long)) xmalloc
,
419 (void (*) (void *)) free
);
420 obstack_alignment_mask (table
->strings
) = 0;
422 table
->flag_pth_debug
= debug
;
423 lt_clear_stats (table
);
428 /* Print the statistics for the lookaside TABLE. */
431 lt_statistics (struct cpp_lookaside
*table
)
433 fprintf (stderr
, "lookaside ");
434 fprintf (stderr
, "order=%u, ", table
->order
);
435 fprintf (stderr
, "active=%u, ", table
->active
);
436 fprintf (stderr
, "search=%llu, ", table
->searches
);
437 fprintf (stderr
, "compare=%llu, ", table
->comparisons
);
438 fprintf (stderr
, "strcmp=%llu, ", table
->strcmps
);
439 fprintf (stderr
, "collide=%llu, ", table
->collisions
);
440 fprintf (stderr
, "miss=%llu, ", table
->misses
);
441 fprintf (stderr
, "insert=%llu, ", table
->insertions
);
442 fprintf (stderr
, "macro=%llu, ", table
->macrovalue
);
443 fprintf (stderr
, "resize=%llu, ", table
->resizes
);
444 fprintf (stderr
, "bump=%llu, ", table
->bumps
);
445 fprintf (stderr
, "iterations=%llu, ", table
->iterations
);
446 fprintf (stderr
, "empties=%llu\n", table
->empties
);
449 /* Destroy (deallocate) a lookaside TABLE. This function is a destructor. */
452 cpp_lt_destroy (cpp_lookaside
*table
)
454 if (table
->flag_pth_debug
>= 2)
455 lt_statistics (table
);
458 obstack_free (table
->strings
, NULL
);
459 free (table
->strings
);
461 free (table
->entries
);
465 /* Call the GROK function for all the entries in the lookaside TABLE.
466 The cpp_lt_forall function passes PASSTHRU to each invocation of GROK,
467 in addition to the STR characters and their LEN
468 for each IDENT and MACRO value. */
469 /* FIXME pph: This code is presently unused, but may prove useful later. */
471 typedef void (*cpp_lookback
) (void *passthru
,
472 const char *ident_str
, unsigned int ident_len
,
473 const char *macro_str
, unsigned int macro_len
);
475 cpp_lt_forall (cpp_lookaside
*table
, cpp_lookback grok
, void *passthru
)
477 unsigned int slots
= 1 << table
->order
;
478 struct lae
*entries
= table
->entries
;
480 for (index
= 0; index
< slots
; ++index
)
482 hashnode node
= entries
[index
].node
;
484 grok (passthru
, (const char *)node
->str
, node
->len
,
485 entries
[index
].value
, entries
[index
].length
);
490 /* Query a CPP_NODE for its macro value from READER. */
493 lt_query_macro (cpp_reader
*reader
, cpp_hashnode
*cpp_node
)
495 const char *definition
= NULL
;
496 if (cpp_node
->flags
& NODE_BUILTIN
)
498 const char *str
= (const char *)cpp_node
->ident
.str
;
499 if ( strcmp(str
, "__DATE__") == 0
500 || strcmp(str
, "__TIME__") == 0
501 || strcmp(str
, "__FILE__") == 0
502 || strcmp(str
, "__LINE__") == 0)
506 static char *string
= 0;
507 static unsigned int space
= 0;
508 unsigned int front
, back
, needed
;
511 value
= (const char *)_cpp_builtin_macro_text (reader
, cpp_node
);
512 front
= strlen (str
);
513 back
= strlen (value
);
514 needed
= front
+ 1 + back
+ 1;
519 string
= XCNEWVEC (char, needed
);
522 strcpy (string
, str
);
524 strcpy (string
+ front
+ 1, value
);
530 definition
= (const char *) cpp_macro_definition (reader
, cpp_node
);
532 if (reader
->lookaside_table
->flag_pth_debug
>= 3)
533 fprintf (stderr
, "PTH: macro %s is %s\n",
534 (const char *)cpp_node
->ident
.str
,
540 /* Capture the current STRING definition of a macro for the
541 libcpp CPP_NODE and store it in the look ASIDE table of the READER. */
544 lt_macro_value (const char** string
, cpp_lookaside
*aside
,
545 cpp_reader
*reader
, cpp_hashnode
*cpp_node
)
547 const char *definition
= lt_query_macro (reader
, cpp_node
);
548 size_t macro_len
= strlen (definition
);
549 *string
= (const char *) obstack_copy0 (aside
->strings
, definition
, macro_len
);
550 if (macro_len
> aside
->max_length
)
551 aside
->max_length
= macro_len
;
556 /* Capture the identifier state in the lookaside table of READER
557 and then empty the lookaside table. */
560 cpp_lt_capture (cpp_reader
*reader
)
562 cpp_idents_used used
;
563 cpp_lookaside
*aside
= reader
->lookaside_table
;
564 unsigned int num_entries
= aside
->active
;
565 unsigned int slots
= 1 << aside
->order
;
566 unsigned int table_index
;
567 unsigned int summary_index
= 0;
569 used
.num_entries
= aside
->active
;
570 used
.entries
= XCNEWVEC (cpp_ident_use
, num_entries
);
572 /* Copy the entry information into used identifiers table. */
573 for (table_index
= 0; table_index
< slots
; ++table_index
)
575 struct lae
*table_entry
= aside
->entries
+ table_index
;
576 hashnode node
= table_entry
->node
;
579 cpp_ident_use
*summary_entry
;
580 cpp_hashnode
*cpp_node
;
582 summary_entry
= used
.entries
+ summary_index
++;
583 summary_entry
->ident_len
= node
->len
;
584 summary_entry
->ident_str
= (const char *)node
->str
;
585 summary_entry
->before_len
= table_entry
->length
;
586 summary_entry
->before_str
= table_entry
->value
;
588 /* Capture any macro value. */
589 cpp_node
= CPP_HASHNODE (node
);
590 if (cpp_node
->type
== NT_MACRO
)
591 summary_entry
->after_len
= lt_macro_value
592 (&summary_entry
->after_str
, aside
, reader
, cpp_node
);
593 /* else .after_str and .after_len are still zero initialized. */
597 /* Take the strings from the table and give to the summary. */
598 used
.strings
= aside
->strings
;
599 aside
->strings
= NULL
;
600 used
.max_length
= aside
->max_length
;
602 aside
->iterations
+= slots
;
605 /* Do we need to reallocate the table? */
606 if (aside
->sticky_order
< aside
->order
- 1)
608 /* Allocate a new table. */
609 reader
->lookaside_table
= cpp_lt_create (aside
->sticky_order
,
610 aside
->flag_pth_debug
);
611 cpp_lt_destroy (aside
); /* May also dump statistics. */
615 /* Reuse the old table. */
617 /* Dump out the statistics. */
618 if (aside
->flag_pth_debug
>= 2)
620 lt_statistics (aside
);
621 lt_clear_stats (aside
);
624 /* Empty out the entries. */
625 memset (aside
->entries
, 0, slots
* sizeof (struct lae
));
628 /* Create a new string table. */
629 aside
->max_length
= 0;
630 aside
->strings
= XCNEW (struct obstack
);
631 /* Strings need no alignment. */
632 _obstack_begin (aside
->strings
, 0, 0,
633 (void *(*) (long)) xmalloc
,
634 (void (*) (void *)) free
);
635 obstack_alignment_mask (aside
->strings
) = 0;
642 /* Verify that the INDENTIFIERS have before states that consistent
643 with the current identifier definitions in the READER.
644 If not, set the BAD_USE and CUR_DEF to indicate the first
645 inconsistency. A null means 'not a macro'. */
648 cpp_lt_verify (cpp_reader
*reader
, cpp_idents_used
* identifiers
,
649 cpp_ident_use
**bad_use
, const char **cur_def
)
652 unsigned int num_entries
= identifiers
->num_entries
;
653 cpp_ident_use
*entries
= identifiers
->entries
;
658 for (i
= 0; i
< num_entries
; ++i
)
660 cpp_hashnode
*cpp_node
;
661 cpp_ident_use
*entry
= entries
+ i
;
662 const char *ident_str
= entry
->ident_str
;
663 unsigned int ident_len
= entry
->ident_len
;
664 const char *before_str
= entry
->before_str
;
665 unsigned int before_len
= entry
->before_len
;
666 cpp_node
= cpp_peek_sym (reader
, (const unsigned char *)ident_str
,
668 if (cpp_node
== NULL
)
670 /* The symbol used to exist, but it doesn't now. */
671 if (before_str
!= NULL
)
678 else if (before_len
== -1U)
680 /* It was not saved as a macro. */
681 if (cpp_node
->type
== NT_MACRO
)
683 /* But it is a macro now! */
685 *cur_def
= (const char*) lt_query_macro (reader
, cpp_node
);
688 /* Otherwise, both agree it is not a macro. */
692 /* It was saved as a macro. */
693 const char *definition
;
695 if (cpp_node
->type
!= NT_MACRO
)
697 /* But it is not a macro now! */
702 /* Otherwise, both agree it is a macro. */
703 definition
= lt_query_macro (reader
, cpp_node
);
704 /* strlen is required to avoid the prefix problem. */
705 if (definition
== NULL
706 || before_len
!= strlen (definition
)
707 || memcmp (definition
, before_str
, before_len
) != 0)
709 /* They do not have the same value. */
711 *cur_def
= definition
;
725 /* Produce the macro definition syntax NEEDED by cpp_define from
726 the syntax GIVEN by cpp_macro_definition. */
729 cpp_lt_define_syntax (char *needed
, const char *given
)
735 /* Copy over macro identifier. */
736 while ( ('0' <= c
&& c
<= '9')
737 || ('A' <= c
&& c
<= 'Z')
738 || ('a' <= c
&& c
<= 'z')
747 /* Copy over parameter list. */
754 /* Copy over trailing parenthesis. */
759 /* Replace definition space by assignment. */
764 /* Copy over macro identifier. */
774 /* Replay the macro definitions captured by the table of IDENTIFIERS
775 into the READER state. */
778 cpp_lt_replay (cpp_reader
*reader
, cpp_idents_used
* identifiers
)
781 unsigned int num_entries
= identifiers
->num_entries
;
782 cpp_ident_use
*entries
= identifiers
->entries
;
783 char *buffer
= XCNEWVEC (char, identifiers
->max_length
+ 1);
785 /* Prevent the lexer from invalidating the tokens we've read so far. */
786 reader
->keep_tokens
++;
788 for (i
= 0; i
< num_entries
; ++i
)
790 cpp_ident_use
*entry
= entries
+ i
;
791 const char *ident_str
= entry
->ident_str
;
792 const char *before_str
= entry
->before_str
;
793 const char *after_str
= entry
->after_str
;
794 if (before_str
== NULL
)
796 if (after_str
!= NULL
)
798 cpp_lt_define_syntax (buffer
, after_str
);
799 cpp_define (reader
, buffer
);
801 /* else consistently not macros */
805 if (after_str
== NULL
)
807 cpp_undef (reader
, ident_str
);
809 else if (strcmp (before_str
, after_str
) != 0)
811 cpp_undef (reader
, ident_str
);
812 cpp_lt_define_syntax (buffer
, after_str
);
813 cpp_define (reader
, buffer
);
815 /* else macro with the same definition */
819 reader
->keep_tokens
--;
824 /* Destroy IDENTIFIERS captured. */
827 cpp_lt_idents_destroy (cpp_idents_used
*identifiers
)
829 obstack_free (identifiers
->strings
, NULL
);
830 XDELETEVEC (identifiers
);
833 /* Mappings from hash to index. */
834 #define LT_MASK(order) (~(~0 << (order)))
835 #define LT_FIRST(hash, order, mask) (((hash) ^ ((hash) >> (order))) & (mask))
836 #define LT_NEXT(index, mask) (((index) + 1) & (mask))
837 /* Linear probing. */
839 /* Resize the look ASIDE table from its OLD_ORDER to a NEW_ORDER.
840 The NEW_ORDER must hold twice the number of active elements. */
843 lt_resize (cpp_lookaside
*aside
, unsigned int old_order
, unsigned int new_order
)
845 unsigned int old_index
;
846 unsigned int old_slots
= 1 << old_order
;
847 unsigned int new_slots
= 1 << new_order
;
848 unsigned int new_mask
= LT_MASK (new_order
);
849 struct lae
*old_entries
= aside
->entries
;
850 struct lae
*new_entries
= XCNEWVEC (struct lae
, new_slots
);
851 for ( old_index
= 0; old_index
< old_slots
; ++old_index
)
853 hashnode node
= old_entries
[old_index
].node
;
856 unsigned int hash
= old_entries
[old_index
].hash
;
857 unsigned int new_index
= LT_FIRST (hash
, new_order
, new_mask
);
858 hashnode probe
= new_entries
[new_index
].node
;
861 new_index
= LT_NEXT (new_index
, new_mask
);
862 probe
= new_entries
[new_index
].node
;
865 new_entries
[new_index
].node
= node
;
866 new_entries
[new_index
].hash
= hash
;
867 new_entries
[new_index
].length
= old_entries
[old_index
].length
;
868 new_entries
[new_index
].value
= old_entries
[old_index
].value
;
872 aside
->entries
= new_entries
;
873 aside
->order
= new_order
;
877 /* Lookup the IDENTIFER of the given LENGTH and HASH value
878 in the READER's lookaside table.
879 The lookup does not compute a hash. */
882 lt_lookup (cpp_reader
*reader
,
883 const unsigned char *identifier
,
887 cpp_lookaside
*aside
= reader
->lookaside_table
;
888 /* Compress the hash to an index.
889 Assume there is sufficient entropy in the lowest 2*order bits. */
890 unsigned int order
= aside
->order
;
891 unsigned int mask
= LT_MASK (order
);
892 unsigned int index
= LT_FIRST (hash
, order
, mask
);
893 cpp_hashnode
*cpp_node
;
895 /* Search the lookaside table. */
896 struct lae
*entries
= aside
->entries
;
897 hashnode node
= entries
[index
].node
;
900 /* Hashes have no sentinel value, so an entry is empty iff there is
901 a null node value. */
904 if (entries
[index
].hash
== hash
)
906 ++aside
->comparisons
;
907 if (node
->len
== length
)
910 if (memcmp (node
->str
, identifier
, length
) == 0)
911 return CPP_HASHNODE (node
);
916 index
= LT_NEXT (index
, mask
);
917 node
= entries
[index
].node
;
922 node
= ht_lookup_with_hash
923 (reader
->hash_table
, identifier
, length
, hash
, HT_ALLOC
);
924 cpp_node
= CPP_HASHNODE(node
);
926 /* Do not save macro parameter names; they don't affect verification. */
927 if (cpp_node
->flags
& NODE_MACRO_ARG
)
932 /* Fill out new entry. */
934 entries
[index
].node
= node
;
935 entries
[index
].hash
= hash
;
936 if (length
> aside
->max_length
)
937 aside
->max_length
= length
;
939 /* Capture any macro value. */
940 if (cpp_node
->type
== NT_MACRO
)
941 entries
[index
].length
= lt_macro_value
942 (&entries
[index
].value
, aside
, reader
, cpp_node
);
943 /* else .value and .length are still zero from initialization. */
945 /* Check table load factor. */
946 if (aside
->active
>= (unsigned)(1 << (order
- 1)))
947 /* Table is at least half full; double it. */
948 lt_resize (aside
, order
, order
+ 1);