Merge git://brick.kernel.dk/data/git/linux-2.6-block
[linux-2.6] / drivers / char / drm / sis_ds.c
1 /* sis_ds.c -- Private header for Direct Rendering Manager -*- linux-c -*-
2  * Created: Mon Jan  4 10:05:05 1999 by sclin@sis.com.tw
3  *
4  * Copyright 2000 Silicon Integrated Systems Corp, Inc., HsinChu, Taiwan.
5  * All rights reserved.
6  *
7  * Permission is hereby granted, free of charge, to any person obtaining a
8  * copy of this software and associated documentation files (the "Software"),
9  * to deal in the Software without restriction, including without limitation
10  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
11  * and/or sell copies of the Software, and to permit persons to whom the
12  * Software is furnished to do so, subject to the following conditions:
13  *
14  * The above copyright notice and this permission notice (including the next
15  * paragraph) shall be included in all copies or substantial portions of the
16  * Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
21  * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
22  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
23  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
24  * DEALINGS IN THE SOFTWARE.
25  *
26  * Authors:
27  *    Sung-Ching Lin <sclin@sis.com.tw>
28  *
29  */
30
31 #include "drmP.h"
32 #include "drm.h"
33 #include "sis_ds.h"
34
35 /* Set Data Structure, not check repeated value
36  * temporarily used
37  */
38
39 set_t *setInit(void)
40 {
41         int i;
42         set_t *set;
43
44         set = (set_t *) drm_alloc(sizeof(set_t), DRM_MEM_DRIVER);
45         if (set != NULL) {
46                 for (i = 0; i < SET_SIZE; i++) {
47                         set->list[i].free_next = i + 1;
48                         set->list[i].alloc_next = -1;
49                 }
50                 set->list[SET_SIZE - 1].free_next = -1;
51                 set->free = 0;
52                 set->alloc = -1;
53                 set->trace = -1;
54         }
55         return set;
56 }
57
58 int setAdd(set_t * set, ITEM_TYPE item)
59 {
60         int free = set->free;
61
62         if (free != -1) {
63                 set->list[free].val = item;
64                 set->free = set->list[free].free_next;
65         } else {
66                 return 0;
67         }
68
69         set->list[free].alloc_next = set->alloc;
70         set->alloc = free;
71         set->list[free].free_next = -1;
72
73         return 1;
74 }
75
76 int setDel(set_t * set, ITEM_TYPE item)
77 {
78         int alloc = set->alloc;
79         int prev = -1;
80
81         while (alloc != -1) {
82                 if (set->list[alloc].val == item) {
83                         if (prev != -1)
84                                 set->list[prev].alloc_next =
85                                     set->list[alloc].alloc_next;
86                         else
87                                 set->alloc = set->list[alloc].alloc_next;
88                         break;
89                 }
90                 prev = alloc;
91                 alloc = set->list[alloc].alloc_next;
92         }
93
94         if (alloc == -1)
95                 return 0;
96
97         set->list[alloc].free_next = set->free;
98         set->free = alloc;
99         set->list[alloc].alloc_next = -1;
100
101         return 1;
102 }
103
104 /* setFirst -> setAdd -> setNext is wrong */
105
106 int setFirst(set_t * set, ITEM_TYPE * item)
107 {
108         if (set->alloc == -1)
109                 return 0;
110
111         *item = set->list[set->alloc].val;
112         set->trace = set->list[set->alloc].alloc_next;
113
114         return 1;
115 }
116
117 int setNext(set_t * set, ITEM_TYPE * item)
118 {
119         if (set->trace == -1)
120                 return 0;
121
122         *item = set->list[set->trace].val;
123         set->trace = set->list[set->trace].alloc_next;
124
125         return 1;
126 }
127
128 int setDestroy(set_t * set)
129 {
130         drm_free(set, sizeof(set_t), DRM_MEM_DRIVER);
131
132         return 1;
133 }
134
135 /*
136  * GLX Hardware Device Driver common code
137  * Copyright (C) 1999 Wittawat Yamwong
138  *
139  * Permission is hereby granted, free of charge, to any person obtaining a
140  * copy of this software and associated documentation files (the "Software"),
141  * to deal in the Software without restriction, including without limitation
142  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
143  * and/or sell copies of the Software, and to permit persons to whom the
144  * Software is furnished to do so, subject to the following conditions:
145  *
146  * The above copyright notice and this permission notice shall be included
147  * in all copies or substantial portions of the Software.
148  *
149  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
150  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
151  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
152  * WITTAWAT YAMWONG, OR ANY OTHER CONTRIBUTORS BE LIABLE FOR ANY CLAIM,
153  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
154  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
155  * OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
156  *
157  */
158
159 #define ISFREE(bptr) ((bptr)->free)
160
161 memHeap_t *mmInit(int ofs, int size)
162 {
163         PMemBlock blocks;
164
165         if (size <= 0)
166                 return NULL;
167
168         blocks = (TMemBlock *) drm_calloc(1, sizeof(TMemBlock), DRM_MEM_DRIVER);
169         if (blocks != NULL) {
170                 blocks->ofs = ofs;
171                 blocks->size = size;
172                 blocks->free = 1;
173                 return (memHeap_t *) blocks;
174         } else
175                 return NULL;
176 }
177
178 /* Checks if a pointer 'b' is part of the heap 'heap' */
179 int mmBlockInHeap(memHeap_t * heap, PMemBlock b)
180 {
181         TMemBlock *p;
182
183         if (heap == NULL || b == NULL)
184                 return 0;
185
186         p = heap;
187         while (p != NULL && p != b) {
188                 p = p->next;
189         }
190         if (p == b)
191                 return 1;
192         else
193                 return 0;
194 }
195
196 static TMemBlock *SliceBlock(TMemBlock * p,
197                              int startofs, int size,
198                              int reserved, int alignment)
199 {
200         TMemBlock *newblock;
201
202         /* break left */
203         if (startofs > p->ofs) {
204                 newblock = (TMemBlock *) drm_calloc(1, sizeof(TMemBlock),
205                                                     DRM_MEM_DRIVER);
206                 newblock->ofs = startofs;
207                 newblock->size = p->size - (startofs - p->ofs);
208                 newblock->free = 1;
209                 newblock->next = p->next;
210                 p->size -= newblock->size;
211                 p->next = newblock;
212                 p = newblock;
213         }
214
215         /* break right */
216         if (size < p->size) {
217                 newblock = (TMemBlock *) drm_calloc(1, sizeof(TMemBlock),
218                                                     DRM_MEM_DRIVER);
219                 newblock->ofs = startofs + size;
220                 newblock->size = p->size - size;
221                 newblock->free = 1;
222                 newblock->next = p->next;
223                 p->size = size;
224                 p->next = newblock;
225         }
226
227         /* p = middle block */
228         p->align = alignment;
229         p->free = 0;
230         p->reserved = reserved;
231         return p;
232 }
233
234 PMemBlock mmAllocMem(memHeap_t * heap, int size, int align2, int startSearch)
235 {
236         int mask, startofs, endofs;
237         TMemBlock *p;
238
239         if (heap == NULL || align2 < 0 || size <= 0)
240                 return NULL;
241
242         mask = (1 << align2) - 1;
243         startofs = 0;
244         p = (TMemBlock *) heap;
245         while (p != NULL) {
246                 if (ISFREE(p)) {
247                         startofs = (p->ofs + mask) & ~mask;
248                         if (startofs < startSearch) {
249                                 startofs = startSearch;
250                         }
251                         endofs = startofs + size;
252                         if (endofs <= (p->ofs + p->size))
253                                 break;
254                 }
255                 p = p->next;
256         }
257         if (p == NULL)
258                 return NULL;
259         p = SliceBlock(p, startofs, size, 0, mask + 1);
260         p->heap = heap;
261         return p;
262 }
263
264 static __inline__ int Join2Blocks(TMemBlock * p)
265 {
266         if (p->free && p->next && p->next->free) {
267                 TMemBlock *q = p->next;
268                 p->size += q->size;
269                 p->next = q->next;
270                 drm_free(q, sizeof(TMemBlock), DRM_MEM_DRIVER);
271                 return 1;
272         }
273         return 0;
274 }
275
276 int mmFreeMem(PMemBlock b)
277 {
278         TMemBlock *p, *prev;
279
280         if (b == NULL)
281                 return 0;
282         if (b->heap == NULL)
283                 return -1;
284
285         p = b->heap;
286         prev = NULL;
287         while (p != NULL && p != b) {
288                 prev = p;
289                 p = p->next;
290         }
291         if (p == NULL || p->free || p->reserved)
292                 return -1;
293
294         p->free = 1;
295         Join2Blocks(p);
296         if (prev)
297                 Join2Blocks(prev);
298         return 0;
299 }