memalloc/ 777 0 0 0 6105270556 5610 5memalloc/FREELIST.CPP 666 0 0 6723 6076533450 7403 /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ #include #include "freelist.h" /* This class supports an unordered list of elements, where all elements are assumed to be the same. Specifically, it supports a "free list" for a memory allocater, where all the elements in the free list are the same size. When items are removed from the list, this object keeps the list "links" for reuse. This reduces the number of times that this object must request more memory when items are frequently added and removed from the list. But it can be a problem if many items are added to the list and then removed, since none of the list memory will be returned to the memory allocater for reuse. */ /* add_to_free_list This function adds "addr" to the free list. When an item is added to a list, it is necessary to allocate a "link" in the list to store information about the item. If there is a free "link" already available from an item that has been previously removed from the list, one of these will be used for the new item. Otherwise a new "link" will be allocated. Once a new linke is available, initialize the link with "addr" and add it to the list. chain_head : a list of free "links" list_head : the list that the new item will be added to */ void freelist::add_to_free_list( void *addr ) { list *new_link; if (addr != NULL) { // don't try to put null pointers in the free list if (chain_head == NULL) { new_link = (list *)get_mem( sizeof( list )); } else { new_link = chain_head; chain_head = chain_head->next; } if (new_link != NULL) { // Initialize the "link" and add it to the free list new_link->addr = addr; new_link->next = list_head; list_head = new_link; } } } // freelist::add_to_free_list /* get_from_free_list Get an item from the free list or return NULL if the list is empty. If the item is retrieved from the free list, add the now unused "link" to the "chain" list, so that it can be reused later, when another item is added to the list. */ void *freelist::get_from_free_list(void) { void *new_elem = NULL; if (list_head != NULL) { list *free_link = list_head; // get the address of the free memory and unlink the list "link". new_elem = list_head->addr; list_head = list_head->next; // Add the list link to the free link chain free_link->next = chain_head; chain_head = free_link; } return new_elem; } // freelist::get_from_free_list // // get_mem // // Memory allocater for the freelist object. The derived class must // supply this function. // void *freelist::get_mem( unsigned int num_bytes ) { printf("freelist::get_mem: no memory allocation function for class\n"); return (void *)NULL; } memalloc/FREELIST.H 666 0 0 4203 6076533672 7145 #ifndef FREELIST_H #define FREELIST_H /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ #include /* Freelist object. This object is designed to support deallocation (free) and reallocation of memory objects that are all of a constant size. The size is set in the constructor. This allows the object to be queried about its size. However, no check is made to make sure that the objects added to, or removed from, the free list are the proper size. The get_from_free_list function picks an item off the free list and returns its address. If there is no item on the free list, NULL is returned. The add_to_free_list function adds "addr" to the free list. The virtual function get_mem must be implemented by the class that inherit this object to provide memory for the free list chain. The list_head chain is the free list. The chain_head is a chain that is kept for unused list "links". */ class freelist { private: // private typedefs and class variables typedef struct list_struct { void *addr; list_struct *next; } list; list *list_head; list *chain_head; unsigned int obj_size; public: freelist(int obj_syze ) { obj_size = obj_syze; list_head = NULL; chain_head = NULL; } unsigned int get_obj_size(void) { return obj_size; } void add_to_free_list( void *addr ); void *get_from_free_list(void); virtual void *get_mem( unsigned int num_bytes ); }; // class freelist #endif memalloc/MEM.CPP 666 0 0 3702 6100341674 6567 /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ #include #include #include "mem.h" // // mem_alloc // // Allocate memory, either from the free list or from page pool // memory. Put block size in the hash table, using the block // address as the key. // void *mem_manage::mem_alloc( unsigned int num_bytes ) { void *mem = NULL; static int cnt; cnt++; // search_free_list returns a pointer (if there is memory in the free // list) and returns "num_bytes" with the actual size of the allocated // memory. Note that the num_bytes that is placed in the hash table // is the actual size of the memory block, which may be larger than // the original request. Potentially this can waste memory. // mem = search_list( num_bytes ); if (mem == NULL) { mem = page_alloc( num_bytes ); } if (mem != NULL) { put_in_hash( mem, num_bytes ); } return mem; } // mem_manage::mem_alloc // // mem_free // // Place the memory in the free list. The size of the block is looked // up in the hash table. // void mem_manage::mem_free( void *addr ) { unsigned int size; size = get_from_hash( addr ); if (size == 0) { printf("mem_manage::free_mem: could not find addr in alloc list\n"); } else { add_to_list( addr, size ); } } // mem_manage::free_mem memalloc/MEM.H 666 0 0 4704 6100341544 6333 #ifndef MEM_H #define MEM_H /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ /* The mem_manage object supports memory allocation, deallocation and reuse. It is built on top of the page_pool memory allocater, which uses large block allocation. The memory allocation code uses a hash table to keep track of the size of allocated block. The hash table support is provided by the hash object. Another way to keep track of the size of an allocated block is to store its size, along with the block itself. The pointer to the allocated memory then points to the word ahead of the allocation size word. This has the potential disadvantage of being sensitive to application bugs that corrupt the block size. By storing the block size elsewhere, the memory allocator may be more robust. A second alternative is to provide a "check sum" word, along with the block size. When a block is freed, the "check sum" work is check to flag memory corruption. In addition, a function can be implemented to walk through the allocated block chain, checking for corrupted memory block values. In retrospect, I would probably use this algorithm, since the hash table has such high overhead (in both time and memory space). What is really amazing is that even with all this overhead, this memory allocater is faster than Microsoft's "malloc" on Windows NT. */ #include "pagepool.h" #include "hash.h" class mem_manage : public page_pool, public hash { private: // typedefs and variables typedef enum { min_block_size = 4 * sizeof(float) } mem_const; protected: void *get_mem( unsigned int num_bytes ) { return page_alloc( num_bytes ); } public: // class functions void *mem_alloc( unsigned int num_bytes ); void mem_free( void *addr ); }; // class mem_manage #endif memalloc/ORDLIST.CPP 666 0 0 7161 6100342342 7265 /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ #include #include #include "ordlist.h" // ordered_list // // Note: The destructor for this class does not deallocate the list // (although it does deallocate the sentinal). This class is // written with the assumption that memory will be deallocated // by the class which inherits this class and provides the memory // allocation function get_mem. // // New is used to allocate the sentinal, since the constructor // for the memory allocator may not have been called yet. // ordered_list::ordered_list(void) { list_elem *tmp; // Create an empty "sentinal" structure to start sorted linked list. // This simplifies the list search and insert algorithm. tmp = new list_elem; tmp->size = 0; tmp->mem = NULL; tmp->next = NULL; free_list = tmp; } // ordered_list constructor // // ~ordered_list // // Make sure that we delete the sentinal, to avoid a memory leak // ordered_list::~ordered_list(void) { delete free_list; } // // search_list // // Search the ordered list for a block whose size is greater than // or equal to the num_bytes argument. Since the block may be // larger, num_bytes is returned with the actual block size. // The function returns the address of the block. // void *ordered_list::search_list( unsigned int &num_bytes ) { list_elem *listptr, *trail; void *retmem = NULL; listptr = free_list; trail = free_list; while (listptr->size < num_bytes && listptr->next != NULL) { trail = listptr; listptr = listptr->next; } if (listptr->size >= num_bytes) { // unlink the memory from the free list and return it num_bytes = listptr->size; retmem = listptr->mem; trail->next = listptr->next; } return retmem; } // // add_to_list // // Add a memory block to the ordered list. // void ordered_list::add_to_list(void *addr, unsigned int size ) { list_elem *listptr, *new_block, *trail; listptr = free_list; trail = free_list; while (listptr->size < size && listptr->next != NULL) { trail = listptr; listptr = listptr->next; } new_block = (list_elem *)get_mem(sizeof( list_elem )); new_block->size = size; new_block->mem = addr; if (listptr->size <= size) { new_block->next = listptr->next; listptr->next = new_block; } else { // listptr->size > size trail->next = new_block; new_block->next = listptr; } } // ordered_list::add_to_free_list // // print_list // // A debug function: print the ordered list. // void ordered_list::print_list(void) { list_elem *listptr; listptr = free_list; while (listptr != NULL) { printf("%d (%0x)", listptr->size, listptr->mem ); listptr = listptr->next; } // while printf("\n"); } // ordered_list::print_free_list void *ordered_list::get_mem( unsigned int num_bytes) { printf("ordered_list::get_mem: no mem. allocation function provided\n"); return NULL; } memalloc/ORDLIST.H 666 0 0 2477 6100342200 7030 #ifndef ORDLIST_H #define ORDLIST_H /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ /* The ordered_list object supports an ordered list (e.g., least to most). The get_mem function is virtual, allowing the class that inherits this one to determine how memory is allocated. */ class ordered_list { typedef struct ordered_list_struct { unsigned int size; void *mem; ordered_list_struct *next; } list_elem; list_elem *free_list; public: ordered_list(void); ~ordered_list(void); void *search_list( unsigned int &num_bytes ); void add_to_list(void *addr, unsigned int size ); void print_list(void); virtual void *get_mem( unsigned int num_bytes ); }; #endif memalloc/PAGEPOOL.CPP 666 0 0 14207 6100035520 7367 /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ #include #include #include "pagepool.h" // // Get the system page size by calling the Windows NT function GetSystemInfo. // This function is system dependant and must be rewritten for a non-Win32 // platform, like UNIX (live free or die). // // This function is used to initialize the static class variable page_size. // unsigned int page_pool::GetSysPageSize( void ) { SYSTEM_INFO sys_info; // system info structure, defined in windows.h GetSystemInfo( &sys_info ); return sys_info.dwPageSize; } // page_pool::GetSysPageSize unsigned int page_pool::page_size = page_pool::GetSysPageSize(); // // page_pool object constructor. Set up the page list pointers and allocate // an initial page of memory. // page_pool::page_pool(void) { page_chain *new_link; new_link = new_block( page_size ); page_list_head = new_link; current_page = new_link; } // page_pool constructor // // page_pool destructor // // This function moves through the link list of memory pages and // deallocates them. // page_pool::~page_pool(void) { page_chain *tmp; while (page_list_head != NULL) { free( page_list_head->block ); tmp = page_list_head; page_list_head = page_list_head->next_page; free( tmp ); } } // // virtual function add_to_list // // User defined ordered list function. This function is optional. // If the memory allocater built on top of the page_pool object supports // allocation, deallocation and reallocation, a free list can be added // to reduce fragementation in the memory allocated by the page_pool // allocator. // void page_pool::add_to_list(void *addr, unsigned int size) { // Don't do anything... } // add_to_free_list // // new_block // // The new_block function is the "root" memory allocator for the // page_pool object. The amount of memory allocated is rounded up // to the next "page_size" boundary. // page_pool::page_chain *page_pool::new_block( unsigned int block_size ) { page_chain *new_link = NULL; int alloc_amt; // round to the nearest page size alloc_amt = ((block_size + (page_size-1)) / page_size) * page_size; if (alloc_amt <= max_block_size) { new_link = (page_chain *)malloc( sizeof( page_chain ) ); if (new_link != NULL) { new_link->block = (void *)malloc( alloc_amt ); new_link->bytes_used = 0; new_link->block_size = alloc_amt; new_link->next_page = NULL; } else { printf("page_pool::page_chain: malloc memory allocation error\n"); } } else { printf("page_pool::new_block: allocation request too large\n"); } return new_link; } // page_chain::new_block // // add_block // // This function is called when the amount of memory requested by page_alloc // will not fit in the current block. If the amount of free memory in // the current block is larger than a minimum allocation value // (min_block_size) this free memory is place in the free list // by calling add_to_list, which is a virtual function. // void *page_pool::add_block( unsigned int block_size ) { page_chain *new_page = NULL; page_chain *last_page; int bytes_free; last_page = current_page; new_page = new_block( block_size ); current_page->next_page = new_page; current_page = new_page; bytes_free = last_page->block_size - last_page->bytes_used; // if there is unused memory in the block and it is larger than the minimum // allocation block, put it in the free list, to avoid fragmentation. if (bytes_free >= min_block_size) { void *addr; addr = (void *)((unsigned int)last_page->block + last_page->bytes_used); last_page->bytes_used += bytes_free; add_to_list(addr, bytes_free); // Add to the ordered free list } return (void *)new_page; } // page_chain::add_block // // page_alloc // // This function is called to allocate memory from the page_pool object // memory pool. If there is enough free memory in the current block to // satisify the memory request, memory is allocated from the current // block and the amount of free memory is updated. If the current block // does not have enough memory, add_block is called to allocate a new memory // block which will be large enough. // void *page_pool::page_alloc( unsigned int num_bytes ) { void *addr = NULL; unsigned int amt_free = current_page->block_size - current_page->bytes_used; if (num_bytes > amt_free) { if (add_block( num_bytes ) != NULL) { amt_free = current_page->block_size; } } if (amt_free >= num_bytes) { addr = (void *)((unsigned int)current_page->block + current_page->bytes_used); current_page->bytes_used += num_bytes; } else { printf("page_pool::page_alloc: allocation error\n"); exit(1); } return addr; } // page_pool::page_alloc // // print_page_pool_info // // Print information about the page pool // void page_pool::print_page_pool_info(void) { int total_allocated = 0; int total_unused = 0; page_chain *ptr = page_list_head; printf("[block size, bytes_used]\n"); while (ptr != NULL) { printf("[%4d, %4d]", ptr->block_size, ptr->bytes_used); total_allocated += ptr->bytes_used; total_unused += (ptr->block_size - ptr->bytes_used); if (ptr->next_page != NULL) { printf(", "); } else { printf("\n"); } ptr = ptr->next_page; } // while printf("Total allocated = %5d, total unused = %3d\n", total_allocated, total_unused ); } memalloc/PAGEPOOL.H 666 0 0 5506 6100334524 7124 #ifndef PAGEPOOL_H #define PAGEPOOL_H /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ /* The page_pool object is designed to support rapid memory allocation and deallocation of all allocated memory, once the object is no longer needed. By using a block allocation scheme, the overhead of memory allocation is greatly reduced, compared to "malloc" (or new). Deallocation of large blocks of memory is also much faster than calling free for every allocated block of memory. The page_pool allocator allocates blocks of memory in "page_size" increments. The page_size variable is set at start-up and contains the system virtual memory page size. The page_pool object contains the virtual function "add_to_list" which, in this case, is implemented by the inherited function ordered_list. Ordered list is a class that supports ordered list insertion and deletion. In this case, this is used to support an ordered list of free memory blocks. The ordered list is only needed if the page_pool is used as the base for a memory allocater that can allocate from a free list. */ #include "ordlist.h" class page_pool : public ordered_list { private: // typedefs and variables typedef struct page_chain_struct { void *block; unsigned int bytes_used; unsigned int block_size; page_chain_struct *next_page; } page_chain; // The min_block_size is the smallest block that will be returned by the // page_pool allocater. The max_block_size is the largest memory block // that can be requested. Ideally, this should be a multiple of the page // size. typedef enum { min_block_size = 96, max_block_size = 1024 * 8 } bogus; page_chain *page_list_head; page_chain *current_page; static unsigned int page_size; // system page size, shared by all instances private: // class functions static unsigned int GetSysPageSize(void); page_chain *new_block( unsigned int block_size ); void *add_block( unsigned int block_size ); public: // class functions page_pool(void); ~page_pool(void); void *page_alloc( unsigned int block_size ); void print_page_pool_info(void); virtual void add_to_list(void *addr, unsigned int size); }; // class page_pool #endif memalloc/HASH.CPP 666 0 0 3316 6100340242 6663 #include #include #include "hash.h" // // get_tree_mem // // Check to see if there is a free tree node in the free list. If so, // reuse it for the newly allocated has element. If not, call the // virtual function get_mem to allocate a new tree node. // binary_tree::bi_tree_ptr hash::get_tree_mem(void) { binary_tree::bi_tree_ptr retptr; retptr = (bi_tree_ptr)get_from_free_list(); if (retptr == NULL) { retptr = (bi_tree_ptr)get_mem( sizeof( bi_tree ) ); } return retptr; } void *hash::get_mem( unsigned int num_bytes ) { printf("hash::get_mem: no virtual function for this class\n"); return NULL; } // // Use a shift algorithm to distribute the key (e.g., make it more // pseudo-random). I actually tried several different algorithms to // do this and this one worked the best. It was suggested by // Brent Gregory at Synopsys, although any mistakes in translating his // suggestion to code are mine. The code below is a loop, which has // been in-lined for speed. // unsigned int hash::hash_value( unsigned int val ) { unsigned int new_val; new_val = val ^ (val << 1); new_val = new_val ^ (val << 2); new_val = new_val ^ (val << 3); new_val = new_val ^ (val << 4); new_val = new_val ^ (val << 5); new_val = new_val ^ (val << 6); new_val = new_val ^ (val << 7); new_val = new_val ^ (val << 8); new_val = new_val ^ (val << 9); new_val = new_val ^ (val << 10); new_val = new_val ^ (val << 11); new_val = new_val ^ (val << 12); new_val = new_val ^ (val << 13); new_val = new_val ^ (val << 14); new_val = new_val ^ (val << 15); new_val = new_val ^ (val << 16); return new_val; } // hash memalloc/HASH.H 666 0 0 6406 6100337734 6447 #ifndef HASH_H #define HASH_H #include "freelist.h" #include "bitree.h" /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ /* This object implements a hash table using a binary tree. The advantage of this implementation is that it is more memory efficient than a hash algorithm that uses an array. The tree has no wasted space, as the array does. The disadvantage is performance. Hash accesses are slower than they would be for a balanced tree and considerably slower than an array based hash table (although this object is still faster than the Microsoft VC++ malloc memory allocator). If the binary tree that this hash function is based on were always perfectly balanced, one access to the tree would require log2(N) operations, on average (where N is the number of elements in the tree). For M access, this will be M * log2(N), which is better than N^2, but not nearly as good as M for a true hash table. In practice, the performance is even worse. Balanced binary trees (AVL trees) require a fair amount of code to implement, so there is a computation time cost. If the tree is not an AVL tree (which is always balanced), the keys can be randomized (see the hash_value function). However, for sequentially increasing keys, it is very difficult to come up with a function that will map a set of sequential numbers into a set of pseudo-random numbers. So for a set of sequential numbers the tree will have branches much longer than log2(N) (the max_branch_size function in the binary_tree object can be used to print the maximum branch for a given tree). This class uses the freelist object to keep track of deallocated tree nodes. This class is inherited, rather than used as a class variable, because its memory allocater (get_mem) is a virtual function. Using a virtual function for the memory allocater allows the user of the class to decide how memory will be allocated. */ class hash : public binary_tree, public freelist { private: // class functions unsigned int hash_value( unsigned int val ); public: // class functions // hash(void) { } hash(void) : freelist( sizeof( bi_tree) ) {} void put_in_hash(void *addr, unsigned int num_bytes ) { tree_insert(hash_value((unsigned int)addr), num_bytes); } unsigned int get_from_hash( void *addr ) { return tree_delete(hash_value((unsigned int)addr) ); } binary_tree::bi_tree_ptr get_tree_mem(void); void free_tree_mem(binary_tree::bi_tree_ptr node) { add_to_free_list( (void *)node ); } virtual void *get_mem( unsigned int num_bytes ); }; // class hash #endif memalloc/BITREE.CPP 666 0 0 22457 6076524316 7163 #include #include "ianstd.h" #include "bitree.h" /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ /* binary_tree class functions This file contains class functions a the binary_tree object, which supports ordered binary tree search, insert and delete. The tree is ordered so that the left branch of a tree node contains values that are less than the current tree node, the right branch contains values that are greater. The tree does not support multiple instances of the same key. */ // bi_tree_init // // Allocate and initialize a binary tree element. // binary_tree::bi_tree_ptr binary_tree::bi_tree_init(unsigned int key, unsigned int val) { bi_tree_ptr tmp = (bi_tree_ptr)get_tree_mem(); tmp->key = key; tmp->val = val; tmp->leftptr = NULL; tmp->rightptr = NULL; return tmp; } // // bi_tree_insert // // Insert a new value into the ordered binary tree. Note that if the // element is found in the tree, it is treated as an error. // void binary_tree::bi_tree_insert(bi_tree_ptr &root, unsigned int key, unsigned int val ) { if (root == NULL) { // the tree is empty root = bi_tree_init(key, val); } else { if (root->key > key) bi_tree_insert(root->leftptr, key, val); // search down left branch else if (root->key < key) bi_tree_insert(root->rightptr, key, val); // search down right branch else { // key == root->key printf("binary_tree::bi_tree_insert: key %d already found in tree\n", key ); } } } // bi_tree_insert // // unlink // // When a value is removed from an ordered binary tree and the value // has children, it will be replaced by the next value in the right // sub-branch which is greater. This value will be the last (terminal) // value in the left branch of the right tree. // // The unlink function walks down a subtree's left branch until it gets // to the end. It removes the value at the end of the branch and // returns it (so it can be inserted into the "hole" left the deleted // value). If the value at the end of the left branch has a right // branch child, replace it with the right branch child. // binary_tree::bi_tree_ptr binary_tree::unlink(bi_tree_ptr &root) { bi_tree_ptr node; node = root; if (root != NULL) { if (root->leftptr != NULL) { node = unlink(root->leftptr); } else { if (root->rightptr != NULL) { // if there is a right branch child root = root->rightptr; // replace the node at the end of } // the left branch with this child. else root = NULL; // no children } } return node; } /* bi_tree_delete This function searches a binary tree for "key" and deletes the item from the tree. The ordering of the tree is maintained (see below). If "key" is found, this function deallocates the node and returns the "val" field. If "key" is not found, the function returns zero. When the node is found in the tree there are three possible cases: - The node is a leaf node (no children). In this case the node can simply be unlinked from the tree and returned. - The node has one child. In this case, the node is replaced by its child node. - The node has two children. In this case the node is replaced by the least value from the right branch. This value is found by taking the right branch, and then walking down the left branch (see the unlink function, above). The value found this way should be the next greatest value in the tree. */ unsigned int binary_tree::bi_tree_delete(bi_tree_ptr &root, unsigned int key ) { unsigned int retval = 0; if (root != NULL) { if (root->key > key) retval = bi_tree_delete(root->leftptr, key); else if (root->key < key) retval = bi_tree_delete(root->rightptr, key); else { // the keys are equal bi_tree_ptr node = NULL; bi_tree_ptr new_child = NULL; int num_children = 0; node = root; retval = root->val; // Count the children of the node if (root->leftptr != NULL) { num_children++; new_child = root->leftptr; } if (root->rightptr != NULL) { num_children++; new_child = root->rightptr; } switch (num_children) { case 0: root = NULL; break; case 1: root = new_child; // Replace the node with its child break; case 2: { bi_tree_ptr tmp1, tmp2; // find the next greater node in the tree and unlink it tmp1 = root->rightptr; tmp2 = unlink(tmp1); // Connect the new node to any children, but make sure that // we don't point a node at itself. if (root->leftptr != tmp2) tmp2->leftptr = root->leftptr; if (root->rightptr != tmp2) tmp2->rightptr = root->rightptr; root = tmp2; } break; } // switch free_tree_mem( node ); } // keys are equal } // root != NULL return retval; } // bi_tree_delete /* ------------------- Class functions for debugging --------------- */ // // Code for displaying the contents of the tree (mainly for debugging // and verification). // void binary_tree::print_spaces(unsigned int indent) { const int BufSize = 80; char buf[BufSize+1]; int i; if (indent > BufSize) indent = BufSize; for (i = 0; i < (int)indent; i++) { buf[i] = ' '; } buf[indent] = '\0'; printf("%s", buf); } // // bi_tree_print // // Print the binary tree in "landscape" form (e.g., down the length // of an infinite page). // void binary_tree::bi_tree_print(bi_tree_ptr root, unsigned int indent) { if (root != NULL) { print_spaces(indent); printf("%d\n", root->key ); if (root->leftptr != NULL) bi_tree_print(root->leftptr, indent+4); else { print_spaces(indent+4); printf("null\n"); } if (root->rightptr != NULL) bi_tree_print(root->rightptr, indent+4); else { print_spaces(indent+4); printf("null\n"); } } } // // bi_tree_print_sorted // // Print the contents of the binary tree in sorted, increasing, order. // void binary_tree::bi_tree_print_sorted(bi_tree_ptr root) { if (root != NULL) { bi_tree_print_sorted(root->leftptr); printf("%d ", root->key ); bi_tree_print_sorted(root->rightptr); } } // // bi_tree_max_branch // // This binary tree is not an AVL tree (e.g., a self balancing binary tree). // As a result, the shape of the tree and the efficiency of tree search // is heavily dependant on the distribution of the input values. The // more evenly (randomly) these values are distributed, the closer the // tree shape will be to a balanced tree and the close the search time // will be to log2(N). This function will return the size of the longest // branch in the tree. This is useful for estimating the worst case // performance for a given data set. // unsigned int binary_tree::bi_tree_max_branch(bi_tree_ptr root ) { unsigned int depth = 0; if (root != NULL) { unsigned int depth_left = 0; unsigned int depth_right = 0; if (root->leftptr != NULL) depth_left = bi_tree_max_branch(root->leftptr); if (root->rightptr != NULL) depth_right = bi_tree_max_branch(root->rightptr); // depth = max(depth_left, depth_right) if (depth_left > depth_right) depth = depth_left; else depth = depth_right; depth++; // Add one for the current node } return depth; } // binary_tree::bi_tree_max_branch // // This function returns the number of elements in the subtree "root". // // The number of elements in the (sub)tree whose root is "root" is // the count of the left branch, plus the count of the right branch, // plus one (for the current node). This function can be useful in // testing to make sure that no elements are "lost". // unsigned int binary_tree::bi_tree_cnt(bi_tree_ptr root) { unsigned int cnt = 0; if (root != NULL) { cnt = bi_tree_cnt(root->leftptr) + bi_tree_cnt(root->rightptr) + 1; } return cnt; } // binary_tree::bi_tree_cnt /* ------------------- Defaults for virtual functions --------------- */ // // The class derived from the binary tree object should supply memory // allocation and deallocation functions. // binary_tree::bi_tree_ptr binary_tree::get_tree_mem(void) { printf("binary_tree::get_tree_mem: no memory alloc provided for class\n"); return (bi_tree_ptr)NULL; } void binary_tree::free_tree_mem( bi_tree_ptr addr ) { printf("binary_tree::free_tree_mem: no memory dealloc provided for class\n"); } memalloc/BITREE.H 666 0 0 5535 6076524770 6712 #ifndef BITREE_H #define BITREE_H #include #include "ianstd.h" /*==================================================================== This software was written by Ian L. Kaplan, Chief Fat Bear, Bear Products International. Use of this software, for any purpose, is granted on two conditions: 1. This copyright notice must be included with the software or any software derived from it. 2. The risk of using this software is accepted by the user. No warranty as to its usefulness or functionality is provided or implied. The author and Bear Products International provides no support. ====================================================================*/ /* binary_tree class definition This class supports insertion and deletion of elements in a simple binary tree (e.g., the tree is not self balancing). The class provides two public functions: tree_insert - insert values into the binary tree tree_delete - delete values from the binrary tree The class derived from this class must supply instances of two virtual functions: get_tree_mem - allocate memory for the binary tree free_tree_mem - deallocate memory for the binary tree Several public functions are also provided for debugging (see bitree.cpp) */ class binary_tree { protected: typedef struct bi_tree_struct { unsigned int key; unsigned int val; bi_tree_struct *leftptr, *rightptr; } bi_tree; public: typedef bi_tree *bi_tree_ptr; private: bi_tree_ptr root; private: // debug functions void bi_tree_print(bi_tree_ptr root, unsigned int indent); void print_spaces(unsigned int indent); void bi_tree_print_sorted(bi_tree_ptr root); unsigned int bi_tree_max_branch( bi_tree_ptr root ); unsigned int bi_tree_cnt( bi_tree_ptr root ); public: // debug functions void print_tree(void) { bi_tree_print( root, 0 ); } void print_sorted(void) { bi_tree_print_sorted( root ); } unsigned int max_branch_size(void) { return bi_tree_max_branch(root); } unsigned int count_tree(void) { return bi_tree_cnt(root); } private: bi_tree_ptr unlink(bi_tree_ptr &root); bi_tree_ptr bi_tree_init(unsigned int key, unsigned int val); void bi_tree_insert(bi_tree_ptr &root, unsigned int key, unsigned int val); unsigned int bi_tree_delete(bi_tree_ptr &root, unsigned int key ); public: binary_tree(void) { root = NULL; } void tree_insert( unsigned int key, unsigned int val ) { bi_tree_insert(root, key, val); } unsigned int tree_delete( unsigned int key ) { return bi_tree_delete(root, key ); } virtual bi_tree_ptr get_tree_mem(void); virtual void free_tree_mem( bi_tree_ptr node ); }; // class binary_tree #endif memalloc/IANSTD.H 666 0 0 760 6027204616 6663 #ifndef IANSTD_H #define IANSTD_H // These rather convoluted ifndef's are required because both FALSE, TRUE // and BOOLEAN are defined by various windows and windows/nt headers. When // these headers are included, a redefine error results without these ifndefs. // typedef enum { #ifndef FALSE FALSE = 0, #endif #ifndef TRUE TRUE = 1, #endif BOGUS} BoolVals; #ifndef _WINNT_ typedef int BOOLEAN; #endif #endif memalloc/MAIN.CPP 666 0 0 2236 6105275752 6706 #include #include #include #include "mem.h" const int NumAllocs = 10000; // // Note: the timeGetTime are Windows NT millisecond timer functions. // Although it is not documented, these functions are in the winmm.lib // library. This must be included in the project settings. // int my_mem_alloc(void) { const int AllocAmt = 64; int TimeStart, TimeEnd, TimeDelta; mem_manage mem; int i; TimeStart = timeGetTime(); for (i = 0; i < NumAllocs; i++) { mem.mem_alloc( AllocAmt ); } TimeEnd = timeGetTime(); TimeDelta = TimeEnd - TimeStart; printf("%d mem_allocs = %d\n", NumAllocs, TimeDelta ); // mem.print_tree(); printf("maximum binary tree branch = %d\n", mem.max_branch_size() ); printf("number of element in the tree (should be %d) = %d\n", NumAllocs, mem.count_tree()); return timeGetTime(); // start time for destructor } void main(void) { int TimeStart, TimeEnd, TimeDelta; TimeStart = my_mem_alloc(); TimeEnd = timeGetTime(); // Destructor completed TimeDelta = TimeEnd - TimeStart; printf("destructor = %d\n", TimeDelta ); } memalloc/MEMALLOC.MAK 666 0 0 21052 6105276334 7353 # Microsoft Developer Studio Generated NMAKE File, Format Version 4.00 # ** DO NOT EDIT ** # TARGTYPE "Win32 (x86) Console Application" 0x0103 !IF "$(CFG)" == "" CFG=memalloc - Win32 Debug !MESSAGE No configuration specified. Defaulting to memalloc - Win32 Debug. !ENDIF !IF "$(CFG)" != "memalloc - Win32 Release" && "$(CFG)" !=\ "memalloc - Win32 Debug" !MESSAGE Invalid configuration "$(CFG)" specified. !MESSAGE You can specify a configuration when running NMAKE on this makefile !MESSAGE by defining the macro CFG on the command line. For example: !MESSAGE !MESSAGE NMAKE /f "memalloc.mak" CFG="memalloc - Win32 Debug" !MESSAGE !MESSAGE Possible choices for configuration are: !MESSAGE !MESSAGE "memalloc - Win32 Release" (based on\ "Win32 (x86) Console Application") !MESSAGE "memalloc - Win32 Debug" (based on "Win32 (x86) Console Application") !MESSAGE !ERROR An invalid configuration is specified. !ENDIF !IF "$(OS)" == "Windows_NT" NULL= !ELSE NULL=nul !ENDIF ################################################################################ # Begin Project # PROP Target_Last_Scanned "memalloc - Win32 Debug" CPP=cl.exe RSC=rc.exe !IF "$(CFG)" == "memalloc - Win32 Release" # PROP BASE Use_MFC 0 # PROP BASE Use_Debug_Libraries 0 # PROP BASE Output_Dir "Release" # PROP BASE Intermediate_Dir "Release" # PROP BASE Target_Dir "" # PROP Use_MFC 0 # PROP Use_Debug_Libraries 0 # PROP Output_Dir "Release" # PROP Intermediate_Dir "Release" # PROP Target_Dir "" OUTDIR=.\Release INTDIR=.\Release ALL : "$(OUTDIR)\memalloc.exe" CLEAN : -@erase ".\Release\memalloc.exe" -@erase ".\Release\pagepool.obj" -@erase ".\Release\mem.obj" -@erase ".\Release\bitree.obj" -@erase ".\Release\main.obj" -@erase ".\Release\ordlist.obj" -@erase ".\Release\hash.obj" -@erase ".\Release\freelist.obj" "$(OUTDIR)" : if not exist "$(OUTDIR)/$(NULL)" mkdir "$(OUTDIR)" # ADD BASE CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /YX /c # ADD CPP /nologo /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /YX /c CPP_PROJ=/nologo /ML /W3 /GX /O2 /D "WIN32" /D "NDEBUG" /D "_CONSOLE"\ /Fp"$(INTDIR)/memalloc.pch" /YX /Fo"$(INTDIR)/" /c CPP_OBJS=.\Release/ CPP_SBRS= # ADD BASE RSC /l 0x409 /d "NDEBUG" # ADD RSC /l 0x409 /d "NDEBUG" BSC32=bscmake.exe # ADD BASE BSC32 /nologo # ADD BSC32 /nologo BSC32_FLAGS=/nologo /o"$(OUTDIR)/memalloc.bsc" BSC32_SBRS= LINK32=link.exe # ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /machine:I386 # ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib winmm.lib /nologo /subsystem:console /machine:I386 LINK32_FLAGS=kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib\ advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib\ odbccp32.lib winmm.lib /nologo /subsystem:console /incremental:no\ /pdb:"$(OUTDIR)/memalloc.pdb" /machine:I386 /out:"$(OUTDIR)/memalloc.exe" LINK32_OBJS= \ "$(INTDIR)/pagepool.obj" \ "$(INTDIR)/mem.obj" \ "$(INTDIR)/bitree.obj" \ "$(INTDIR)/main.obj" \ "$(INTDIR)/ordlist.obj" \ "$(INTDIR)/hash.obj" \ "$(INTDIR)/freelist.obj" "$(OUTDIR)\memalloc.exe" : "$(OUTDIR)" $(DEF_FILE) $(LINK32_OBJS) $(LINK32) @<< $(LINK32_FLAGS) $(LINK32_OBJS) << !ELSEIF "$(CFG)" == "memalloc - Win32 Debug" # PROP BASE Use_MFC 0 # PROP BASE Use_Debug_Libraries 1 # PROP BASE Output_Dir "Debug" # PROP BASE Intermediate_Dir "Debug" # PROP BASE Target_Dir "" # PROP Use_MFC 0 # PROP Use_Debug_Libraries 1 # PROP Output_Dir "Debug" # PROP Intermediate_Dir "Debug" # PROP Target_Dir "" OUTDIR=.\Debug INTDIR=.\Debug ALL : "$(OUTDIR)\memalloc.exe" CLEAN : -@erase ".\Debug\vc40.pdb" -@erase ".\Debug\vc40.idb" -@erase ".\Debug\memalloc.exe" -@erase ".\Debug\ordlist.obj" -@erase ".\Debug\hash.obj" -@erase ".\Debug\freelist.obj" -@erase ".\Debug\pagepool.obj" -@erase ".\Debug\bitree.obj" -@erase ".\Debug\mem.obj" -@erase ".\Debug\main.obj" -@erase ".\Debug\memalloc.ilk" -@erase ".\Debug\memalloc.pdb" "$(OUTDIR)" : if not exist "$(OUTDIR)/$(NULL)" mkdir "$(OUTDIR)" # ADD BASE CPP /nologo /W3 /Gm /GX /Zi /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /YX /c # ADD CPP /nologo /W3 /Gm /GX /Zi /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE" /YX /c CPP_PROJ=/nologo /MLd /W3 /Gm /GX /Zi /Od /D "WIN32" /D "_DEBUG" /D "_CONSOLE"\ /Fp"$(INTDIR)/memalloc.pch" /YX /Fo"$(INTDIR)/" /Fd"$(INTDIR)/" /c CPP_OBJS=.\Debug/ CPP_SBRS= # ADD BASE RSC /l 0x409 /d "_DEBUG" # ADD RSC /l 0x409 /d "_DEBUG" BSC32=bscmake.exe # ADD BASE BSC32 /nologo # ADD BSC32 /nologo BSC32_FLAGS=/nologo /o"$(OUTDIR)/memalloc.bsc" BSC32_SBRS= LINK32=link.exe # ADD BASE LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib /nologo /subsystem:console /debug /machine:I386 # ADD LINK32 kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib odbccp32.lib winmm.lib /nologo /subsystem:console /debug /machine:I386 LINK32_FLAGS=kernel32.lib user32.lib gdi32.lib winspool.lib comdlg32.lib\ advapi32.lib shell32.lib ole32.lib oleaut32.lib uuid.lib odbc32.lib\ odbccp32.lib winmm.lib /nologo /subsystem:console /incremental:yes\ /pdb:"$(OUTDIR)/memalloc.pdb" /debug /machine:I386\ /out:"$(OUTDIR)/memalloc.exe" LINK32_OBJS= \ "$(INTDIR)/ordlist.obj" \ "$(INTDIR)/hash.obj" \ "$(INTDIR)/freelist.obj" \ "$(INTDIR)/pagepool.obj" \ "$(INTDIR)/bitree.obj" \ "$(INTDIR)/mem.obj" \ "$(INTDIR)/main.obj" "$(OUTDIR)\memalloc.exe" : "$(OUTDIR)" $(DEF_FILE) $(LINK32_OBJS) $(LINK32) @<< $(LINK32_FLAGS) $(LINK32_OBJS) << !ENDIF .c{$(CPP_OBJS)}.obj: $(CPP) $(CPP_PROJ) $< .cpp{$(CPP_OBJS)}.obj: $(CPP) $(CPP_PROJ) $< .cxx{$(CPP_OBJS)}.obj: $(CPP) $(CPP_PROJ) $< .c{$(CPP_SBRS)}.sbr: $(CPP) $(CPP_PROJ) $< .cpp{$(CPP_SBRS)}.sbr: $(CPP) $(CPP_PROJ) $< .cxx{$(CPP_SBRS)}.sbr: $(CPP) $(CPP_PROJ) $< ################################################################################ # Begin Target # Name "memalloc - Win32 Release" # Name "memalloc - Win32 Debug" !IF "$(CFG)" == "memalloc - Win32 Release" !ELSEIF "$(CFG)" == "memalloc - Win32 Debug" !ENDIF ################################################################################ # Begin Source File SOURCE=.\pagepool.cpp DEP_CPP_PAGEP=\ ".\pagepool.h"\ ".\ordlist.h"\ "$(INTDIR)\pagepool.obj" : $(SOURCE) $(DEP_CPP_PAGEP) "$(INTDIR)" # End Source File ################################################################################ # Begin Source File SOURCE=.\ordlist.cpp DEP_CPP_ORDLI=\ ".\ordlist.h"\ "$(INTDIR)\ordlist.obj" : $(SOURCE) $(DEP_CPP_ORDLI) "$(INTDIR)" # End Source File ################################################################################ # Begin Source File SOURCE=.\mem.cpp DEP_CPP_MEM_C=\ ".\mem.h"\ ".\pagepool.h"\ ".\hash.h"\ ".\ordlist.h"\ ".\freelist.h"\ ".\bitree.h"\ ".\ianstd.h"\ "$(INTDIR)\mem.obj" : $(SOURCE) $(DEP_CPP_MEM_C) "$(INTDIR)" # End Source File ################################################################################ # Begin Source File SOURCE=.\main.cpp DEP_CPP_MAIN_=\ ".\mem.h"\ ".\pagepool.h"\ ".\hash.h"\ ".\ordlist.h"\ ".\freelist.h"\ ".\bitree.h"\ ".\ianstd.h"\ "$(INTDIR)\main.obj" : $(SOURCE) $(DEP_CPP_MAIN_) "$(INTDIR)" # End Source File ################################################################################ # Begin Source File SOURCE=.\hash.cpp DEP_CPP_HASH_=\ ".\hash.h"\ ".\freelist.h"\ ".\bitree.h"\ ".\ianstd.h"\ "$(INTDIR)\hash.obj" : $(SOURCE) $(DEP_CPP_HASH_) "$(INTDIR)" # End Source File ################################################################################ # Begin Source File SOURCE=.\freelist.cpp DEP_CPP_FREEL=\ ".\freelist.h"\ "$(INTDIR)\freelist.obj" : $(SOURCE) $(DEP_CPP_FREEL) "$(INTDIR)" # End Source File ################################################################################ # Begin Source File SOURCE=.\bitree.cpp DEP_CPP_BITRE=\ ".\ianstd.h"\ ".\bitree.h"\ "$(INTDIR)\bitree.obj" : $(SOURCE) $(DEP_CPP_BITRE) "$(INTDIR)" # End Source File # End Target # End Project ################################################################################