home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Windows Gam…ming Gurus (2nd Edition) / Disc2.iso / msdn_vcb / samples / vc98 / sdk / sdktools / windiff / tree.c < prev    next >
C/C++ Source or Header  |  1997-10-05  |  15KB  |  523 lines
  1.  
  2. /******************************************************************************\
  3. *       This is a part of the Microsoft Source Code Samples. 
  4. *       Copyright (C) 1993-1997 Microsoft Corporation.
  5. *       All rights reserved. 
  6. *       This source code is only intended as a supplement to 
  7. *       Microsoft Development Tools and/or WinHelp documentation.
  8. *       See these sources for detailed information regarding the 
  9. *       Microsoft samples programs.
  10. \******************************************************************************/
  11.  
  12. /****************************** Module Header *******************************
  13. * Module Name: TREE.C
  14. *
  15. * Functions supporting an unbalanced binary tree.
  16. *
  17. * Functions:
  18. *
  19. * tree_delitem()
  20. * tree_newitem()
  21. * tree_getitem()
  22. * tree_create()
  23. * tree_delete()
  24. * tree_update()
  25. * tree_find()
  26. * tree_search()
  27. * tree_addafter()
  28. * ctree_create()
  29. * ctree_delete()
  30. * ctree_update()
  31. * ctree_getcount()
  32. * ctree_find()
  33. *
  34. * Comments:
  35. *
  36. * TREE is a data type providing a map between a KEY and a VALUE. The KEY is a
  37. * 32-bit DWORD, and the VALUE is any arbitrary area of storage.
  38. *
  39. * Mmemory is allocated from gmem_get, using hHeap as the heap handle.
  40. * hHeap must be declared and initialised elsewhere.
  41. *
  42. * Currently implemented as a unbalanced binary tree.
  43. *
  44. ****************************************************************************/
  45.  
  46. #include <windows.h>
  47. #include <stdlib.h>
  48. #include <memory.h>
  49.  
  50. #include "gutils.h"
  51. #include "tree.h"
  52.  
  53.  
  54. /* -- data types ----------------------------------------------- */
  55.  
  56. /* on creating a tree, we return a TREE handle. This is in fact a pointer
  57.  * to a struct tree, defined here.
  58.  */
  59. struct tree {
  60.         HANDLE hHeap;
  61.         TREEITEM first;
  62. };
  63.  
  64. /* each element in the tree is stored in a TREEITEM. a TREEITEM handle
  65.  * is a pointer to a struct treeitem, defined here
  66.  */
  67. struct treeitem {
  68.         TREE root;
  69.  
  70.         TREEKEY key;
  71.  
  72.         TREEITEM left, right;
  73.  
  74.         UINT length;            /* length of the user's data */
  75.  
  76.         LPVOID data;            /* pointer to our copy of the users data */
  77.  
  78. };
  79.  
  80. /***************************************************************************
  81.  * Function: tree_delitems
  82.  *
  83.  * Purpose:
  84.  *
  85.  * Free up an element of the tree. Recursively calls itself to
  86.  * free left and right children
  87.  */
  88. void
  89. tree_delitem(TREEITEM item)
  90. {
  91.         if (item == NULL) {
  92.                 return;
  93.         }
  94.         if (item->left != NULL) {
  95.                 tree_delitem(item->left);
  96.         }
  97.         if (item->right != NULL) {
  98.                 tree_delitem(item->right);
  99.         }
  100.         if (item->data != NULL) {
  101.                 gmem_free(item->root->hHeap, item->data, item->length);
  102.         }
  103.  
  104.         gmem_free(item->root->hHeap, (LPSTR) item, sizeof(struct treeitem));
  105. }
  106.  
  107. /***************************************************************************
  108.  * Function: tree_newitem
  109.  *
  110.  * Purpose:
  111.  *
  112.  * Creates a new treeitem, with a data block of length bytes.
  113.  * If the value pointer is not NULL, initialise the data block with
  114.  * the contents of value.
  115.  */
  116. TREEITEM
  117. tree_newitem(TREE root, TREEKEY key, LPVOID value, UINT length)
  118. {
  119.         TREEITEM item;
  120.  
  121.         item = (TREEITEM) gmem_get(root->hHeap, sizeof(struct treeitem));
  122.  
  123.         item->root = root;
  124.         item->key = key;
  125.         item->left = NULL;
  126.         item->right = NULL;
  127.         item->length = length;
  128.         item->data = gmem_get(root->hHeap, length);
  129.         if (value != NULL) {
  130.                 memcpy(item->data, value, length);
  131.         }
  132.  
  133.         return(item);
  134. }
  135.  
  136.  
  137. /***************************************************************************
  138.  * Function: tree_getitem
  139.  *
  140.  * Purpose:
  141.  *
  142.  * Finds the item with the given key. If it does not exist, return
  143.  * the parent item to which it would be attached. Returns NULL if
  144.  * no items in the tree
  145.  */
  146. TREEITEM
  147. tree_getitem(TREE tree, TREEKEY key)
  148. {
  149.         TREEITEM item, prev;
  150.  
  151.  
  152.         prev = NULL;
  153.         for (item = tree->first; item != NULL; ) {
  154.                 
  155.                 if (item->key == key) {
  156.                         return(item);
  157.                 }
  158.  
  159.                 /* not this item - go on to the correct child item.
  160.                  * remember this item as if the child is NULL, this item
  161.                  * will be the correct insertion point for the new item
  162.                  */
  163.                 prev = item;
  164.  
  165.                 if (key < item->key) {
  166.                         item = item->left;
  167.                 } else {
  168.                         item = item->right;
  169.                 }
  170.         }       
  171.         /* prev is the parent - or null if nothing in tree */
  172.         return(prev);
  173. }
  174.  
  175. /***************************************************************************
  176.  * Function: tree_create
  177.  *
  178.  * Purpose:
  179.  *
  180.  * Creates an empty tree. hHeap is the handle to use for all
  181.  * memory allocations for this tree.
  182.  */
  183. TREE APIENTRY
  184. tree_create(HANDLE hHeap)
  185. {
  186.         TREE tree;
  187.  
  188.         tree = (TREE) gmem_get(hHeap, sizeof(struct tree));
  189.         tree->first = NULL;
  190.         tree->hHeap = hHeap;
  191.         return(tree);
  192. }
  193.  
  194.  
  195. /***************************************************************************
  196.  * Function: tree_delete
  197.  *
  198.  * Purpose:
  199.  *
  200.  * Deletes an entire tree, including all the user data
  201.  */
  202. void APIENTRY
  203. tree_delete(TREE tree)
  204. {
  205.  
  206.         tree_delitem(tree->first);
  207.  
  208.         gmem_free(tree->hHeap, (LPSTR) tree, sizeof(struct tree));
  209. }
  210.  
  211. /***************************************************************************
  212.  * Function: tree_update
  213.  *
  214.  * Purpose:
  215.  *
  216.  * Adds a new element to the tree, mapping the key given to the value given.
  217.  * The value is a block of storage: a copy of this is inserted into the tree.
  218.  * We return a pointer to the copy of the data in the tree.
  219.  *
  220.  * The value pointer can be NULL: in this case, we insert a block of
  221.  * length bytes, but don't initialise it. You get a pointer to it and
  222.  * can initialise it yourself.
  223.  *
  224.  * If the key already exists, the value will be replaced with the new data.
  225.  */
  226. LPVOID APIENTRY
  227. tree_update(TREE tree, TREEKEY key, LPVOID value, UINT length)
  228. {
  229.         TREEITEM item;
  230.  
  231.         /* find the place in the tree for this key to go */
  232.         item = tree_getitem(tree, key);
  233.  
  234.         if (item == NULL) {
  235.                 /* there is nothing in the tree: this item should
  236.                  * go at the top
  237.                  */
  238.                 tree->first = tree_newitem(tree, key, value, length);
  239.                 return(tree->first->data);
  240.         }
  241.  
  242.         /* is this the same key ? */
  243.         if (item->key == key) {
  244.  
  245.                 /* this key already inserted. re-alloc the data */
  246.                 if (length != item->length) {
  247.                         gmem_free(tree->hHeap, item->data, item->length);
  248.                         item->data = gmem_get(tree->hHeap, length);
  249.                 }
  250.                 /* don't initialise block if no pointer passed */
  251.                 if (value != NULL) {
  252.                         memcpy(item->data, value, length);
  253.                 }
  254.                 return(item->data);
  255.         }
  256.  
  257.         /* not the same key - getitem returned the parent for
  258.          * the new tree. insert it as a child of item.
  259.          */
  260.         return(tree_addafter(tree, &item, key, value, length));
  261. }
  262.  
  263. /***************************************************************************
  264.  * Function: tree_find
  265.  *
  266.  * Purpose:
  267.  *
  268.  * Returns a pointer to the value (data block) for a given key. Returns
  269.  * null if not found.
  270.  */
  271. LPVOID APIENTRY
  272. tree_find(TREE tree, TREEKEY key)
  273. {
  274.         TREEITEM item;
  275.  
  276.         /* find the correct place in the tree */
  277.         item = tree_getitem(tree, key);
  278.  
  279.         if (item == NULL) {
  280.                 /* nothing in the tree */
  281.                 return(NULL);
  282.         }
  283.  
  284.         if (item->key != key) {
  285.                 /* this key not in. getitem has returned parent */
  286.                 return(NULL);
  287.         }
  288.  
  289.         /* found the right element - return pointer to the
  290.          * data block
  291.          */
  292.         return(item->data);
  293. }
  294.  
  295. /* The next two routines are an optimisation for a common tree operation. In
  296.  * this case, the user will want to insert a new element only if
  297.  * the key is not there. If it is there, he will want to modify the
  298.  * existing value (increment a reference count, for example).
  299.  *
  300.  * If tree_search fails to find the key, it will return a TREEITEM handle
  301.  * for the parent. This can be passed to tree_addafter to insert the
  302.  * new element without re-searching the tree.
  303.  */
  304.  
  305. /***************************************************************************
  306.  * Function: tree_search
  307.  *
  308.  * Purpose:
  309.  *
  310.  * Find an element. If not, find it's correct parent item
  311.  */
  312. LPVOID APIENTRY
  313. tree_search(TREE tree, TREEKEY key, PTREEITEM pplace)
  314. {
  315.         TREEITEM item;
  316.  
  317.         item = tree_getitem(tree, key);
  318.  
  319.         if (item == NULL) {
  320.                 /* no items in tree. set placeholder to NULL to
  321.                  * indicate insert at top of tree
  322.                  */
  323.                 *pplace = NULL;         
  324.  
  325.                 /* return NULL to indicate key not found */
  326.                 return(NULL);
  327.         }
  328.  
  329.         if (item->key == key) {
  330.                 /* found the key already there -
  331.                  * set pplace to null just for safety
  332.                  */
  333.                 *pplace = NULL;
  334.  
  335.                 /* give the user a pointer to his data */
  336.                 return(item->data);
  337.         }
  338.  
  339.  
  340.         /* key was not found - getitem has returned the parent
  341.          * - set this as the place for new insertions
  342.          */
  343.         *pplace = item;         
  344.  
  345.         /* return NULL to indicate that the key was not found */
  346.         return(NULL);
  347. }
  348.  
  349. /***************************************************************************
  350.  * Function: tree_addafter
  351.  *
  352.  * Purpose:
  353.  *
  354.  * Insert a key in the position already found by tree_search.
  355.  *
  356.  * Return a pointer to the user's data in the tree. If the value
  357.  * pointer passed in is null, then we allocate the block, but don't
  358.  * initialise it to anything.
  359.  */
  360. LPVOID APIENTRY
  361. tree_addafter(TREE tree, PTREEITEM place, TREEKEY key, LPVOID value, UINT length)
  362. {
  363.         TREEITEM item, child;
  364.  
  365.         item = *place;
  366.         if (item == NULL) {
  367.                 tree->first = tree_newitem(tree, key, value, length);
  368.                 return (tree->first->data);
  369.         }               
  370.  
  371.         child = tree_newitem(tree, key, value, length);         
  372.         if (child->key < item->key ) {
  373.                 /* should go on left leg */
  374.                 item->left = child;
  375.         } else {        
  376.                 item->right = child;
  377.         }
  378.         return(child->data);
  379. }
  380.  
  381.  
  382. /* --- ctree ------------------------------------------------------*/
  383.  
  384. /*
  385.  * ctree is a class of tree built on top of the tree interface. a
  386.  * ctree keeps count of the number of insertions of identical keys.
  387.  *
  388.  * We do this be adding a long counter to the beginning of the user
  389.  * data before inserting into the tree. If the key is not found, we set
  390.  * this to one. If the key was already there, we *do not* insert the
  391.  * data (data is always from the first insertion) - we simply increment
  392.  * the count.
  393.  */
  394.  
  395. /* Create a tree for use by CTREE - same as an ordinary tree
  396.  */
  397. TREE APIENTRY
  398. ctree_create(HANDLE hHeap)
  399. {
  400.         return(tree_create(hHeap));
  401. }
  402.  
  403. /*
  404.  * Delete a ctree - same as for TREE
  405.  */
  406. void APIENTRY
  407. ctree_delete(TREE tree)
  408. {
  409.         tree_delete(tree);
  410. }
  411.  
  412.  
  413. /***************************************************************************
  414.  * Function: ctree_update
  415.  *
  416.  * Purpose:
  417.  *
  418.  * Insert an element in the tree. If the element is not there,
  419.  * insert the data and set the reference count for this key to 1.
  420.  * If the key was there already, don't change the data, just increment
  421.  * the reference count
  422.  *
  423.  * If the value pointer is not null, we initialise the value block
  424.  * in the tree to contain this.
  425.  *
  426.  * We return a pointer to the users data in the tree
  427.  */
  428. LPVOID APIENTRY
  429. ctree_update(TREE tree, TREEKEY key, LPVOID value, UINT length)
  430. {
  431.         TREEITEM item;
  432.         long FAR * pcounter;
  433.         LPVOID datacopy;
  434.  
  435.         pcounter = tree_search(tree, key, &item);
  436.  
  437.         if (pcounter == NULL) {
  438.                 /* element not found - insert a new one
  439.                  * the data block for this element should be
  440.                  * the user's block with our reference count at
  441.                  * the beginning
  442.                  */
  443.                 pcounter = tree_addafter(tree, &item, key, NULL,
  444.                                 length + sizeof(long));
  445.                 *pcounter = 1;
  446.                 /* add on size of one long to get the start of the user
  447.                  * data
  448.                  */
  449.                 datacopy = pcounter + 1;
  450.                 if (value != NULL) {
  451.                         memcpy(datacopy, value, length);
  452.                 }
  453.                 return(datacopy);
  454.         }
  455.  
  456.         /* key was already there - increment reference count and
  457.          * return pointer to data
  458.          */
  459.  
  460.         (*pcounter)++;
  461.  
  462.         /* add on size of one long to get the start of the user
  463.          * data
  464.          */
  465.         datacopy = pcounter + 1;
  466.         return(datacopy);
  467. }
  468.  
  469. /***************************************************************************
  470.  * Function: ctree_getcount
  471.  *
  472.  * Purpose:
  473.  *
  474.  * Return the reference count for this key 
  475.  */
  476. long APIENTRY
  477. ctree_getcount(TREE tree, TREEKEY key)
  478. {
  479.         long FAR * pcounter;
  480.  
  481.         pcounter = tree_find(tree, key);
  482.         if (pcounter == NULL) {
  483.                 return(0);
  484.         }
  485.         return(*pcounter);
  486. }
  487.  
  488. /***************************************************************************
  489.  * Function: ctree_find
  490.  *
  491.  * Purpose:
  492.  *
  493.  * Return a pointer to the user's data block for this key,
  494.  * or NULL if key not present
  495.  */
  496. LPVOID APIENTRY
  497. ctree_find(TREE tree, TREEKEY key)
  498. {
  499.         long FAR * pcounter;
  500.  
  501.  
  502.         pcounter = tree_find(tree, key);
  503.         if (pcounter == NULL) {
  504.                 return(0);
  505.         }
  506.  
  507.         /* increment pointer by size of 1 long to point to
  508.          * user's datablock
  509.          */
  510.         return(pcounter+1);
  511. }
  512.  
  513.  
  514.  
  515.  
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.