![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to tree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff|
Return to tree.c CVS log | Up to [WindowsNT SDKs] / mstools / samples / sdktools / windiff |
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.