1 /* Copyright (C) 1995, 1996 Aladdin Enterprises. All rights reserved.
2
3 This software is provided AS-IS with no warranty, either express or
4 implied.
5
6 This software is distributed under license and may not be copied,
7 modified or distributed except as expressly authorized under the terms
8 of the license contained in the file LICENSE in this distribution.
9
10 For more information about licensing, please refer to
11 http://www.ghostscript.com/licensing/. For information on
12 commercial licensing, go to http://www.artifex.com/licensing/ or
13 contact Artifex Software, Inc., 101 Lucas Valley Road #110,
14 San Rafael, CA 94903, U.S.A., +1(415)492-9861.
15 */
16
17 /* $Id: gxbcache.c,v 1.4 2002/02/21 22:24:52 giles Exp $ */
18 /* Bitmap cache implementation */
19 #include "memory_.h"
20 #include "gx.h"
21 #include "gsmdebug.h"
22 #include "gxbcache.h"
23
24 /* ------ Entire cache ------ */
25
26 /* Initialize a cache. The caller must allocate and initialize */
27 /* the first chunk. */
28 void
gx_bits_cache_init(gx_bits_cache * bc,gx_bits_cache_chunk * bck)29 gx_bits_cache_init(gx_bits_cache * bc, gx_bits_cache_chunk * bck)
30 {
31 bck->next = bck;
32 bc->chunks = bck;
33 bc->cnext = 0;
34 bc->bsize = 0;
35 bc->csize = 0;
36 }
37
38 /* ------ Chunks ------ */
39
40 /* Initialize a chunk. The caller must allocate it and its data. */
41 void
gx_bits_cache_chunk_init(gx_bits_cache_chunk * bck,byte * data,uint size)42 gx_bits_cache_chunk_init(gx_bits_cache_chunk * bck, byte * data, uint size)
43 {
44 bck->next = 0;
45 bck->data = data;
46 bck->size = size;
47 bck->allocated = 0;
48 if (data != 0) {
49 gx_cached_bits_head *cbh = (gx_cached_bits_head *) data;
50
51 cbh->size = size;
52 cb_head_set_free(cbh);
53 }
54 }
55
56 /* ------ Individual entries ------ */
57
58 /* Attempt to allocate an entry. If successful, set *pcbh and return 0. */
59 /* If there isn't enough room, set *pcbh to an entry requiring freeing, */
60 /* or to 0 if we are at the end of the chunk, and return -1. */
61 int
gx_bits_cache_alloc(gx_bits_cache * bc,ulong lsize,gx_cached_bits_head ** pcbh)62 gx_bits_cache_alloc(gx_bits_cache * bc, ulong lsize, gx_cached_bits_head ** pcbh)
63 {
64 #define ssize ((uint)lsize)
65 ulong lsize1 = lsize + sizeof(gx_cached_bits_head);
66
67 #define ssize1 ((uint)lsize1)
68 uint cnext = bc->cnext;
69 gx_bits_cache_chunk *bck = bc->chunks;
70 uint left = bck->size - cnext;
71 gx_cached_bits_head *cbh;
72 gx_cached_bits_head *cbh_next;
73 uint fsize = 0;
74
75 if (lsize1 > bck->size - cnext && lsize != left) { /* Not enough room to allocate in this chunk. */
76 *pcbh = 0;
77 return -1;
78 }
79 /* Look for and/or free enough space. */
80 cbh = cbh_next = (gx_cached_bits_head *) (bck->data + cnext);
81 while (fsize < ssize1 && fsize != ssize) {
82 if (!cb_head_is_free(cbh_next)) { /* Ask the caller to free the entry. */
83 if (fsize)
84 cbh->size = fsize;
85 *pcbh = cbh_next;
86 return -1;
87 }
88 fsize += cbh_next->size;
89 if_debug2('K', "[K]merging free bits 0x%lx(%u)\n",
90 (ulong) cbh_next, cbh_next->size);
91 cbh_next = (gx_cached_bits_head *) ((byte *) cbh + fsize);
92 }
93 if (fsize > ssize) { /* fsize >= ssize1 */
94 cbh_next = (gx_cached_bits_head *) ((byte *) cbh + ssize);
95 cbh_next->size = fsize - ssize;
96 cb_head_set_free(cbh_next);
97 if_debug2('K', "[K]shortening bits 0x%lx by %u (initial)\n",
98 (ulong) cbh, fsize - ssize);
99 }
100 gs_alloc_fill(cbh, gs_alloc_fill_block, ssize);
101 cbh->size = ssize;
102 bc->bsize += ssize;
103 bc->csize++;
104 bc->cnext += ssize;
105 bck->allocated += ssize;
106 *pcbh = cbh;
107 return 0;
108 #undef ssize
109 #undef ssize1
110 }
111
112 /* Shorten an entry by a given amount. */
113 void
gx_bits_cache_shorten(gx_bits_cache * bc,gx_cached_bits_head * cbh,uint diff,gx_bits_cache_chunk * bck)114 gx_bits_cache_shorten(gx_bits_cache * bc, gx_cached_bits_head * cbh,
115 uint diff, gx_bits_cache_chunk * bck)
116 {
117 gx_cached_bits_head *next;
118
119 if ((byte *) cbh + cbh->size == bck->data + bc->cnext &&
120 bck == bc->chunks
121 )
122 bc->cnext -= diff;
123 bc->bsize -= diff;
124 bck->allocated -= diff;
125 cbh->size -= diff;
126 next = (gx_cached_bits_head *) ((byte *) cbh + cbh->size);
127 cb_head_set_free(next);
128 next->size = diff;
129 }
130
131 /* Free an entry. The caller is responsible for removing the entry */
132 /* from any other structures (like a hash table). */
133 void
gx_bits_cache_free(gx_bits_cache * bc,gx_cached_bits_head * cbh,gx_bits_cache_chunk * bck)134 gx_bits_cache_free(gx_bits_cache * bc, gx_cached_bits_head * cbh,
135 gx_bits_cache_chunk * bck)
136 {
137 uint size = cbh->size;
138
139 bc->csize--;
140 bc->bsize -= size;
141 bck->allocated -= size;
142 gs_alloc_fill(cbh, gs_alloc_fill_deleted, size);
143 cbh->size = size; /* gs_alloc_fill may have overwritten */
144 cb_head_set_free(cbh);
145 }
146