graph.3f42772.271-338.cpp

	std::vector<double> loMem(m_nodes.size());
	std::vector<double> hiMem(m_nodes.size());
	std::vector<double> prio(m_nodes.size());
	for (size_t i = 0; i < m_nodes.size(); ++i) {
		loMem[i] = static_cast<double>(m_nodes[i]->get_minimum_memory()) / m;
		prio[i] = m_nodes[i]->get_memory_fraction() / fraction;

		memory_size_type hi = m_nodes[i]->get_maximum_memory();
		if (hi == 0)
			hiMem[i] = 1.0;
		else
			hiMem[i] = static_cast<double>(hi) / m;
	}

	double c_lo = 0.0;
	double c_hi = 1.0;
	// Exponential search
	while (true) {
		double memoryAssigned = 0.0;
		for (size_t i = 0; i < m_nodes.size(); ++i) {
			memoryAssigned +=
				std::max(loMem[i], std::min(hiMem[i],
											c_hi * prio[i]));
		}
		if (memoryAssigned < 1.0)
			c_hi *= 2;
		else
			break;
	}

	// Binary search
	while (true) {
		double memoryAssigned = 0.0;
		double c = c_lo + (c_hi-c_lo)/2;

		for (size_t i = 0; i < m_nodes.size(); ++i) {
			memoryAssigned +=
				std::max(loMem[i], std::min(hiMem[i],
											c * prio[i]));
		}

		memory_size_type memory = static_cast<memory_size_type>(memoryAssigned * m);
		if (memory > m) {
			c_hi = c;
		} else {
			c_lo = c;

			memory_size_type spill = m - memory;
			if (spill == 0) break;
		}
	}

	memory_size_type memoryAssigned = 0;

	for (size_t i = 0; i < m_nodes.size(); ++i) {
		memory_size_type lo = m_nodes[i]->get_minimum_memory();
		memory_size_type hi = m_nodes[i]->get_maximum_memory();
		memory_size_type assign =
			std::max(lo, std::min(hi, static_cast<memory_size_type>(m * c_lo * prio[i])));
		memoryAssigned += assign;
		m_nodes[i]->set_available_memory(assign);
	}

	if (memoryAssigned > m) {
		log_warning() << "Too much memory assigned in graph.cpp: Got " << m
			<< ", but assigned " << memoryAssigned
			<< " (" << (memoryAssigned-m) << " b too much)" << std::endl;
	}