Ninja
|
00001 // Copyright 2012 Google Inc. All Rights Reserved. 00002 // 00003 // Licensed under the Apache License, Version 2.0 (the "License"); 00004 // you may not use this file except in compliance with the License. 00005 // You may obtain a copy of the License at 00006 // 00007 // http://www.apache.org/licenses/LICENSE-2.0 00008 // 00009 // Unless required by applicable law or agreed to in writing, software 00010 // distributed under the License is distributed on an "AS IS" BASIS, 00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00012 // See the License for the specific language governing permissions and 00013 // limitations under the License. 00014 00015 #include "build_log.h" 00016 00017 #include <algorithm> 00018 using namespace std; 00019 00020 #include <time.h> 00021 00022 int random(int low, int high) { 00023 return int(low + (rand() / double(RAND_MAX)) * (high - low) + 0.5); 00024 } 00025 00026 void RandomCommand(char** s) { 00027 int len = random(5, 100); 00028 *s = new char[len]; 00029 for (int i = 0; i < len; ++i) 00030 (*s)[i] = (char)random(32, 127); 00031 } 00032 00033 int main() { 00034 const int N = 20 * 1000 * 1000; 00035 00036 // Leak these, else 10% of the runtime is spent destroying strings. 00037 char** commands = new char*[N]; 00038 pair<uint64_t, int>* hashes = new pair<uint64_t, int>[N]; 00039 00040 srand((int)time(NULL)); 00041 00042 for (int i = 0; i < N; ++i) { 00043 RandomCommand(&commands[i]); 00044 hashes[i] = make_pair(BuildLog::LogEntry::HashCommand(commands[i]), i); 00045 } 00046 00047 sort(hashes, hashes + N); 00048 00049 int num_collisions = 0; 00050 for (int i = 1; i < N; ++i) { 00051 if (hashes[i - 1].first == hashes[i].first) { 00052 if (strcmp(commands[hashes[i - 1].second], 00053 commands[hashes[i].second]) != 0) { 00054 printf("collision!\n string 1: '%s'\n string 2: '%s'\n", 00055 commands[hashes[i - 1].second], 00056 commands[hashes[i].second]); 00057 num_collisions++; 00058 } 00059 } 00060 } 00061 printf("\n\n%d collisions after %d runs\n", num_collisions, N); 00062 }