// Balances reference queues.
// Move entries from all queues[0, 1, ..., _max_num_q-1] to
// queues[0, 1, ..., _num_q-1] because only the first _num_q
// corresponding to the active workers will be processed.

void ReferenceProcessor::balance_queues(DiscoveredList ref_lists[])
{

  {- -------------------------------------------
  (1) まず, 全 DiscoveredList 合計での要素数を計算する (以下の total_refs).
      ---------------------------------------- -}

      // calculate total length
      size_t total_refs = 0;
      if (TraceReferenceGC && PrintGCDetails) {
        gclog_or_tty->print_cr("\nBalance ref_lists ");
      }

      for (int i = 0; i < _max_num_q; ++i) {
        total_refs += ref_lists[i].length();
        if (TraceReferenceGC && PrintGCDetails) {
          gclog_or_tty->print("%d ", ref_lists[i].length());
        }
      }
      if (TraceReferenceGC && PrintGCDetails) {
        gclog_or_tty->print_cr(" = %d", total_refs);
      }

  {- -------------------------------------------
  (1) 調整後の各リストの要素数を計算する (以下の avg_refs)
      (調整後には, どのリストにも同じだけの要素が入るようにする. 
       具体的には  total_refs/_num_q  + 1  個の要素が入る)
      ---------------------------------------- -}

      size_t avg_refs = total_refs / _num_q + 1;

  {- -------------------------------------------
  (1) _num_q 本目までに入らないリスト, もしくは avg_refs 個以上の要素数を持つリストから要素を移動させる.
      (移動先は以下の to_idx で管理. といっても, 0 番目のリストから初めて, リストが一杯であれば to_idx を1つずつインクリメントしていくだけ)
      ---------------------------------------- -}

      int to_idx = 0;
      for (int from_idx = 0; from_idx < _max_num_q; from_idx++) {
        bool move_all = false;
        if (from_idx >= _num_q) {
          move_all = ref_lists[from_idx].length() > 0;
        }
        while ((ref_lists[from_idx].length() > avg_refs) ||
               move_all) {
          assert(to_idx < _num_q, "Sanity Check!");
          if (ref_lists[to_idx].length() < avg_refs) {
            // move superfluous refs
            size_t refs_to_move;
            // Move all the Ref's if the from queue will not be processed.
            if (move_all) {
              refs_to_move = MIN2(ref_lists[from_idx].length(),
                                  avg_refs - ref_lists[to_idx].length());
            } else {
              refs_to_move = MIN2(ref_lists[from_idx].length() - avg_refs,
                                  avg_refs - ref_lists[to_idx].length());
            }
            oop move_head = ref_lists[from_idx].head();
            oop move_tail = move_head;
            oop new_head  = move_head;
            // find an element to split the list on
            for (size_t j = 0; j < refs_to_move; ++j) {
              move_tail = new_head;
              new_head = java_lang_ref_Reference::discovered(new_head);
            }
            java_lang_ref_Reference::set_discovered(move_tail, ref_lists[to_idx].head());
            ref_lists[to_idx].set_head(move_head);
            ref_lists[to_idx].inc_length(refs_to_move);
            ref_lists[from_idx].set_head(new_head);
            ref_lists[from_idx].dec_length(refs_to_move);
            if (ref_lists[from_idx].length() == 0) {
              break;
            }
          } else {
            to_idx = (to_idx + 1) % _num_q;
          }
        }
      }

  {- -------------------------------------------
  (1) (デバッグ用の処理) (#ifdef ASSERT 時にのみ実行)
      ---------------------------------------- -}

    #ifdef ASSERT
      size_t balanced_total_refs = 0;
      for (int i = 0; i < _max_num_q; ++i) {
        balanced_total_refs += ref_lists[i].length();
        if (TraceReferenceGC && PrintGCDetails) {
          gclog_or_tty->print("%d ", ref_lists[i].length());
        }
      }
      if (TraceReferenceGC && PrintGCDetails) {
        gclog_or_tty->print_cr(" = %d", balanced_total_refs);
        gclog_or_tty->flush();
      }
      assert(total_refs == balanced_total_refs, "Balancing was incomplete");
    #endif
    }