data-stack.c revision db562225ac6e1f0e2b1a87af97f115febb09cba9
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen data-stack.c : Data stack implementation
2d49f150b4bce6f2f59a84e268e4777901c3e42cTimo Sirainen Copyright (c) 2001-2002 Timo Sirainen
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen Permission is hereby granted, free of charge, to any person obtaining
1dd875d96ab5640f78250079961c10e99ed4aa79Timo Sirainen a copy of this software and associated documentation files (the
bb10ebcf076c959c752f583746d83805d7686df8Timo Sirainen "Software"), to deal in the Software without restriction, including
ffd9a1898a18fadfc5dce399162c25d50548f905Timo Sirainen without limitation the rights to use, copy, modify, merge, publish,
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen distribute, sublicense, and/or sell copies of the Software, and to
89b548af722113acb5d63dfffb44423cb60f91e4Timo Sirainen permit persons to whom the Software is furnished to do so, subject to
31ddc75584c5cde53d2e78a737587f2e7fdcb0d2Timo Sirainen the following conditions:
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen The above copyright notice and this permission notice shall be
66ae183b6e895216037bd921367670f4b0665911Timo Sirainen included in all copies or substantial portions of the Software.
a2f250a332dfc1e6cd4ffd196c621eb9dbf7b8a1Timo Sirainen THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
da5d50534cfca45d0aaaf0bdac17b287b4588809Timo Sirainen MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen/* Use malloc() and free() for all memory allocations. Useful for debugging
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen memory corruption. */
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen/* #define DISABLE_DATA_STACK */
8fa41238067c854435884c459963fde6f8c6436bTimo Sirainen/* Max. number of bytes to even try to allocate. This is done just to avoid
8fa41238067c854435884c459963fde6f8c6436bTimo Sirainen allocating less memory than was actually requested because of integer
91dca97b367c54a139c268b56a0c67f564bd9197Timo Sirainen overflows. */
46c31f64b9f0949f00b7819f45b22f2d64b2ea27Timo Sirainen/* Initial stack size - this should be kept in a size that doesn't exceed
d6badc27cd6e8d3398877b6766cb0aaeef3a7800Timo Sirainen in a normal use to avoid extra malloc()ing. */
91dca97b367c54a139c268b56a0c67f564bd9197Timo Sirainentypedef struct _StackFrameBlock StackFrameBlock;
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainen /* unsigned char data[]; */
d5cebe7f98e63d4e2822863ef2faa4971e8b3a5dTimo Sirainen#define SIZEOF_MEMBLOCK MEM_ALIGN(sizeof(StackBlock))
ee246b46953e4b94b2f22e093373674fa9155500Timo Sirainen/* current_frame_block contains last t_push()ed frames. After that new
bb10ebcf076c959c752f583746d83805d7686df8Timo Sirainen StackFrameBlock is created and it's ->prev is set to current_frame_block. */
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainenstatic int frame_pos; /* current frame position current_frame_block */
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainenstatic StackFrameBlock *current_frame_block; /* current stack frame block */
0cb2e8eb55e70f8ebe1e8349bdf49e4cbe5d8834Timo Sirainenstatic StackFrameBlock *unused_frame_blocks; /* unused stack frames */
80fc743146da5130de34174cdaad2576f103723fTimo Sirainenstatic StackBlock *current_block; /* block currently used for allocation */
80fc743146da5130de34174cdaad2576f103723fTimo Sirainenstatic StackBlock *unused_block; /* largest unused block is kept here */
20a802016205bbcafc90f164f769ea801f88d014Timo Sirainenunsigned int t_push(void)
e156adefc1260d31a145df2f5e9b3c82050d4163Timo Sirainen /* frame block full */
20a802016205bbcafc90f164f769ea801f88d014Timo Sirainen /* allocate new block */
7797aa2479e99aeb71057b7a2584b2cb72e4d3f8Timo Sirainen frame_block = calloc(sizeof(StackFrameBlock), 1);
8e7da21696c9f8a6d5e601243fb6172ec85d47b2Timo Sirainen /* use existing unused frame_block */
c5454841b5067a22827556ca9bc7935d190f57baTimo Sirainen unused_frame_blocks = unused_frame_blocks->prev;
1e923fcf497665fe071a154c31fb452766b0b2deTimo Sirainen /* mark our current position */
d161e3c2cde2bd8d5917840f68823a2259ed426eTimo Sirainen current_frame_block->block[frame_pos] = current_block;
d161e3c2cde2bd8d5917840f68823a2259ed426eTimo Sirainen current_frame_block->block_space_used[frame_pos] = current_block->left;
c5454841b5067a22827556ca9bc7935d190f57baTimo Sirainen current_frame_block->last_alloc_size[frame_pos] = 0;
c27f03fa8fd2ef4acd1db814fae7d90e0eb9d3aeTimo Sirainen /* free all the blocks, except if any of them is bigger than
c27f03fa8fd2ef4acd1db814fae7d90e0eb9d3aeTimo Sirainen unused_block, replace it */
c27f03fa8fd2ef4acd1db814fae7d90e0eb9d3aeTimo Sirainen if (unused_block == NULL || block->size > unused_block->size) {
c5454841b5067a22827556ca9bc7935d190f57baTimo Sirainenunsigned int t_pop(void)
c5454841b5067a22827556ca9bc7935d190f57baTimo Sirainen /* update the current block */
5a07b37a9df398b5189c14872a600384208ab74bTimo Sirainen current_block = current_frame_block->block[frame_pos];
5a07b37a9df398b5189c14872a600384208ab74bTimo Sirainen current_block->left = current_frame_block->block_space_used[frame_pos];
da985034a708db2f61394b30d117050ae6829ee5Timo Sirainen (current_block->size - current_block->left), 0xde,
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen /* free unused blocks */
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen /* frame block is now unused, add it to unused list */
5626ae5e3316eced244adb6485c0927f1c7fdc41Timo Sirainenstatic StackBlock *mem_block_alloc(size_t min_size)
c27f03fa8fd2ef4acd1db814fae7d90e0eb9d3aeTimo Sirainen prev_size = current_block == NULL ? 0 : current_block->size;
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen alloc_size = nearest_power(prev_size + min_size);
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen "Out of memory when allocating %"PRIuSIZE_T" bytes",
c27f03fa8fd2ef4acd1db814fae7d90e0eb9d3aeTimo Sirainenstatic void *t_malloc_real(size_t size, int permanent)
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen i_panic("Trying to allocate too much memory");
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen /* reset t_buffer_get() mark - not really needed but makes it easier
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen to notice if t_malloc() is called between t_buffer_get() and
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen t_buffer_alloc() */
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen /* allocate only aligned amount of memory so alignment comes
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen always properly */
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen /* used for t_try_realloc() */
519e0a461271843833a2b42626ad93f6e7ddc497Timo Sirainen current_frame_block->last_alloc_size[frame_pos] = size;
6ef7e31619edfaa17ed044b45861d106a86191efTimo Sirainen /* enough space in current block, use it */
3ccab0bac68040f179a7de45c516cec258e28fdbTimo Sirainen /* current block is full, see if we can use the unused_block */
3ccab0bac68040f179a7de45c516cec258e28fdbTimo Sirainen if (unused_block != NULL && unused_block->size >= size) {
6825360d446542046757b06064282301c4c6b27cTimo Sirainen i_warning("Growing data stack with: %"PRIuSIZE_T, block->size);
c53e8ee216904ffe6de4f6518d9f9f5107b7610eTimo Sirainen last_alloc_size = current_frame_block->last_alloc_size[frame_pos];
c53e8ee216904ffe6de4f6518d9f9f5107b7610eTimo Sirainen /* see if we're trying to grow the memory we allocated last */
e4b09b008ab544eb8994beecbfffefa21d855e43Timo Sirainen /* yeah, see if we have space to grow */
1e47cfede3a0b62654105daab00e97b5d660bc6bTimo Sirainen if (current_block->left >= size - last_alloc_size) {
1e47cfede3a0b62654105daab00e97b5d660bc6bTimo Sirainen /* just shrink the available size */
e4b09b008ab544eb8994beecbfffefa21d855e43Timo Sirainen current_block->left -= size - last_alloc_size;
1e47cfede3a0b62654105daab00e97b5d660bc6bTimo Sirainen current_frame_block->last_alloc_size[frame_pos] = size;
4b231ca0bbe3b536acbd350101e183441ce0247aTimo Sirainenvoid *t_buffer_reget(void *buffer, size_t size)
4b231ca0bbe3b536acbd350101e183441ce0247aTimo Sirainen /* we've already reserved the space, now we just mark it used */
1f80b32fc28f7a723ff07c1694230a090808b506Timo Sirainen current_block = mem_block_alloc(INITIAL_STACK_SIZE);
2d49f150b4bce6f2f59a84e268e4777901c3e42cTimo Sirainen StackFrameBlock *frame_block = unused_frame_blocks;
94aa90d2d17a7aebcda5a4193a62e80ddbb169b7Timo Sirainen unused_frame_blocks = unused_frame_blocks->prev;
2a6af811ea3de3cf9e2f15e446674dd21b0705f3Timo Sirainenunsigned int t_push(void)
0c27b881989bc2b391281650ee89a8cc4d89f5e7Timo Sirainenunsigned int t_pop(void)