gperf/src/search.cc

98    In other words, each step finds a projection that is injective on the
905    means that we split the work into several steps.  Each step chooses
909    Look at this partitioning:  After every step, the _asso_values[] of a
921    The partition before a step is always a refinement of the partition
922    after the step.
924    broader at each step.  (A step that only chooses an _asso_values[c]
925    without changing the partition is better merged with the previous step,
945   /* The characters whose values are being determined in this step.  */
948   /* Exclusive upper bound for the _asso_values[c] of this step.
951   /* The characters whose values will be determined after this step.  */
953   /* The keyword set partition after this step.  */
955   /* The expected number of iterations in this step.  */
1139         /* Determine the main character to be chosen in this step.
1164                  are the starting situation and don't need any more step.  */
1172         /* We need one more step.  */
1173         Step *step = new Step();
1175         step->_undetermined = new bool[_alpha_size];
1176         memcpy (step->_undetermined, undetermined, _alpha_size*sizeof(bool));
1178         step->_partition = partition;
1181            step.  */
1186            step, because they will not change the equivalence classes at
1202         /* Now the set of changing characters of this step.  */
1207           if (undetermined[c] && !step->_undetermined[c])
1213           if (undetermined[c] && !step->_undetermined[c])
1216         step->_changing = changing;
1217         step->_changing_count = changing_count;
1219         step->_asso_value_max = _asso_value_max;
1221         step->_expected_lower =
1224         step->_expected_upper =
1230         step->_next = steps;
1231         steps = step;
1241       for (Step *step = steps; step; step = step->_next)
1245           for (unsigned int i = 0; i < step->_changing_count; i++)
1249               fprintf (stderr, "'%c'", step->_changing[i]);
1252                    step->_expected_lower, step->_expected_upper);
1254           for (EquivalenceClass *cls = step->_partition; cls; cls = cls->_next)
1274   for (Step *step = steps; step; step = step->_next)
1279       unsigned int k = step->_changing_count;
1282           unsigned int c = step->_changing[i];
1285             & (step->_asso_value_max - 1);
1299           for (EquivalenceClass *cls = step->_partition; cls; cls = cls->_next)
1316                       if (!step->_undetermined[*p])
1344                    asso_values[step->_changing[0],...step->_changing[k-1]]
1352                    asso_values[step->_changing[i]] =
1360                   unsigned int c = step->_changing[i];
1363                     (_asso_values[c] + _jump) & (step->_asso_value_max - 1);
1368                     & (step->_asso_value_max - 1);
1375                   unsigned int c = step->_changing[i];
1378                     (_asso_values[c] + _jump) & (step->_asso_value_max - 1);
1383                     & (step->_asso_value_max - 1);
1389                 unsigned int c = step->_changing[ii];
1392                   & (step->_asso_value_max - 1);
1401                   if (bound == step->_asso_value_max)
1404                          increase the available search space of this step.
1406                       step->_asso_value_max = 2 * step->_asso_value_max;
1407                       if (step->_asso_value_max > _asso_value_max)
1409                           _asso_value_max = step->_asso_value_max;
1422                 unsigned int c = step->_changing[ii];
1426                   & (step->_asso_value_max - 1);
1433               unsigned int c = step->_changing[ii];
1435                 (_asso_values[c] + rand ()) & (step->_asso_value_max - 1);
1447           for (unsigned int i = 0; i < step->_changing_count; i++)
1451               fprintf (stderr, "'%c'", step->_changing[i]);
1460       Step *step = steps;
1461       steps = step->_next;
1462       delete[] step->_changing;
1463       delete[] step->_undetermined;
1464       delete_partition (step->_partition);
1465       delete step;