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_ident_len
= 0;
415 table
->max_value_len
= 0;
416 table
->strings
= XCNEW (struct obstack
);
417 /* Strings need no alignment. */
418 _obstack_begin (table
->strings
, 0, 0,
419 (void *(*) (long)) xmalloc
,
420 (void (*) (void *)) free
);
421 obstack_alignment_mask (table
->strings
) = 0;
423 table
->pth_debug_level
= debug
;
424 lt_clear_stats (table
);
429 /* Print the statistics for the lookaside TABLE. */
432 lt_statistics (struct cpp_lookaside
*table
)
434 fprintf (stderr
, "lookaside ");
435 fprintf (stderr
, "order=%u, ", table
->order
);
436 fprintf (stderr
, "active=%u, ", table
->active
);
437 fprintf (stderr
, "search=%llu, ", table
->searches
);
438 fprintf (stderr
, "compare=%llu, ", table
->comparisons
);
439 fprintf (stderr
, "strcmp=%llu, ", table
->strcmps
);
440 fprintf (stderr
, "collide=%llu, ", table
->collisions
);
441 fprintf (stderr
, "miss=%llu, ", table
->misses
);
442 fprintf (stderr
, "insert=%llu, ", table
->insertions
);
443 fprintf (stderr
, "macro=%llu, ", table
->macrovalue
);
444 fprintf (stderr
, "resize=%llu, ", table
->resizes
);
445 fprintf (stderr
, "bump=%llu, ", table
->bumps
);
446 fprintf (stderr
, "iterations=%llu, ", table
->iterations
);
447 fprintf (stderr
, "empties=%llu\n", table
->empties
);
450 /* Destroy (deallocate) a lookaside TABLE. This function is a destructor. */
453 cpp_lt_destroy (cpp_lookaside
*table
)
455 if (table
->pth_debug_level
>= 2)
456 lt_statistics (table
);
459 obstack_free (table
->strings
, NULL
);
460 free (table
->strings
);
462 free (table
->entries
);
466 /* Call the GROK function for all the entries in the lookaside TABLE.
467 The cpp_lt_forall function passes PASSTHRU to each invocation of GROK,
468 in addition to the STR characters and their LEN
469 for each IDENT and MACRO value. */
470 /* FIXME pph: This code is presently unused, but may prove useful later. */
472 typedef void (*cpp_lookback
) (void *passthru
,
473 const char *ident_str
, unsigned int ident_len
,
474 const char *macro_str
, unsigned int macro_len
);
476 cpp_lt_forall (cpp_lookaside
*table
, cpp_lookback grok
, void *passthru
)
478 unsigned int slots
= 1 << table
->order
;
479 struct lae
*entries
= table
->entries
;
481 for (index
= 0; index
< slots
; ++index
)
483 hashnode node
= entries
[index
].node
;
485 grok (passthru
, (const char *)node
->str
, node
->len
,
486 entries
[index
].value
, entries
[index
].length
);
491 /* Query a CPP_NODE for its macro value from READER. */
494 lt_query_macro (cpp_reader
*reader
, cpp_hashnode
*cpp_node
)
496 const char *definition
= NULL
;
497 if (cpp_node
->flags
& NODE_BUILTIN
)
499 const char *str
= (const char *)cpp_node
->ident
.str
;
500 if ( strcmp(str
, "__DATE__") == 0
501 || strcmp(str
, "__TIME__") == 0
502 || strcmp(str
, "__FILE__") == 0
503 || strcmp(str
, "__LINE__") == 0)
507 static char *string
= 0;
508 static unsigned int space
= 0;
509 unsigned int back
, needed
;
512 value
= (const char *)_cpp_builtin_macro_text (reader
, cpp_node
);
513 back
= strlen (value
);
514 needed
= 1 + back
+ 1;
519 string
= XCNEWVEC (char, needed
);
523 strcpy (string
+ 1, value
);
530 definition
= (const char *) cpp_macro_definition (reader
, cpp_node
);
531 /* Skip over the macro name within the definition. */
533 while ( ('0' <= c
&& c
<= '9')
534 || ('A' <= c
&& c
<= 'Z')
535 || ('a' <= c
&& c
<= 'z')
542 if (reader
->lookaside_table
->pth_debug_level
>= 3)
543 fprintf (stderr
, "PTH: macro %s is %s\n",
544 (const char *)cpp_node
->ident
.str
,
550 /* Capture the current STRING definition of a macro for the
551 libcpp CPP_NODE and store it in the look ASIDE table of the READER. */
554 lt_macro_value (const char** string
, cpp_lookaside
*aside
,
555 cpp_reader
*reader
, cpp_hashnode
*cpp_node
)
557 const char *definition
= lt_query_macro (reader
, cpp_node
);
558 size_t macro_len
= strlen (definition
);
559 *string
= (const char *) obstack_copy0 (aside
->strings
, definition
, macro_len
);
560 if (macro_len
> aside
->max_value_len
)
561 aside
->max_value_len
= macro_len
;
566 /* Capture the identifier state in the lookaside table of READER
567 and then empty the lookaside table. */
570 cpp_lt_capture (cpp_reader
*reader
)
572 cpp_idents_used used
;
573 cpp_lookaside
*aside
= reader
->lookaside_table
;
574 unsigned int num_entries
= aside
->active
;
575 unsigned int slots
= 1 << aside
->order
;
576 unsigned int table_index
;
577 unsigned int summary_index
= 0;
579 used
.num_entries
= aside
->active
;
580 used
.entries
= XCNEWVEC (cpp_ident_use
, num_entries
);
582 /* Copy the entry information into used identifiers table. */
583 for (table_index
= 0; table_index
< slots
; ++table_index
)
585 struct lae
*table_entry
= aside
->entries
+ table_index
;
586 hashnode node
= table_entry
->node
;
589 cpp_ident_use
*summary_entry
= used
.entries
+ summary_index
++;
590 cpp_hashnode
*cpp_node
= CPP_HASHNODE (node
);
592 summary_entry
->used_by_directive
= cpp_node
->used_by_directive
;
593 summary_entry
->expanded_to_text
= cpp_node
->expanded_to_text
;
594 summary_entry
->ident_len
= node
->len
;
595 summary_entry
->ident_str
= (const char *)node
->str
;
596 summary_entry
->before_len
= table_entry
->length
;
597 summary_entry
->before_str
= table_entry
->value
;
599 /* Capture any macro value. */
600 if (cpp_node
->type
== NT_MACRO
)
601 summary_entry
->after_len
= lt_macro_value
602 (&summary_entry
->after_str
, aside
, reader
, cpp_node
);
603 /* else .after_str and .after_len are still zero initialized. */
607 /* Take the strings from the table and give to the summary. */
608 used
.strings
= aside
->strings
;
609 aside
->strings
= NULL
;
610 used
.max_ident_len
= aside
->max_ident_len
;
611 used
.max_value_len
= aside
->max_value_len
;
613 aside
->iterations
+= slots
;
616 /* Do we need to reallocate the table? */
617 if (aside
->sticky_order
< aside
->order
- 1)
619 /* Allocate a new table. */
620 reader
->lookaside_table
= cpp_lt_create (aside
->sticky_order
,
621 aside
->pth_debug_level
);
622 cpp_lt_destroy (aside
); /* May also dump statistics. */
626 /* Reuse the old table. */
628 /* Dump out the statistics. */
629 if (aside
->pth_debug_level
>= 2)
631 lt_statistics (aside
);
632 lt_clear_stats (aside
);
635 /* Empty out the entries. */
636 memset (aside
->entries
, 0, slots
* sizeof (struct lae
));
639 /* Create a new string table. */
640 aside
->max_ident_len
= 0;
641 aside
->max_value_len
= 0;
642 aside
->strings
= XCNEW (struct obstack
);
643 /* Strings need no alignment. */
644 _obstack_begin (aside
->strings
, 0, 0,
645 (void *(*) (long)) xmalloc
,
646 (void (*) (void *)) free
);
647 obstack_alignment_mask (aside
->strings
) = 0;
654 /* Verify that the INDENTIFIERS have before states that consistent
655 with the current identifier definitions in the READER.
656 If not, set the BAD_USE and CUR_DEF to indicate the first
657 inconsistency. A null means 'not a macro'. */
660 cpp_lt_verify_1 (cpp_reader
*reader
, cpp_idents_used
* identifiers
,
661 cpp_ident_use
**bad_use
, const char **cur_def
,
665 unsigned int num_entries
= identifiers
->num_entries
;
666 cpp_ident_use
*entries
= identifiers
->entries
;
671 for (i
= 0; i
< num_entries
; ++i
)
673 cpp_hashnode
*cpp_node
;
674 cpp_ident_use
*entry
= entries
+ i
;
675 const char *ident_str
= entry
->ident_str
;
676 unsigned int ident_len
= entry
->ident_len
;
677 const char *before_str
= entry
->before_str
;
678 unsigned int before_len
= entry
->before_len
;
679 cpp_node
= cpp_peek_sym (reader
, (const unsigned char *)ident_str
,
681 if (cpp_node
== NULL
)
683 /* The symbol used to exist, but it doesn't now. */
684 if (before_str
!= NULL
)
691 else if (before_len
== -1U)
693 /* It was not saved as a macro. */
694 if (cpp_node
->type
== NT_MACRO
)
696 /* But it is a macro now! */
697 const char *definition
;
698 definition
= (const char*) lt_query_macro (reader
, cpp_node
);
701 /* Check to see if the current value is the after value. */
702 unsigned int after_len
= entry
->after_len
;
703 /* strlen is required to avoid the prefix problem. */
704 if (definition
== NULL
705 || after_len
!= strlen (definition
)
706 || memcmp (definition
, entry
->after_str
, after_len
) != 0)
708 /* They do not have the same value. */
710 *cur_def
= definition
;
717 *cur_def
= definition
;
721 /* Otherwise, both agree it is not a macro. */
725 /* It was saved as a macro. */
726 const char *definition
;
728 if (cpp_node
->type
!= NT_MACRO
)
730 /* But it is not a macro now! */
735 /* Otherwise, both agree it is a macro. */
736 definition
= lt_query_macro (reader
, cpp_node
);
737 /* strlen is required to avoid the prefix problem. */
738 if (definition
== NULL
739 || before_len
!= strlen (definition
)
740 || memcmp (definition
, before_str
, before_len
) != 0)
742 /* They do not have the same value. */
744 *cur_def
= definition
;
759 cpp_lt_verify (cpp_reader
*reader
, cpp_idents_used
* identifiers
,
760 cpp_ident_use
**bad_use
, const char **cur_def
)
762 return cpp_lt_verify_1 (reader
, identifiers
, bad_use
, cur_def
, false);
765 /* Produce the macro definition syntax NEEDED by cpp_define from
766 the syntax GIVEN by cpp_macro_definition. */
769 cpp_lt_define_syntax (char *needed
, const char *ident
, const char *given
)
773 /* Copy over macro identifier. */
781 /* Copy over macro definition. */
785 /* Copy over parameter list. */
792 /* Copy over trailing parenthesis. */
797 /* Replace definition space by assignment. */
801 /* Copy over macro value. */
812 /* Replay the macro definitions captured by the table of IDENTIFIERS
813 into the READER state. */
816 cpp_lt_replay (cpp_reader
*reader
, cpp_idents_used
* identifiers
)
819 unsigned int num_entries
= identifiers
->num_entries
;
820 cpp_ident_use
*entries
= identifiers
->entries
;
821 char *buffer
= XCNEWVEC (char, identifiers
->max_ident_len
822 + identifiers
->max_value_len
+ 1);
824 /* Prevent the lexer from invalidating the tokens we've read so far. */
825 reader
->keep_tokens
++;
827 for (i
= 0; i
< num_entries
; ++i
)
829 cpp_ident_use
*entry
= entries
+ i
;
830 const char *ident_str
= entry
->ident_str
;
831 const char *before_str
= entry
->before_str
;
832 const char *after_str
= entry
->after_str
;
833 if (before_str
== NULL
)
835 if (after_str
!= NULL
)
837 cpp_lt_define_syntax (buffer
, ident_str
, after_str
);
838 cpp_define (reader
, buffer
);
840 /* else consistently not macros */
844 if (after_str
== NULL
)
846 cpp_undef (reader
, ident_str
);
848 else if (strcmp (before_str
, after_str
) != 0)
850 cpp_undef (reader
, ident_str
);
851 cpp_lt_define_syntax (buffer
, ident_str
, after_str
);
852 cpp_define (reader
, buffer
);
854 /* else macro with the same definition */
858 reader
->keep_tokens
--;
863 /* Destroy IDENTIFIERS captured. */
866 cpp_lt_idents_destroy (cpp_idents_used
*identifiers
)
868 obstack_free (identifiers
->strings
, NULL
);
869 XDELETEVEC (identifiers
->entries
);
872 /* Mappings from hash to index. */
873 #define LT_MASK(order) (~(~0 << (order)))
874 #define LT_FIRST(hash, order, mask) (((hash) ^ ((hash) >> (order))) & (mask))
875 #define LT_NEXT(index, mask) (((index) + 1) & (mask))
876 /* Linear probing. */
878 /* Resize the look ASIDE table from its OLD_ORDER to a NEW_ORDER.
879 The NEW_ORDER must hold twice the number of active elements. */
882 lt_resize (cpp_lookaside
*aside
, unsigned int old_order
, unsigned int new_order
)
884 unsigned int old_index
;
885 unsigned int old_slots
= 1 << old_order
;
886 unsigned int new_slots
= 1 << new_order
;
887 unsigned int new_mask
= LT_MASK (new_order
);
888 struct lae
*old_entries
= aside
->entries
;
889 struct lae
*new_entries
= XCNEWVEC (struct lae
, new_slots
);
890 for ( old_index
= 0; old_index
< old_slots
; ++old_index
)
892 hashnode node
= old_entries
[old_index
].node
;
895 unsigned int hash
= old_entries
[old_index
].hash
;
896 unsigned int new_index
= LT_FIRST (hash
, new_order
, new_mask
);
897 hashnode probe
= new_entries
[new_index
].node
;
900 new_index
= LT_NEXT (new_index
, new_mask
);
901 probe
= new_entries
[new_index
].node
;
904 new_entries
[new_index
].node
= node
;
905 new_entries
[new_index
].hash
= hash
;
906 new_entries
[new_index
].length
= old_entries
[old_index
].length
;
907 new_entries
[new_index
].value
= old_entries
[old_index
].value
;
911 aside
->entries
= new_entries
;
912 aside
->order
= new_order
;
916 /* Lookup the IDENTIFER of the given LENGTH and HASH value
917 in the READER's lookaside table.
918 The lookup does not compute a hash. */
921 lt_lookup (cpp_reader
*reader
,
922 const unsigned char *identifier
,
926 cpp_lookaside
*aside
= reader
->lookaside_table
;
927 /* Compress the hash to an index.
928 Assume there is sufficient entropy in the lowest 2*order bits. */
929 unsigned int order
= aside
->order
;
930 unsigned int mask
= LT_MASK (order
);
931 unsigned int index
= LT_FIRST (hash
, order
, mask
);
932 cpp_hashnode
*cpp_node
;
934 /* Search the lookaside table. */
935 struct lae
*entries
= aside
->entries
;
936 hashnode node
= entries
[index
].node
;
939 /* Hashes have no sentinel value, so an entry is empty iff there is
940 a null node value. */
943 if (entries
[index
].hash
== hash
)
945 ++aside
->comparisons
;
946 if (node
->len
== length
)
949 if (memcmp (node
->str
, identifier
, length
) == 0)
950 return CPP_HASHNODE (node
);
955 index
= LT_NEXT (index
, mask
);
956 node
= entries
[index
].node
;
961 node
= ht_lookup_with_hash
962 (reader
->hash_table
, identifier
, length
, hash
, HT_ALLOC
);
963 cpp_node
= CPP_HASHNODE(node
);
965 /* Do not save macro parameter names; they don't affect verification. */
966 if (cpp_node
->flags
& NODE_MACRO_ARG
)
971 /* Fill out new entry. */
973 entries
[index
].node
= node
;
974 entries
[index
].hash
= hash
;
975 if (length
> aside
->max_ident_len
)
976 aside
->max_ident_len
= length
;
978 /* Capture any macro value. */
979 if (cpp_node
->type
== NT_MACRO
)
980 entries
[index
].length
= lt_macro_value
981 (&entries
[index
].value
, aside
, reader
, cpp_node
);
982 /* else .value and .length are still zero from initialization. */
984 /* Check table load factor. */
985 if (aside
->active
>= (unsigned)(1 << (order
- 1)))
986 /* Table is at least half full; double it. */
987 lt_resize (aside
, order
, order
+ 1);