summaryrefslogtreecommitdiff
path: root/firmware/test/memory/memory-page.c
diff options
context:
space:
mode:
authorAlan Korr <alkorr@rockbox.org>2002-04-21 12:21:14 +0000
committerAlan Korr <alkorr@rockbox.org>2002-04-21 12:21:14 +0000
commitb7cf0602fd08f6a367d42f0b6adadb8322b3d35d (patch)
treeabbfb87b615f4c01a5f56eedacd75acbd2e52b87 /firmware/test/memory/memory-page.c
parent257d17da6d64d2e265df3c80192a01f47e1dd2b7 (diff)
downloadrockbox-b7cf0602fd08f6a367d42f0b6adadb8322b3d35d.tar.gz
rockbox-b7cf0602fd08f6a367d42f0b6adadb8322b3d35d.zip
removing all that stuff permanently.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@159 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'firmware/test/memory/memory-page.c')
-rw-r--r--firmware/test/memory/memory-page.c408
1 files changed, 0 insertions, 408 deletions
diff --git a/firmware/test/memory/memory-page.c b/firmware/test/memory/memory-page.c
deleted file mode 100644
index 1327cf57c9..0000000000
--- a/firmware/test/memory/memory-page.c
+++ /dev/null
@@ -1,408 +0,0 @@
1/***************************************************************************
2 * __________ __ ___.
3 * Open \______ \ ____ ____ | | _\_ |__ _______ ___
4 * Source | _// _ \_/ ___\| |/ /| __ \ / _ \ \/ /
5 * Jukebox | | ( <_> ) \___| < | \_\ ( <_> > < <
6 * Firmware |____|_ /\____/ \___ >__|_ \|___ /\____/__/\_ \
7 * \/ \/ \/ \/ \/
8 * $Id$
9 *
10 * Copyright (C) 2002 by Alan Korr
11 *
12 * All files in this archive are subject to the GNU General Public License.
13 * See the file COPYING in the source tree root for full license agreement.
14 *
15 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
16 * KIND, either express or implied.
17 *
18 ****************************************************************************/
19#include <memory.h>
20#include "memory-page.h"
21#if 0
22#include "memory-slab.h"
23#endif
24
25#ifdef TEST
26
27// IA32 has no problem with shift operation
28static inline unsigned int __memory_get_size (int order)
29 {
30 return (MEMORY_PAGE_MINIMAL_SIZE << order);
31 }
32
33// Arghhhh ! I cannot align 'free_page' on 512-byte boundary (max is 16-byte for Cygwin)
34static inline struct memory_free_page *__memory_get_neighbour (struct memory_free_page *node,unsigned int size)
35 {
36 return ((struct memory_free_page *)((unsigned)__memory_free_page + (((unsigned)node - (unsigned)__memory_free_page) ^ size)));
37 }
38
39#else
40
41// SH1 has very poor shift instructions (only <<1,>>1,<<2,>>2,<<8,>>8,<<16 and >>16).
42// so we should use a lookup table to speedup.
43static inline unsigned int __memory_get_size (int order)
44 {
45 static unsigned short size [MEMORY_TOTAL_ORDERS] =
46 {
47 1<<MEMORY_PAGE_MINIMAL_ORDER,
48 2<<MEMORY_PAGE_MINIMAL_ORDER,
49 4<<MEMORY_PAGE_MINIMAL_ORDER,
50 8<<MEMORY_PAGE_MINIMAL_ORDER,
51 16<<MEMORY_PAGE_MINIMAL_ORDER,
52 32<<MEMORY_PAGE_MINIMAL_ORDER,
53 64<<MEMORY_PAGE_MINIMAL_ORDER,
54 128<<MEMORY_PAGE_MINIMAL_ORDER,
55 256<<MEMORY_PAGE_MINIMAL_ORDER,
56 512<<MEMORY_PAGE_MINIMAL_ORDER,
57 1024<<MEMORY_PAGE_MINIMAL_ORDER,
58 2048<<MEMORY_PAGE_MINIMAL_ORDER,
59 4096<<MEMORY_PAGE_MINIMAL_ORDER
60 };
61 return size[order];
62 }
63
64static inline struct memory_free_page *__memory_get_neighbour (struct memory_free_page *node,unsigned int size)
65 {
66 return ((struct memory_free_page *)((unsigned)node ^ size));
67 }
68
69#endif
70
71static inline int __memory_get_order (struct memory_free_page *node)
72 {
73 return __memory_free_page_order[node - __memory_free_page];
74 }
75static inline void __memory_set_order (struct memory_free_page *node,int order)
76 {
77 __memory_free_page_order[node - __memory_free_page] = order;
78 }
79
80#if MEMORY_PAGE_USE_SPLAY_TREE
81
82static struct memory_free_page *__memory_splay_page (struct memory_free_page *root,struct memory_free_page *node)
83 {
84 struct memory_free_page *down;
85 struct memory_free_page *less;
86 struct memory_free_page *more;
87 struct memory_free_page head;
88 head.less =
89 head.more = 0;
90 less =
91 more = &head;
92 while (1)
93 {
94 if (node < root)
95 {
96 if ((down = root->less))
97 {
98 if (node < down)
99 {
100 root->less = down->more;
101 down->more = root;
102 root = down;
103 if (!root->less)
104 break;
105 }
106 more->less = root;
107 more = root;
108 root = root->less;
109 continue;
110 }
111 break;
112 }
113 if (root < node)
114 {
115 if ((down = root->more))
116 {
117 if (root < node)
118 {
119 root->more = down->less;
120 down->less = root;
121 root = down;
122 if (!root->more)
123 break;
124 }
125 less->more = root;
126 less = root;
127 root = root->more;
128 continue;
129 }
130 }
131 break;
132 }
133 less->more = root->less;
134 more->less = root->more;
135 root->less = head.more;
136 root->more = head.less;
137 return root;
138 }
139
140static inline void __memory_insert_page (int order,struct memory_free_page *node)
141 {
142 struct memory_free_page *root = __memory_free_page_bin[order];
143 if (!root)
144 {
145 node->less =
146 node->more = 0;
147 }
148 else if (node < (root = __memory_splay_page (root,node)))
149 {
150 node->less = root->less;
151 node->more = root;
152 root->less = 0;
153 }
154 else if (node > root)
155 {
156 node->less = root;
157 node->more = root->more;
158 node->more = 0;
159 }
160 __memory_free_page_bin[order] = node;
161 __memory_set_order (node,order);
162 return;
163 }
164
165static inline struct memory_free_page *__memory_pop_page (int order,int want)
166 {
167 struct memory_free_page *root = __memory_free_page_bin[order];
168 if (root)
169 {
170 root = __memory_splay_page (root,__memory_free_page);
171 __memory_free_page_bin[order] = root->more;
172 __memory_set_order (root,~want);
173 }
174 return root;
175 }
176
177static inline void __memory_remove_page (int order,struct memory_free_page *node)
178 {
179 struct memory_free_page *root = __memory_free_page_bin[order];
180 root = __memory_splay_page (root,node);
181 if (root->less)
182 {
183 node = __memory_splay_page (root->less,node);
184 node->more = root->more;
185 }
186 else
187 node = root->more;
188 __memory_free_page_bin[order] = node;
189 }
190
191#else
192
193static inline void __memory_insert_page (int order,struct memory_free_page *node)
194 {
195 struct memory_free_page *head = __memory_free_page_bin[order];
196 node->less = 0;
197 node->more = head;
198 if (head)
199 head->less = node;
200 __memory_free_page_bin[order] = node;
201 __memory_set_order (node,order);
202 }
203
204static inline struct memory_free_page *pop_page (int order,int want)
205 {
206 struct memory_free_page *node = __memory_free_page_bin[order];
207 if (node)
208 {
209 __memory_free_page_bin[order] = node->more;
210 if (node->more)
211 node->more->less = 0;
212 __memory_set_order (node,~want);
213 }
214 return node;
215 }
216
217static inline void __memory_remove_page (int order,struct memory_free_page *node)
218 {
219 if (node->less)
220 node->less->more = node->more;
221 else
222 __memory_free_page_bin[order] = node->more;
223 if (node->more)
224 node->more->less = node->less;
225 }
226
227#endif
228
229static inline void __memory_push_page (int order,struct memory_free_page *node)
230 {
231 node->less = 0;
232 node->more = 0;
233 __memory_free_page_bin[order] = node;
234 __memory_set_order (node,order);
235 }
236
237static struct memory_free_page *__memory_allocate_page (unsigned int size,int order)
238 {
239 struct memory_free_page *node;
240 int min = order;
241 while ((unsigned)order <= (MEMORY_TOTAL_ORDERS - 1))
242 // order is valid ?
243 {
244 if (!(node = __memory_pop_page (order,min)))
245 // no free page of this order ?
246 {
247 ++order; size <<= 1;
248 continue;
249 }
250 while (order > min)
251 // split our larger page in smaller pages
252 {
253 --order; size >>= 1;
254 __memory_push_page (order,(struct memory_free_page *)((unsigned int)node + size));
255 }
256 return node;
257 }
258 return MEMORY_RETURN_FAILURE;
259 }
260
261static inline void __memory_release_page (struct memory_free_page *node,unsigned int size,int order)
262 {
263 struct memory_free_page *neighbour;
264 while ((order <= (MEMORY_TOTAL_ORDERS - 1)) &&
265 ((neighbour = __memory_get_neighbour (node,size)),
266 (__memory_get_order (neighbour) == order)))
267 // merge our released page with its contiguous page into a larger page
268 {
269 __memory_remove_page (order,neighbour);
270 ++order; size <<= 1;
271 if (neighbour < node)
272 node = neighbour;
273 }
274 __memory_insert_page (order,node);
275 }
276
277
278/*****************************************************************************/
279/* PUBLIC FUNCTIONS */
280/*****************************************************************************/
281
282void *memory_allocate_page (int order)
283 {
284 if (order < 0)
285 return MEMORY_RETURN_FAILURE;
286 return __memory_allocate_page (__memory_get_size (order),order);
287 }
288
289// release a page :
290// when called, 'address' MUST be a valid address pointing
291// to &dram[i], where i ranges from 0 to MEMORY_TOTAL_PAGES - 1.
292// FAILURE if block is already freed.
293int memory_release_page (void *address)
294 {
295 struct memory_free_page *node = (struct memory_free_page *)address;
296 int order = ~__memory_get_order (node);
297 if (order < 0)
298 return MEMORY_RETURN_FAILURE;
299 __memory_release_page (node,__memory_get_size (order),order);
300 return MEMORY_RETURN_SUCCESS;
301 }
302
303
304#ifdef TEST
305# include <stdio.h>
306# include <stdlib.h>
307# if MEMORY_PAGE_USE_SPLAY_TREE
308
309void __memory_dump_splay_node (struct memory_free_page *node,int level)
310 {
311 if (!node)
312 return;
313 __memory_dump_splay_node (node->less,level+1);
314 printf ("\n%*s[%d-%d]",level,"",(node - __memory_free_page),(node - __memory_free_page) + (1 << __memory_get_order (node)) - 1);
315 __memory_dump_splay_node (node->more,level+1);
316 }
317
318void __memory_dump_splay_tree (struct memory_free_page *root)
319 {
320 __memory_dump_splay_node (root,2); fflush (stdout);
321 }
322
323# endif
324
325void __memory_spy_page (void *address)
326 {
327 struct memory_free_page *node = (struct memory_free_page *)address;
328 int order,used;
329 if (node)
330 {
331 order = __memory_get_order (node);
332 used = order < 0;
333 if (used)
334 order = ~order;
335 printf("\n(%s,%2d,%7d)",(used ? "used" : "free"),order,__memory_get_size (order));
336 }
337 }
338
339void __memory_dump (int order)
340 {
341 struct memory_free_page *node = __memory_free_page_bin[order];
342 printf("\n(%s,%2d,%7d)",node ? "free" : "none",order,__memory_get_size (order));
343# if MEMORY_PAGE_USE_SPLAY_TREE
344 __memory_dump_splay_tree (node);
345# else
346 while (node)
347 {
348 printf("[%d-%d]",(node - __memory_free_page),(node - __memory_free_page) + (1<<order) - 1);
349 node = node->more;
350 }
351# endif
352
353 }
354
355void __memory_check (int order)
356 {
357 struct memory_free_page *node[4096],*swap;
358 unsigned int i = 0,j = 0;
359 while (i <= 12)
360 __memory_dump (i++);
361 i = 0;
362 printf ("\nallocating...\n");
363 while (order >= 0)
364 {
365 j = order;
366 while ((swap = memory_allocate_page (j)))
367 {
368 node[i++] = swap;
369 printf("[%d-%d]",(swap - __memory_free_page),(swap - __memory_free_page) + ((1 << j)-1));
370 for (j += (rand () & 15); j > (unsigned int)order; j -= order);
371 }
372 --order;
373 }
374 node[i] = 0;
375 while (j <= 12)
376 __memory_dump (j++);
377 j = 0;
378 printf ("\nreleasing...");
379 --i;
380 while (i > 0)
381 {
382 unsigned int k = 0;
383# if 0
384 printf ("\n");
385# endif
386 swap = node[k++];
387# if 0
388 while (swap)
389 {
390 printf("[%d-%d]",(swap - __memory_free_page),(swap - __memory_free_page) + ((1 << ~__memory_get_order (swap))-1));
391 swap = node[k++];
392 }
393# endif
394 for (j += 1 + (rand () & 15); j >= i; j -= i);
395 swap = node[j];
396 node[j] = node[i];
397 memory_release_page (swap);
398 node[i] = 0;
399 --i;
400 }
401 memory_release_page (node[0]);
402 i = 0;
403 while (i <= 12)
404 __memory_dump (i++);
405 printf("\n\n%s !",(__memory_get_order (__memory_free_page) == 12) ? "SUCCESS" : "FAILURE");
406 }
407
408#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-24 11:25:41 +0000