1
2/*
3 * Copyright (c) 1998-2001 by The XFree86 Project, Inc.
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice shall be included in
13 * all copies or substantial portions of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
18 * THE COPYRIGHT HOLDER(S) OR AUTHOR(S) BE LIABLE FOR ANY CLAIM, DAMAGES OR
19 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
20 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
21 * OTHER DEALINGS IN THE SOFTWARE.
22 *
23 * Except as contained in this notice, the name of the copyright holder(s)
24 * and author(s) shall not be used in advertising or otherwise to promote
25 * the sale, use or other dealings in this Software without prior written
26 * authorization from the copyright holder(s) and author(s).
27 */
28
29#ifdef HAVE_XORG_CONFIG_H
30#include <xorg-config.h>
31#endif
32
33#include "misc.h"
34#include "xf86.h"
35
36#include <X11/X.h>
37#include "scrnintstr.h"
38#include "regionstr.h"
39#include "xf86fbman.h"
40
41/*
42#define DEBUG
43*/
44
45static DevPrivateKeyRec xf86FBManagerKeyRec;
46static DevPrivateKey xf86FBManagerKey;
47
48Bool xf86RegisterOffscreenManager(
49    ScreenPtr pScreen,
50    FBManagerFuncsPtr funcs
51){
52
53   xf86FBManagerKey = &xf86FBManagerKeyRec;
54
55   if (!dixRegisterPrivateKey(&xf86FBManagerKeyRec, PRIVATE_SCREEN, 0))
56       return FALSE;
57
58   dixSetPrivate(&pScreen->devPrivates, xf86FBManagerKey, funcs);
59
60   return TRUE;
61}
62
63
64Bool
65xf86FBManagerRunning(ScreenPtr pScreen)
66{
67    if (xf86FBManagerKey == NULL)
68	return FALSE;
69
70    if(!dixLookupPrivate(&pScreen->devPrivates, xf86FBManagerKey))
71	return FALSE;
72
73    return TRUE;
74}
75
76Bool
77xf86RegisterFreeBoxCallback(
78    ScreenPtr pScreen,
79    FreeBoxCallbackProcPtr FreeBoxCallback,
80    pointer devPriv
81){
82   FBManagerFuncsPtr funcs;
83
84   if(xf86FBManagerKey == NULL)
85	return FALSE;
86   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(&pScreen->devPrivates,
87						    xf86FBManagerKey)))
88	return FALSE;
89
90   return (*funcs->RegisterFreeBoxCallback)(pScreen, FreeBoxCallback, devPriv);
91}
92
93
94FBAreaPtr
95xf86AllocateOffscreenArea(
96   ScreenPtr pScreen,
97   int w, int h,
98   int gran,
99   MoveAreaCallbackProcPtr moveCB,
100   RemoveAreaCallbackProcPtr removeCB,
101   pointer privData
102){
103   FBManagerFuncsPtr funcs;
104
105   if(xf86FBManagerKey == NULL)
106	return NULL;
107   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(&pScreen->devPrivates,
108						    xf86FBManagerKey)))
109	return NULL;
110
111   return (*funcs->AllocateOffscreenArea)(
112		pScreen, w, h, gran, moveCB, removeCB, privData);
113}
114
115
116FBLinearPtr
117xf86AllocateOffscreenLinear(
118    ScreenPtr pScreen,
119    int length,
120    int gran,
121    MoveLinearCallbackProcPtr moveCB,
122    RemoveLinearCallbackProcPtr removeCB,
123    pointer privData
124){
125   FBManagerFuncsPtr funcs;
126
127   if(xf86FBManagerKey == NULL)
128	return NULL;
129   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(&pScreen->devPrivates,
130						    xf86FBManagerKey)))
131	return NULL;
132
133   return (*funcs->AllocateOffscreenLinear)(
134		pScreen, length, gran, moveCB, removeCB, privData);
135}
136
137
138void
139xf86FreeOffscreenArea(FBAreaPtr area)
140{
141   FBManagerFuncsPtr funcs;
142
143   if(!area) return;
144
145   if(xf86FBManagerKey == NULL)
146	return;
147   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(
148	    &area->pScreen->devPrivates, xf86FBManagerKey)))
149	return;
150
151   (*funcs->FreeOffscreenArea)(area);
152
153   return;
154}
155
156
157void
158xf86FreeOffscreenLinear(FBLinearPtr linear)
159{
160   FBManagerFuncsPtr funcs;
161
162   if(!linear) return;
163
164   if(xf86FBManagerKey == NULL)
165	return;
166   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(
167	    &linear->pScreen->devPrivates, xf86FBManagerKey)))
168	return;
169
170   (*funcs->FreeOffscreenLinear)(linear);
171
172   return;
173}
174
175
176Bool
177xf86ResizeOffscreenArea(
178   FBAreaPtr resize,
179   int w, int h
180){
181   FBManagerFuncsPtr funcs;
182
183   if(!resize) return FALSE;
184
185   if(xf86FBManagerKey == NULL)
186	return FALSE;
187   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(
188	    &resize->pScreen->devPrivates, xf86FBManagerKey)))
189	return FALSE;
190
191   return (*funcs->ResizeOffscreenArea)(resize, w, h);
192}
193
194Bool
195xf86ResizeOffscreenLinear(
196   FBLinearPtr resize,
197   int size
198){
199   FBManagerFuncsPtr funcs;
200
201   if(!resize) return FALSE;
202
203   if(xf86FBManagerKey == NULL)
204	return FALSE;
205   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(
206	    &resize->pScreen->devPrivates, xf86FBManagerKey)))
207	return FALSE;
208
209   return (*funcs->ResizeOffscreenLinear)(resize, size);
210}
211
212
213Bool
214xf86QueryLargestOffscreenArea(
215    ScreenPtr pScreen,
216    int *w, int *h,
217    int gran,
218    int preferences,
219    int severity
220){
221   FBManagerFuncsPtr funcs;
222
223   *w = 0;
224   *h = 0;
225
226   if(xf86FBManagerKey == NULL)
227	return FALSE;
228   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(&pScreen->devPrivates,
229						    xf86FBManagerKey)))
230	return FALSE;
231
232   return (*funcs->QueryLargestOffscreenArea)(
233		pScreen, w, h, gran, preferences, severity);
234}
235
236Bool
237xf86QueryLargestOffscreenLinear(
238    ScreenPtr pScreen,
239    int *size,
240    int gran,
241    int severity
242){
243   FBManagerFuncsPtr funcs;
244
245   *size = 0;
246
247   if(xf86FBManagerKey == NULL)
248	return FALSE;
249   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(&pScreen->devPrivates,
250						    xf86FBManagerKey)))
251	return FALSE;
252
253   return (*funcs->QueryLargestOffscreenLinear)(
254		pScreen, size, gran, severity);
255}
256
257
258Bool
259xf86PurgeUnlockedOffscreenAreas(ScreenPtr pScreen)
260{
261   FBManagerFuncsPtr funcs;
262
263   if(xf86FBManagerKey == NULL)
264	return FALSE;
265   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(&pScreen->devPrivates,
266						    xf86FBManagerKey)))
267	return FALSE;
268
269   return (*funcs->PurgeOffscreenAreas)(pScreen);
270}
271
272/************************************************************\
273
274   Below is a specific implementation of an offscreen manager.
275
276\************************************************************/
277
278static DevPrivateKeyRec xf86FBScreenKeyRec;
279#define xf86FBScreenKey (&xf86FBScreenKeyRec)
280
281typedef struct _FBLink {
282  FBArea area;
283  struct _FBLink *next;
284} FBLink, *FBLinkPtr;
285
286typedef struct _FBLinearLink {
287  FBLinear linear;
288  int free;	/* need to add free here as FBLinear is publicly accessible */
289  FBAreaPtr area;	/* only used if allocation came from XY area */
290  struct _FBLinearLink *next;
291} FBLinearLink, *FBLinearLinkPtr;
292
293
294typedef struct {
295   ScreenPtr    		pScreen;
296   RegionPtr    		InitialBoxes;
297   RegionPtr    		FreeBoxes;
298   FBLinkPtr    		UsedAreas;
299   int          		NumUsedAreas;
300   FBLinearLinkPtr              LinearAreas;
301   CloseScreenProcPtr           CloseScreen;
302   int                          NumCallbacks;
303   FreeBoxCallbackProcPtr       *FreeBoxesUpdateCallback;
304   DevUnion                     *devPrivates;
305} FBManager, *FBManagerPtr;
306
307
308static void
309SendCallFreeBoxCallbacks(FBManagerPtr offman)
310{
311   int i = offman->NumCallbacks;
312
313   while(i--) {
314	(*offman->FreeBoxesUpdateCallback[i])(
315	   offman->pScreen, offman->FreeBoxes, offman->devPrivates[i].ptr);
316   }
317}
318
319static Bool
320localRegisterFreeBoxCallback(
321    ScreenPtr pScreen,
322    FreeBoxCallbackProcPtr FreeBoxCallback,
323    pointer devPriv
324){
325   FBManagerPtr offman;
326   FreeBoxCallbackProcPtr *newCallbacks;
327   DevUnion *newPrivates;
328
329   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
330					   xf86FBScreenKey);
331   newCallbacks = realloc( offman->FreeBoxesUpdateCallback,
332		sizeof(FreeBoxCallbackProcPtr) * (offman->NumCallbacks + 1));
333
334   newPrivates = realloc(offman->devPrivates,
335			  sizeof(DevUnion) * (offman->NumCallbacks + 1));
336
337   if(!newCallbacks || !newPrivates)
338	return FALSE;
339
340   offman->FreeBoxesUpdateCallback = newCallbacks;
341   offman->devPrivates = newPrivates;
342
343   offman->FreeBoxesUpdateCallback[offman->NumCallbacks] = FreeBoxCallback;
344   offman->devPrivates[offman->NumCallbacks].ptr = devPriv;
345   offman->NumCallbacks++;
346
347   SendCallFreeBoxCallbacks(offman);
348
349   return TRUE;
350}
351
352
353static FBAreaPtr
354AllocateArea(
355   FBManagerPtr offman,
356   int w, int h,
357   int granularity,
358   MoveAreaCallbackProcPtr moveCB,
359   RemoveAreaCallbackProcPtr removeCB,
360   pointer privData
361){
362   ScreenPtr pScreen = offman->pScreen;
363   FBLinkPtr link = NULL;
364   FBAreaPtr area = NULL;
365   RegionRec NewReg;
366   int i, x = 0, num;
367   BoxPtr boxp;
368
369   if(granularity <= 1) granularity = 0;
370
371   boxp = RegionRects(offman->FreeBoxes);
372   num = RegionNumRects(offman->FreeBoxes);
373
374   /* look through the free boxes */
375   for(i = 0; i < num; i++, boxp++) {
376	x = boxp->x1;
377	if (granularity > 1)
378	    x = ((x + granularity - 1) / granularity) * granularity;
379
380	if(((boxp->y2 - boxp->y1) < h) || ((boxp->x2 - x) < w))
381	   continue;
382
383	link = malloc(sizeof(FBLink));
384	if(!link) return NULL;
385
386        area = &(link->area);
387        link->next = offman->UsedAreas;
388        offman->UsedAreas = link;
389        offman->NumUsedAreas++;
390	break;
391   }
392
393   /* try to boot a removeable one out if we are not expendable ourselves */
394   if(!area && !removeCB) {
395	link = offman->UsedAreas;
396
397	while(link) {
398	   if(!link->area.RemoveAreaCallback) {
399		link = link->next;
400		continue;
401	   }
402
403	   boxp = &(link->area.box);
404	   x = boxp->x1;
405 	   if (granularity > 1)
406		x = ((x + granularity - 1) / granularity) * granularity;
407
408	   if(((boxp->y2 - boxp->y1) < h) || ((boxp->x2 - x) < w)) {
409		link = link->next;
410		continue;
411	   }
412
413	   /* bye, bye */
414	   (*link->area.RemoveAreaCallback)(&link->area);
415	   RegionInit(&NewReg, &(link->area.box), 1);
416	   RegionUnion(offman->FreeBoxes, offman->FreeBoxes, &NewReg);
417	   RegionUninit(&NewReg);
418
419           area = &(link->area);
420	   break;
421	}
422   }
423
424   if(area) {
425	area->pScreen = pScreen;
426	area->granularity = granularity;
427	area->box.x1 = x;
428	area->box.x2 = x + w;
429	area->box.y1 = boxp->y1;
430	area->box.y2 = boxp->y1 + h;
431	area->MoveAreaCallback = moveCB;
432	area->RemoveAreaCallback = removeCB;
433	area->devPrivate.ptr = privData;
434
435        RegionInit(&NewReg, &(area->box), 1);
436	RegionSubtract(offman->FreeBoxes, offman->FreeBoxes, &NewReg);
437	RegionUninit(&NewReg);
438   }
439
440   return area;
441}
442
443static FBAreaPtr
444localAllocateOffscreenArea(
445   ScreenPtr pScreen,
446   int w, int h,
447   int gran,
448   MoveAreaCallbackProcPtr moveCB,
449   RemoveAreaCallbackProcPtr removeCB,
450   pointer privData
451){
452   FBManagerPtr offman;
453   FBAreaPtr area = NULL;
454
455   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
456					   xf86FBScreenKey);
457   if((area = AllocateArea(offman, w, h, gran, moveCB, removeCB, privData)))
458	SendCallFreeBoxCallbacks(offman);
459
460   return area;
461}
462
463
464static void
465localFreeOffscreenArea(FBAreaPtr area)
466{
467   FBManagerPtr offman;
468   FBLinkPtr pLink, pLinkPrev = NULL;
469   RegionRec FreedRegion;
470   ScreenPtr pScreen;
471
472   pScreen = area->pScreen;
473   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
474					   xf86FBScreenKey);
475   pLink = offman->UsedAreas;
476   if(!pLink) return;
477
478   while(&(pLink->area) != area) {
479	pLinkPrev = pLink;
480	pLink = pLink->next;
481	if(!pLink) return;
482   }
483
484   /* put the area back into the pool */
485   RegionInit(&FreedRegion, &(pLink->area.box), 1);
486   RegionUnion(offman->FreeBoxes, offman->FreeBoxes, &FreedRegion);
487   RegionUninit(&FreedRegion);
488
489   if(pLinkPrev)
490	pLinkPrev->next = pLink->next;
491   else offman->UsedAreas = pLink->next;
492
493   free(pLink);
494   offman->NumUsedAreas--;
495
496   SendCallFreeBoxCallbacks(offman);
497}
498
499
500
501static Bool
502localResizeOffscreenArea(
503   FBAreaPtr resize,
504   int w, int h
505){
506   FBManagerPtr offman;
507   ScreenPtr pScreen;
508   BoxRec OrigArea;
509   RegionRec FreedReg;
510   FBAreaPtr area = NULL;
511   FBLinkPtr pLink, newLink, pLinkPrev = NULL;
512
513   pScreen = resize->pScreen;
514   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
515					   xf86FBScreenKey);
516   /* find this link */
517   if(!(pLink = offman->UsedAreas))
518	return FALSE;
519
520   while(&(pLink->area) != resize) {
521	pLinkPrev = pLink;
522	pLink = pLink->next;
523	if(!pLink) return FALSE;
524   }
525
526   OrigArea.x1 = resize->box.x1;
527   OrigArea.x2 = resize->box.x2;
528   OrigArea.y1 = resize->box.y1;
529   OrigArea.y2 = resize->box.y2;
530
531   /* if it's smaller, this is easy */
532
533   if((w <= (resize->box.x2 - resize->box.x1)) &&
534      (h <= (resize->box.y2 - resize->box.y1))) {
535	RegionRec NewReg;
536
537	resize->box.x2 = resize->box.x1 + w;
538	resize->box.y2 = resize->box.y1 + h;
539
540        if((resize->box.y2 == OrigArea.y2) &&
541	   (resize->box.x2 == OrigArea.x2))
542		return TRUE;
543
544	RegionInit(&FreedReg, &OrigArea, 1);
545	RegionInit(&NewReg, &(resize->box), 1);
546	RegionSubtract(&FreedReg, &FreedReg, &NewReg);
547	RegionUnion(offman->FreeBoxes, offman->FreeBoxes, &FreedReg);
548	RegionUninit(&FreedReg);
549	RegionUninit(&NewReg);
550
551	SendCallFreeBoxCallbacks(offman);
552
553	return TRUE;
554   }
555
556
557   /* otherwise we remove the old region */
558
559   RegionInit(&FreedReg, &OrigArea, 1);
560   RegionUnion(offman->FreeBoxes, offman->FreeBoxes, &FreedReg);
561
562   /* remove the old link */
563   if(pLinkPrev)
564	pLinkPrev->next = pLink->next;
565   else offman->UsedAreas = pLink->next;
566
567   /* and try to add a new one */
568
569   if((area = AllocateArea(offman, w, h, resize->granularity,
570		resize->MoveAreaCallback, resize->RemoveAreaCallback,
571		resize->devPrivate.ptr))) {
572
573        /* copy data over to our link and replace the new with old */
574	memcpy(resize, area, sizeof(FBArea));
575
576        pLinkPrev = NULL;
577 	newLink = offman->UsedAreas;
578
579        while(&(newLink->area) != area) {
580	    pLinkPrev = newLink;
581	    newLink = newLink->next;
582        }
583
584	if(pLinkPrev)
585	    pLinkPrev->next = newLink->next;
586	else offman->UsedAreas = newLink->next;
587
588        pLink->next = offman->UsedAreas;
589        offman->UsedAreas = pLink;
590
591	free(newLink);
592
593	/* AllocateArea added one but we really only exchanged one */
594	offman->NumUsedAreas--;
595   } else {
596      /* reinstate the old region */
597      RegionSubtract(offman->FreeBoxes, offman->FreeBoxes, &FreedReg);
598      RegionUninit(&FreedReg);
599
600      pLink->next = offman->UsedAreas;
601      offman->UsedAreas = pLink;
602      return FALSE;
603   }
604
605
606   RegionUninit(&FreedReg);
607
608   SendCallFreeBoxCallbacks(offman);
609
610   return TRUE;
611}
612
613static Bool
614localQueryLargestOffscreenArea(
615    ScreenPtr pScreen,
616    int *width, int *height,
617    int granularity,
618    int preferences,
619    int severity
620){
621    FBManagerPtr offman;
622    RegionPtr newRegion = NULL;
623    BoxPtr pbox;
624    int nbox;
625    int x, w, h, area, oldArea;
626
627    *width = *height = oldArea = 0;
628
629    if(granularity <= 1) granularity = 0;
630
631    if((preferences < 0) || (preferences > 3))
632	return FALSE;
633
634    offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
635					    xf86FBScreenKey);
636    if(severity < 0) severity = 0;
637    if(severity > 2) severity = 2;
638
639    switch(severity) {
640    case 2:
641	if(offman->NumUsedAreas) {
642	    FBLinkPtr pLink;
643	    RegionRec tmpRegion;
644	    newRegion = RegionCreate(NULL, 1);
645	    RegionCopy(newRegion, offman->InitialBoxes);
646	    pLink = offman->UsedAreas;
647
648	    while(pLink) {
649		if(!pLink->area.RemoveAreaCallback) {
650		    RegionInit(&tmpRegion, &(pLink->area.box), 1);
651		    RegionSubtract(newRegion, newRegion, &tmpRegion);
652		    RegionUninit(&tmpRegion);
653		}
654		pLink = pLink->next;
655	    }
656
657	    nbox = RegionNumRects(newRegion);
658	    pbox = RegionRects(newRegion);
659	    break;
660	}
661    case 1:
662	if(offman->NumUsedAreas) {
663	    FBLinkPtr pLink;
664	    RegionRec tmpRegion;
665	    newRegion = RegionCreate(NULL, 1);
666	    RegionCopy(newRegion, offman->FreeBoxes);
667	    pLink = offman->UsedAreas;
668
669	    while(pLink) {
670		if(pLink->area.RemoveAreaCallback) {
671		    RegionInit(&tmpRegion, &(pLink->area.box), 1);
672		    RegionAppend(newRegion, &tmpRegion);
673		    RegionUninit(&tmpRegion);
674		}
675		pLink = pLink->next;
676	    }
677
678	    nbox = RegionNumRects(newRegion);
679	    pbox = RegionRects(newRegion);
680	    break;
681	}
682    default:
683	nbox = RegionNumRects(offman->FreeBoxes);
684	pbox = RegionRects(offman->FreeBoxes);
685	break;
686    }
687
688    while(nbox--) {
689	x = pbox->x1;
690	if (granularity > 1)
691	   x = ((x + granularity - 1) / granularity) * granularity;
692
693	w = pbox->x2 - x;
694	h = pbox->y2 - pbox->y1;
695	area = w * h;
696
697	if(w > 0) {
698	    Bool gotIt = FALSE;
699	    switch(preferences) {
700	    case FAVOR_AREA_THEN_WIDTH:
701		if((area > oldArea) || ((area == oldArea) && (w > *width)))
702		    gotIt = TRUE;
703		break;
704	    case FAVOR_AREA_THEN_HEIGHT:
705		if((area > oldArea) || ((area == oldArea) && (h > *height)))
706		    gotIt = TRUE;
707		break;
708	    case FAVOR_WIDTH_THEN_AREA:
709		if((w > *width) || ((w == *width) && (area > oldArea)))
710		    gotIt = TRUE;
711		break;
712	    case FAVOR_HEIGHT_THEN_AREA:
713		if((h > *height) || ((h == *height) && (area > oldArea)))
714		    gotIt = TRUE;
715		break;
716	    }
717	    if(gotIt) {
718		*width = w;
719		*height = h;
720		oldArea = area;
721	    }
722        }
723	pbox++;
724    }
725
726    if(newRegion)
727	RegionDestroy(newRegion);
728
729    return TRUE;
730}
731
732static Bool
733localPurgeUnlockedOffscreenAreas(ScreenPtr pScreen)
734{
735   FBManagerPtr offman;
736   FBLinkPtr pLink, tmp, pPrev = NULL;
737   RegionRec FreedRegion;
738   Bool anyUsed = FALSE;
739
740   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
741					   xf86FBScreenKey);
742   pLink = offman->UsedAreas;
743   if(!pLink) return TRUE;
744
745   while(pLink) {
746	if(pLink->area.RemoveAreaCallback) {
747	    (*pLink->area.RemoveAreaCallback)(&pLink->area);
748
749	    RegionInit(&FreedRegion, &(pLink->area.box), 1);
750	    RegionAppend(offman->FreeBoxes, &FreedRegion);
751	    RegionUninit(&FreedRegion);
752
753	    if(pPrev)
754	      pPrev->next = pLink->next;
755	    else offman->UsedAreas = pLink->next;
756
757	    tmp = pLink;
758	    pLink = pLink->next;
759            free(tmp);
760	    offman->NumUsedAreas--;
761	    anyUsed = TRUE;
762	} else {
763	    pPrev = pLink;
764	    pLink = pLink->next;
765	}
766   }
767
768   if(anyUsed) {
769	RegionValidate(offman->FreeBoxes, &anyUsed);
770	SendCallFreeBoxCallbacks(offman);
771   }
772
773   return TRUE;
774}
775
776static void
777LinearMoveCBWrapper(FBAreaPtr from, FBAreaPtr to)
778{
779    /* this will never get called */
780}
781
782static void
783LinearRemoveCBWrapper(FBAreaPtr area)
784{
785   FBManagerPtr offman;
786   FBLinearLinkPtr pLink, pLinkPrev = NULL;
787   ScreenPtr pScreen = area->pScreen;
788
789   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
790					   xf86FBScreenKey);
791   pLink = offman->LinearAreas;
792   if(!pLink) return;
793
794   while(pLink->area != area) {
795        pLinkPrev = pLink;
796        pLink = pLink->next;
797        if(!pLink) return;
798   }
799
800   /* give the user the callback it is expecting */
801   (*pLink->linear.RemoveLinearCallback)(&(pLink->linear));
802
803   if(pLinkPrev)
804        pLinkPrev->next = pLink->next;
805   else offman->LinearAreas = pLink->next;
806
807   free(pLink);
808}
809
810static void
811DumpDebug(FBLinearLinkPtr pLink)
812{
813#ifdef DEBUG
814   if (!pLink) ErrorF("MMmm, PLINK IS NULL!\n");
815
816   while (pLink) {
817	 ErrorF("  Offset:%08x, Size:%08x, %s,%s\n",
818		pLink->linear.offset,
819		pLink->linear.size,
820		pLink->free ? "Free" : "Used",
821		pLink->area ? "Area" : "Linear");
822
823	 pLink = pLink->next;
824   }
825#endif
826}
827
828static FBLinearPtr
829AllocateLinear(
830   FBManagerPtr offman,
831   int size,
832   int granularity,
833   pointer privData
834){
835   ScreenPtr pScreen = offman->pScreen;
836   FBLinearLinkPtr linear = NULL;
837   FBLinearLinkPtr newlink = NULL;
838   int offset, end;
839
840   if(size <= 0) return NULL;
841
842   if (!offman->LinearAreas) return NULL;
843
844   linear = offman->LinearAreas;
845   while (linear) {
846 	/* Make sure we get a free area that's not an XY fallback case */
847      if (!linear->area && linear->free) {
848	 offset = linear->linear.offset;
849	 if (granularity > 1)
850	    offset = ((offset + granularity - 1) / granularity) * granularity;
851	 end = offset+size;
852	 if (end <= (linear->linear.offset + linear->linear.size))
853	    break;
854      }
855      linear = linear->next;
856   }
857   if (!linear)
858      return NULL;
859
860   /* break left */
861   if (offset > linear->linear.offset) {
862      newlink = malloc(sizeof(FBLinearLink));
863      if (!newlink)
864	 return NULL;
865      newlink->area = NULL;
866      newlink->linear.offset = offset;
867      newlink->linear.size = linear->linear.size - (offset - linear->linear.offset);
868      newlink->free = 1;
869      newlink->next = linear->next;
870      linear->linear.size -= newlink->linear.size;
871      linear->next = newlink;
872      linear = newlink;
873   }
874
875   /* break right */
876   if (size < linear->linear.size) {
877      newlink = malloc(sizeof(FBLinearLink));
878      if (!newlink)
879	 return NULL;
880      newlink->area = NULL;
881      newlink->linear.offset = offset + size;
882      newlink->linear.size = linear->linear.size - size;
883      newlink->free = 1;
884      newlink->next = linear->next;
885      linear->linear.size = size;
886      linear->next = newlink;
887   }
888
889   /* p = middle block */
890   linear->linear.granularity = granularity;
891   linear->free = 0;
892   linear->linear.pScreen = pScreen;
893   linear->linear.MoveLinearCallback = NULL;
894   linear->linear.RemoveLinearCallback = NULL;
895   linear->linear.devPrivate.ptr = NULL;
896
897   DumpDebug(offman->LinearAreas);
898
899   return &(linear->linear);
900}
901
902static FBLinearPtr
903localAllocateOffscreenLinear(
904    ScreenPtr pScreen,
905    int length,
906    int gran,
907    MoveLinearCallbackProcPtr moveCB,
908    RemoveLinearCallbackProcPtr removeCB,
909    pointer privData
910){
911   FBManagerPtr offman;
912   FBLinearLinkPtr link;
913   FBAreaPtr area;
914   FBLinearPtr linear = NULL;
915   BoxPtr extents;
916   int w, h, pitch;
917
918   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
919					   xf86FBScreenKey);
920
921   /* Try to allocate from linear memory first...... */
922   DebugF("ALLOCATING LINEAR\n");
923   if ((linear = AllocateLinear(offman, length, gran, privData)))
924  	return linear;
925
926   DebugF("NOPE, ALLOCATING AREA\n");
927
928   if(!(link = malloc(sizeof(FBLinearLink))))
929     return NULL;
930
931   /* No linear available, so try and pinch some from the XY areas */
932   extents = RegionExtents(offman->InitialBoxes);
933   pitch = extents->x2 - extents->x1;
934
935   if (gran > 1) {
936        if (gran > pitch) {
937            /* we can't match the specified alignment with XY allocations */
938            free(link);
939            return NULL;
940        }
941
942        if (pitch % gran) {
943            /* pitch and granularity aren't a perfect match, let's allocate
944             * a bit more so we can align later on
945             */
946            length += gran - 1;
947        }
948    }
949
950   if(length < pitch) { /* special case */
951	w = length;
952	h = 1;
953   } else {
954	w = pitch;
955	h = (length + pitch - 1) / pitch;
956   }
957
958   if((area = localAllocateOffscreenArea(pScreen, w, h, gran,
959			moveCB   ? LinearMoveCBWrapper   : NULL,
960			removeCB ? LinearRemoveCBWrapper : NULL,
961			privData)))
962   {
963	link->area = area;
964	link->free = 0;
965	link->next = offman->LinearAreas;
966	offman->LinearAreas = link;
967	linear = &(link->linear);
968	linear->pScreen = pScreen;
969	linear->size = h * w;
970	linear->offset = (pitch * area->box.y1) + area->box.x1;
971	if (gran > 1)
972            linear->offset = ((linear->offset + gran - 1) / gran) * gran;
973	linear->granularity = gran;
974	linear->MoveLinearCallback = moveCB;
975	linear->RemoveLinearCallback = removeCB;
976	linear->devPrivate.ptr = privData;
977   } else
978	free(link);
979
980   DumpDebug(offman->LinearAreas);
981
982   return linear;
983}
984
985
986static void
987localFreeOffscreenLinear(FBLinearPtr linear)
988{
989   FBManagerPtr offman;
990   FBLinearLinkPtr pLink, pLinkPrev = NULL;
991   ScreenPtr pScreen = linear->pScreen;
992
993   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
994					   xf86FBScreenKey);
995   pLink = offman->LinearAreas;
996   if(!pLink) return;
997
998   while(&(pLink->linear) != linear) {
999        pLinkPrev = pLink;
1000        pLink = pLink->next;
1001        if(!pLink) return;
1002   }
1003
1004   if(pLink->area) {  /* really an XY area */
1005	DebugF("FREEING AREA\n");
1006	localFreeOffscreenArea(pLink->area);
1007   	if(pLinkPrev)
1008	    pLinkPrev->next = pLink->next;
1009   	else offman->LinearAreas = pLink->next;
1010        free(pLink);
1011	DumpDebug(offman->LinearAreas);
1012	return;
1013   }
1014
1015   pLink->free = 1;
1016
1017   if (pLink->next && pLink->next->free) {
1018      FBLinearLinkPtr p = pLink->next;
1019      pLink->linear.size += p->linear.size;
1020      pLink->next = p->next;
1021      free(p);
1022   }
1023
1024   if(pLinkPrev) {
1025   	if (pLinkPrev->next && pLinkPrev->next->free && !pLinkPrev->area) {
1026      	    FBLinearLinkPtr p = pLinkPrev->next;
1027      	    pLinkPrev->linear.size += p->linear.size;
1028      	    pLinkPrev->next = p->next;
1029      	    free(p);
1030    	}
1031   }
1032
1033   DebugF("FREEING LINEAR\n");
1034   DumpDebug(offman->LinearAreas);
1035}
1036
1037
1038static Bool
1039localResizeOffscreenLinear(FBLinearPtr resize, int length)
1040{
1041   FBManagerPtr offman;
1042   FBLinearLinkPtr pLink;
1043   ScreenPtr pScreen = resize->pScreen;
1044
1045   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
1046					   xf86FBScreenKey);
1047   pLink = offman->LinearAreas;
1048   if(!pLink) return FALSE;
1049
1050   while(&(pLink->linear) != resize) {
1051        pLink = pLink->next;
1052        if(!pLink) return FALSE;
1053   }
1054
1055   /* This could actually be alot smarter and try to move allocations
1056      from XY to linear when available.  For now if it was XY, we keep
1057      it XY */
1058
1059   if(pLink->area) {  /* really an XY area */
1060	BoxPtr extents;
1061	int pitch, w, h;
1062
1063	extents = RegionExtents(offman->InitialBoxes);
1064	pitch = extents->x2 - extents->x1;
1065
1066	if(length < pitch) { /* special case */
1067	    w = length;
1068	    h = 1;
1069	} else {
1070	    w = pitch;
1071	    h = (length + pitch - 1) / pitch;
1072	}
1073
1074	if(localResizeOffscreenArea(pLink->area, w, h)) {
1075	    resize->size = h * w;
1076	    resize->offset = (pitch * pLink->area->box.y1) + pLink->area->box.x1;
1077	    return TRUE;
1078	}
1079   } else {
1080	/* TODO!!!! resize the linear area */
1081   }
1082
1083   return FALSE;
1084}
1085
1086
1087static Bool
1088localQueryLargestOffscreenLinear(
1089    ScreenPtr pScreen,
1090    int *size,
1091    int gran,
1092    int priority
1093)
1094{
1095    FBManagerPtr offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
1096							 xf86FBScreenKey);
1097    FBLinearLinkPtr pLink;
1098    FBLinearLinkPtr pLinkRet;
1099
1100    *size = 0;
1101
1102    pLink = offman->LinearAreas;
1103
1104    if (pLink && !pLink->area) {
1105	pLinkRet = pLink;
1106	while (pLink) {
1107	    if (pLink->free) {
1108		if (pLink->linear.size > pLinkRet->linear.size)
1109		    pLinkRet = pLink;
1110	    }
1111	    pLink = pLink->next;
1112    	}
1113
1114	if (pLinkRet->free) {
1115	    *size = pLinkRet->linear.size;
1116	    return TRUE;
1117    	}
1118    } else {
1119	int w, h;
1120
1121    	if(localQueryLargestOffscreenArea(pScreen, &w, &h, gran,
1122				FAVOR_WIDTH_THEN_AREA, priority))
1123    	{
1124	    FBManagerPtr offman;
1125	    BoxPtr extents;
1126
1127	    offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
1128						    xf86FBScreenKey);
1129	    extents = RegionExtents(offman->InitialBoxes);
1130	    if((extents->x2 - extents->x1) == w)
1131	    	*size = w * h;
1132	    return TRUE;
1133        }
1134    }
1135
1136    return FALSE;
1137}
1138
1139
1140
1141static FBManagerFuncs xf86FBManFuncs = {
1142   localAllocateOffscreenArea,
1143   localFreeOffscreenArea,
1144   localResizeOffscreenArea,
1145   localQueryLargestOffscreenArea,
1146   localRegisterFreeBoxCallback,
1147   localAllocateOffscreenLinear,
1148   localFreeOffscreenLinear,
1149   localResizeOffscreenLinear,
1150   localQueryLargestOffscreenLinear,
1151   localPurgeUnlockedOffscreenAreas
1152 };
1153
1154
1155static Bool
1156xf86FBCloseScreen (int i, ScreenPtr pScreen)
1157{
1158   FBLinkPtr pLink, tmp;
1159   FBLinearLinkPtr pLinearLink, tmp2;
1160   FBManagerPtr offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
1161							xf86FBScreenKey);
1162
1163   pScreen->CloseScreen = offman->CloseScreen;
1164
1165   pLink = offman->UsedAreas;
1166   while(pLink) {
1167	tmp = pLink;
1168	pLink = pLink->next;
1169	free(tmp);
1170   }
1171
1172   pLinearLink = offman->LinearAreas;
1173   while(pLinearLink) {
1174	tmp2 = pLinearLink;
1175	pLinearLink = pLinearLink->next;
1176	free(tmp2);
1177   }
1178
1179   RegionDestroy(offman->InitialBoxes);
1180   RegionDestroy(offman->FreeBoxes);
1181
1182   free(offman->FreeBoxesUpdateCallback);
1183   free(offman->devPrivates);
1184   free(offman);
1185   dixSetPrivate(&pScreen->devPrivates, xf86FBScreenKey, NULL);
1186
1187   return (*pScreen->CloseScreen) (i, pScreen);
1188}
1189
1190Bool
1191xf86InitFBManager(
1192    ScreenPtr pScreen,
1193    BoxPtr FullBox
1194){
1195   ScrnInfoPtr pScrn = xf86Screens[pScreen->myNum];
1196   RegionRec ScreenRegion;
1197   RegionRec FullRegion;
1198   BoxRec ScreenBox;
1199   Bool ret;
1200
1201   ScreenBox.x1 = 0;
1202   ScreenBox.y1 = 0;
1203   ScreenBox.x2 = pScrn->virtualX;
1204   ScreenBox.y2 = pScrn->virtualY;
1205
1206   if((FullBox->x1 >  ScreenBox.x1) || (FullBox->y1 >  ScreenBox.y1) ||
1207      (FullBox->x2 <  ScreenBox.x2) || (FullBox->y2 <  ScreenBox.y2)) {
1208	return FALSE;
1209   }
1210
1211   if (FullBox->y2 < FullBox->y1) return FALSE;
1212   if (FullBox->x2 < FullBox->x1) return FALSE;
1213
1214   RegionInit(&ScreenRegion, &ScreenBox, 1);
1215   RegionInit(&FullRegion, FullBox, 1);
1216
1217   RegionSubtract(&FullRegion, &FullRegion, &ScreenRegion);
1218
1219   ret = xf86InitFBManagerRegion(pScreen, &FullRegion);
1220
1221   RegionUninit(&ScreenRegion);
1222   RegionUninit(&FullRegion);
1223
1224   return ret;
1225}
1226
1227Bool
1228xf86InitFBManagerArea(
1229    ScreenPtr pScreen,
1230    int PixelArea,
1231    int Verbosity
1232)
1233{
1234    ScrnInfoPtr pScrn = xf86Screens[pScreen->myNum];
1235    xRectangle Rect[3];
1236    RegionPtr pRegion, pScreenRegion;
1237    int nRect;
1238    Bool ret = FALSE;
1239
1240    if (PixelArea < (pScrn->displayWidth * pScrn->virtualY))
1241	return FALSE;
1242
1243    Rect[0].x = Rect[0].y = 0;
1244    Rect[0].width = pScrn->displayWidth;
1245    Rect[0].height = PixelArea / pScrn->displayWidth;
1246    nRect = 1;
1247
1248    /* Add a possible partial scanline */
1249    if ((Rect[1].height = Rect[1].width = PixelArea % pScrn->displayWidth)) {
1250	Rect[1].x = 0;
1251	Rect[1].y = Rect[0].height;
1252	Rect[1].height = 1;
1253	nRect++;
1254    }
1255
1256    /* Factor out virtual resolution */
1257    pRegion = RegionFromRects(nRect, Rect, 0);
1258    if (pRegion) {
1259	if (!RegionNar(pRegion)) {
1260	    Rect[2].x = Rect[2].y = 0;
1261	    Rect[2].width = pScrn->virtualX;
1262	    Rect[2].height = pScrn->virtualY;
1263
1264	    pScreenRegion = RegionFromRects(1, &Rect[2], 0);
1265	    if (pScreenRegion) {
1266		if (!RegionNar(pScreenRegion)) {
1267		    RegionSubtract(pRegion, pRegion, pScreenRegion);
1268
1269		    ret = xf86InitFBManagerRegion(pScreen, pRegion);
1270
1271		    if (ret && xf86GetVerbosity() >= Verbosity) {
1272			int scrnIndex = pScrn->scrnIndex;
1273
1274			xf86DrvMsgVerb(scrnIndex, X_INFO, Verbosity,
1275			    "Largest offscreen areas (with overlaps):\n");
1276
1277			if (Rect[2].width < Rect[0].width) {
1278			    xf86DrvMsgVerb(scrnIndex, X_INFO, Verbosity,
1279				"\t%d x %d rectangle at %d,0\n",
1280				Rect[0].width - Rect[2].width,
1281				Rect[0].height,
1282				Rect[2].width);
1283			}
1284			if (Rect[2].width < Rect[1].width) {
1285			    xf86DrvMsgVerb(scrnIndex, X_INFO, Verbosity,
1286				"\t%d x %d rectangle at %d,0\n",
1287				Rect[1].width - Rect[2].width,
1288				Rect[0].height + Rect[1].height,
1289				Rect[2].width);
1290			}
1291			if (Rect[2].height < Rect[0].height) {
1292			    xf86DrvMsgVerb(scrnIndex, X_INFO, Verbosity,
1293				"\t%d x %d rectangle at 0,%d\n",
1294				Rect[0].width,
1295				Rect[0].height - Rect[2].height,
1296				Rect[2].height);
1297			}
1298			if (Rect[1].height) {
1299			    xf86DrvMsgVerb(scrnIndex, X_INFO, Verbosity,
1300				"\t%d x %d rectangle at 0,%d\n",
1301				Rect[1].width,
1302				Rect[0].height - Rect[2].height +
1303				    Rect[1].height,
1304				Rect[2].height);
1305			}
1306		    }
1307		}
1308
1309		RegionDestroy(pScreenRegion);
1310	    }
1311	}
1312
1313	RegionDestroy(pRegion);
1314    }
1315
1316    return ret;
1317}
1318
1319Bool
1320xf86InitFBManagerRegion(
1321    ScreenPtr pScreen,
1322    RegionPtr FullRegion
1323){
1324   FBManagerPtr offman;
1325
1326   if(RegionNil(FullRegion))
1327	return FALSE;
1328
1329   if (!dixRegisterPrivateKey(&xf86FBScreenKeyRec, PRIVATE_SCREEN, 0))
1330       return FALSE;
1331
1332   if(!xf86RegisterOffscreenManager(pScreen, &xf86FBManFuncs))
1333	return FALSE;
1334
1335   offman = malloc(sizeof(FBManager));
1336   if(!offman) return FALSE;
1337
1338   dixSetPrivate(&pScreen->devPrivates, xf86FBScreenKey, offman);
1339
1340   offman->CloseScreen = pScreen->CloseScreen;
1341   pScreen->CloseScreen = xf86FBCloseScreen;
1342
1343   offman->InitialBoxes = RegionCreate(NULL, 1);
1344   offman->FreeBoxes = RegionCreate(NULL, 1);
1345
1346   RegionCopy(offman->InitialBoxes, FullRegion);
1347   RegionCopy(offman->FreeBoxes, FullRegion);
1348
1349   offman->pScreen = pScreen;
1350   offman->UsedAreas = NULL;
1351   offman->LinearAreas = NULL;
1352   offman->NumUsedAreas = 0;
1353   offman->NumCallbacks = 0;
1354   offman->FreeBoxesUpdateCallback = NULL;
1355   offman->devPrivates = NULL;
1356
1357   return TRUE;
1358}
1359
1360Bool
1361xf86InitFBManagerLinear(
1362    ScreenPtr pScreen,
1363    int offset,
1364    int size
1365){
1366   FBManagerPtr offman;
1367   FBLinearLinkPtr link;
1368   FBLinearPtr linear;
1369
1370   if (size <= 0)
1371	return FALSE;
1372
1373   /* we expect people to have called the Area setup first for pixmap cache */
1374   if (!dixLookupPrivate(&pScreen->devPrivates, xf86FBScreenKey))
1375	return FALSE;
1376
1377   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
1378					   xf86FBScreenKey);
1379   offman->LinearAreas = malloc(sizeof(FBLinearLink));
1380   if (!offman->LinearAreas)
1381	return FALSE;
1382
1383   link = offman->LinearAreas;
1384   link->area = NULL;
1385   link->next = NULL;
1386   link->free = 1;
1387   linear = &(link->linear);
1388   linear->pScreen = pScreen;
1389   linear->size = size;
1390   linear->offset = offset;
1391   linear->granularity = 0;
1392   linear->MoveLinearCallback = NULL;
1393   linear->RemoveLinearCallback = NULL;
1394   linear->devPrivate.ptr = NULL;
1395
1396   return TRUE;
1397}
1398
1399
1400/* This is an implementation specific function and should
1401   disappear after the next release.  People should use the
1402   real linear functions instead */
1403
1404FBAreaPtr
1405xf86AllocateLinearOffscreenArea (
1406   ScreenPtr pScreen,
1407   int length,
1408   int gran,
1409   MoveAreaCallbackProcPtr moveCB,
1410   RemoveAreaCallbackProcPtr removeCB,
1411   pointer privData
1412){
1413   FBManagerFuncsPtr funcs;
1414   FBManagerPtr offman;
1415   BoxPtr extents;
1416   int w, h;
1417
1418   if(xf86FBManagerKey == NULL)
1419        return NULL;
1420   if(!(funcs = (FBManagerFuncsPtr)dixLookupPrivate(&pScreen->devPrivates,
1421						    xf86FBManagerKey)))
1422        return NULL;
1423
1424   offman = (FBManagerPtr)dixLookupPrivate(&pScreen->devPrivates,
1425					   xf86FBScreenKey);
1426   extents = RegionExtents(offman->InitialBoxes);
1427   w = extents->x2 - extents->x1;
1428
1429   if (gran > 1) {
1430	if (gran > w)
1431	    return NULL;
1432
1433	if (w % gran)
1434	    length += gran - 1;
1435   }
1436
1437   if(length <= w) { /* special case */
1438	h = 1;
1439	w = length;
1440   } else {
1441	h = (length + w - 1) / w;
1442   }
1443
1444   return (*funcs->AllocateOffscreenArea)(
1445                pScreen, w, h, gran, moveCB, removeCB, privData);
1446}
1447