/*############################################################################## FUNNNELWEB COPYRIGHT ==================== FunnelWeb is a literate-programming macro preprocessor. The FunnelWeb web is at http://www.ross.net/funnelweb/ Copyright (c) Ross N. Williams 1992. All rights reserved. This program is free software; you can redistribute it and/or modify it under the terms of Version 2 of the GNU General Public License as published by the Free Software Foundation (http://www.gnu.org/). This program is distributed WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See Version 2 of the GNU General Public License for more details. You should have received a copy of Version 2 of the GNU General Public License along with this program. If not, you can obtain a copy as follows: ftp://prep.ai.mit.edu/pub/gnu/COPYING-2.0 or write to: Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA Section 2a of the license requires that all changes to this file be recorded prominently in this file. Please record all changes here. Programmers: RNW Ross N. Williams (ross@ross.net) Changes: 07-May-1992 RNW Program prepared for release under GNU GPL V2. ##############################################################################*/ /******************************************************************************/ /* TABLE.C */ /******************************************************************************/ /* */ /* Notes */ /* ----- */ /* - There are few comments at the start of each function. As definitions */ /* appear in the .H file, and it is dangerous to duplicate definitions, I */ /* have simply omitted them here. */ /* */ /* About The Cache */ /* --------------- */ /* A typical usage sequence for tables is for the user to first call tb_itb */ /* to see if a key is in the table and then call either tb_loo or tb_ins */ /* to lookup the value or to add a new (key,value) pair to the table. */ /* In order to avoid performing TWO searches down the binary tree in such */ /* cases, a CACHE is maintained in the table data structure between calls. */ /* */ /* ca_valid stores whether the cache contents are valid. If TRUE then: */ /* ca_p_key points to a key. */ /* ca_p_node points to the node in the tree containing the key, or contains */ /* NULL if no such node exists. */ /* ca_p_parent points to the node in the tree that is the parent of the node */ /* ca_p_node in the tree, or (if ca_p_node==NULL) WOULD BE the parent if a */ /* node containing the key were inserted in the tree. If the tree is */ /* currently empty, ca_p_parent will be NULL. */ /* */ /******************************************************************************/ #include "style.h" #include "as.h" #include "machin.h" #include "memory.h" /******************************************************************************/ /* In order to catch uninitialized and corrupted tables, the first and last */ /* fields of legitimate table objects contain magic numbers. The following */ /* #defines give the values of these numbers. The first thing that each */ /* function of this package does is to check the two magic number fields of */ /* the table it has just been passed, and bomb the package if the fields have */ /* the wrong values. This technique is likely to pick uninitialized tables, */ /* as well as tables that have been partially overwritten. */ #define MAGIC_HEAD_VALUE (53456839L) #define MAGIC_TAIL_VALUE (28434290L) /* Comparing keys is messy and so we define a macro to help us out. */ #define key_compare(a,b) ((*(p_tb->p_kycm))((a),(b))) /******************************************************************************/ /* The functions of the table abstraction pass keys and values exclusively */ /* using pointers. These two definitions define types for these pointers. */ /* Although the two types are both 'p_void', the different types are useful */ /* to indicate what is expected in each position of the parameter lists. */ typedef p_void p_tbky_t; typedef p_void p_tbvl_t; /* Define a type for a function to compare two keys. Such functions are */ /* needed to organize the storage of (key,value) pairs inside the table. */ /* Given the arguments are (a,b), the function should return: */ /* -1 if ab */ /* The user must create such a function and hand it to the 'tb_create' */ /* function when creating new a new table. */ typedef sign (*p_kycm_t) P_((p_tbky_t,p_tbky_t)); /* The (key,value) pairs in the table are stored in a binary tree. The tree */ /* is ordered by the key ordering function passed in at table creation. */ typedef struct node_t_ { struct node_t_ *p_left; struct node_t_ *p_right; struct node_t_ *p_parent; p_tbky_t p_key; p_tbvl_t p_value; } node_t; typedef node_t *p_node_t; /* The type tb_t (table type) defines the root table data record. This */ /* record stores attributes of the table along with the main binary tree of */ /* (key,value) pairs. */ typedef struct { ulong magic_head; /* Magic number to allow corruption checks. */ size_t key_bytes; /* Number of bytes in a key. */ size_t value_bytes; /* Number of bytes in a value. */ p_kycm_t p_kycm; /* Pointer to function to compare keys. */ p_node_t tree; /* Ptr to root of (key,value) binary tree. */ ulong num_keys; /* Number of (k,v) pairs in the table. */ bool ca_valid; /* Cache: TRUE iff cache contents are valid. */ p_tbky_t ca_p_key; /* Cache: Key value cache contents refer to. */ p_node_t ca_p_node; /* Cache: Pointer to node in binary tree. */ p_node_t ca_p_parent; /* Cache: Pointer to parent of ca_p_node. */ p_node_t p_read_next; /* Pointer to next node to be read. */ ulong magic_tail; /* Magic number to allow corruption checks. */ } tb_t; typedef tb_t *p_tb_t; /* Pointer to main table record. */ /* Defining INTABLEC hides the abstract definition. */ #define INTABLEC #include "table.h" /******************************************************************************/ /* PRIVATE FUNCTIONS */ /******************************************************************************/ LOCAL p_node_t new_node P_((p_tb_t,p_tbky_t,p_tbvl_t)); LOCAL p_node_t new_node(p_tb,p_tbky,p_tbvl) /* Creates a new tree node and returns a pointer to it. */ /* p_tb is the table for which the new node is to be created. */ /* p_tbky and p_tbvl point to the key and value to go in the new node. */ /* Assumes that a tb_check(p_tb) has already been performed by the caller. */ p_tb_t p_tb; p_tbky_t p_tbky; p_tbvl_t p_tbvl; { p_node_t p_node; p_node=(p_node_t) mm_temp(sizeof(node_t)); p_node->p_left = NULL; p_node->p_right = NULL; p_node->p_parent = NULL; p_node->p_key = mm_temp(p_tb->key_bytes ); p_node->p_value = mm_temp(p_tb->value_bytes); memcpy(p_node->p_key ,p_tbky,p_tb->key_bytes ); memcpy(p_node->p_value,p_tbvl,p_tb->value_bytes); return p_node; } /******************************************************************************/ LOCAL void tb_check P_((p_tb_t)); LOCAL void tb_check(p_tb) /* Accepts a pointer to a table and performs a series of checks to make sure */ /* that the table has not been corrupted in some way. */ p_tb_t p_tb; { as_cold(p_tb!=NULL,"tb_check: Table pointer is NULL."); as_cold(p_tb->magic_head==MAGIC_HEAD_VALUE, "tb_check: Magic number at head of record is incorrect."); as_cold(p_tb->magic_tail==MAGIC_TAIL_VALUE, "tb_check: Magic number at tail of record is incorrect."); } /******************************************************************************/ LOCAL p_node_t min_leaf P_((p_node_t)); LOCAL p_node_t min_leaf(p_node) /* Returns a pointer to the node that is leftmost (has the smallest value */ /* according to the ordering function) in the specified node's subtree. */ p_node_t p_node; { if (p_node==NULL) return NULL; while (p_node->p_left != NULL) p_node=p_node->p_left; return p_node; } /******************************************************************************/ LOCAL p_node_t next_node P_((p_node_t)); LOCAL p_node_t next_node(p_node) /* Give a pointer to a node in the binary tree, returns a pointer to the next */ /* node (in sequence defined by the order function) or NULL if the given node */ /* is the last node in the ordered sequence. */ p_node_t p_node; { /* If there is a right subtree, we need the minimum node of that subtree. */ if (p_node->p_right != NULL) return min_leaf(p_node->p_right); /* Otherwise go up as far as possible through right arcs. */ while (p_node->p_parent!=NULL && p_node->p_parent->p_right==p_node) p_node=p_node->p_parent; return p_node->p_parent; } /******************************************************************************/ LOCAL void tb_search P_((p_tb_t,p_tbky_t)); LOCAL void tb_search(p_tb,p_tbky) /* Calling this function with a particular key value results in the cache */ /* becoming valid and containing the specified key. */ p_tb_t p_tb; p_tbky_t p_tbky; { p_node_t p,p_parent; tb_check(p_tb); /* Return if the cache is already up to date. */ if (p_tb->ca_valid) if (key_compare(p_tbky,p_tb->ca_p_key) == 0) return; p_parent=NULL; p=p_tb->tree; while (p != NULL) switch(key_compare(p_tbky,p->p_key)) { case -1: p_parent=p; p=p->p_left; break; case 1: p_parent=p; p=p->p_right; break; case 0: goto found; default: as_bomb("tb_search: Key comparison function returned bad value."); } found: p_tb->ca_valid = TRUE; memcpy(p_tb->ca_p_key,p_tbky,p_tb->key_bytes); p_tb->ca_p_node = p; p_tb->ca_p_parent = p_parent; } /******************************************************************************/ LOCAL void des_tree P_((p_node_t)); LOCAL void des_tree(p_root) p_node_t p_root; { if (p_root==NULL) return; des_tree(p_root->p_left); des_tree(p_root->p_right); /* This is what we would need if it wasn't for the MM watermark system. */ /* DEALLOCATE(PV p_root); */ } /******************************************************************************/ /* EXPORTED FUNCTIONS */ /******************************************************************************/ EXPORT p_tb_t tb_cre(key_bytes,value_bytes,p_kycm) size_t key_bytes; size_t value_bytes; p_kycm_t p_kycm; { p_tb_t p_tb; p_tb = (p_tb_t) mm_temp(sizeof(tb_t)); p_tb->magic_head = MAGIC_HEAD_VALUE; p_tb->key_bytes = key_bytes; p_tb->value_bytes = value_bytes; p_tb->p_kycm = p_kycm; p_tb->tree = NULL; p_tb->num_keys = 0; p_tb->ca_valid = FALSE; p_tb->ca_p_key = (p_tbky_t) mm_temp(key_bytes); p_tb->ca_p_node = NULL; /* This initialization not strictly necessary. */ p_tb->ca_p_parent = NULL; /* This initialization not strictly necessary. */ p_tb->p_read_next = NULL; p_tb->magic_tail = MAGIC_TAIL_VALUE; return p_tb; } /******************************************************************************/ EXPORT bool tb_itb(p_tb,p_tbky) p_tb_t p_tb; p_tbky_t p_tbky; { tb_check(p_tb); tb_search(p_tb,p_tbky); return p_tb->ca_p_node != NULL; } /******************************************************************************/ EXPORT void tb_loo(p_tb,p_tbky,p_tbvl) p_tb_t p_tb; p_tbky_t p_tbky; p_tbvl_t p_tbvl; { tb_check(p_tb); tb_search(p_tb,p_tbky); as_cold(p_tb->ca_p_node!=NULL,"tb_loo: Requested key is absent."); memcpy(p_tbvl,p_tb->ca_p_node->p_value,p_tb->value_bytes); } /******************************************************************************/ EXPORT void tb_ins(p_tb,p_tbky,p_tbvl) p_tb_t p_tb; p_tbky_t p_tbky; p_tbvl_t p_tbvl; { p_node_t p_new; tb_check(p_tb); /* Validate the cache. Note: tb_search does it's own cache check. */ tb_search(p_tb,p_tbky); /* Ensure that the table does not already contain the key. */ as_cold(p_tb->ca_p_node==NULL,"tb_ins: Key is already present in the p_tb."); /* Create the new node. */ p_new=new_node(p_tb,p_tbky,p_tbvl); /* Insert the new node into the tree. */ if (p_tb->ca_p_parent==NULL) p_tb->tree=p_new; else switch(key_compare(p_tbky,p_tb->ca_p_parent->p_key)) { case -1: p_tb->ca_p_parent->p_left =p_new; break; case 1: p_tb->ca_p_parent->p_right=p_new; break; default: as_bomb("tb_ins: Key comparison function is inconsistent."); } p_new->p_parent=p_tb->ca_p_parent; /* Need to fiddle cache to make it correct, and inc num_keys. */ p_tb->ca_p_node=p_new; p_tb->num_keys++; } /******************************************************************************/ EXPORT ulong tb_len(p_tb) p_tb_t p_tb; { tb_check(p_tb); return p_tb->num_keys; } /******************************************************************************/ EXPORT void tb_fir(p_tb) p_tb_t p_tb; { tb_check(p_tb); p_tb->p_read_next=min_leaf(p_tb->tree); } /******************************************************************************/ EXPORT bool tb_rea(p_tb,p_tbky,p_tbvl) p_tb_t p_tb; p_tbky_t p_tbky; p_tbvl_t p_tbvl; { tb_check(p_tb); if (p_tb->p_read_next == NULL) return FALSE; memcpy(p_tbky,p_tb->p_read_next->p_key ,p_tb->key_bytes ); memcpy(p_tbvl,p_tb->p_read_next->p_value,p_tb->value_bytes); p_tb->p_read_next=next_node(p_tb->p_read_next); return TRUE; } /******************************************************************************/ #if FALSE EXPORT void tb_des(p_tb) p_tb_t p_tb; { /* This routine now unused because of the watermark system. */ return; /* tb_check(p_tb); */ /* Zap the magic numbers in case the memory is re-used in same alignment. */ /* p_tb->magic_head=0; */ /* p_tb->magic_tail=0; */ /* This is what we would need if it wasn't for the MM watermark system. */ /* des_tree(p_tb->tree); */ /* Zap the binary tree. */ /* DEALLOCATE(PV p_tb); */ /* Zap the node itself. */ } #endif /******************************************************************************/ /* TABLE.C */ /******************************************************************************/