gperf/src/search.cc

101    In other words, each step finds a projection that is injective on the
908    means that we split the work into several steps.  Each step chooses
912    Look at this partitioning:  After every step, the _asso_values[] of a
924    The partition before a step is always a refinement of the partition
925    after the step.
927    broader at each step.  (A step that only chooses an _asso_values[c]
928    without changing the partition is better merged with the previous step,
948   /* The characters whose values are being determined in this step.  */
951   /* Exclusive upper bound for the _asso_values[c] of this step.
954   /* The characters whose values will be determined after this step.  */
956   /* The keyword set partition after this step.  */
958   /* The expected number of iterations in this step.  */
1142         /* Determine the main character to be chosen in this step.
1167                  are the starting situation and don't need any more step.  */
1175         /* We need one more step.  */
1176         Step *step = new Step();
1178         step->_undetermined = new bool[_alpha_size];
1179         memcpy (step->_undetermined, undetermined, _alpha_size*sizeof(bool));
1181         step->_partition = partition;
1184            step.  */
1189            step, because they will not change the equivalence classes at
1205         /* Now the set of changing characters of this step.  */
1210           if (undetermined[c] && !step->_undetermined[c])
1216           if (undetermined[c] && !step->_undetermined[c])
1219         step->_changing = changing;
1220         step->_changing_count = changing_count;
1222         step->_asso_value_max = _asso_value_max;
1224         step->_expected_lower =
1227         step->_expected_upper =
1233         step->_next = steps;
1234         steps = step;
1244       for (Step *step = steps; step; step = step->_next)
1248           for (unsigned int i = 0; i < step->_changing_count; i++)
1252               fprintf (stderr, "'%c'", step->_changing[i]);
1255                    step->_expected_lower, step->_expected_upper);
1257           for (EquivalenceClass *cls = step->_partition; cls; cls = cls->_next)
1277   for (Step *step = steps; step; step = step->_next)
1282       unsigned int k = step->_changing_count;
1285           unsigned int c = step->_changing[i];
1288             & (step->_asso_value_max - 1);
1302           for (EquivalenceClass *cls = step->_partition; cls; cls = cls->_next)
1319                       if (!step->_undetermined[*p])
1347                    asso_values[step->_changing[0],...step->_changing[k-1]]
1355                    asso_values[step->_changing[i]] =
1363                   unsigned int c = step->_changing[i];
1366                     (_asso_values[c] + _jump) & (step->_asso_value_max - 1);
1371                     & (step->_asso_value_max - 1);
1378                   unsigned int c = step->_changing[i];
1381                     (_asso_values[c] + _jump) & (step->_asso_value_max - 1);
1386                     & (step->_asso_value_max - 1);
1392                 unsigned int c = step->_changing[ii];
1395                   & (step->_asso_value_max - 1);
1404                   if (bound == step->_asso_value_max)
1407                          increase the available search space of this step.
1409                       step->_asso_value_max = 2 * step->_asso_value_max;
1410                       if (step->_asso_value_max > _asso_value_max)
1412                           _asso_value_max = step->_asso_value_max;
1425                 unsigned int c = step->_changing[ii];
1429                   & (step->_asso_value_max - 1);
1436               unsigned int c = step->_changing[ii];
1438                 (_asso_values[c] + rand ()) & (step->_asso_value_max - 1);
1450           for (unsigned int i = 0; i < step->_changing_count; i++)
1454               fprintf (stderr, "'%c'", step->_changing[i]);
1463       Step *step = steps;
1464       steps = step->_next;
1465       delete[] step->_changing;
1466       delete[] step->_undetermined;
1467       delete_partition (step->_partition);
1468       delete step;