vreg.cpp@ 44596

Last change on this file since 44596 was 44596, checked in by vboxsync, 12 years ago
GuestHost/OpenGL: warning (false positive)
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 33.5 KB

Line
1	/* $Id: vreg.cpp 44596 2013-02-08 10:32:22Z vboxsync $ */
2
3	/** @file
4	* Visible Regions processing API implementation
5	*/
6
7	/*
8	* Copyright (C) 2012 Oracle Corporation
9	*
10	* This file is part of VirtualBox Open Source Edition (OSE), as
11	* available from http://www.virtualbox.org. This file is free software;
12	* you can redistribute it and/or modify it under the terms of the GNU
13	* General Public License (GPL) as published by the Free Software
14	* Foundation, in version 2 as it comes in the "COPYING" file of the
15	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
16	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
17	*/
18	#include <cr_vreg.h>
19	#include <iprt/memcache.h>
20	#include <iprt/err.h>
21	#include <iprt/assert.h>
22
23	#ifndef IN_RING0
24	#include <cr_error.h>
25	#define WARN(_m) do { crWarning _m ; } while (0)
26	#else
27	# error port me!
28	#endif
29
30	typedef struct VBOXVR_REG
31	{
32	RTLISTNODE ListEntry;
33	RTRECT Rect;
34	} VBOXVR_REG, *PVBOXVR_REG;
35
36	#define PVBOXVR_REG_FROM_ENTRY(_pEntry) ((PVBOXVR_REG)(((uint8_t*)(_pEntry)) - RT_OFFSETOF(VBOXVR_REG, ListEntry)))
37
38	#ifdef DEBUG_misha
39	//# define VBOXVDBG_VR_LAL_DISABLE
40	#endif
41
42	#ifndef VBOXVDBG_VR_LAL_DISABLE
43	static RTMEMCACHE g_VBoxVrLookasideList;
44	#endif
45
46	static PVBOXVR_REG vboxVrRegCreate()
47	{
48	#ifndef VBOXVDBG_VR_LAL_DISABLE
49	PVBOXVR_REG pReg = (PVBOXVR_REG)RTMemCacheAlloc(g_VBoxVrLookasideList);
50	if (!pReg)
51	{
52	WARN(("ExAllocateFromLookasideListEx failed!"));
53	}
54	return pReg;
55	#else
56	return (PVBOXVR_REG)RTMemAlloc(sizeof (VBOXVR_REG));
57	#endif
58	}
59
60	static void vboxVrRegTerm(PVBOXVR_REG pReg)
61	{
62	#ifndef VBOXVDBG_VR_LAL_DISABLE
63	RTMemCacheFree(g_VBoxVrLookasideList, pReg);
64	#else
65	RTMemFree(pReg);
66	#endif
67	}
68
69	VBOXVREGDECL(void) VBoxVrListClear(PVBOXVR_LIST pList)
70	{
71	PVBOXVR_REG pReg, pRegNext;
72
73	RTListForEachSafe(&pList->ListHead, pReg, pRegNext, VBOXVR_REG, ListEntry)
74	{
75	vboxVrRegTerm(pReg);
76	}
77	VBoxVrListInit(pList);
78	}
79
80	#define VBOXVR_MEMTAG 'vDBV'
81
82	VBOXVREGDECL(int) VBoxVrInit()
83	{
84	#ifndef VBOXVDBG_VR_LAL_DISABLE
85	int rc = RTMemCacheCreate(&g_VBoxVrLookasideList, sizeof (VBOXVR_REG),
86	0, /* size_t cbAlignment */
87	UINT32_MAX, /* uint32_t cMaxObjects */
88	NULL, /* PFNMEMCACHECTOR pfnCtor*/
89	NULL, /* PFNMEMCACHEDTOR pfnDtor*/
90	NULL, /* void pvUser/
91	0 /* uint32_t fFlags*/
92	);
93	if (!RT_SUCCESS(rc))
94	{
95	WARN(("ExInitializeLookasideListEx failed, rc (%d)", rc));
96	return rc;
97	}
98	#endif
99
100	return VINF_SUCCESS;
101	}
102
103	VBOXVREGDECL(void) VBoxVrTerm()
104	{
105	#ifndef VBOXVDBG_VR_LAL_DISABLE
106	RTMemCacheDestroy(g_VBoxVrLookasideList);
107	#endif
108	}
109
110	typedef DECLCALLBACK(int) FNVBOXVR_CB_COMPARATOR(const PVBOXVR_REG pReg1, const PVBOXVR_REG pReg2);
111	typedef FNVBOXVR_CB_COMPARATOR *PFNVBOXVR_CB_COMPARATOR;
112
113	static DECLCALLBACK(int) vboxVrRegNonintersectedComparator(const RTRECT* pRect1, const RTRECT* pRect2)
114	{
115	Assert(!VBoxRectIsIntersect(pRect1, pRect2));
116	if (pRect1->yTop != pRect2->yTop)
117	return pRect1->yTop - pRect2->yTop;
118	return pRect1->xLeft - pRect2->xLeft;
119	}
120
121	#ifdef DEBUG_misha
122	static void vboxVrDbgListDoVerify(PVBOXVR_LIST pList)
123	{
124	PVBOXVR_REG pReg1, pReg2;
125	RTListForEach(&pList->ListHead, pReg1, VBOXVR_REG, ListEntry)
126	{
127	for (RTLISTNODE *pEntry2 = pReg1->ListEntry.pNext; pEntry2 != &pList->ListHead; pEntry2 = pEntry2->pNext)
128	{
129	pReg2 = PVBOXVR_REG_FROM_ENTRY(pEntry2);
130	Assert(vboxVrRegNonintersectedComparator(&pReg1->Rect, &pReg2->Rect) < 0);
131	}
132	}
133	}
134
135	#define vboxVrDbgListVerify vboxVrDbgListDoVerify
136	#else
137	#define vboxVrDbgListVerify(_p) do {} while (0)
138	#endif
139
140	static int vboxVrListUniteIntersection(PVBOXVR_LIST pList, PVBOXVR_LIST pIntersection);
141
142	#define VBOXVR_INVALID_COORD (~0U)
143
144	DECLINLINE(void) vboxVrListRegAdd(PVBOXVR_LIST pList, PVBOXVR_REG pReg, PRTLISTNODE pPlace, bool fAfter)
145	{
146	if (fAfter)
147	RTListPrepend(pPlace, &pReg->ListEntry);
148	else
149	RTListAppend(pPlace, &pReg->ListEntry);
150	++pList->cEntries;
151	vboxVrDbgListVerify(pList);
152	}
153
154	DECLINLINE(void) vboxVrListRegRemove(PVBOXVR_LIST pList, PVBOXVR_REG pReg)
155	{
156	RTListNodeRemove(&pReg->ListEntry);
157	--pList->cEntries;
158	}
159
160	static void vboxVrListRegAddOrder(PVBOXVR_LIST pList, PRTLISTNODE pMemberEntry, PVBOXVR_REG pReg)
161	{
162	do
163	{
164	if (pMemberEntry != &pList->ListHead)
165	{
166	PVBOXVR_REG pMemberReg = PVBOXVR_REG_FROM_ENTRY(pMemberEntry);
167	if (vboxVrRegNonintersectedComparator(&pMemberReg->Rect, &pReg->Rect) < 0)
168	{
169	pMemberEntry = pMemberEntry->pNext;
170	continue;
171	}
172	}
173	vboxVrListRegAdd(pList, pReg, pMemberEntry, false);
174	break;
175	} while (1);
176	}
177
178	static void vboxVrListAddNonintersected(PVBOXVR_LIST pList1, PVBOXVR_LIST pList2)
179	{
180	PRTLISTNODE pEntry1 = pList1->ListHead.pNext;
181
182	for (PRTLISTNODE pEntry2 = pList2->ListHead.pNext; pEntry2 != &pList2->ListHead; pEntry2 = pList2->ListHead.pNext)
183	{
184	PVBOXVR_REG pReg2 = PVBOXVR_REG_FROM_ENTRY(pEntry2);
185	do {
186	if (pEntry1 != &pList1->ListHead)
187	{
188	PVBOXVR_REG pReg1 = PVBOXVR_REG_FROM_ENTRY(pEntry1);
189	if (vboxVrRegNonintersectedComparator(&pReg1->Rect, &pReg2->Rect) < 0)
190	{
191	pEntry1 = pEntry1->pNext;
192	continue;
193	}
194	}
195	vboxVrListRegRemove(pList2, pReg2);
196	vboxVrListRegAdd(pList1, pReg2, pEntry1, false);
197	break;
198	} while (1);
199	}
200
201	Assert(VBoxVrListIsEmpty(pList2));
202	}
203
204	static int vboxVrListRegIntersectSubstNoJoin(PVBOXVR_LIST pList1, PVBOXVR_REG pReg1, const RTRECT * pRect2)
205	{
206	uint32_t topLim = VBOXVR_INVALID_COORD;
207	uint32_t bottomLim = VBOXVR_INVALID_COORD;
208	RTLISTNODE List;
209	PVBOXVR_REG pBottomReg = NULL;
210	#ifdef DEBUG_misha
211	RTRECT tmpRect = pReg1->Rect;
212	vboxVrDbgListVerify(pList1);
213	#endif
214
215	RTListInit(&List);
216
217	Assert(VBoxRectIsIntersect(&pReg1->Rect, pRect2));
218
219	if (pReg1->Rect.yTop < pRect2->yTop)
220	{
221	Assert(pRect2->yTop < pReg1->Rect.yBottom);
222	PVBOXVR_REG pRegResult = vboxVrRegCreate();
223	pRegResult->Rect.yTop = pReg1->Rect.yTop;
224	pRegResult->Rect.xLeft = pReg1->Rect.xLeft;
225	pRegResult->Rect.yBottom = pRect2->yTop;
226	pRegResult->Rect.xRight = pReg1->Rect.xRight;
227	topLim = pRect2->yTop;
228	RTListAppend(&List, &pRegResult->ListEntry);
229	}
230
231	if (pReg1->Rect.yBottom > pRect2->yBottom)
232	{
233	Assert(pRect2->yBottom > pReg1->Rect.yTop);
234	PVBOXVR_REG pRegResult = vboxVrRegCreate();
235	pRegResult->Rect.yTop = pRect2->yBottom;
236	pRegResult->Rect.xLeft = pReg1->Rect.xLeft;
237	pRegResult->Rect.yBottom = pReg1->Rect.yBottom;
238	pRegResult->Rect.xRight = pReg1->Rect.xRight;
239	bottomLim = pRect2->yBottom;
240	pBottomReg = pRegResult;
241	}
242
243	if (pReg1->Rect.xLeft < pRect2->xLeft)
244	{
245	Assert(pRect2->xLeft < pReg1->Rect.xRight);
246	PVBOXVR_REG pRegResult = vboxVrRegCreate();
247	pRegResult->Rect.yTop = topLim == VBOXVR_INVALID_COORD ? pReg1->Rect.yTop : topLim;
248	pRegResult->Rect.xLeft = pReg1->Rect.xLeft;
249	pRegResult->Rect.yBottom = bottomLim == VBOXVR_INVALID_COORD ? pReg1->Rect.yBottom : bottomLim;
250	pRegResult->Rect.xRight = pRect2->xLeft;
251	RTListAppend(&List, &pRegResult->ListEntry);
252	}
253
254	if (pReg1->Rect.xRight > pRect2->xRight)
255	{
256	Assert(pRect2->xRight > pReg1->Rect.xLeft);
257	PVBOXVR_REG pRegResult = vboxVrRegCreate();
258	pRegResult->Rect.yTop = topLim == VBOXVR_INVALID_COORD ? pReg1->Rect.yTop : topLim;
259	pRegResult->Rect.xLeft = pRect2->xRight;
260	pRegResult->Rect.yBottom = bottomLim == VBOXVR_INVALID_COORD ? pReg1->Rect.yBottom : bottomLim;
261	pRegResult->Rect.xRight = pReg1->Rect.xRight;
262	RTListAppend(&List, &pRegResult->ListEntry);
263	}
264
265	if (pBottomReg)
266	RTListAppend(&List, &pBottomReg->ListEntry);
267
268	PRTLISTNODE pMemberEntry = pReg1->ListEntry.pNext;
269	vboxVrListRegRemove(pList1, pReg1);
270	vboxVrRegTerm(pReg1);
271
272	if (RTListIsEmpty(&List))
273	return VINF_SUCCESS; /* the region is covered by the pRect2 */
274
275	PRTLISTNODE pEntry = List.pNext, pNext;
276	for (; pEntry != &List; pEntry = pNext)
277	{
278	pNext = pEntry->pNext;
279	PVBOXVR_REG pReg = PVBOXVR_REG_FROM_ENTRY(pEntry);
280
281	vboxVrListRegAddOrder(pList1, pMemberEntry, pReg);
282	pMemberEntry = pEntry->pNext; /* the following elements should go after the given pEntry since they are ordered already */
283	}
284	return VINF_SUCCESS;
285	}
286
287	typedef DECLCALLBACK(PRTLISTNODE) FNVBOXVR_CB_INTERSECTED_VISITOR(PVBOXVR_LIST pList1, PVBOXVR_REG pReg1, const RTRECT * pRect2, void pvContext, PRTLISTNODE ppNext);
288	typedef FNVBOXVR_CB_INTERSECTED_VISITOR *PFNVBOXVR_CB_INTERSECTED_VISITOR;
289
290	static void vboxVrListVisitIntersected(PVBOXVR_LIST pList1, uint32_t cRects, const RTRECT aRects, PFNVBOXVR_CB_INTERSECTED_VISITOR pfnVisitor, void pvVisitor)
291	{
292	PRTLISTNODE pEntry1 = pList1->ListHead.pNext;
293	PRTLISTNODE pNext1;
294	uint32_t iFirst2 = 0;
295
296	for (; pEntry1 != &pList1->ListHead; pEntry1 = pNext1)
297	{
298	pNext1 = pEntry1->pNext;
299	PVBOXVR_REG pReg1 = PVBOXVR_REG_FROM_ENTRY(pEntry1);
300	for (uint32_t i = iFirst2; i < cRects; ++i)
301	{
302	const RTRECT *pRect2 = &aRects[i];
303	if (pReg1->Rect.yBottom <= pRect2->yTop)
304	continue;
305	else if (pRect2->yBottom <= pReg1->Rect.yTop)
306	continue;
307	/* y coords intersect */
308	else if (pReg1->Rect.xRight <= pRect2->xLeft)
309	continue;
310	else if (pRect2->xRight <= pReg1->Rect.xLeft)
311	continue;
312	/* x coords intersect */
313
314	/* the visitor can modify the list 1, apply necessary adjustments after it */
315	PRTLISTNODE pEntry1 = pfnVisitor (pList1, pReg1, pRect2, pvVisitor, &pNext1);
316	if (pEntry1 == &pList1->ListHead)
317	break;
318	}
319	}
320	}
321
322
323	static void vboxVrListJoinRectsHV(PVBOXVR_LIST pList, bool fHorizontal)
324	{
325	PRTLISTNODE pNext1, pNext2;
326
327	for (PRTLISTNODE pEntry1 = pList->ListHead.pNext; pEntry1 != &pList->ListHead; pEntry1 = pNext1)
328	{
329	PVBOXVR_REG pReg1 = PVBOXVR_REG_FROM_ENTRY(pEntry1);
330	pNext1 = pEntry1->pNext;
331	for (PRTLISTNODE pEntry2 = pEntry1->pNext; pEntry2 != &pList->ListHead; pEntry2 = pNext2)
332	{
333	PVBOXVR_REG pReg2 = PVBOXVR_REG_FROM_ENTRY(pEntry2);
334	pNext2 = pEntry2->pNext;
335	if (fHorizontal)
336	{
337	if (pReg1->Rect.yTop == pReg2->Rect.yTop)
338	{
339	if (pReg1->Rect.xRight == pReg2->Rect.xLeft)
340	{
341	/* join rectangles */
342	vboxVrListRegRemove(pList, pReg2);
343	if (pReg1->Rect.yBottom > pReg2->Rect.yBottom)
344	{
345	int32_t oldRight1 = pReg1->Rect.xRight;
346	int32_t oldBottom1 = pReg1->Rect.yBottom;
347	pReg1->Rect.xRight = pReg2->Rect.xRight;
348	pReg1->Rect.yBottom = pReg2->Rect.yBottom;
349
350	vboxVrDbgListVerify(pList);
351
352	pReg2->Rect.xLeft = pReg1->Rect.xLeft;
353	pReg2->Rect.yTop = pReg1->Rect.yBottom;
354	pReg2->Rect.xRight = oldRight1;
355	pReg2->Rect.yBottom = oldBottom1;
356	vboxVrListRegAddOrder(pList, pReg1->ListEntry.pNext, pReg2);
357	/* restart the pNext1 & pNext2 since regs are splitted into smaller ones in y dimension
358	* and thus can match one of the previous rects */
359	pNext1 = pList->ListHead.pNext;
360	break;
361	}
362	else if (pReg1->Rect.yBottom < pReg2->Rect.yBottom)
363	{
364	pReg1->Rect.xRight = pReg2->Rect.xRight;
365	vboxVrDbgListVerify(pList);
366	pReg2->Rect.yTop = pReg1->Rect.yBottom;
367	vboxVrListRegAddOrder(pList, pReg1->ListEntry.pNext, pReg2);
368	/* restart the pNext1 & pNext2 since regs are splitted into smaller ones in y dimension
369	* and thus can match one of the previous rects */
370	pNext1 = pList->ListHead.pNext;
371	break;
372	}
373	else
374	{
375	pReg1->Rect.xRight = pReg2->Rect.xRight;
376	vboxVrDbgListVerify(pList);
377	/* reset the pNext1 since it could be the pReg2 being destroyed */
378	pNext1 = pEntry1->pNext;
379	/* pNext2 stays the same since it is pReg2->ListEntry.pNext, which is kept intact */
380	vboxVrRegTerm(pReg2);
381	}
382	}
383	continue;
384	}
385	else if (pReg1->Rect.yBottom == pReg2->Rect.yBottom)
386	{
387	Assert(pReg1->Rect.yTop < pReg2->Rect.yTop); /* <- since pReg1 > pReg2 && pReg1->Rect.yTop != pReg2->Rect.yTop*/
388	if (pReg1->Rect.xRight == pReg2->Rect.xLeft)
389	{
390	/* join rectangles */
391	vboxVrListRegRemove(pList, pReg2);
392
393	pReg1->Rect.yBottom = pReg2->Rect.yTop;
394	vboxVrDbgListVerify(pList);
395	pReg2->Rect.xLeft = pReg1->Rect.xLeft;
396
397	vboxVrListRegAddOrder(pList, pReg2->ListEntry.pNext, pReg2);
398
399	/* restart the pNext1 & pNext2 since regs are splitted into smaller ones in y dimension
400	* and thus can match one of the previous rects */
401	pNext1 = pList->ListHead.pNext;
402	break;
403	}
404	else if (pReg1->Rect.xLeft == pReg2->Rect.xRight)
405	{
406	/* join rectangles */
407	vboxVrListRegRemove(pList, pReg2);
408
409	pReg1->Rect.yBottom = pReg2->Rect.yTop;
410	vboxVrDbgListVerify(pList);
411	pReg2->Rect.xRight = pReg1->Rect.xRight;
412
413	vboxVrListRegAddOrder(pList, pReg2->ListEntry.pNext, pReg2);
414
415	/* restart the pNext1 & pNext2 since regs are splitted into smaller ones in y dimension
416	* and thus can match one of the previous rects */
417	pNext1 = pList->ListHead.pNext;
418	break;
419	}
420	continue;
421	}
422	}
423	else
424	{
425	if (pReg1->Rect.yBottom == pReg2->Rect.yTop)
426	{
427	if (pReg1->Rect.xLeft == pReg2->Rect.xLeft)
428	{
429	if (pReg1->Rect.xRight == pReg2->Rect.xRight)
430	{
431	/* join rects */
432	vboxVrListRegRemove(pList, pReg2);
433
434	pReg1->Rect.yBottom = pReg2->Rect.yBottom;
435	vboxVrDbgListVerify(pList);
436
437	/* reset the pNext1 since it could be the pReg2 being destroyed */
438	pNext1 = pEntry1->pNext;
439	/* pNext2 stays the same since it is pReg2->ListEntry.pNext, which is kept intact */
440	vboxVrRegTerm(pReg2);
441	continue;
442	}
443	/* no more to be done for for pReg1 */
444	break;
445	}
446	else if (pReg1->Rect.xRight > pReg2->Rect.xLeft)
447	{
448	/* no more to be done for for pReg1 */
449	break;
450	}
451
452	continue;
453	}
454	else if (pReg1->Rect.yBottom < pReg2->Rect.yTop)
455	{
456	/* no more to be done for for pReg1 */
457	break;
458	}
459	}
460	}
461	}
462	}
463
464	static void vboxVrListJoinRects(PVBOXVR_LIST pList)
465	{
466	vboxVrListJoinRectsHV(pList, true);
467	vboxVrListJoinRectsHV(pList, false);
468	}
469
470	typedef struct VBOXVR_CBDATA_SUBST
471	{
472	int rc;
473	bool fChanged;
474	} VBOXVR_CBDATA_SUBST, *PVBOXVR_CBDATA_SUBST;
475
476	static DECLCALLBACK(PRTLISTNODE) vboxVrListSubstNoJoinCb(PVBOXVR_LIST pList, PVBOXVR_REG pReg1, const RTRECT pRect2, void pvContext, PRTLISTNODE *ppNext)
477	{
478	PVBOXVR_CBDATA_SUBST pData = (PVBOXVR_CBDATA_SUBST)pvContext;
479	/* store the prev to get the new pNext out of it*/
480	PRTLISTNODE pPrev = pReg1->ListEntry.pPrev;
481	pData->fChanged = true;
482
483	Assert(VBoxRectIsIntersect(&pReg1->Rect, pRect2));
484
485	/* NOTE: the pReg1 will be invalid after the vboxVrListRegIntersectSubstNoJoin call!!! */
486	int rc = vboxVrListRegIntersectSubstNoJoin(pList, pReg1, pRect2);
487	if (RT_SUCCESS(rc))
488	{
489	*ppNext = pPrev->pNext;
490	return &pList->ListHead;
491	}
492	WARN(("vboxVrListRegIntersectSubstNoJoin failed!"));
493	Assert(!RT_SUCCESS(rc));
494	pData->rc = rc;
495	*ppNext = &pList->ListHead;
496	return &pList->ListHead;
497	}
498
499	static int vboxVrListSubstNoJoin(PVBOXVR_LIST pList, uint32_t cRects, const RTRECT * aRects, bool *pfChanged)
500	{
501	if (VBoxVrListIsEmpty(pList))
502	return VINF_SUCCESS;
503
504	VBOXVR_CBDATA_SUBST Data;
505	Data.rc = VINF_SUCCESS;
506	Data.fChanged = false;
507
508	*pfChanged = false;
509
510	vboxVrListVisitIntersected(pList, cRects, aRects, vboxVrListSubstNoJoinCb, &Data);
511	if (!RT_SUCCESS(Data.rc))
512	{
513	WARN(("vboxVrListVisitIntersected failed!"));
514	return Data.rc;
515	}
516
517	*pfChanged = Data.fChanged;
518	return VINF_SUCCESS;
519	}
520
521	#if 0
522	static const RTRECT * vboxVrRectsOrder(uint32_t cRects, const RTRECT * aRects)
523	{
524	#ifdef DEBUG
525	{
526	for (uint32_t i = 0; i < cRects; ++i)
527	{
528	RTRECT *pRectI = &aRects[i];
529	for (uint32_t j = i + 1; j < cRects; ++j)
530	{
531	RTRECT *pRectJ = &aRects[j];
532	Assert(!VBoxRectIsIntersect(pRectI, pRectJ));
533	}
534	}
535	}
536	#endif
537
538	RTRECT * pRects = (RTRECT *)aRects;
539	/* check if rects are ordered already */
540	for (uint32_t i = 0; i < cRects - 1; ++i)
541	{
542	RTRECT *pRect1 = &pRects[i];
543	RTRECT *pRect2 = &pRects[i+1];
544	if (vboxVrRegNonintersectedComparator(pRect1, pRect2) < 0)
545	continue;
546
547	WARN(("rects are unoreded!"));
548
549	if (pRects == aRects)
550	{
551	pRects = (RTRECT )RTMemAlloc(sizeof (RTRECT) cRects);
552	if (!pRects)
553	{
554	WARN(("RTMemAlloc failed!"));
555	return NULL;
556	}
557
558	memcpy(pRects, aRects, sizeof (RTRECT) * cRects);
559	}
560
561	Assert(pRects != aRects);
562
563	int j = (int)i - 1;
564	do {
565	RTRECT Tmp = *pRect1;
566	pRect1 = pRect2;
567	*pRect2 = Tmp;
568
569	if (j < 0)
570	break;
571
572	if (vboxVrRegNonintersectedComparator(pRect1, pRect1-1) > 0)
573	break;
574
575	pRect2 = pRect1--;
576	--j;
577	} while (1);
578	}
579
580	return pRects;
581	}
582	#endif
583
584	VBOXVREGDECL(void) VBoxVrListTranslate(PVBOXVR_LIST pList, int32_t x, int32_t y)
585	{
586	for (PRTLISTNODE pEntry1 = pList->ListHead.pNext; pEntry1 != &pList->ListHead; pEntry1 = pEntry1->pNext)
587	{
588	PVBOXVR_REG pReg1 = PVBOXVR_REG_FROM_ENTRY(pEntry1);
589	VBoxRectTranslate(&pReg1->Rect, x, y);
590	}
591	}
592
593	VBOXVREGDECL(int) VBoxVrListRectsSubst(PVBOXVR_LIST pList, uint32_t cRects, const RTRECT * aRects, bool *pfChanged)
594	{
595	#if 0
596	const RTRECT * pRects = vboxVrRectsOrder(cRects, aRects);
597	if (!pRects)
598	{
599	WARN(("vboxVrRectsOrder failed!"));
600	return VERR_NO_MEMORY;
601	}
602	#endif
603
604	int rc = vboxVrListSubstNoJoin(pList, cRects, aRects, pfChanged);
605	if (!RT_SUCCESS(rc))
606	{
607	WARN(("vboxVrListSubstNoJoin failed!"));
608	goto done;
609	}
610
611	if (!*pfChanged)
612	goto done;
613
614	vboxVrListJoinRects(pList);
615
616	done:
617	#if 0
618	if (pRects != aRects)
619	RTMemFree(pRects);
620	#endif
621	return rc;
622	}
623
624	VBOXVREGDECL(int) VBoxVrListRectsAdd(PVBOXVR_LIST pList, uint32_t cRects, const RTRECT * aRects, bool *pfChanged)
625	{
626	uint32_t cCovered = 0;
627
628	#if 0
629	#ifdef DEBUG
630	{
631	for (uint32_t i = 0; i < cRects; ++i)
632	{
633	RTRECT *pRectI = &aRects[i];
634	for (uint32_t j = i + 1; j < cRects; ++j)
635	{
636	RTRECT *pRectJ = &aRects[j];
637	Assert(!VBoxRectIsIntersect(pRectI, pRectJ));
638	}
639	}
640	}
641	#endif
642	#endif
643
644	/* early sort out the case when there are no new rects */
645	for (uint32_t i = 0; i < cRects; ++i)
646	{
647	for (PRTLISTNODE pEntry1 = pList->ListHead.pNext; pEntry1 != &pList->ListHead; pEntry1 = pEntry1->pNext)
648	{
649	PVBOXVR_REG pReg1 = PVBOXVR_REG_FROM_ENTRY(pEntry1);
650	if (VBoxRectIsCoveres(&pReg1->Rect, &aRects[i]))
651	{
652	cCovered++;
653	break;
654	}
655	}
656	}
657
658	if (cCovered == cRects)
659	{
660	*pfChanged = false;
661	return VINF_SUCCESS;
662	}
663
664	/* rects are not covered, need to go the slow way */
665
666	VBOXVR_LIST DiffList;
667	VBoxVrListInit(&DiffList);
668	RTRECT * pListRects = NULL;
669	uint32_t cAllocatedRects = 0;
670	bool fNeedRectreate = true;
671	bool fChanged = false;
672	int rc = VINF_SUCCESS;
673
674	for (uint32_t i = 0; i < cRects; ++i)
675	{
676	PVBOXVR_REG pReg = vboxVrRegCreate();
677	if (!pReg)
678	{
679	WARN(("vboxVrRegCreate failed!"));
680	rc = VERR_NO_MEMORY;
681	break;
682	}
683	pReg->Rect = aRects[i];
684
685	uint32_t cListRects = VBoxVrListRectsCount(pList);
686	if (!cListRects)
687	{
688	vboxVrListRegAdd(pList, pReg, &pList->ListHead, false);
689	fChanged = true;
690	continue;
691	}
692	else
693	{
694	Assert(VBoxVrListIsEmpty(&DiffList));
695	vboxVrListRegAdd(&DiffList, pReg, &DiffList.ListHead, false);
696	}
697
698	if (cAllocatedRects < cListRects)
699	{
700	cAllocatedRects = cListRects + cRects;
701	Assert(fNeedRectreate);
702	if (pListRects)
703	RTMemFree(pListRects);
704	pListRects = (RTRECT )RTMemAlloc(sizeof (RTRECT) cAllocatedRects);
705	if (!pListRects)
706	{
707	WARN(("RTMemAlloc failed!"));
708	rc = VERR_NO_MEMORY;
709	break;
710	}
711	}
712
713
714	if (fNeedRectreate)
715	{
716	rc = VBoxVrListRectsGet(pList, cListRects, pListRects);
717	Assert(rc == VINF_SUCCESS);
718	fNeedRectreate = false;
719	}
720
721	bool fDummyChanged = false;
722	rc = vboxVrListSubstNoJoin(&DiffList, cListRects, pListRects, &fDummyChanged);
723	if (!RT_SUCCESS(rc))
724	{
725	WARN(("vboxVrListSubstNoJoin failed!"));
726	rc = VERR_NO_MEMORY;
727	break;
728	}
729
730	if (!VBoxVrListIsEmpty(&DiffList))
731	{
732	vboxVrListAddNonintersected(pList, &DiffList);
733	fNeedRectreate = true;
734	fChanged = true;
735	}
736
737	Assert(VBoxVrListIsEmpty(&DiffList));
738	}
739
740	if (pListRects)
741	RTMemFree(pListRects);
742
743	Assert(VBoxVrListIsEmpty(&DiffList) \|\| rc != VINF_SUCCESS);
744	VBoxVrListClear(&DiffList);
745
746	if (fChanged)
747	vboxVrListJoinRects(pList);
748
749	*pfChanged = fChanged;
750
751	return VINF_SUCCESS;
752	}
753
754	VBOXVREGDECL(int) VBoxVrListRectsGet(PVBOXVR_LIST pList, uint32_t cRects, RTRECT * aRects)
755	{
756	if (cRects < VBoxVrListRectsCount(pList))
757	return VERR_BUFFER_OVERFLOW;
758
759	uint32_t i = 0;
760	for (PRTLISTNODE pEntry1 = pList->ListHead.pNext; pEntry1 != &pList->ListHead; pEntry1 = pEntry1->pNext, ++i)
761	{
762	PVBOXVR_REG pReg1 = PVBOXVR_REG_FROM_ENTRY(pEntry1);
763	aRects[i] = pReg1->Rect;
764	}
765	return VINF_SUCCESS;
766	}
767
768	VBOXVREGDECL(int) VBoxVrListCmp(PVBOXVR_LIST pList1, PVBOXVR_LIST pList2)
769	{
770	int cTmp = pList1->cEntries - pList2->cEntries;
771	if (cTmp)
772	return cTmp;
773
774	PVBOXVR_REG pReg1, pReg2;
775
776	for (pReg1 = RTListNodeGetNext(&pList1->ListHead, VBOXVR_REG, ListEntry),
777	pReg2 = RTListNodeGetNext(&pList2->ListHead, VBOXVR_REG, ListEntry);
778	!RTListNodeIsDummy(&pList1->ListHead, pReg1, VBOXVR_REG, ListEntry);
779	pReg1 = RT_FROM_MEMBER(pReg1->ListEntry.pNext, VBOXVR_REG, ListEntry),
780	pReg2 = RT_FROM_MEMBER(pReg2->ListEntry.pNext, VBOXVR_REG, ListEntry))
781	{
782	Assert(!RTListNodeIsDummy(&pList2->ListHead, pReg2, VBOXVR_REG, ListEntry));
783	cTmp = VBoxRectCmp(&pReg1->Rect, &pReg2->Rect);
784	if (cTmp)
785	return cTmp;
786	}
787	Assert(RTListNodeIsDummy(&pList2->ListHead, pReg2, VBOXVR_REG, ListEntry));
788	return 0;
789	}
790
791	VBOXVREGDECL(void) VBoxVrCompositorInit(PVBOXVR_COMPOSITOR pCompositor, PFNVBOXVRCOMPOSITOR_ENTRY_REMOVED pfnEntryRemoved)
792	{
793	RTListInit(&pCompositor->List);
794	pCompositor->pfnEntryRemoved = pfnEntryRemoved;
795	}
796
797	VBOXVREGDECL(void) VBoxVrCompositorTerm(PVBOXVR_COMPOSITOR pCompositor)
798	{
799	PVBOXVR_COMPOSITOR_ENTRY pEntry, pEntryNext;
800	RTListForEachSafe(&pCompositor->List, pEntry, pEntryNext, VBOXVR_COMPOSITOR_ENTRY, Node);
801	{
802	VBoxVrCompositorEntryRemove(pCompositor, pEntry);
803	}
804	}
805
806	DECLINLINE(void) vboxVrCompositorEntryAdd(PVBOXVR_COMPOSITOR pCompositor, PVBOXVR_COMPOSITOR_ENTRY pEntry)
807	{
808	RTListPrepend(&pCompositor->List, &pEntry->Node);
809	}
810
811	DECLINLINE(void) vboxVrCompositorEntryRemove(PVBOXVR_COMPOSITOR pCompositor, PVBOXVR_COMPOSITOR_ENTRY pEntry, PVBOXVR_COMPOSITOR_ENTRY pReplacingEntry)
812	{
813	RTListNodeRemove(&pEntry->Node);
814	if (pCompositor->pfnEntryRemoved)
815	pCompositor->pfnEntryRemoved(pCompositor, pEntry, pReplacingEntry);
816	}
817
818	VBOXVREGDECL(void) VBoxVrCompositorEntryInit(PVBOXVR_COMPOSITOR_ENTRY pEntry)
819	{
820	VBoxVrListInit(&pEntry->Vr);
821	}
822
823	VBOXVREGDECL(bool) VBoxVrCompositorEntryRemove(PVBOXVR_COMPOSITOR pCompositor, PVBOXVR_COMPOSITOR_ENTRY pEntry)
824	{
825	if (!VBoxVrCompositorEntryIsInList(pEntry))
826	return false;
827	VBoxVrListClear(&pEntry->Vr);
828	vboxVrCompositorEntryRemove(pCompositor, pEntry, NULL);
829	return true;
830	}
831
832	static int vboxVrCompositorEntryRegionsSubst(PVBOXVR_COMPOSITOR pCompositor, PVBOXVR_COMPOSITOR_ENTRY pEntry, uint32_t cRects, const RTRECT * paRects, bool *pfChanged)
833	{
834	bool fChanged;
835	int rc = VBoxVrListRectsSubst(&pEntry->Vr, cRects, paRects, &fChanged);
836	if (RT_SUCCESS(rc))
837	{
838	if (VBoxVrListIsEmpty(&pEntry->Vr))
839	{
840	Assert(fChanged);
841	vboxVrCompositorEntryRemove(pCompositor, pEntry, NULL);
842	}
843	if (pfChanged)
844	*pfChanged = false;
845	return VINF_SUCCESS;
846	}
847
848	WARN(("VBoxVrListRectsSubst failed, rc %d", rc));
849	return rc;
850	}
851
852	VBOXVREGDECL(int) VBoxVrCompositorEntryRegionsAdd(PVBOXVR_COMPOSITOR pCompositor, PVBOXVR_COMPOSITOR_ENTRY pEntry, uint32_t cRects, const RTRECT paRects, uint32_t pfChangeFlags)
853	{
854	bool fOthersChanged = false, fCurChanged = false, fEntryChanged = false, fEntryInList = false, fEntryReplaces = false;
855	PVBOXVR_COMPOSITOR_ENTRY pCur;
856	int rc = VINF_SUCCESS;
857
858	if (!cRects)
859	{
860	if (pfChangeFlags)
861	*pfChangeFlags = 0;
862	return VINF_SUCCESS;
863	}
864
865	if (pEntry)
866	{
867	fEntryInList = VBoxVrCompositorEntryIsInList(pEntry);
868	rc = VBoxVrListRectsAdd(&pEntry->Vr, cRects, paRects, &fEntryChanged);
869	if (RT_SUCCESS(rc))
870	{
871	if (VBoxVrListIsEmpty(&pEntry->Vr))
872	{
873	WARN(("Empty rectangles passed in, is it expected?"));
874	if (pfChangeFlags)
875	*pfChangeFlags = 0;
876	return VINF_SUCCESS;
877	}
878	}
879	else
880	{
881	WARN(("VBoxVrListRectsAdd failed, rc %d", rc));
882	return rc;
883	}
884
885	Assert(!VBoxVrListIsEmpty(&pEntry->Vr));
886	}
887
888	RTListForEach(&pCompositor->List, pCur, VBOXVR_COMPOSITOR_ENTRY, Node)
889	{
890	Assert(!VBoxVrListIsEmpty(&pCur->Vr));
891	if (pCur == pEntry)
892	{
893	Assert(fEntryInList);
894	}
895	else
896	{
897	if (pEntry && !VBoxVrListCmp(&pCur->Vr, &pEntry->Vr))
898	{
899	VBoxVrListClear(&pCur->Vr);
900	vboxVrCompositorEntryRemove(pCompositor, pCur, pEntry);
901	fEntryReplaces = true;
902	}
903	else
904	{
905	rc = vboxVrCompositorEntryRegionsSubst(pCompositor, pCur, cRects, paRects, &fCurChanged);
906	if (RT_SUCCESS(rc))
907	fOthersChanged \|= fCurChanged;
908	else
909	{
910	WARN(("vboxVrCompositorEntryRegionsSubst failed, rc %d", rc));
911	return rc;
912	}
913	}
914	}
915	}
916
917	AssertRC(rc);
918
919	if (pEntry && !fEntryInList)
920	{
921	Assert(!VBoxVrListIsEmpty(&pEntry->Vr));
922	vboxVrCompositorEntryAdd(pCompositor, pEntry);
923	}
924
925	if (pfChangeFlags)
926	{
927	uint32_t fFlags = 0;
928	if (fOthersChanged)
929	fFlags = VBOXVR_COMPOSITOR_CF_ENTRIES_REGIONS_CHANGED \| VBOXVR_COMPOSITOR_CF_COMPOSITED_REGIONS_CHANGED;
930	else if (fEntryReplaces)
931	{
932	Assert(fEntryChanged);
933	fFlags = VBOXVR_COMPOSITOR_CF_ENTRIES_REGIONS_CHANGED;
934	}
935	else if (fEntryChanged)
936	fFlags = VBOXVR_COMPOSITOR_CF_ENTRIES_REGIONS_CHANGED \| VBOXVR_COMPOSITOR_CF_COMPOSITED_REGIONS_CHANGED;
937
938	*pfChangeFlags = fFlags;
939	}
940
941	return VINF_SUCCESS;
942	}
943
944	VBOXVREGDECL(int) VBoxVrCompositorEntryRegionsSubst(PVBOXVR_COMPOSITOR pCompositor, PVBOXVR_COMPOSITOR_ENTRY pEntry, uint32_t cRects, const RTRECT * paRects, bool *pfChanged)
945	{
946	if (!pEntry)
947	{
948	WARN(("VBoxVrCompositorEntryRegionsSubst called with zero entry, unsupported!"));
949	if (pfChanged)
950	*pfChanged = false;
951	return VERR_INVALID_PARAMETER;
952	}
953
954	if (VBoxVrListIsEmpty(&pEntry->Vr))
955	{
956	if (pfChanged)
957	*pfChanged = false;
958	return VINF_SUCCESS;
959
960	}
961
962	int rc = vboxVrCompositorEntryRegionsSubst(pCompositor, pEntry, cRects, paRects, pfChanged);
963	if (RT_SUCCESS(rc))
964	return VINF_SUCCESS;
965
966	WARN(("pfChanged failed, rc %d", rc));
967	return rc;
968	}
969
970	VBOXVREGDECL(int) VBoxVrCompositorEntryRegionsSet(PVBOXVR_COMPOSITOR pCompositor, PVBOXVR_COMPOSITOR_ENTRY pEntry, uint32_t cRects, const RTRECT paRects, bool pfChanged)
971	{
972	if (!pEntry)
973	{
974	WARN(("VBoxVrCompositorEntryRegionsSet called with zero entry, unsupported!"));
975	if (pfChanged)
976	*pfChanged = false;
977	return VERR_INVALID_PARAMETER;
978	}
979
980	bool fChanged = false, fCurChanged = false;
981	uint32_t fChangeFlags = 0;
982	int rc;
983	fCurChanged = VBoxVrCompositorEntryRemove(pCompositor, pEntry);
984	fChanged \|= fCurChanged;
985
986	rc = VBoxVrCompositorEntryRegionsAdd(pCompositor, pEntry, cRects, paRects, &fChangeFlags);
987	if (RT_SUCCESS(rc))
988	fChanged \|= !!fChangeFlags;
989	else
990	{
991	WARN(("VBoxVrCompositorEntryRegionsAdd failed, rc %d", rc));
992	return rc;
993	}
994
995	AssertRC(rc);
996
997	if (pfChanged)
998	*pfChanged = fChanged;
999	return VINF_SUCCESS;
1000	}
1001
1002	VBOXVREGDECL(int) VBoxVrCompositorEntryRegionsTranslate(PVBOXVR_COMPOSITOR pCompositor, PVBOXVR_COMPOSITOR_ENTRY pEntry, int32_t x, int32_t y, bool *pfChanged)
1003	{
1004	if (!pEntry)
1005	{
1006	WARN(("VBoxVrCompositorEntryRegionsTranslate called with zero entry, unsupported!"));
1007	if (pfChanged)
1008	*pfChanged = false;
1009	return VERR_INVALID_PARAMETER;
1010	}
1011
1012	if ((!x && !y)
1013	\|\| !VBoxVrCompositorEntryIsInList(pEntry))
1014	{
1015	if (pfChanged)
1016	*pfChanged = false;
1017	return VINF_SUCCESS;
1018	}
1019
1020	VBoxVrListTranslate(&pEntry->Vr, x, y);
1021
1022	Assert(!VBoxVrListIsEmpty(&pEntry->Vr));
1023
1024	PVBOXVR_COMPOSITOR_ENTRY pCur;
1025	uint32_t cRects = 0;
1026	RTRECT *paRects = NULL;
1027	int rc = VINF_SUCCESS;
1028	RTListForEach(&pCompositor->List, pCur, VBOXVR_COMPOSITOR_ENTRY, Node)
1029	{
1030	Assert(!VBoxVrListIsEmpty(&pCur->Vr));
1031
1032	if (pCur == pEntry)
1033	continue;
1034
1035	if (!paRects)
1036	{
1037	cRects = VBoxVrListRectsCount(&pEntry->Vr);
1038	Assert(cRects);
1039	paRects = (RTRECT)RTMemAlloc(cRects sizeof (RTRECT));
1040	if (!paRects)
1041	{
1042	WARN(("RTMemAlloc failed!"));
1043	rc = VERR_NO_MEMORY;
1044	break;
1045	}
1046
1047	rc = VBoxVrListRectsGet(&pEntry->Vr, cRects, paRects);
1048	if (!RT_SUCCESS(rc))
1049	{
1050	WARN(("VBoxVrListRectsGet failed! rc %d", rc));
1051	break;
1052	}
1053	}
1054
1055	rc = vboxVrCompositorEntryRegionsSubst(pCompositor, pCur, cRects, paRects, NULL);
1056	if (!RT_SUCCESS(rc))
1057	{
1058	WARN(("vboxVrCompositorEntryRegionsSubst failed! rc %d", rc));
1059	break;
1060	}
1061	}
1062
1063	if (pfChanged)
1064	*pfChanged = true;
1065
1066	if (paRects)
1067	RTMemFree(paRects);
1068
1069	return rc;
1070	}
1071
1072	VBOXVREGDECL(void) VBoxVrCompositorVisit(PVBOXVR_COMPOSITOR pCompositor, PFNVBOXVRCOMPOSITOR_VISITOR pfnVisitor, void *pvVisitor)
1073	{
1074	PVBOXVR_COMPOSITOR_ENTRY pEntry, pEntryNext;
1075	RTListForEachSafe(&pCompositor->List, pEntry, pEntryNext, VBOXVR_COMPOSITOR_ENTRY, Node);
1076	{
1077	if (!pfnVisitor(pCompositor, pEntry, pvVisitor))
1078	return;
1079	}
1080	}

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/VBox/GuestHost/OpenGL/util/vreg.cpp@ 44596

Download in other formats: