Return to tree.c CVS log

Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff

Annotation of mstools/samples/sdktools/windiff/tree.c, revision 1.1

1.1     ! root        1: 
        !             2: /******************************************************************************\
        !             3: *       This is a part of the Microsoft Source Code Samples. 
        !             4: *       Copyright (C) 1993 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: 

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.