1 /* ========================================================================== */
2 /* === UMF_mem_alloc_tail_block ============================================= */
3 /* ========================================================================== */
4
5 /* -------------------------------------------------------------------------- */
6 /* Copyright (c) 2005-2012 by Timothy A. Davis, http://www.suitesparse.com. */
7 /* All Rights Reserved. See ../Doc/License.txt for License. */
8 /* -------------------------------------------------------------------------- */
9
10 /* The UMF_mem_* routines manage the Numeric->Memory memory space. */
11
12 #include "umf_internal.h"
13 #include "umf_mem_alloc_tail_block.h"
14
15 /* allocate nunits from tail of Numeric->Memory */
16 /* (requires nunits+1, for header). */
17 /* Returns the index into Numeric->Memory if successful, or 0 on failure. */
18
UMF_mem_alloc_tail_block(NumericType * Numeric,Int nunits)19 GLOBAL Int UMF_mem_alloc_tail_block
20 (
21 NumericType *Numeric,
22 Int nunits
23 )
24 {
25 Int bigsize, usage ;
26 Unit *p, *pnext, *pbig ;
27
28 ASSERT (Numeric != (NumericType *) NULL) ;
29 ASSERT (Numeric->Memory != (Unit *) NULL) ;
30
31 #ifndef NDEBUG
32 if (UMF_allocfail)
33 {
34 /* pretend to fail, to test garbage_collection */
35 DEBUGm2 (("UMF_mem_alloc_tail_block: pretend to fail\n")) ;
36 UMF_allocfail = FALSE ; /* don't fail the next time */
37 return (0) ;
38 }
39 DEBUG2 (("UMF_mem_alloc_tail_block, size: "ID" + 1 = "ID": ",
40 nunits, nunits+1)) ;
41 #endif
42
43 bigsize = 0 ;
44 pbig = (Unit *) NULL ;
45
46 ASSERT (nunits > 0) ; /* size must be positive */
47 if (Numeric->ibig != EMPTY)
48 {
49 ASSERT (Numeric->ibig > Numeric->itail) ;
50 ASSERT (Numeric->ibig < Numeric->size) ;
51 pbig = Numeric->Memory + Numeric->ibig ;
52 bigsize = -pbig->header.size ;
53 ASSERT (bigsize > 0) ; /* Numeric->ibig is free */
54 ASSERT (pbig->header.prevsize >= 0) ; /* prev. is not free */
55 }
56
57 if (pbig && bigsize >= nunits)
58 {
59
60 /* use the biggest block, somewhere in middle of memory */
61 p = pbig ;
62 pnext = p + 1 + bigsize ;
63 /* next is in range */
64 ASSERT (pnext < Numeric->Memory + Numeric->size) ;
65 /* prevsize of next = this size */
66 ASSERT (pnext->header.prevsize == bigsize) ;
67 /* next is not free */
68 ASSERT (pnext->header.size > 0) ;
69 bigsize -= nunits + 1 ;
70
71 if (bigsize < 4)
72 {
73 /* internal fragmentation would be too small */
74 /* allocate the entire free block */
75 p->header.size = -p->header.size ;
76 DEBUG2 (("GET BLOCK: p: "ID" size: "ID", all of big: "ID" size: "
77 ID"\n", (Int) (p-Numeric->Memory), nunits, Numeric->ibig,
78 p->header.size)) ;
79 /* no more biggest block */
80 Numeric->ibig = EMPTY ;
81
82 }
83 else
84 {
85
86 /* allocate just the first nunits Units of the free block */
87 p->header.size = nunits ;
88 /* make a new free block */
89 Numeric->ibig += nunits + 1 ;
90 pbig = Numeric->Memory + Numeric->ibig ;
91 pbig->header.size = -bigsize ;
92 pbig->header.prevsize = nunits ;
93 pnext->header.prevsize = bigsize ;
94 DEBUG2 (("GET BLOCK: p: "ID" size: "ID", some of big: "ID" left: "
95 ID"\n", (Int) (p-Numeric->Memory), nunits, Numeric->ibig,
96 bigsize)) ;
97 }
98
99 }
100 else
101 {
102
103 /* allocate from the top of tail */
104 pnext = Numeric->Memory + Numeric->itail ;
105 DEBUG2 (("GET BLOCK: from tail ")) ;
106 if ((nunits + 1) > (Numeric->itail - Numeric->ihead))
107 {
108 DEBUG2 (("\n")) ;
109 return (0) ;
110 }
111 Numeric->itail -= (nunits + 1) ;
112 p = Numeric->Memory + Numeric->itail ;
113 p->header.size = nunits ;
114 p->header.prevsize = 0 ;
115 pnext->header.prevsize = nunits ;
116 DEBUG2 (("p: "ID" size: "ID", new tail "ID"\n",
117 (Int) (p-Numeric->Memory), nunits, Numeric->itail)) ;
118 }
119
120 Numeric->tail_usage += p->header.size + 1 ;
121 usage = Numeric->ihead + Numeric->tail_usage ;
122 Numeric->max_usage = MAX (Numeric->max_usage, usage) ;
123
124 #ifndef NDEBUG
125 UMF_debug -= 10 ;
126 UMF_dump_memory (Numeric) ;
127 UMF_debug += 10 ;
128 #endif
129
130 /* p points to the header. Add one to point to the usable block itself. */
131 /* return the offset into Numeric->Memory */
132 return ((p - Numeric->Memory) + 1) ;
133 }
134