This is an automated email from the git hooks/post-receive script. x2go pushed a commit to branch 3.6.x-rpm-debug in repository nx-libs. commit 158701a2188ffb232da7a60db60e7ff713dbb1ca Author: Mihai Moldovan <ionic@ionic.de> Date: Thu Mar 29 00:30:48 2018 +0200 nx-X11/programs/Xserver/hw/nxagent/Screen.c: implement basic screen boxes extending algorithm, generating a list of solutions. --- nx-X11/programs/Xserver/hw/nxagent/Screen.c | 1355 +++++++++++++++++++++++++++ 1 file changed, 1355 insertions(+) diff --git a/nx-X11/programs/Xserver/hw/nxagent/Screen.c b/nx-X11/programs/Xserver/hw/nxagent/Screen.c index 903a773..2213040 100644 --- a/nx-X11/programs/Xserver/hw/nxagent/Screen.c +++ b/nx-X11/programs/Xserver/hw/nxagent/Screen.c @@ -5524,6 +5524,1361 @@ static nxagentScreenCrtcsSolutions* nxagentScreenCrtcsGenerateSolutionsSingleScr } /* + * Helper calculating an obsolete boxes count, given a list of all boxes. + * + * Note that it might be zero if there are no obsolete boxes or an error + * happened. If the error parameter is non-NULL, its value will be set to true + * to indicate an error. + */ +#ifdef DEBUG +/* + * When debugging, make sure the guards are not optimized away. Otherwise + * providing NULL for the err parameter will crash when calling the function + * directly in debuggers. + */ +__attribute__((optimize("O0"))) +#endif +static size_t nxagentScreenBoxesObsoleteCount(const nxagentScreenBoxes *all_boxes, Bool *err) { + size_t ret = 0; + + if (err) { + *err = FALSE; + } + + if (!(all_boxes)) { + if (err) { + *err = TRUE; + } + + return(ret); + } + + nxagentScreenBoxesElem *cur = NULL; + xorg_list_for_each_entry(cur, &(all_boxes->head), entry) { + if (cur->obsolete) { + ++ret; + } + } + + return(ret); +} + +/* + * Helper that exchanges a screen box for a new one. + * The original box is destroyed, the new box is deep-copied. + * + * Returns true on success, otherwise false. + */ +static Bool nxagentScreenBoxesUpdateScreenBox(nxagentScreenBoxes *boxes, const size_t screen_number, const nxagentScreenBoxesElem *new_box) { + Bool ret = FALSE; + + if ((!(boxes)) || (!(new_box))) { + return(ret); + } + + nxagentScreenBoxesElem *cur_box = NULL; + size_t i = 0; + xorg_list_for_each_entry(cur_box, &(boxes->head), entry) { + if (cur_box->screen_id == new_box->screen_id) { + /* Need to exchange the current box. */ + nxagentScreenBoxesElem *new_copy = nxagentScreenBoxesElemCopy(new_box, TRUE); + + if (!(new_copy)) { + return(ret); + } + + /* + * Taking out the magic wand here: + * Since an xorg_list is cyclic and we know that the current element + * exists, we can use an append operation to insert the new element and + * then delete the old one. + * Instead of appending to the original list head (in this case boxes), + * we'll append to the current element. The actual magic is that a list + * append operation is *actually* a prepend operation relative to the + * passed head element. + * + * Example: + * Original list (each edge is actually a double edge pointing in both + * directions): + * + * ┌──────────────────────────────────────────┐ + * ↓ │ + * [HEAD] ↔ [elem1] ↔ [elem2] ↔ [elem3] ↔ ... ←─┘ + * + * Append operation relative to HEAD: + * + * ┌───────────────────────────────────────────────────────┐ + * ↓ │ + * [HEAD] ↔ [elem1] ↔ [elem2] ↔ [elem3] ↔ ... ↔ [new_elem] ←─┘ + * + * Append operation relative to elem2: + * + * ┌───────────────────────────────────────────────────────┐ + * ↓ │ + * [HEAD] ↔ [elem1] ↔ [new_elem] ↔ [elem2] ↔ [elem3] ↔ ... ←─┘ + * + * Afterwards, delete operation on elem2: + * + * ┌─────────────────────────────────────────────┐ + * ↓ │ + * [HEAD] ↔ [elem1] ↔ [new_elem] ↔ [elem3] ↔ ... ←─┘ + * + * Observant readers might have noticed that using either a list append + * or add operation (i.e., relative to given head element an inverse + * append or "real" append operation) followed by a delete operation for + * the current element will lead to the same result. + * + * We'll use an append/inverse append operation, though, since this makes + * the most sense. + */ + xorg_list_append(&(new_copy->entry), &(cur_box->entry)); + xorg_list_del(&(cur_box->entry)); + + /* Get rid of cur_box. */ + SAFE_FREE(cur_box); + + ret = TRUE; + break; + } + + i++; + } + + /* + * If ret is still false here it means that the list did not contain an + * element at position pos (i.e., it was too small). + * + * No need for special treatment. + */ + + return(ret); +} + +/* + * Helper that generates an array with solution lists for each screen box and + * direction. + * + * The array will always be screen_count-sized. + * + * Returns a pointer to the array. Will be NULL on failure. + */ +static nxagentScreenCrtcsSolutions** nxagentScreenCrtcsGeneratePotentialSolutionArray(const nxagentScreenBoxes *all_boxes, const nxagentScreenBoxes *screen_boxes, const size_t screen_count) { + nxagentScreenCrtcsSolutions **ret = NULL; + + /* FIXME: xorg_list_is_empty is not const-correct. */ + if ((!(screen_count)) || (xorg_list_is_empty((struct xorg_list *)(&(screen_boxes->head)))) || (xorg_list_is_empty((struct xorg_list *)(&(all_boxes->head))))) { + return(ret); + } + + ret = calloc(screen_count, sizeof(nxagentScreenCrtcsSolutions*)); + + if (!(ret)) { + return(ret); + } + + for (size_t i = 0; i < screen_count; ++i) { + nxagentScreenBoxesElem *tmp_box = NULL; + { + size_t y = 0; + xorg_list_for_each_entry(tmp_box, &(screen_boxes->head), entry) { + /* y == i means that we found our current box and can break out. */ + if (y++ == i) { + break; + } + } + + if ((&(tmp_box->entry)) == &(screen_boxes->head)) { +#ifdef WARNING + fprintf(stderr, "%s: reached end of list while fetching specific box. Algorithm error.\n", __func__); +#endif + + for (size_t z = 0; z < screen_count; ++z) { + nxagentScreenCrtcsFreeSolutions(ret[z]); + + SAFE_FREE(ret[z]); + } + + SAFE_FREE(ret); + + return(ret); + } + } + + /* Build other_screens list. */ + nxagentScreenBoxes *other_screens = calloc(1, sizeof(nxagentScreenBoxes)); + + if (!(other_screens)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to allocate space for other_screens list.\n", __func__); +#endif + + for (size_t y = 0; y < screen_count; ++y) { + nxagentScreenCrtcsFreeSolutions(ret[y]); + + SAFE_FREE(ret[y]); + } + + SAFE_FREE(ret); + + return(ret); + } + + xorg_list_init(&(other_screens->head)); + other_screens->screen_id = -1; + + nxagentScreenBoxesElem *tmp = NULL; + xorg_list_for_each_entry(tmp, &(screen_boxes->head), entry) { + if (tmp != tmp_box) { + /* Copy current element. */ + nxagentScreenBoxesElem *box_copy = nxagentScreenBoxesElemCopy(tmp, TRUE); + + if (!(box_copy)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to copy current screen box.\n", __func__); +#endif + + for (size_t y = 0; y < screen_count; ++y) { + nxagentScreenCrtcsFreeSolutions(ret[y]); + + SAFE_FREE(ret[y]); + } + + nxagentFreeScreenBoxes(other_screens, TRUE); + + SAFE_FREE(other_screens); + + SAFE_FREE(ret); + + return(ret); + } + + /* Add to other_screens list. */ + xorg_list_append(&(box_copy->entry), &(other_screens->head)); + } + } + + /* + * Right now, all_boxes contains all boxes, including obsolete + * information, tmp_box is the current screen box to extend and + * other_screens contains the other screen boxes. + * + * With that, we can fetch a solutions list comprising of the best(!) + * solutions for extending the current box in all directions. + */ + nxagentScreenCrtcsSolutions *cur_screen_solutions = nxagentScreenCrtcsGenerateSolutionsSingleScreen(all_boxes, tmp_box, other_screens); + + /* + * Clean up other_screens. Doing that now means we don't have to do it in + * the error handling. + */ + nxagentFreeScreenBoxes(other_screens, TRUE); + + SAFE_FREE(other_screens); + + /* NULL means failure or no solutions. */ + if (!(cur_screen_solutions)) { +#ifdef WARNING + fprintf(stderr, "%s: no solution found for current configuration. Algorithm error.\n", __func__); +#endif + + for (size_t y = 0; y < screen_count; ++y) { + nxagentScreenCrtcsFreeSolutions(ret[y]); + + SAFE_FREE(ret[y]); + } + + SAFE_FREE(ret); + + return(ret); + } + + /* + * If everything worked out, we'll have a solutions list. + * It might contain multiple entries, but at this point we don't care, + * since they may not have the highest overall rating. + * Just add them to our general solutions list. + * + * We're just setting plain pointer values here, which should work fine + * since the next and prev pointers point to the addresses of an + * element's entry xorg_list struct. + * + * Be careful, though. + */ + ret[i] = cur_screen_solutions; + } + + return(ret); +} + +/* + * Helper that extracts the best solutions from a screen_count-sized solutions + * array and, at the same time, records if a screen is suitable for extension. + * + * The arrays will always likewise be screen_count-sized. + * + * The last two parameters are output parameters that expect to be passed a + * valid address. NULL pointers for any parameter or a zero screen count will be + * treated as an error. init might be zero (i.e., false). + * + * Returns true on success, otherwise false. + */ +static Bool nxagentScreenCrtcsFilterScreenSolutions(const nxagentScreenCrtcsSolutions * const *solutions, const size_t screen_count, const Bool init, const Bool *screens_init, nxagentScreenCrtcsSolutions ***best_screen_solutions, Bool **screen_selection) { + Bool ret = FALSE; + + if ((!(solutions)) || (!(screen_count)) || (!(screens_init)) || (!(best_screen_solutions)) || (!(screen_selection))) { + return(ret); + } + + (*screen_selection) = NULL; + (*best_screen_solutions) = NULL; + + double *screen_ratings = calloc(screen_count, sizeof(double)); + + if (!(screen_ratings)) { + return(ret); + } + + Bool *screen_overlap_free = calloc(screen_count, sizeof(Bool)); + + if (!(screen_overlap_free)) { + SAFE_FREE(screen_ratings); + + return(ret); + } + + (*screen_selection) = calloc(screen_count, sizeof(Bool)); + (*best_screen_solutions) = calloc(screen_count, sizeof(nxagentScreenCrtcsSolutions*)); + + if ((!((*screen_selection))) || (!((*best_screen_solutions)))) { + SAFE_FREE(screen_ratings); + SAFE_FREE(screen_overlap_free); + + /* Let caller handle other cleanup. It'll be done there anyway. */ + return(ret); + } + + /* + * We consider two different cases when filtering solutions: + * - the initial case, used as long as we have non-extended (i.e., + * initial) screen boxes and + * - the normal case. + * + * The initial case is slightly different, since we generally need to + * consider every best solution per initial box. + * This ensures initial expansion (together with the rating function + * favoring initial expansion). + * + * In both cases, we still have to consider all screen boxes (i.e., also + * the already extended ones in the initial case), since we want to fish + * out solutions with no additional overlap. + * + * Viable solutions will be selected with this preference (n.b.: as the + * name implies, all solutions we can select from are the best for their + * respective screen): + * - if we have solutions with no additional overlap, take the best + * one(s) + * otherwise + * - if there are still screens to extend, take the best one(s) for an + * unextended screen + * otherwise + * - take the overall best one(s). + * + * Mixing all solutions into one list and extracting the best solutions is + * not feasible in this algorithmic branch siince we wouldn't be able to + * map the solution back to an initial screen. + * + * Instead, we'll mark screens as selected and pull out solutions manually. + */ + + /* Update the screen_overlap_free and screen_ratings arrays. */ + Bool overlap_free = FALSE; + double max_rating = INVALID_RATING, + max_overlap_free_rating = INVALID_RATING; + for (size_t i = 0; i < screen_count; ++i) { + screen_ratings[i] = INVALID_RATING; + screen_overlap_free[i] = FALSE; + + /* Extract best solutions first. */ + (*best_screen_solutions)[i] = nxagentScreenCrtcsExtractBestSolutions(solutions[i]); + + if (!((*best_screen_solutions)[i])) { + SAFE_FREE(screen_ratings); + SAFE_FREE(screen_overlap_free); + + /* Let caller handle other cleanup. It'll be done there anyway. */ + return(ret); + } + + /* Skip this part if we have no solutions in the list. */ + if (!(xorg_list_is_empty((*best_screen_solutions)[i]))) { + nxagentScreenCrtcsSolution *cur = xorg_list_first_entry((*best_screen_solutions)[i], nxagentScreenCrtcsSolution, entry); + + /* + * Rating must be the same for all entries in a list as returned by + * nxagentScreenCrtcsExtractBestSolutions(). + */ + screen_ratings[i] = cur->rating; + + /* + * Covers might be different per-solution, so go through the full list. + */ + cur = NULL; + xorg_list_for_each_entry(cur, (*best_screen_solutions)[i], entry) { + if (!(cur->rating_cover_penalty)) { + screen_overlap_free[i] = TRUE; + + if (screen_ratings[i] > max_overlap_free_rating) { + max_overlap_free_rating = screen_ratings[i]; + } + + /* First non-overlapping solution is all we care about. */ + break; + } + } + } + + overlap_free |= screen_overlap_free[i]; + + /* + * max_rating is useful in the case we have no overlap-free solutions. + * + * We care for all screens after initialization or for non-extended screens + * prior to initialization. + */ + if ((init) || (!(screens_init[i]))) { + if (screen_ratings[i] > max_rating) { + max_rating = screen_ratings[i]; + } + } + } + + if (((overlap_free) && (INVALID_RATING == max_overlap_free_rating)) || ((!(overlap_free)) && (INVALID_RATING == max_rating))) { +#ifdef WARNING + fprintf(stderr, "%s: no solution found for current configuration in %sscreen extension run%s. Algorithm error.\n", __func__, init ? "initial " : "", init ? ", but not all initial screen boxes have been extended yet" : ""); +#endif + + SAFE_FREE(screen_ratings); + SAFE_FREE(screen_overlap_free); + + /* Let caller handle other cleanup. It'll be done there anyway. */ + return(ret); + } + + if (overlap_free) { + /* + * We know that there is at least one overlap-free solution. The real + * question left is which screens have the highest-rating solutions. + * + * Go through the list and compare with the best rating. + * + * FIXME: do we want some more magic here to prefer non-extended screens + * during the initial extension run, even if that would mean picking + * worse (i.e., non-best) solutions? + */ + for (size_t i = 0; i < screen_count; ++i) { + if ((screen_overlap_free[i]) && (screen_ratings[i] == max_overlap_free_rating)) { + /* + * This screen has a maximum overlap-free rating. Since it may also + * contain non-overlap-free solutions, filter them out to make later + * handling easier. + */ + nxagentScreenCrtcsSolution *cur = NULL, + *tmp = NULL; + xorg_list_for_each_entry_safe(cur, tmp, (*best_screen_solutions)[i], entry) { + if (cur->rating_cover_penalty) { + xorg_list_del(&(cur->entry)); + + nxagentScreenCrtcsFreeSolution(cur); + + SAFE_FREE(cur); + } + } + + /* Mark this screen as suitable for further processing. */ + (*screen_selection)[i] = TRUE; + } + } + } + else { + /* + * No non-overlapping solutions found, so either select the best-rated + * non-extended screen(s) or generally the best-rated screen(s). + * + * Luckily we've already got the best rating value as max_rating, so we'll + * just need to go through the list again and mark the affected solutions + * as selected. + */ + for (size_t i = 0; i < screen_count; ++i) { + if (screen_ratings[i] == max_rating) { + (*screen_selection)[i] = TRUE; + } + } + } + + ret = TRUE; + + SAFE_FREE(screen_ratings); + SAFE_FREE(screen_overlap_free); + + return(ret); +} + +/* + * Helper setting up its my_solution output parameter according to the first + * solution in the best_screen_solutions list. + * + * No pointer parameters may be NULL. screen_number is allowed to be zero + * (indicating the first screen). + * + * Returns true on success, otherwise false. + */ +static Bool nxagentScreenCrtcsSelectSolution(const nxagentScreenBoxes *screen_boxes, const size_t screen_number, const Bool *screens_init, const nxagentScreenCrtcsSolutions *best_screen_solutions, nxagentScreenCrtcsSolution **my_solution) { + Bool ret = FALSE; + + if ((!(screen_boxes)) || (!(screens_init)) || (!(best_screen_solutions)) || (!(my_solution))) { + return(ret); + } + + /* + * Always take the first entry for the current run. + */ + nxagentScreenCrtcsSolution *first_entry = xorg_list_first_entry(best_screen_solutions, nxagentScreenCrtcsSolution, entry); + + /* + * Assert that first_entry is always a legit one - since we checked + * the amount of solutions before, that should be safe. + * This is why we don't check the return value here. + */ + + nxagentScreenCrtcsSolution *tmp_solution = nxagentScreenCrtcsSolutionCopy(first_entry); + + if (!(tmp_solution)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to copy generated solution.\n", __func__); +#endif + + return(ret); + } + + if (!(*my_solution)) { + /* If we don't have a solution yet, use this one. */ + (*my_solution) = tmp_solution; + } + else { + /* Otherwise, modify my_solution. */ + (*my_solution)->rating_size_change += tmp_solution->rating_size_change; + (*my_solution)->rating_cover_penalty += tmp_solution->rating_cover_penalty; + + if (!(screens_init[screen_number])) { + (*my_solution)->rating_extended_boxes_count += tmp_solution->rating_extended_boxes_count; /* Should always be +1. */ + } + + (*my_solution)->rating += tmp_solution->rating; + + /* Plainly take the all_boxes pointer. */ + nxagentFreeScreenBoxes((*my_solution)->all_boxes, TRUE); + SAFE_FREE((*my_solution)->all_boxes); + (*my_solution)->all_boxes = nxagentScreenBoxesCopy(tmp_solution->all_boxes); + + if (!((*my_solution)->all_boxes)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to copy current all boxes state.\n", __func__); +#endif + + return(ret); + } + } + + /* + * The solution boxes list handling is more complicated. + * Our new, temporary solution only has the extended screen box + * in its solution list - we will want to merge that into our + * solutions list, replacing the original one in there (if it + * exists). + */ + + /* Take a copy of the original solutions boxes pointer. */ + nxagentScreenBoxes *orig_solution_boxes = (*my_solution)->solution_boxes; + + /* Copy work_screens to the solution boxes of my_solution. */ + (*my_solution)->solution_boxes = nxagentScreenBoxesCopy(screen_boxes); + + if (!((*my_solution)->solution_boxes)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to copy current screen state.\n", __func__); +#endif + + return(ret); + } + + if ((!(orig_solution_boxes)) || (xorg_list_is_empty(&(orig_solution_boxes->head)))) { +#ifdef WARNING + fprintf(stderr, "%s: original solution boxes list invalid or empty.\n", __func__); +#endif + + nxagentFreeScreenBoxes(orig_solution_boxes, TRUE); + + SAFE_FREE(orig_solution_boxes); + + return(ret); + } + + /* + * Fetch actual screen box. The solutions list should only + * contain one element, so breaking out directly should be + * safe. + */ + nxagentScreenBoxesElem *cur_box = xorg_list_first_entry(&(first_entry->solution_boxes->head), nxagentScreenBoxesElem, entry); + + const Bool update = nxagentScreenBoxesUpdateScreenBox((*my_solution)->solution_boxes, screen_number, cur_box); + + /* + * Outside of error handling, since we need to get rid of this + * data unconditionally. + */ + nxagentFreeScreenBoxes(orig_solution_boxes, TRUE); + + SAFE_FREE(orig_solution_boxes); + + if (!(update)) { +#ifdef WARNING + { + const unsigned long long screen_number_ = screen_number; + fprintf(stderr, "%s: unable to update solution screen number %llu.\n", __func__, screen_number_); + } +#endif + + return(ret); + } + + /* Delete taken solution out of the list. */ + xorg_list_del(&(first_entry->entry)); + + /* Get rid of the entry. */ + nxagentScreenCrtcsFreeSolution(first_entry); + + SAFE_FREE(first_entry); + + ret = TRUE; + + return(ret); +} + +/* + * Declaration needed since the next function is using one that is only defined + * at a later point. + * + * Moving it up would be problematic since in that case we'd need even more + * declarations for other functions. + */ +static nxagentScreenCrtcsSolutions* nxagentScreenCrtcsGenerateSolutions(const nxagentScreenBoxes *all_boxes, const nxagentScreenBoxes *initial_screens, const size_t all_boxes_count, const size_t screen_count, const Bool *orig_screens_init); + +/* + * Helper handling all the solutions in best_screen_solutions recursively, + * adding them to the ret_solutions output parameter list. + * + * No pointer parameters may be NULL. screen_count and screen_number might be + * zero. + * + * Returns true on success, otherwise false. + */ +static Bool nxagentScreenCrtcsRecurseSolutions(const nxagentScreenBoxes *screen_boxes, const size_t screen_count, const size_t all_boxes_count, const Bool *screens_init, const size_t screen_number, const nxagentScreenCrtcsSolutions *best_screen_solutions, nxagentScreenCrtcsSolutions *ret_solutions) { + Bool ret = FALSE; + + if ((!(screen_boxes)) || (!(screen_count)) || (!(all_boxes_count)) || (!(screens_init)) || (!(best_screen_solutions)) || (!(ret_solutions))) { + return(ret); + } + + nxagentScreenCrtcsSolution *cur_solution = NULL; + xorg_list_for_each_entry(cur_solution, best_screen_solutions, entry) { + /* Other solutions will be handled recursively. */ + + /* Copy screens_init and set current screen value to true. */ + Bool *recursive_screens_init = calloc(screen_count, sizeof(Bool)); + + if (!(recursive_screens_init)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to copy screen initialization array.\n", __func__); +#endif + + return(ret); + } + + memmove(recursive_screens_init, screens_init, (screen_count * sizeof(Bool))); + + recursive_screens_init[screen_number] = TRUE; + + nxagentScreenBoxes *recursive_work_screens = nxagentScreenBoxesCopy(screen_boxes); + + if (!(recursive_work_screens)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to copy current screen state.\n", __func__); +#endif + + SAFE_FREE(recursive_screens_init); + + return(ret); + } + + if ((!(cur_solution->solution_boxes)) || (xorg_list_is_empty(&(cur_solution->solution_boxes->head)))) { +#ifdef WARNING + fprintf(stderr, "%s: current solution boxes list is empty or invalid. Algorithm error.\n", __func__); +#endif + + nxagentFreeScreenBoxes(recursive_work_screens, TRUE); + + SAFE_FREE(recursive_work_screens); + + SAFE_FREE(recursive_screens_init); + + return(ret); + } + + nxagentScreenBoxesElem *cur_box = xorg_list_first_entry(&(cur_solution->solution_boxes->head), nxagentScreenBoxesElem, entry); + + const Bool update = nxagentScreenBoxesUpdateScreenBox(recursive_work_screens, screen_number, cur_box); + + if (!(update)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to update screen state.\n", __func__); +#endif + + nxagentFreeScreenBoxes(recursive_work_screens, TRUE); + + SAFE_FREE(recursive_screens_init); + + SAFE_FREE(recursive_work_screens); + + return(ret); + } + + nxagentScreenCrtcsSolutions *tmp_solutions = nxagentScreenCrtcsGenerateSolutions(cur_solution->all_boxes, recursive_work_screens, all_boxes_count, screen_count, recursive_screens_init); + + /* Get rid of the temporary screens init array again. */ + SAFE_FREE(recursive_screens_init); + + /* Get rid of the modified work screens list. */ + nxagentFreeScreenBoxes(recursive_work_screens, TRUE); + + SAFE_FREE(recursive_work_screens); + + if (!(tmp_solutions)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to generate a new solutions list. Algorithm error.\n", __func__); +#endif + + return(ret); + } + + /* + * tmp_solutions should now contain a list of possible solutions, + * add to ret_solutions. + */ + nxagentScreenCrtcsSolution *cur_solution_it = NULL, + *next_solution = NULL; + xorg_list_for_each_entry_safe(cur_solution_it, next_solution, tmp_solutions, entry) { + xorg_list_del(&(cur_solution_it->entry)); + xorg_list_append(&(cur_solution_it->entry), ret_solutions); + } + + /* tmp_solutions should be empty now, safe to free. */ + SAFE_FREE(tmp_solutions); + } + + ret = TRUE; + + return(ret); +} + +/* + * Helper for handling solution lists. This probably is the heart of the screen + * extension code. The function is called once per extension run and calls + * other functions to save the very first solution and recursively generate + * alternative solutions. + * + * No pointer parameters might be NULL. init might be zero (i.e., false). + * + * Returns true on success, otherwise false. + */ +static Bool nxagentScreenCrtcsHandleSolutions(const nxagentScreenBoxes *all_boxes, const nxagentScreenBoxes *screen_boxes, const Bool init, const Bool *screens_init, const size_t screen_count, const size_t all_boxes_count, const Bool *screen_selection, nxagentScreenCrtcsSolutions *ret_solutions, ssize_t *screen_to_init, nxagentScreenCrtcsSolutions **best_screen_solutions, nxagentScreenCrtcsSolution **my_solution) { + Bool ret = FALSE; + + if ((!(all_boxes)) || (!(screen_boxes)) || (!(screens_init)) || (!(screen_count)) || (!(all_boxes_count)) || (!(screen_selection)) || (!(ret_solutions)) || (!(screen_to_init)) || (!(best_screen_solutions)) || (!(my_solution))) { + return(ret); + } + + /* + * In case we have multiple solutions with a maximum rating, we need to + * consider each solution, which means branching off for all but one + * solution and only handling one solution in this run. + * Selecting the solution for the current run is tricky, though. We + * could either take the very first one, which is relatively easy, the + * last one, which is complicated because there might be multiple + * screens with a maximum rating and finding the last one is tricky + * with a spread-out array. Merging all solutions into one list and then + * taking the last element would be easy to do, but has the negative + * consequence of not being able to tell what screen the individual + * solutions belonged to originally - at least not without + * "sophisticated" means like keeping the original list and deep-checking + * objects for equality or creating another structure. + * Selecting a more or less random solution at the end of the first + * screen would work, but feels weird if there are more screens with + * potential solutions. + * + * Hence, let's go for selecting the very first solution. + */ + Bool fetched_solution = FALSE; + (*screen_to_init) = -1; + for (size_t i = 0; i < screen_count; ++i) { + if (screen_selection[i]) { + /* + * This screen has been selected. + * Its solution list may include more than one solution, though, + * which means that we have to branch off and consider each + * individual solution. + * At the very end, we select (potentially one of) the overall best + * solution. + */ + + if ((!(best_screen_solutions[i])) || (xorg_list_is_empty(best_screen_solutions[i]))) { +#ifdef WARNING + fprintf(stderr, "%s: current screen marked with a maximum rating, but no solutions found in screen extension run. Algorithm error.\n", __func__); +#endif + + return(ret); + } + + /* + * One or more solution(s), if necessary take the first one as the + * current solution and then branch off for the others. + */ + if (!(fetched_solution)) { + Bool fetch = nxagentScreenCrtcsSelectSolution(screen_boxes, i, screens_init, best_screen_solutions[i], my_solution); + + if (!(fetch)) { +#ifdef WARNING + fprintf(stderr, "%s: error while selecting solution for current run.\n", __func__); +#endif + + return(ret); + } + + fetched_solution = TRUE; + + /* + * DO NOT modify other data (screen, all boxes or screen initialization + * array) here! + * We will need to change these variables eventually, but given + * that we may have further solutions to process/generate, doing + * it here would be an error. + * Refer to the later part of nxagentScreenCrtcsGenerateSolutions for + * this. + */ + if (init) { + (*screen_to_init) = i; + } + } + + Bool recursive_solutions = nxagentScreenCrtcsRecurseSolutions(screen_boxes, screen_count, all_boxes_count, screens_init, i, best_screen_solutions[i], ret_solutions); + + if (!(recursive_solutions)) { +#ifdef WARNING + fprintf(stderr, "%s: error while handling other solutions recursively in current run.\n", __func__); +#endif + + return(ret); + } + } + } + + ret = TRUE; + + return(ret); +} + +/* + * Helper updating internal data in nxagentScreenCrtcsGenerateSolutions(). + * This mostly exists to avoid complicated data freeing while updating the + * internal data. + * + * No pointers might be NULL. screens_to_init is allowed to be zero or + * negative, although negative values will not lead to changed data. This is + * not considered an error. + * + * Returns true on success, otherwise false. + */ +static Bool nxagentScreenCrtcsGenerateSolutionsUpdateInternalData(const nxagentScreenBoxes *all_boxes, const nxagentScreenBoxes *screen_boxes, const ssize_t screen_to_init, nxagentScreenBoxes **work_all_boxes, nxagentScreenBoxes **work_screens, Bool *screens_init) { + Bool ret = FALSE; + + if ((!(all_boxes)) || (!(screen_boxes)) || (!(work_all_boxes)) || (!(work_screens)) || (!(screens_init))) { + return(ret); + } + + nxagentFreeScreenBoxes((*work_all_boxes), TRUE); + + SAFE_FREE((*work_all_boxes)); + + nxagentFreeScreenBoxes((*work_screens), TRUE); + + SAFE_FREE((*work_screens)); + + (*work_all_boxes) = nxagentScreenBoxesCopy(all_boxes); + + if (!((*work_all_boxes))) { +#ifdef WARNING + fprintf(stderr, "%s: unable to copy current screen boxes.\n", __func__); +#endif + + return(ret); + } + + (*work_screens) = nxagentScreenBoxesCopy(screen_boxes); + + if (!((*work_screens))) { +#ifdef WARNING + fprintf(stderr, "%s: unable to copy current screen boxes.\n", __func__); +#endif + + nxagentFreeScreenBoxes((*work_all_boxes), TRUE); + + SAFE_FREE((*work_all_boxes)); + + return(ret); + } + + /* + * Mark the current screen as initialized. + * DO NOT move this to the other functions, since we might have + * multiple screens with a maximum rating, but will not extend + * the other screens in the current run (but rather in recursive + * calls). + */ + if (0 <= screen_to_init) { +#ifdef WARNING + if (screens_init[screen_to_init]) { + const unsigned long long screen_number = screen_to_init; + fprintf(stderr, "%s: shall set screen init for screen number %llu to TRUE, but already marked as initialized. Algorithm warning.\n", __func__, screen_number); + } +#endif + + screens_init[screen_to_init] = TRUE; + } + + ret = TRUE; + + return(ret); +} + +/* + * Helper generating a "fake" solution based on the passed-in data. + * + * This is useful if no screens needed extension. + * + * No pointer parameters might be NULL. + * + * On success, returns a "fake" solution, otherwise NULL. + */ +static nxagentScreenCrtcsSolution* nxagentScreenCrtcsGenerateFakeSolution(const nxagentScreenBoxes *all_boxes, const nxagentScreenBoxes *screen_boxes) { + nxagentScreenCrtcsSolution *ret = NULL; + + if ((!(all_boxes)) || (!(screen_boxes))) { + return(ret); + } + + ret = calloc(1, sizeof(nxagentScreenCrtcsSolution)); + + if (!(ret)) { + return(ret); + } + + xorg_list_init(&(ret->entry)); + + ret->all_boxes = nxagentScreenBoxesCopy(all_boxes); + + if (!(ret->all_boxes)) { + nxagentScreenCrtcsFreeSolution(ret); + + SAFE_FREE(ret); + + return(ret); + } + + ret->solution_boxes = nxagentScreenBoxesCopy(screen_boxes); + + if (!(ret->solution_boxes)) { + nxagentScreenCrtcsFreeSolution(ret); + + SAFE_FREE(ret); + + return(ret); + } + + ret->rating_size_change = ret->rating_cover_penalty = ret->rating_extended_boxes_count = 0; + ret->rating = 0.0; + + nxagentScreenCrtcsSolutionCalculateRating(ret, FALSE); + + return(ret); +} + +/* + * Helper generating a list of solutions, extending the initial screen boxes. + * + * All pointer arguments but orig_screens_init must be non-NULL. All size + * parameters must be non-zero. + * + * Returns either a pointer to the solutions list or NULL on failure. + */ +static nxagentScreenCrtcsSolutions* nxagentScreenCrtcsGenerateSolutions(const nxagentScreenBoxes *all_boxes, const nxagentScreenBoxes *initial_screens, const size_t all_boxes_count, const size_t screen_count, const Bool *orig_screens_init) { + nxagentScreenCrtcsSolutions *ret = NULL; + + /* + * We assume that the screen and all boxes count as passed in match the + * actual data. + * + * We also assume that there is at least one screen. Otherwise, generating a + * fake one here and running an expensive algorithm on this which trivially + * will cover all base boxes anyway doesn't make a lot of sense. + * Theoretically, such a situation could occur if moving the nxagent window + * completely out of any screen bounds. This could potentially also happen if + * the window is initialized on a screen, which is later disconnected. + * Normally X11 window managers should take care of this situation and move + * the window to a connected screen again, but that doesn't happen on Windows + * for instance. This makes such windows inaccessible and would lead to an + * empty initial screens list. + */ + if ((!(all_boxes)) || (!(initial_screens)) || (!(all_boxes_count)) || (!(screen_count))) { + return(ret); + } + + /* Check that initial_screens and all_boxes are not empty. */ + /* FIXME: xorg_list_is_empty is not const-correct. */ + if ((xorg_list_is_empty((struct xorg_list *)(&(initial_screens->head)))) || (xorg_list_is_empty((struct xorg_list *)(&(all_boxes->head))))) { +#ifdef WARNING + fprintf(stderr, "%s: initial_screens or all_boxes empty, assuming error and returning NULL.\n", __func__); +#endif + + return(ret); + } + + Bool err = FALSE; + size_t obsolete_boxes_count = nxagentScreenBoxesObsoleteCount(all_boxes, &err); + + if (err) { + return(ret); + } + +#ifdef DEBUG + { + const unsigned long long obsolete_boxes_count_ = obsolete_boxes_count; + fprintf(stderr, "%s: calculated initial obsolete boxes count: %llu\n", __func__, obsolete_boxes_count_); + } +#endif + + /* + * orig_screens_init as passed-in to the function (if non-NULL) will serve as + * the base initialization of the array. + * Each function execution is reponsible for freeing the memory at the end - + * not callees. + */ + Bool *screens_init = calloc(screen_count, sizeof(Bool)); + + if (!(screens_init)) { + return(ret); + } + + if (orig_screens_init) { + memmove(screens_init, orig_screens_init, (screen_count * sizeof(*screens_init))); + } + + /* + * Let work_screens and work_all_boxes point to initial_screens and all_boxes + * respectively. + */ + nxagentScreenBoxes *work_screens = nxagentScreenBoxesCopy(initial_screens); + + if (!(work_screens)) { + SAFE_FREE(screens_init); + + return(ret); + } + + nxagentScreenBoxes *work_all_boxes = nxagentScreenBoxesCopy(all_boxes); + + if (!(work_all_boxes)) { + nxagentFreeScreenBoxes(work_screens, TRUE); + + SAFE_FREE(work_screens); + + SAFE_FREE(screens_init); + + return(ret); + } + + ret = calloc(1, sizeof(nxagentScreenCrtcsSolutions)); + + if (!(ret)) { + nxagentFreeScreenBoxes(work_screens, TRUE); + nxagentFreeScreenBoxes(work_all_boxes, TRUE); + + SAFE_FREE(work_screens); + SAFE_FREE(work_all_boxes); + + SAFE_FREE(screens_init); + + return(ret); + } + + xorg_list_init(ret); + + Bool init = TRUE; + nxagentScreenCrtcsSolution *my_solution = NULL; + while (obsolete_boxes_count < all_boxes_count) { + ssize_t screen_to_init = -1; + + nxagentScreenCrtcsSolutions **extended_screens = nxagentScreenCrtcsGeneratePotentialSolutionArray(work_all_boxes, work_screens, screen_count); + + if (!(extended_screens)) { + nxagentScreenCrtcsFreeSolutions(ret); + + nxagentScreenCrtcsFreeSolution(my_solution); + + nxagentFreeScreenBoxes(work_screens, TRUE); + nxagentFreeScreenBoxes(work_all_boxes, TRUE); + + SAFE_FREE(ret); + + SAFE_FREE(my_solution); + + SAFE_FREE(work_screens); + SAFE_FREE(work_all_boxes); + + SAFE_FREE(screens_init); + + return(ret); + } + + init = FALSE; + + /* If one screen wasn't extended yet, init should be true. Sync state. */ + for (size_t i = 0; i < screen_count; ++i) { + init |= (!(screens_init[i])); + } + + nxagentScreenCrtcsSolutions **best_screen_solutions = NULL; + Bool *screen_selection = NULL; + + /* + * Could work without an explicit cast, but C doesn't implement a more + * complicated implicit cast rule while C++ does. + */ + Bool filter = nxagentScreenCrtcsFilterScreenSolutions((const nxagentScreenCrtcsSolutions * const *)(extended_screens), screen_count, init, screens_init, &best_screen_solutions, &screen_selection); + + /* + * Clean up extended_screens. We don't need it any longer. + * Do this before error handling, since it will need to be free'd in any + * case. + */ + for (size_t i = 0; i < screen_count; ++i) { + nxagentScreenCrtcsFreeSolutions(extended_screens[i]); + + SAFE_FREE(extended_screens[i]); + } + + SAFE_FREE(extended_screens); + + if (!(filter)) { + for (size_t i = 0; i < screen_count; ++i) { + nxagentScreenCrtcsFreeSolutions(best_screen_solutions[i]); + + SAFE_FREE(best_screen_solutions[i]); + } + + nxagentScreenCrtcsFreeSolutions(ret); + + nxagentScreenCrtcsFreeSolution(my_solution); + + nxagentFreeScreenBoxes(work_screens, TRUE); + nxagentFreeScreenBoxes(work_all_boxes, TRUE); + + SAFE_FREE(best_screen_solutions); + + SAFE_FREE(ret); + + SAFE_FREE(my_solution); + + SAFE_FREE(work_screens); + SAFE_FREE(work_all_boxes); + + SAFE_FREE(screens_init); + SAFE_FREE(screen_selection); + + return(ret); + } + + Bool solution_handling = nxagentScreenCrtcsHandleSolutions(work_all_boxes, work_screens, init, screens_init, screen_count, all_boxes_count, screen_selection, ret, &screen_to_init, best_screen_solutions, &my_solution); + + /* Unconditionally get rid of best_screen_solutions. */ + for (size_t i = 0; i < screen_count; ++i) { + nxagentScreenCrtcsFreeSolutions(best_screen_solutions[i]); + + SAFE_FREE(best_screen_solutions[i]); + } + + SAFE_FREE(best_screen_solutions); + + /* And screen_selection. */ + SAFE_FREE(screen_selection); + + if (!(solution_handling)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to handle screen boxes in current run.\n", __func__); +#endif + + nxagentScreenCrtcsFreeSolutions(ret); + + nxagentScreenCrtcsFreeSolution(my_solution); + + nxagentFreeScreenBoxes(work_screens, TRUE); + nxagentFreeScreenBoxes(work_all_boxes, TRUE); + + SAFE_FREE(ret); + + SAFE_FREE(my_solution); + + SAFE_FREE(work_screens); + SAFE_FREE(work_all_boxes); + + SAFE_FREE(screens_init); + + return(ret); + } + + /* + * This is actually the right place to change these variables. For more + * information, refer to comments in the other functions. + */ + Bool update_data = nxagentScreenCrtcsGenerateSolutionsUpdateInternalData(my_solution->all_boxes, my_solution->solution_boxes, screen_to_init, &work_all_boxes, &work_screens, screens_init); + + if (!(update_data)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to update internal data in current run.\n", __func__); +#endif + + nxagentScreenCrtcsFreeSolutions(ret); + + nxagentScreenCrtcsFreeSolution(my_solution); + + nxagentFreeScreenBoxes(work_screens, TRUE); + nxagentFreeScreenBoxes(work_all_boxes, TRUE); + + SAFE_FREE(ret); + + SAFE_FREE(my_solution); + + SAFE_FREE(work_screens); + SAFE_FREE(work_all_boxes); + + SAFE_FREE(screens_init); + + return(ret); + } + + obsolete_boxes_count = nxagentScreenBoxesObsoleteCount(work_all_boxes, &err); + + if (err) { +#ifdef WARNING + fprintf(stderr, "%s: unable to update obsolete base boxes.\n", __func__); +#endif + + nxagentScreenCrtcsFreeSolutions(ret); + + nxagentScreenCrtcsFreeSolution(my_solution); + + nxagentFreeScreenBoxes(work_screens, TRUE); + nxagentFreeScreenBoxes(work_all_boxes, TRUE); + + SAFE_FREE(ret); + + SAFE_FREE(my_solution); + + SAFE_FREE(work_screens); + SAFE_FREE(work_all_boxes); + + SAFE_FREE(screens_init); + + return(ret); + } + +#ifdef DEBUG + { + const unsigned long long obsolete_boxes_count_ = obsolete_boxes_count; + fprintf(stderr, "%s: recalculated obsolete boxes count: %llu\n", __func__, obsolete_boxes_count_); + } +#endif + } + + /* Unconditional cleanup. */ + SAFE_FREE(screens_init); + + /* + * Having no solution means that we didn't have to generate one, i.e., that + * the original screen boxes were all extended in the first place. + * + * In such a case, copy the input data and recalculate the rating with size + * changes set to zero. + */ + if (!(my_solution)) { + my_solution = nxagentScreenCrtcsGenerateFakeSolution(work_all_boxes, work_screens); + } + + /* Cleanup. */ + nxagentFreeScreenBoxes(work_screens, TRUE); + nxagentFreeScreenBoxes(work_all_boxes, TRUE); + + SAFE_FREE(work_screens); + SAFE_FREE(work_all_boxes); + + if (!(my_solution)) { +#ifdef WARNING + fprintf(stderr, "%s: unable to generate \"fake\" solution.\n", __func__); +#endif + + nxagentScreenCrtcsFreeSolutions(ret); + + SAFE_FREE(ret); + + return(ret); + } + + /* + * Reaching this point means that we've extended everything to cover all + * non-obsoleted base boxes. + * + * my_solution isn't part of ret yet, so add it. + */ + xorg_list_append(&(my_solution->entry), ret); + + /* + * At the end of this function, we should only have fully extended solutions + * (i.e., no partial ones). + * Due to that, extracing the best solution(s) should work fine and leave out + * solutions that are not interesting to us. + */ + nxagentScreenCrtcsSolutions *best_ret = nxagentScreenCrtcsExtractBestSolutions(ret); + + /* Get rid of old solutions list. */ + nxagentScreenCrtcsFreeSolutions(ret); + + SAFE_FREE(ret); + + ret = best_ret; + + + return(ret); +} + +/* Destroy an output after removing it from any crtc that might reference it */ void nxagentDropOutput(RROutputPtr o) { -- Alioth's /home/x2go-admin/maintenancescripts/git/hooks/post-receive-email on /srv/git/code.x2go.org/nx-libs.git