home *** CD-ROM | disk | FTP | other *** search
/ GEMini Atari / GEMini_Atari_CD-ROM_Walnut_Creek_December_1993.iso / files / program / funnel / table.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-23  |  15.9 KB  |  430 lines
  1. /*##############################################################################
  2.  
  3. FUNNNELWEB COPYRIGHT
  4. ====================
  5. FunnelWeb is a literate-programming macro preprocessor.
  6.  
  7. Copyright (C) 1992 Ross N. Williams.
  8.  
  9.    Ross N. Williams
  10.    ross@spam.adelaide.edu.au
  11.    16 Lerwick Avenue, Hazelwood Park 5066, Australia.
  12.  
  13. This program is free software; you can redistribute it and/or modify
  14. it under the terms of Version 2 of the GNU General Public License as
  15. published by the Free Software Foundation.
  16.  
  17. This program is distributed WITHOUT ANY WARRANTY; without even the implied
  18. warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  19. See Version 2 of the GNU General Public License for more details.
  20.  
  21. You should have received a copy of Version 2 of the GNU General Public
  22. License along with this program. If not, you can FTP the license from
  23. prep.ai.mit.edu/pub/gnu/COPYING-2 or write to the Free Software
  24. Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  25.  
  26. Section 2a of the license requires that all changes to this file be
  27. recorded prominently in this file. Please record all changes here.
  28.  
  29. Programmers:
  30.    RNW  Ross N. Williams  ross@spam.adelaide.edu.au
  31.  
  32. Changes:
  33.    07-May-1992  RNW  Program prepared for release under GNU GPL V2.
  34.  
  35. ##############################################################################*/
  36.  
  37.  
  38. /******************************************************************************/
  39. /*                                   TABLE.C                                  */
  40. /******************************************************************************/
  41. /*                                                                            */
  42. /* Notes                                                                      */
  43. /* -----                                                                      */
  44. /* - There are few comments at the start of each function. As definitions     */
  45. /*   appear in the .H file, and it is dangerous to duplicate definitions, I   */
  46. /*   have simply omitted them here.                                           */
  47. /*                                                                            */
  48. /* About The Cache                                                            */
  49. /* ---------------                                                            */
  50. /* A typical usage sequence for tables is for the user to first call tb_itb   */
  51. /* to see if a key is in the table and then call either tb_loo or tb_ins      */
  52. /* to lookup the value or to add a new (key,value) pair to the table.         */
  53. /* In order to avoid performing TWO searches down the binary tree in such     */
  54. /* cases, a CACHE is maintained in the table data structure between calls.    */
  55. /*                                                                            */
  56. /* ca_valid stores whether the cache contents are valid. If TRUE then:        */
  57. /* ca_p_key points to a key.                                                  */
  58. /* ca_p_node points to the node in the tree containing the key, or contains   */
  59. /*    NULL if no such node exists.                                            */
  60. /* ca_p_parent points to the node in the tree that is the parent of the node  */
  61. /*    ca_p_node in the tree, or (if ca_p_node==NULL) WOULD BE the parent if a */
  62. /*    node containing the key were inserted in the tree. If the tree is       */
  63. /*    currently empty, ca_p_parent will be NULL.                              */
  64. /*                                                                            */
  65. /******************************************************************************/
  66.  
  67. #include "style.h"
  68.  
  69. #include "as.h"
  70. #include "machin.h"
  71. #include "memory.h"
  72.  
  73. /******************************************************************************/
  74.  
  75. /* In order to catch uninitialized and corrupted tables, the first and last   */
  76. /* fields of legitimate table objects contain magic numbers. The following    */
  77. /* #defines give the values of these numbers. The first thing that each       */
  78. /* function of this package does is to check the two magic number fields of   */
  79. /* the table it has just been passed, and bomb the package if the fields have */
  80. /* the wrong values. This technique is likely to pick uninitialized tables,   */
  81. /* as well as tables that have been partially overwritten.                    */
  82. #define MAGIC_HEAD_VALUE  (53456839L)
  83. #define MAGIC_TAIL_VALUE  (28434290L)
  84.  
  85. /* Comparing keys is messy and so we define a macro to help us out.           */
  86. #define key_compare(a,b) ((*(p_tb->p_kycm))((a),(b)))
  87.  
  88. /******************************************************************************/
  89.  
  90. /* The functions of the table abstraction pass keys and values exclusively    */
  91. /* using pointers. These two definitions define types for these pointers.     */
  92. /* Although the two types are both 'p_void', the different types are useful   */
  93. /* to indicate what is expected in each position of the parameter lists.      */
  94. typedef p_void p_tbky_t;
  95. typedef p_void p_tbvl_t;
  96.  
  97. /* Define a type for a function to compare two keys. Such functions are       */
  98. /* needed to organize the storage of (key,value) pairs inside the table.      */
  99. /* Given the arguments are (a,b), the function should return:                 */
  100. /*    -1 if a<b                                                               */
  101. /*     0 if a==b                                                              */
  102. /*     1 if a>b                                                               */
  103. /* The user must create such a function and hand it to the 'tb_create'        */
  104. /* function when creating new a new table.                                    */
  105. typedef sign (*p_kycm_t) P_((p_tbky_t,p_tbky_t));
  106.  
  107. /* The (key,value) pairs in the table are stored in a binary tree. The tree   */
  108. /* is ordered by the key ordering function passed in at table creation.       */
  109. typedef struct node_t_
  110.   {
  111.    struct node_t_ *p_left;
  112.    struct node_t_ *p_right;
  113.    struct node_t_ *p_parent;
  114.    p_tbky_t        p_key;
  115.    p_tbvl_t        p_value;
  116.   }
  117.   node_t;
  118. typedef node_t *p_node_t;
  119.  
  120. /* The type tb_t (table type) defines the root table data record. This      */
  121. /* record stores attributes of the table along with the main binary tree of */
  122. /* (key,value) pairs.                                                       */
  123. typedef struct
  124.   {
  125.    ulong     magic_head;       /* Magic number to allow corruption checks.  */
  126.    size_t    key_bytes;        /* Number of bytes in a key.                 */
  127.    size_t    value_bytes;      /* Number of bytes in a value.               */
  128.    p_kycm_t  p_kycm;           /* Pointer to function to compare keys.      */
  129.    p_node_t  tree;             /* Ptr to root of (key,value) binary tree.   */
  130.    ulong     num_keys;         /* Number of (k,v) pairs in the table.       */
  131.    bool      ca_valid;         /* Cache: TRUE iff cache contents are valid. */
  132.    p_tbky_t  ca_p_key;         /* Cache: Key value cache contents refer to. */
  133.    p_node_t  ca_p_node;        /* Cache: Pointer to node in binary tree.    */
  134.    p_node_t  ca_p_parent;      /* Cache: Pointer to parent of ca_p_node.    */
  135.    p_node_t  p_read_next;      /* Pointer to next node to be read.          */
  136.    ulong     magic_tail;       /* Magic number to allow corruption checks.  */
  137.   } tb_t;
  138.  
  139. typedef tb_t *p_tb_t;           /* Pointer to main table record.            */
  140.  
  141. /* Defining INTABLEC hides the abstract definition. */
  142. #define INTABLEC
  143. #include "table.h"
  144.  
  145. /******************************************************************************/
  146. /*                              PRIVATE FUNCTIONS                             */
  147. /******************************************************************************/
  148.  
  149. LOCAL p_node_t new_node P_((p_tb_t,p_tbky_t,p_tbvl_t));
  150. LOCAL p_node_t new_node(p_tb,p_tbky,p_tbvl)
  151. /* Creates a new tree node and returns a pointer to it.                       */
  152. /* p_tb is the table for which the new node is to be created.                 */
  153. /* p_tbky and p_tbvl point to the key and value to go in the new node.        */
  154. /* Assumes that a tb_check(p_tb) has already been performed by the caller.    */
  155. p_tb_t   p_tb;
  156. p_tbky_t p_tbky;
  157. p_tbvl_t p_tbvl;
  158. {
  159.  p_node_t p_node;
  160.  
  161.  p_node=(p_node_t) mm_temp(sizeof(node_t));
  162.  
  163.  p_node->p_left   = NULL;
  164.  p_node->p_right  = NULL;
  165.  p_node->p_parent = NULL;
  166.  p_node->p_key    = mm_temp(p_tb->key_bytes  );
  167.  p_node->p_value  = mm_temp(p_tb->value_bytes);
  168.  
  169.  memcpy(p_node->p_key  ,p_tbky,p_tb->key_bytes  );
  170.  memcpy(p_node->p_value,p_tbvl,p_tb->value_bytes);
  171.  
  172.  return p_node;
  173. }
  174.  
  175. /******************************************************************************/
  176.  
  177. LOCAL void tb_check P_((p_tb_t));
  178. LOCAL void tb_check(p_tb)
  179. /* Accepts a pointer to a table and performs a series of checks to make sure  */
  180. /* that the table has not been corrupted in some way.                         */
  181. p_tb_t p_tb;
  182. {
  183.  as_cold(p_tb!=NULL,"tb_check: Table pointer is NULL.");
  184.  as_cold(p_tb->magic_head==MAGIC_HEAD_VALUE,
  185.          "tb_check: Magic number at head of record is incorrect.");
  186.  as_cold(p_tb->magic_tail==MAGIC_TAIL_VALUE,
  187.          "tb_check: Magic number at tail of record is incorrect.");
  188. }
  189.  
  190. /******************************************************************************/
  191.  
  192. LOCAL p_node_t min_leaf P_((p_node_t));
  193. LOCAL p_node_t min_leaf(p_node)
  194. /* Returns a pointer to the node that is leftmost (has the smallest value     */
  195. /* according to the ordering function) in the specified node's subtree.       */
  196. p_node_t p_node;
  197. {
  198.  if (p_node==NULL)
  199.     return NULL;
  200.  while (p_node->p_left != NULL)
  201.     p_node=p_node->p_left;
  202.  return p_node;
  203. }
  204.  
  205. /******************************************************************************/
  206.  
  207. LOCAL p_node_t next_node P_((p_node_t));
  208. LOCAL p_node_t next_node(p_node)
  209. /* Give a pointer to a node in the binary tree, returns a pointer to the next */
  210. /* node (in sequence defined by the order function) or NULL if the given node */
  211. /* is the last node in the ordered sequence.                                  */
  212. p_node_t p_node;
  213. {
  214.  /* If there is a right subtree, we need the minimum node of that subtree.    */
  215.  if (p_node->p_right != NULL)
  216.     return min_leaf(p_node->p_right);
  217.  
  218.  /* Otherwise go up as far as possible through right arcs. */
  219.  while (p_node->p_parent!=NULL && p_node->p_parent->p_right==p_node)
  220.     p_node=p_node->p_parent;
  221.  return p_node->p_parent;
  222. }
  223.  
  224. /******************************************************************************/
  225.  
  226. LOCAL void tb_search P_((p_tb_t,p_tbky_t));
  227. LOCAL void tb_search(p_tb,p_tbky)
  228. /* Calling this function with a particular key value results in the cache     */
  229. /* becoming valid and containing the specified key.                           */
  230. p_tb_t   p_tb;
  231. p_tbky_t p_tbky;
  232. {
  233.  p_node_t p,p_parent;
  234.  
  235.  tb_check(p_tb);
  236.  
  237.  /* Return if the cache is already up to date. */
  238.  if (p_tb->ca_valid)
  239.    if (key_compare(p_tbky,p_tb->ca_p_key) == 0)
  240.       return;
  241.  
  242.   p_parent=NULL;
  243.   p=p_tb->tree;
  244.   while (p != NULL)
  245.      switch(key_compare(p_tbky,p->p_key))
  246.        {
  247.         case -1: p_parent=p; p=p->p_left;  break;
  248.         case  1: p_parent=p; p=p->p_right; break;
  249.         case  0: goto found;
  250.         default:
  251.            as_bomb("tb_search: Key comparison function returned bad value.");
  252.        }
  253.   found:
  254.   p_tb->ca_valid    = TRUE;
  255.   memcpy(p_tb->ca_p_key,p_tbky,p_tb->key_bytes);
  256.   p_tb->ca_p_node   = p;
  257.   p_tb->ca_p_parent = p_parent;
  258. }
  259.  
  260. /******************************************************************************/
  261.  
  262. LOCAL void des_tree P_((p_node_t));
  263. LOCAL void des_tree(p_root)
  264. p_node_t p_root;
  265. {
  266.  if (p_root==NULL)
  267.     return;
  268.  des_tree(p_root->p_left);
  269.  des_tree(p_root->p_right);
  270.  
  271.  /* This is what we would need if it wasn't for the MM watermark system.      */
  272.  /* DEALLOCATE(PV p_root); */
  273. }
  274.  
  275. /******************************************************************************/
  276. /*                              EXPORTED FUNCTIONS                            */
  277. /******************************************************************************/
  278.  
  279. EXPORT p_tb_t tb_cre(key_bytes,value_bytes,p_kycm)
  280. size_t   key_bytes;
  281. size_t   value_bytes;
  282. p_kycm_t p_kycm;
  283. {
  284.  p_tb_t p_tb;
  285.  
  286.  p_tb              = (p_tb_t) mm_temp(sizeof(tb_t));
  287.  p_tb->magic_head  = MAGIC_HEAD_VALUE;
  288.  p_tb->key_bytes   = key_bytes;
  289.  p_tb->value_bytes = value_bytes;
  290.  p_tb->p_kycm      = p_kycm;
  291.  p_tb->tree        = NULL;
  292.  p_tb->num_keys    = 0;
  293.  p_tb->ca_valid    = FALSE;
  294.  p_tb->ca_p_key    = (p_tbky_t) mm_temp(key_bytes);
  295.  p_tb->ca_p_node   = NULL; /* This initialization not strictly necessary. */
  296.  p_tb->ca_p_parent = NULL; /* This initialization not strictly necessary. */
  297.  p_tb->p_read_next = NULL;
  298.  p_tb->magic_tail  = MAGIC_TAIL_VALUE;
  299.  
  300.  return p_tb;
  301. }
  302.  
  303. /******************************************************************************/
  304.  
  305. EXPORT bool tb_itb(p_tb,p_tbky)
  306. p_tb_t   p_tb;
  307. p_tbky_t p_tbky;
  308. {
  309.  tb_check(p_tb);
  310.  
  311.  tb_search(p_tb,p_tbky);
  312.  return p_tb->ca_p_node != NULL;
  313. }
  314.  
  315. /******************************************************************************/
  316.  
  317. EXPORT void tb_loo(p_tb,p_tbky,p_tbvl)
  318. p_tb_t   p_tb;
  319. p_tbky_t p_tbky;
  320. p_tbvl_t p_tbvl;
  321. {
  322.  tb_check(p_tb);
  323.  
  324.  tb_search(p_tb,p_tbky);
  325.  as_cold(p_tb->ca_p_node!=NULL,"tb_loo: Requested key is absent.");
  326.  memcpy(p_tbvl,p_tb->ca_p_node->p_value,p_tb->value_bytes);
  327. }
  328.  
  329. /******************************************************************************/
  330.  
  331. EXPORT void tb_ins(p_tb,p_tbky,p_tbvl)
  332. p_tb_t   p_tb;
  333. p_tbky_t p_tbky;
  334. p_tbvl_t p_tbvl;
  335. {
  336.  p_node_t p_new;
  337.  
  338.  tb_check(p_tb);
  339.  
  340.  /* Validate the cache. Note: tb_search does it's own cache check. */
  341.  tb_search(p_tb,p_tbky);
  342.  
  343.  /* Ensure that the table does not already contain the key. */
  344.  as_cold(p_tb->ca_p_node==NULL,"tb_ins: Key is already present in the p_tb.");
  345.  
  346.  /* Create the new node. */
  347.  p_new=new_node(p_tb,p_tbky,p_tbvl);
  348.  
  349.  /* Insert the new node into the tree. */
  350.  if (p_tb->ca_p_parent==NULL)
  351.     p_tb->tree=p_new;
  352.  else
  353.     switch(key_compare(p_tbky,p_tb->ca_p_parent->p_key))
  354.       {
  355.        case -1: p_tb->ca_p_parent->p_left =p_new; break;
  356.        case  1: p_tb->ca_p_parent->p_right=p_new; break;
  357.        default: as_bomb("tb_ins: Key comparison function is inconsistent.");
  358.       }
  359.  p_new->p_parent=p_tb->ca_p_parent;
  360.  
  361.  /* Need to fiddle cache to make it correct, and inc num_keys. */
  362.  p_tb->ca_p_node=p_new;
  363.  p_tb->num_keys++;
  364. }
  365.  
  366. /******************************************************************************/
  367.  
  368. EXPORT ulong tb_len(p_tb)
  369. p_tb_t p_tb;
  370. {
  371.  tb_check(p_tb);
  372.  return p_tb->num_keys;
  373. }
  374.  
  375. /******************************************************************************/
  376.  
  377. EXPORT void tb_fir(p_tb)
  378. p_tb_t p_tb;
  379. {
  380.  tb_check(p_tb);
  381.  
  382.  p_tb->p_read_next=min_leaf(p_tb->tree);
  383. }
  384.  
  385. /******************************************************************************/
  386.  
  387. EXPORT bool tb_rea(p_tb,p_tbky,p_tbvl)
  388. p_tb_t    p_tb;
  389. p_tbky_t  p_tbky;
  390. p_tbvl_t  p_tbvl;
  391. {
  392.  tb_check(p_tb);
  393.  
  394.  if (p_tb->p_read_next == NULL)
  395.     return FALSE;
  396.  
  397.  memcpy(p_tbky,p_tb->p_read_next->p_key  ,p_tb->key_bytes  );
  398.  memcpy(p_tbvl,p_tb->p_read_next->p_value,p_tb->value_bytes);
  399.  
  400.  p_tb->p_read_next=next_node(p_tb->p_read_next);
  401.  
  402.  return TRUE;
  403. }
  404.  
  405. /******************************************************************************/
  406.  
  407. #if FALSE
  408. EXPORT void tb_des(p_tb)
  409. p_tb_t p_tb;
  410. {
  411.  /* This routine now unused because of the watermark system. */
  412.  return;
  413.  
  414.  /* tb_check(p_tb); */
  415.  
  416.  /* Zap the magic numbers in case the memory is re-used in same alignment. */
  417.  /* p_tb->magic_head=0; */
  418.  /* p_tb->magic_tail=0; */
  419.  
  420.  /* This is what we would need if it wasn't for the MM watermark system.      */
  421.  /* des_tree(p_tb->tree); */  /* Zap the binary tree. */
  422.  /* DEALLOCATE(PV p_tb);  */  /* Zap the node itself. */
  423. }
  424. #endif
  425.  
  426. /******************************************************************************/
  427. /*                                   TABLE.C                                  */
  428. /******************************************************************************/
  429.  
  430.