Changes in directory llvm/include/llvm/ADT:
StringMap.h updated: 1.10 -> 1.11
---
Log message:
do not allow hash table to be filled with tombstones.
---
Diffs of the changes: (+10 -4)
StringMap.h | 14 ++++++++++----
1 files changed, 10 insertions(+), 4 deletions(-)
Index: llvm/include/llvm/ADT/StringMap.h
diff -u llvm/include/llvm/ADT/StringMap.h:1.10
llvm/include/llvm/ADT/StringMap.h:1.11
--- llvm/include/llvm/ADT/StringMap.h:1.10 Sun Feb 11 14:58:00 2007
+++ llvm/include/llvm/ADT/StringMap.h Sun Feb 11 15:07:36 2007
@@ -218,8 +218,11 @@
Bucket.Item = KeyValue;
++NumItems;
- // If the hash table is now more than 3/4 full, rehash into a larger table.
- if (NumItems > NumBuckets*3/4)
+ // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
+ // the buckets are empty (meaning that many are filled with tombstones),
+ // grow the table.
+ if (NumItems*4 > NumBuckets*3 ||
+ NumBuckets-(NumItems+NumTombstones) < NumBuckets/8)
RehashTable();
return true;
}
@@ -244,8 +247,11 @@
// filled in by LookupBucketFor.
Bucket.Item = NewItem;
- // If the hash table is now more than 3/4 full, rehash into a larger table.
- if (NumItems > NumBuckets*3/4)
+ // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
+ // the buckets are empty (meaning that many are filled with tombstones),
+ // grow the table.
+ if (NumItems*4 > NumBuckets*3 ||
+ NumBuckets-(NumItems+NumTombstones) < NumBuckets/8)
RehashTable();
return *NewItem;
}
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
