src/testhash.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     testhash.c
   8
   9 Abstract:
  10
  11     Test of the main hash table code.
  12
  13 Author:
  14
  15     Scott Gasch ([email protected]) 19 Oct 2004
  16
  17 Revision History:
  18
  19 **/
  20
  21 #ifdef TEST
  22 #include "chess.h"
  23
  24 extern UCHAR g_cDirty;
  25
  26 #define CONVERT_HASH_DEPTH_TO_SEARCH_DEPTH(x) \
  27     ASSERT(((x) & 0xffffff00) == 0); \
  28     (x) <<= 4
  29
  30 FLAG
  31 SanityCheckHashEntry(HASH_ENTRY *p)
  32 /**
  33
  34 Routine description:
  35
  36     Make sure a hash table entry looks valid.
  37
  38 Parameters:
  39
  40     HASH_ENTRY *p
  41
  42 Return value:
  43
  44     FLAG
  45
  46 **/
  47 {
  48     ULONG uDepth;
  49
  50     if (p->u64Sig == 0)
  51     {
  52         if ((p->mv.uMove != 0) ||
  53             (p->uDepth != 0) ||
  54             (p->bvFlags != 0) ||
  55             (p->iValue != 0))
  56         {
  57             ASSERT(FALSE);
  58             return(FALSE);
  59         }
  60     }
  61     else
  62     {
  63         uDepth = p->uDepth;
  64         CONVERT_HASH_DEPTH_TO_SEARCH_DEPTH(uDepth);
  65         if (!IS_VALID_DEPTH(uDepth))
  66         {
  67             ASSERT(FALSE);
  68             return(FALSE);
  69         }
  70
  71         switch(p->bvFlags & HASH_FLAG_VALID_BOUNDS)
  72         {
  73             case HASH_FLAG_LOWER:
  74             case HASH_FLAG_UPPER:
  75                 break;
  76
  77             case HASH_FLAG_EXACT:
  78                 if (p->mv.uMove == 0)
  79                 {
  80                     ASSERT(FALSE);
  81                     return(FALSE);
  82                 }
  83                 break;
  84
  85             default:
  86                 ASSERT(FALSE);
  87                 return(FALSE);
  88         }
  89     }
  90     return(TRUE);
  91 }
  92
  93
  94 void
  95 AnalyzeFullHashTable(void)
  96 /**
  97
  98 Routine description:
  99
 100     Walk over the hash table and validate populated entries.
 101
 102 Parameters:
 103
 104     void
 105
 106 Return value:
 107
 108     void
 109
 110 **/
 111 {
 112     ULONG uEntry;
 113     ULONG uLine;
 114     ULONG uNumEntries = g_uHashTableSizeBytes / sizeof(HASH_ENTRY);
 115     HASH_ENTRY *p;
 116     ULONG uEmpty = 0;
 117     ULONG uStale = 0;
 118     ULONG uUnique = 0;
 119     ULONG uCount = 0;
 120     ULONG u;
 121     double d;
 122     FLAG fUnique;
 123
 124     uLine = 0;
 125     for (uEntry = 0;
 126          uEntry < uNumEntries;
 127          uEntry++)
 128     {
 129         if ((uEntry % NUM_HASH_ENTRIES_PER_LINE) == 0)
 130         {
 131             uLine++;
 132         }
 133
 134         p = &(g_pHashTable[uEntry]);
 135
 136         //
 137         // See if it's stale
 138         //
 139         if ((p->bvFlags & 0xF0) != g_cDirty)
 140         {
 141             uStale++;
 142         }
 143
 144         //
 145         // Sanity checks
 146         //
 147         if (FALSE == SanityCheckHashEntry(p))
 148         {
 149             UtilPanic(TESTCASE_FAILURE,
 150                       NULL, "TestHash", NULL, NULL,
 151                       __FILE__, __LINE__);
 152         }
 153
 154         //
 155         // See if it's empty
 156         //
 157         if (p->u64Sig == 0)
 158         {
 159             uEmpty++;
 160         }
 161         else
 162         {
 163             uCount++;
 164
 165             //
 166             // See if it's unique
 167             //
 168             if (uEntry % NUM_HASH_ENTRIES_PER_LINE)
 169             {
 170                 fUnique = TRUE;
 171                 u = uEntry - 1;
 172                 do
 173                 {
 174                     if (p->u64Sig == g_pHashTable[u].u64Sig)
 175                     {
 176                         fUnique = FALSE;
 177                         break;
 178                     }
 179                     u--;
 180                 }
 181                 while(u % NUM_HASH_ENTRIES_PER_LINE);
 182             }
 183             else
 184             {
 185                 fUnique = TRUE;
 186             }
 187             uUnique += fUnique;
 188         }
 189     }
 190
 191     //
 192     // Show results
 193     //
 194     Trace("There are %u entries in the hash table.\n", uNumEntries);
 195
 196     d = (double)uStale / (double)uNumEntries * 100.0;
 197     Trace("The hash table is %6.3f percent stale.\n", d);
 198
 199     d = (double)uEmpty / (double)uNumEntries * 100.0;
 200     Trace("The hash table is %6.3f percent empty.\n", d);
 201
 202     d = (double)uUnique / (double)uCount * 100.0;
 203     Trace("The hash table is %6.3f percent unique.\n", d);
 204 }
 205 #endif