heapmm.h revision f71323e297a928af368937089d3ed71239786f86
190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* 2f71323e297a928af368937089d3ed71239786f86Andreas Huber * Copyright (c) 2010 The WebM project authors. All Rights Reserved. 390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber * 4f71323e297a928af368937089d3ed71239786f86Andreas Huber * Use of this source code is governed by a BSD-style license 5f71323e297a928af368937089d3ed71239786f86Andreas Huber * that can be found in the LICENSE file in the root of the source 6f71323e297a928af368937089d3ed71239786f86Andreas Huber * tree. An additional intellectual property rights grant can be found 7f71323e297a928af368937089d3ed71239786f86Andreas Huber * in the file PATENTS. All contributing project authors may 8f71323e297a928af368937089d3ed71239786f86Andreas Huber * be found in the AUTHORS file in the root of the source tree. 990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber */ 1090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* This code is in the public domain. 1390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** Version: 1.1 Author: Walt Karas 1490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 1590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 1690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* External header file for Heap Memory Manager. See documentation in 1790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber** heapmm.html. 1890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber*/ 1990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 2090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#undef HMM_PROCESS 2190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 2290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Include once per configuration in a particular translation unit. */ 2390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 2490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifndef HMM_CNFG_NUM 2590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 2690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Default configuration. */ 2790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 2890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifndef HMM_INC_CNFG_DFLT 2990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_INC_CNFG_DFLT 3090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_PROCESS 3190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 3290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 3390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif HMM_CNFG_NUM == 0 3490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 3590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Test configuration. */ 3690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 3790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifndef HMM_INC_CNFG_0 3890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_INC_CNFG_0 3990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_PROCESS 4090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 4190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif HMM_CNFG_NUM == 1 4390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifndef HMM_INC_CNFG_1 4590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_INC_CNFG_1 4690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_PROCESS 4790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 4890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 4990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif HMM_CNFG_NUM == 2 5090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifndef HMM_INC_CNFG_2 5290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_INC_CNFG_2 5390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_PROCESS 5490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 5590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif HMM_CNFG_NUM == 3 5790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 5890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifndef HMM_INC_CNFG_3 5990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_INC_CNFG_3 6090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_PROCESS 6190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 6290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif HMM_CNFG_NUM == 4 6490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 6590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifndef HMM_INC_CNFG_4 6690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_INC_CNFG_4 6790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_PROCESS 6890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 6990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#elif HMM_CNFG_NUM == 5 7190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifndef HMM_INC_CNFG_5 7390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_INC_CNFG_5 7490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#define HMM_PROCESS 7590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 7690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif 7890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 7990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#ifdef HMM_PROCESS 8090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#include "hmm_cnfg.h" 8290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Heap descriptor. */ 8490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Hubertypedef struct HMM_UNIQUE(structure) 8590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber{ 8690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* private: */ 8790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 8890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Pointer to (payload of) root node in AVL tree. This field should 8990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** really be the AVL tree descriptor (type avl_avl). But (in the 9090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** instantiation of the AVL tree generic package used in package) the 9190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** AVL tree descriptor simply contains a pointer to the root. So, 9290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** whenever a pointer to the AVL tree descriptor is needed, I use the 9390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** cast: 9490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** 9590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** (avl_avl *) &(heap_desc->avl_tree_root) 9690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** 9790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** (where heap_desc is a pointer to a heap descriptor). This trick 9890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber ** allows me to avoid including cavl_if.h in this external header. */ 9990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber void *avl_tree_root; 10090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* Pointer to first byte of last block freed, after any coalescing. */ 10290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber void *last_freed; 10390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber /* public: */ 10590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 10690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(size_bau) num_baus_can_shrink; 10790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber void *end_of_shrinkable_chunk; 10890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber} 10990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberHMM_UNIQUE(descriptor); 11090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* Prototypes for externally-callable functions. */ 11290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Hubervoid HMM_UNIQUE(init)(HMM_UNIQUE(descriptor) *desc); 11490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Hubervoid *HMM_UNIQUE(alloc)( 11690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(descriptor) *desc, HMM_UNIQUE(size_aau) num_addr_align_units); 11790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 11890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* NOT YET IMPLEMENTED */ 11990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Hubervoid *HMM_UNIQUE(greedy_alloc)( 12090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(descriptor) *desc, HMM_UNIQUE(size_aau) needed_addr_align_units, 12190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(size_aau) coveted_addr_align_units); 12290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huberint HMM_UNIQUE(resize)( 12490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(descriptor) *desc, void *mem, 12590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(size_aau) num_addr_align_units); 12690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 12790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* NOT YET IMPLEMENTED */ 12890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huberint HMM_UNIQUE(greedy_resize)( 12990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(descriptor) *desc, void *mem, 13090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(size_aau) needed_addr_align_units, 13190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(size_aau) coveted_addr_align_units); 13290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Hubervoid HMM_UNIQUE(free)(HMM_UNIQUE(descriptor) *desc, void *mem); 13490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberHMM_UNIQUE(size_aau) HMM_UNIQUE(true_size)(void *mem); 13690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 13790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas HuberHMM_UNIQUE(size_aau) HMM_UNIQUE(largest_available)( 13890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(descriptor) *desc); 13990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Hubervoid HMM_UNIQUE(new_chunk)( 14190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(descriptor) *desc, void *start_of_chunk, 14290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(size_bau) num_block_align_units); 14390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14490d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Hubervoid HMM_UNIQUE(grow_chunk)( 14590d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(descriptor) *desc, void *end_of_chunk, 14690d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(size_bau) num_block_align_units); 14790d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 14890d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber/* NOT YET IMPLEMENTED */ 14990d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Hubervoid HMM_UNIQUE(shrink_chunk)( 15090d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(descriptor) *desc, 15190d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber HMM_UNIQUE(size_bau) num_block_align_units); 15290d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber 15390d3ed91ae9228e1c8bab561b6138d4cb8c1e4fdAndreas Huber#endif /* defined HMM_PROCESS */ 154