1 /***************************************************************************
2 * Copyright 1995, Technion, Israel Institute of Technology
3 * Electrical Eng, Software Lab.
4 * Author: Michael Veksler.
5 ***************************************************************************
7 * Purpose: Data fragments and free list items. Allocate and free blocks.
8 ***************************************************************************
10 #include <stdio.h> /* for debugging only */
12 #include <debug.h> /* for "stddeb" */
14 #include "shm_fragment.h"
15 #include "shm_block.h"
17 /******************************************************************************
19 * Free list: all fragments are ordered according to memory location.
20 * new fragments are inserted in this way.
22 ******************************************************************************
25 #define FRAG_PTR(block,ofs) ((struct shm_fragment *) ((char *) block + ofs) )
26 #define NEXT_FRAG(block,ofs) ( FRAG_PTR(block,ofs)->info.next )
28 /* setup first item in the free list */
29 void shm_FragmentInit(struct shm_block
*block
,int first
, int size
)
31 struct shm_fragment
*fragment
;
33 /* round up to nearest 16 byte boundary */
34 first
=(first
+15)& ~15;
35 block
->free_list
=first
;
37 /* make all the block (exluding the header) free */
38 fragment
= FRAG_PTR(block
, first
);
39 block
->free
= fragment
->size
= size
-first
;
40 fragment
->info
.next
=0;
43 void shm_FragPtrFree(struct shm_block
*block
, void *ptr
)
45 /* ptr points to fragment->info.data, find pointer to fragment,
46 * find the offset of this pointer in block.
49 shm_FragmentFree(block
, PTR2REL(block
, ptr
));
51 void shm_FragmentFree(struct shm_block
*block
, int fragment_ofs
)
53 struct shm_fragment
*fragment
=NULL
;
57 fragment_ofs
-=(int )&fragment
->info
.data
;
58 fragment
= FRAG_PTR(block
, fragment_ofs
);
60 block
->free
+=fragment
->size
;
61 /* scan free list to find candidates for merging with fragment */
62 for (prev
=0, next
=block
->free_list
;
63 (next
!=0) && (fragment_ofs
> next
) ;
64 prev
=next
, next
=NEXT_FRAG(block
,next
) )
67 /* insert fragment between, prev and next
68 * prev==0: fragment will be the first item in free list
69 * next==0: fragment will be the last item in free list
73 /* update fragment (point to next, or merge with next) */
75 if ( fragment_ofs
+fragment
->size
== next
) {
76 /* merge with the next free block */
77 fragment
->size
+= FRAG_PTR(block
,next
)->size
;
78 fragment
->info
.next
=FRAG_PTR(block
,next
)->info
.next
;
80 /* fragment should be inserted before the next fragment or end of */
81 /* list. (not merged) */
82 fragment
->info
.next
=next
;
83 /* now fragment has all the information about the rest of the list */
86 /* upate prev fragment (point or merge with fragment) */
88 if (prev
==0) /* first item in free list */
89 block
->free_list
=fragment_ofs
;
90 else if ( prev
+FRAG_PTR(block
,prev
)->size
== fragment_ofs
) {
91 /* merge fragment with previous fragment */
92 FRAG_PTR(block
,prev
)->size
+= fragment
->size
;
93 FRAG_PTR(block
,prev
)->info
.next
=fragment
->info
.next
;
95 /* insert fragment after previous fragment */
96 FRAG_PTR(block
,prev
)->info
.next
=fragment_ofs
;
99 /* use "first fit" algorithm,
100 * return: offset to data in fragment.
102 int shm_FragmentAlloc(struct shm_block
*block
, int size
)
106 struct shm_fragment
*fragment
;
107 struct shm_fragment
*ret_fragment
;
111 /* add size of "fragment->size" */
112 size
+= (char *)&fragment
->info
.data
- (char *)fragment
;
114 /* round "size" to nearest 16 byte value */
115 size
= (size
+15) & ~15;
116 if (size
> block
->free
)
118 /* scan free list to find candidates for allocation */
119 for (prev
=0, candidate
=block
->free_list
;
121 prev
=candidate
, candidate
= fragment
->info
.next
)
123 fragment
=FRAG_PTR(block
,candidate
);
124 if (fragment
->size
>= size
)
132 if (fragment
->size
== size
) {
134 block
->free_list
= fragment
->info
.next
;
136 FRAG_PTR(block
,prev
)->info
.next
= fragment
->info
.next
;
137 return PTR2REL(block
, &fragment
->info
.data
);
140 /* fragment->size > size */
142 /* Split fragment in two, return one part, put the other in free list. */
143 /* The part that starts at the old location - will stay in the free list. */
144 fragment
->size
-= size
;
146 ret_fragment
=FRAG_PTR(block
, candidate
+ fragment
->size
);
147 ret_fragment
->size
= size
;
148 return PTR2REL(block
, ret_fragment
->info
.data
);
151 /* like shm_FragmentAlloc, returns pointer instead of offset */
152 char *shm_FragPtrAlloc(struct shm_block
*block
, int size
)
155 ofs
= shm_FragmentAlloc(block
,size
);
159 return (char *) REL2PTR(block
, ofs
);
161 /* This is used for debugging only */
162 void shm_print_free_list(struct shm_block
*block
)
164 struct shm_fragment
*fragment
;
167 item
=block
->free_list
;
169 fprintf(stddeb
,"no free fragments");
171 for (; item
; item
=fragment
->info
.next
) {
172 fragment
=FRAG_PTR(block
,item
);
173 fprintf(stddeb
,"{0x%04x,0x%04x} ",item
,fragment
->size
);
176 fprintf(stddeb
," [total free=%04x]\n",block
->free
);