/*
**==============================================================================
**
** Open Management Infrastructure (OMI)
**
** Copyright (c) Microsoft Corporation
**
** Licensed under the Apache License, Version 2.0 (the "License"); you may not
** use this file except in compliance with the License. You may obtain a copy
** of the License at
**
** http://www.apache.org/licenses/LICENSE-2.0
**
** THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
** KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
** WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
** MERCHANTABLITY OR NON-INFRINGEMENT.
**
** See the Apache 2 License for the specific language governing permissions
** and limitations under the License.
**
**==============================================================================
*/
#include <iostream>
#include <cctype>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <map>
using namespace std;
const char* arg0;
typedef pair<string, string> Pair;
typedef vector<Pair> Vector;
void LoadSpecFile(const char* path, Vector& pairs)
{
// Open input file:
FILE* is = fopen(path, "r");
if (!is)
{
fprintf(stderr, "%s: failed to open: %s\n", arg0, path);
exit(1);
}
// Read each line:
char buf[1024];
unsigned int line = 1;
for (; fgets(buf, sizeof(buf), is) != NULL; line++)
{
char* p;
vector<string> toks;
char* str;
char* tag;
// Skip leading spaces:
for (p = buf; isspace(*p); p++)
;
// Skip comments:
if (p[0] == '#')
continue;
// Remove trailing spaces:
{
char* end = p + strlen(buf);
while (end != p && isspace(end[-1]))
*--end = '\0';
}
// Expect string
{
str = p;
while (*p && *p != ',')
p++;
}
// Skip spaces:
while (isspace(*p))
p++;
if (!*p)
{
char buf[32];
sprintf(buf, "TAG%u", line);
pairs.push_back(Pair(str, buf));
continue;
}
// Expect ':'
if (*p != ',')
{
fprintf(stderr, "%s: syntax error on line %u\n", arg0, line);
exit(1);
}
*p++ = '\0';
// Skip spaces:
while (isspace(*p))
p++;
// Expect tag
{
tag = p;
if (!isalpha(*p) && *p != '_')
{
fprintf(stderr, "%s: syntax error on line %u\n", arg0, line);
exit(1);
}
while (isalnum(*p) || *p == '_')
p++;
}
*p++ = '\0';
// Skip spaces:
while (isspace(*p))
p++;
if (*p)
{
fprintf(stderr, "%s: syntax error on line %u\n", arg0, line);
exit(1);
}
pairs.push_back(Pair(str, tag));
}
}
static void _GenEnum(FILE* f, const Vector& pairs)
{
// Generate enumeration:
{
fprintf(f, "enum\n");
fprintf(f, "{\n");
for (size_t i = 0; i < pairs.size(); i++)
{
fprintf(f, " %s = %u%s\n", pairs[i].second.c_str(), (int)(i + 1), ((i+1) == pairs.size() ? "" : ","));
}
fprintf(f, "};\n");
fprintf(f, "\n");
}
}
#if 0
static void GenSimpleFunction(const char* fileName, const Vector& pairs)
{
FILE* f = fopen(fileName, "w");
if (!f)
{
fprintf(stderr, "%s: failed to open: %s\n", arg0, fileName);
exit(1);
}
//_GenEnum(f, pairs);
/* header */
fprintf(f, "static int SimpleStr(const char* s, size_t n)\n");
fprintf(f, "{\n");
/* generate function body */
fprintf(f, "n=n;\n ");
for (size_t i = 0; i < pairs.size(); i++)
{
const string& str = pairs[i].first.c_str();
const string& tok = pairs[i].second.c_str();
fprintf(f, " if (strcmp(s, \"%s\") == 0)\n",
str.c_str());
fprintf(f, " ");
fprintf(f, "return %s;\n", tok.c_str());
fprintf(f, " else");
}
fprintf(f, "\n return 0; /* not found */\n");
/* close the function */
//fprintf(f, "\n");
fprintf(f, "}\n\n");
fclose(f);
}
#endif
#if 0
static void GenHashFunction(const char* fileName, const Vector& pairs)
{
FILE* f = fopen(fileName, "w");
if (!f)
{
fprintf(stderr, "%s: failed to open: %s\n", arg0, fileName);
exit(1);
}
//_GenEnum(f, pairs);
// Generate function
{
typedef pair<unsigned int, Vector> MPair;
typedef map<unsigned int, Vector> Map;
Map m;
fprintf(f, "int HashStr(const char* s, size_t n)\n");
fprintf(f, "{\n");
fprintf(f, " unsigned int h = (unsigned int)(n ^ s[0] ^ s[n-1]);\n");
fprintf(f, "\n");
fprintf(f, " switch (h)\n");
fprintf(f, " {\n");
// Conslidate pairs with like hash codes
for (size_t i = 0; i < pairs.size(); i++)
{
const char* s = pairs[i].first.c_str();
size_t n = pairs[i].first.size();
unsigned int h = n ^ s[0] ^ s[n-1];
Map::iterator pos = m.find(h);
if (pos == m.end())
{
Vector v;
v.push_back(pairs[i]);
m.insert(MPair(h,v));
}
else
{
(*pos).second.push_back(pairs[i]);
}
}
// Print cases:
for (Map::iterator p = m.begin(); p != m.end(); p++)
{
const Vector& v = (*p).second;
fprintf(f, " case %u:\n", (*p).first);
for (size_t i = 0; i < v.size(); i++)
{
const string& str = v[i].first.c_str();
const string& tok = v[i].second.c_str();
fprintf(f, " ");
fprintf(f, "if (n == %u && memcmp(s, \"%s\", n) == 0)\n",
(int)str.size(), str.c_str());
fprintf(f, " ");
fprintf(f, "return %s;\n", tok.c_str());
}
fprintf(f, " break;\n");
}
fprintf(f, " }\n");
fprintf(f, " /* Not found */\n");
fprintf(f, " return 0;\n");
fprintf(f, "}\n");
}
fclose(f);
}
#endif
typedef multimap<unsigned int, Pair> Map;
typedef pair<unsigned int, Pair> MPair;
static void _GenStringCmp(FILE* f, const Pair& p)
{
const string& str = p.first.c_str();
const string& tok = p.second.c_str();
fprintf(f, " ");
fprintf(f, "if (strcmp(s, \"%s\") == 0)\n",
str.c_str());
fprintf(f, " ");
fprintf(f, "return %s;\n", tok.c_str());
}
static void _GenSubSwitchForRange(
FILE* f,
Map::const_iterator pos,
Map::const_iterator range_end)
{
// find best character with min. number of collisions
unsigned int bestIndex = 0;
unsigned int bestCollision = 0xFFFFFFFF;
unsigned int n = pos->first;
for ( unsigned int index = 0; index < n; index++ )
{
vector<unsigned int> collisions(256, 0);
unsigned int currentMax = 0;
for ( Map::const_iterator it = pos; it != range_end; it++ )
{
unsigned char c = it->second.first[index];
collisions[c]++;
if (collisions[c] > currentMax)
currentMax = collisions[c];
}
#if 0
printf("n is %d, index %d, currentMax %d, best %d\n",
n, index, currentMax, bestCollision);
#endif
if (bestCollision > currentMax)
{
bestCollision = currentMax;
bestIndex = index;
}
if (1 == bestCollision)
break;
}
#if 0
printf("n is %d, best index %d, best %d\n",
n, bestIndex, bestCollision);
#endif
// build a submap based on best index value
Map subMap;
for ( Map::const_iterator it = pos; it != range_end; it++ )
{
unsigned char c = it->second.first[bestIndex];
subMap.insert(MPair(c, it->second));
}
fprintf(f, " switch (s[%u])\n", bestIndex);
fprintf(f, " {\n");
// process submap
// generate cases for each length
Map::const_iterator posSubMap = subMap.begin();
while (posSubMap != subMap.end())
{
unsigned int n = posSubMap->first;
Map::const_iterator range_end = subMap.upper_bound(n);
fprintf(f, " case %u:\n", n);
while (posSubMap != range_end)
{
_GenStringCmp(f, posSubMap->second);
posSubMap++;
}
//printf("n is %d, number of items is %d\n", n, distance(posSubMap, range_end));
fprintf(f, " break;\n");
posSubMap = subMap.lower_bound(n+1);
}
fprintf(f, " }\n");
fprintf(f, "\n");
}
static void GenHashStrHeader(
const string& fileName,
const Vector& pairs)
{
FILE* f = fopen(fileName.c_str(), "w");
if (!f)
{
fprintf(stderr, "%s: failed to open: %s\n", arg0, fileName.c_str());
exit(1);
}
_GenEnum(f, pairs);
/* file header */
fprintf(f, "int HashStr(const char* s, size_t n);\n");
fprintf(f, "\n");
printf("Created %s\n", fileName.c_str());
}
static void GenHashStrFunction(
const string& fileName,
const Vector& pairs)
{
FILE* f = fopen(fileName.c_str(), "w");
if (!f)
{
fprintf(stderr, "%s: failed to open: %s\n", arg0, fileName.c_str());
exit(1);
}
//_GenEnum(f, pairs);
/* file header */
fprintf(f, "int HashStr(const char* s, size_t n)\n");
fprintf(f, "{\n");
fprintf(f, "\n");
fprintf(f, " switch (n)\n");
fprintf(f, " {\n");
/* create a map based on str len */
Map m;
// Conslidate pairs with like str length
for (size_t i = 0; i < pairs.size(); i++)
{
size_t n = pairs[i].first.size();
m.insert(MPair(n, pairs[i]));
}
// generate cases for each length
Map::const_iterator pos = m.begin();
while (pos != m.end())
{
unsigned int n = pos->first;
Map::const_iterator range_end = m.upper_bound(n);
fprintf(f, " case %u:\n", n);
if (1 >= distance(pos, range_end))
{
// special case - only few elements in range
while (pos != range_end)
{
_GenStringCmp(f, pos->second);
pos++;
}
}
else
{
_GenSubSwitchForRange(f, pos, range_end);
}
//printf("n is %d, number of items is %d\n", n, distance(pos, range_end));
fprintf(f, " break;\n");
pos = m.lower_bound(n+1);
}
fprintf(f, " }\n");
fprintf(f, " /* Not found */\n");
fprintf(f, " return 0;\n");
fprintf(f, "}\n");
fclose(f);
printf("Created %s\n", fileName.c_str());
}
#if 0
static void GenUnittest(const char* fileName, const Vector& pairs)
{
FILE* f = fopen(fileName, "w");
if (!f)
{
fprintf(stderr, "%s: failed to open: %s\n", arg0, fileName);
exit(1);
}
/* file header */
fprintf(f, "#include <ut/ut.h>\n");
fprintf(f, "#include <string.h>\n");
fprintf(f, "#include \"../quickstr.h\"\n");
fprintf(f, "#include \"../quickstr.inc\"\n");
fprintf(f, "#include \"hash.inc\"\n");
fprintf(f, "#include \"simple.inc\"\n");
fprintf(f, "\n");
fprintf(f, "static void setUp()\n{\n}\n");
fprintf(f, "static void cleanup()\n{\n}\n");
fprintf(f, "typedef int (*FN)(const char* s, size_t n);\n");
fprintf(f, "static void testAllStrings(FN f)\n{\n");
/* generate all tests */
for (size_t i = 0; i < pairs.size(); i++)
{
const string& str = pairs[i].first.c_str();
const string& tok = pairs[i].second.c_str();
fprintf(f, " UT_ASSERT((*f)(\"%s\", %u) == %s);\n",
str.c_str(), (int)str.size(), tok.c_str() );
}
/* add comparison with not-exisitng strings */
fprintf(f, " UT_ASSERT((*f)(\"*\", 1) == 0);\n") ;
fprintf(f, " UT_ASSERT((*f)(\"**\", 2) == 0);\n") ;
fprintf(f, " UT_ASSERT((*f)(\"***\", 3) == 0);\n") ;
fprintf(f, " UT_ASSERT((*f)(\"****\", 4) == 0);\n") ;
fprintf(f, " UT_ASSERT((*f)(\"*****\", 5) == 0);\n") ;
fprintf(f, " UT_ASSERT((*f)(\"******\", 6) == 0);\n") ;
/* Generate end of unittest file */
fprintf(f, "}\n\n");
fprintf(f, "static void TestSimple()\n");
fprintf(f, "{\n");
fprintf(f, " for(int i=0; i< 10000; i++) testAllStrings(SimpleStr);\n");
fprintf(f, "}\n");
fprintf(f, "\n");
fprintf(f, "static void TestHash()\n");
fprintf(f, "{\n");
fprintf(f, " for(int i=0; i< 10000; i++) testAllStrings(HashStr);\n");
fprintf(f, "}\n");
fprintf(f, "\n");
fprintf(f, "static void TestHashStr()\n");
fprintf(f, "{\n");
fprintf(f, " for(int i=0; i< 10000; i++) testAllStrings(HashStr);\n");
fprintf(f, "}\n");
fprintf(f, "\n");
fprintf(f, "static void RunTests()\n");
fprintf(f, "{\n");
fprintf(f, " UT_TEST(TestSimple);\n");
fprintf(f, " UT_TEST(TestHash);\n");
fprintf(f, " UT_TEST(TestHashStr);\n");
fprintf(f, "}\n");
fprintf(f, "\n");
fprintf(f, "UT_ENTRY_POINT(RunTests);\n");
fclose(f);
}
#endif
int main(int argc, char** argv)
{
arg0 = argv[0];
if (argc < 2)
{
fprintf(stderr, "Usage: %s path\n", arg0);
exit(1);
}
Vector pairs;
LoadSpecFile(argv[1], pairs);
if (pairs.empty())
{
fprintf(stderr, "no data for building hash function\n");
exit(1);
}
#if 0
GenSimpleFunction("simple.inc", pairs);
GenHashFunction("hash.inc", pairs);
#endif
// Determine the base filename:
string base = argv[1];
{
size_t pos = base.rfind('/');
if (pos != string::npos)
base = base.substr(pos + 1);
pos = base.rfind('.');
if (pos != string::npos)
base = base.substr(0, pos);
}
GenHashStrHeader(base + ".h", pairs);
GenHashStrFunction(base + ".inc", pairs);
#if 0
GenUnittest("tests/test_strhash.cpp", pairs);
#endif
return 0;
}
Return to
strhash.cpp
CVS log
Up to [OMI] / omi / strhash