hi,
0001-Add-back-WINGs-tree.c-that-was-removed-in-c9d0c7c.patch then
0001-WINGs-tree-enhancements.patch
the first one adds back tree hopefully as exactly as it was removed.
the second one enhances it a bit, quoting commit message:
- add WMFindInTreeWithDepthLimit, which is like WMFindInTree, but
does not descend down more than a set limit.
- add WMTreeWalk, which will walk a WMTreeNode, running a callback
function on each node.
in retrospect, WMFindInTreeWithDepthLimit could probably have been
implemented outside of wings with judicious use of cdata, but it was
much simpler this way. please just add it for now (next batch depends
on it), and if it makes too many eyes bleed too badly, i'll re-do the
application later.
--
[-]
mkdir /nonexistent
From a0c043630c76d76d2984848a1077c01e5dc8144e Mon Sep 17 00:00:00 2001
From: Tamas TEVESZ <[email protected]>
Date: Thu, 7 Oct 2010 23:39:55 +0200
Subject: [PATCH] Add back WINGs/tree.c that was removed in c9d0c7c
Signed-off-by: Tamas TEVESZ <[email protected]>
---
WINGs/Makefile.am | 1 +
WINGs/WINGs/WUtil.h | 42 +++++++++
WINGs/tree.c | 231 +++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 274 insertions(+), 0 deletions(-)
create mode 100644 WINGs/tree.c
diff --git a/WINGs/Makefile.am b/WINGs/Makefile.am
index 0f4db4a..95f829b 100644
--- a/WINGs/Makefile.am
+++ b/WINGs/Makefile.am
@@ -72,6 +72,7 @@ libWUtil_la_SOURCES = \
notification.c \
proplist.c \
string.c \
+ tree.c \
userdefaults.c \
usleep.c \
wapplication.c \
diff --git a/WINGs/WINGs/WUtil.h b/WINGs/WINGs/WUtil.h
index 25d2ae3..5e68105 100644
--- a/WINGs/WINGs/WUtil.h
+++ b/WINGs/WINGs/WUtil.h
@@ -96,6 +96,7 @@ enum {
typedef struct W_Array WMArray;
typedef struct W_Bag WMBag;
typedef struct W_Data WMData;
+typedef struct W_TreeNode WMTreeNode;
typedef struct W_HashTable WMHashTable;
typedef struct W_UserDefaults WMUserDefaults;
typedef struct W_Notification WMNotification;
@@ -602,6 +603,47 @@ void WMSetDataFormat(WMData *aData, unsigned format);
unsigned WMGetDataFormat(WMData *aData);
/* Storing data */
+/* ---[ WINGs/tree.c ]---------------------------------------------------- */
+
+/* Generic Tree and TreeNode */
+
+WMTreeNode* WMCreateTreeNode(void *data);
+
+WMTreeNode* WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc *destructor);
+
+WMTreeNode* WMInsertItemInTree(WMTreeNode *parent, int index, void *item);
+
+#define WMAddItemToTree(parent, item) WMInsertItemInTree(parent, -1, item)
+
+WMTreeNode* WMInsertNodeInTree(WMTreeNode *parent, int index, WMTreeNode *aNode);
+
+#define WMAddNodeToTree(parent, aNode) WMInsertNodeInTree(parent, -1, aNode)
+
+void WMDestroyTreeNode(WMTreeNode *aNode);
+
+void WMDeleteLeafForTreeNode(WMTreeNode *aNode, int index);
+
+void WMRemoveLeafForTreeNode(WMTreeNode *aNode, void *leaf);
+
+void* WMReplaceDataForTreeNode(WMTreeNode *aNode, void *newData);
+
+void* WMGetDataForTreeNode(WMTreeNode *aNode);
+
+int WMGetTreeNodeDepth(WMTreeNode *aNode);
+
+WMTreeNode* WMGetParentForTreeNode(WMTreeNode *aNode);
+
+/* Sort only the leaves of the passed node */
+void WMSortLeavesForTreeNode(WMTreeNode *aNode, WMCompareDataProc *comparer);
+
+/* Sort all tree recursively starting from the passed node */
+void WMSortTree(WMTreeNode *aNode, WMCompareDataProc *comparer);
+
+/* Returns the first node which matches node's data with cdata by 'match' */
+WMTreeNode* WMFindInTree(WMTreeNode *aTree, WMMatchDataProc *match, void *cdata);
+
+/* Returns first tree node that has data == cdata */
+#define WMGetFirstInTree(aTree, cdata) WMFindInTree(aTree, NULL, cdata)
/* ---[ WINGs/data.c ]---------------------------------------------------- */
diff --git a/WINGs/tree.c b/WINGs/tree.c
new file mode 100644
index 0000000..875d46d
--- /dev/null
+++ b/WINGs/tree.c
@@ -0,0 +1,231 @@
+
+#include <string.h>
+
+#include "WUtil.h"
+
+typedef struct W_TreeNode {
+ void *data;
+
+ /*unsigned int uflags:16; */
+
+ WMArray *leaves;
+
+ int depth;
+
+ struct W_TreeNode *parent;
+
+ WMFreeDataProc *destructor;
+} W_TreeNode;
+
+void destroyNode(void *data)
+{
+ WMTreeNode *aNode = (WMTreeNode *) data;
+
+ if (aNode->destructor) {
+ (*aNode->destructor) (aNode->data);
+ }
+ if (aNode->leaves) {
+ WMFreeArray(aNode->leaves);
+ }
+ wfree(aNode);
+}
+
+WMTreeNode *WMCreateTreeNode(void *data)
+{
+ return WMCreateTreeNodeWithDestructor(data, NULL);
+}
+
+WMTreeNode *WMCreateTreeNodeWithDestructor(void *data, WMFreeDataProc * destructor)
+{
+ WMTreeNode *aNode;
+
+ aNode = (WMTreeNode *) wmalloc(sizeof(W_TreeNode));
+ aNode->destructor = destructor;
+ aNode->data = data;
+ aNode->parent = NULL;
+ aNode->depth = 0;
+ aNode->leaves = NULL;
+ /*aNode->leaves = WMCreateArrayWithDestructor(1, destroyNode); */
+
+ return aNode;
+}
+
+WMTreeNode *WMInsertItemInTree(WMTreeNode * parent, int index, void *item)
+{
+ WMTreeNode *aNode;
+
+ wassertrv(parent != NULL, NULL);
+
+ aNode = WMCreateTreeNodeWithDestructor(item, parent->destructor);
+ aNode->parent = parent;
+ aNode->depth = parent->depth + 1;
+ if (!parent->leaves) {
+ parent->leaves = WMCreateArrayWithDestructor(1, destroyNode);
+ }
+ if (index < 0) {
+ WMAddToArray(parent->leaves, aNode);
+ } else {
+ WMInsertInArray(parent->leaves, index, aNode);
+ }
+
+ return aNode;
+}
+
+static void updateNodeDepth(WMTreeNode * aNode, int depth)
+{
+ int i;
+
+ aNode->depth = depth;
+
+ if (aNode->leaves) {
+ for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
+ updateNodeDepth(WMGetFromArray(aNode->leaves, i), depth + 1);
+ }
+ }
+}
+
+WMTreeNode *WMInsertNodeInTree(WMTreeNode * parent, int index, WMTreeNode * aNode)
+{
+ wassertrv(parent != NULL, NULL);
+ wassertrv(aNode != NULL, NULL);
+
+ aNode->parent = parent;
+ updateNodeDepth(aNode, parent->depth + 1);
+ if (!parent->leaves) {
+ parent->leaves = WMCreateArrayWithDestructor(1, destroyNode);
+ }
+ if (index < 0) {
+ WMAddToArray(parent->leaves, aNode);
+ } else {
+ WMInsertInArray(parent->leaves, index, aNode);
+ }
+
+ return aNode;
+}
+
+void WMDestroyTreeNode(WMTreeNode * aNode)
+{
+ wassertr(aNode != NULL);
+
+ if (aNode->parent && aNode->parent->leaves) {
+ WMRemoveFromArray(aNode->parent->leaves, aNode);
+ } else {
+ destroyNode(aNode);
+ }
+}
+
+void WMDeleteLeafForTreeNode(WMTreeNode * aNode, int index)
+{
+ wassertr(aNode != NULL);
+ wassertr(aNode->leaves != NULL);
+
+ WMDeleteFromArray(aNode->leaves, index);
+}
+
+static int sameData(const void *item, const void *data)
+{
+ return (((WMTreeNode *) item)->data == data);
+}
+
+void WMRemoveLeafForTreeNode(WMTreeNode * aNode, void *leaf)
+{
+ int index;
+
+ wassertr(aNode != NULL);
+ wassertr(aNode->leaves != NULL);
+
+ index = WMFindInArray(aNode->leaves, sameData, leaf);
+ if (index != WANotFound) {
+ WMDeleteFromArray(aNode->leaves, index);
+ }
+}
+
+void *WMReplaceDataForTreeNode(WMTreeNode * aNode, void *newData)
+{
+ void *old;
+
+ wassertrv(aNode != NULL, NULL);
+
+ old = aNode->data;
+ aNode->data = newData;
+
+ return old;
+}
+
+void *WMGetDataForTreeNode(WMTreeNode * aNode)
+{
+ return aNode->data;
+}
+
+int WMGetTreeNodeDepth(WMTreeNode * aNode)
+{
+ return aNode->depth;
+}
+
+WMTreeNode *WMGetParentForTreeNode(WMTreeNode * aNode)
+{
+ return aNode->parent;
+}
+
+void WMSortLeavesForTreeNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
+{
+ wassertr(aNode != NULL);
+
+ if (aNode->leaves) {
+ WMSortArray(aNode->leaves, comparer);
+ }
+}
+
+static void sortLeavesForNode(WMTreeNode * aNode, WMCompareDataProc * comparer)
+{
+ int i;
+
+ if (!aNode->leaves)
+ return;
+
+ WMSortArray(aNode->leaves, comparer);
+ for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
+ sortLeavesForNode(WMGetFromArray(aNode->leaves, i), comparer);
+ }
+}
+
+void WMSortTree(WMTreeNode * aNode, WMCompareDataProc * comparer)
+{
+ wassertr(aNode != NULL);
+
+ sortLeavesForNode(aNode, comparer);
+}
+
+static WMTreeNode *findNodeInTree(WMTreeNode * aNode, WMMatchDataProc * match, void *cdata)
+{
+ if (match == NULL) {
+ if (aNode->data == cdata) {
+ return aNode;
+ }
+ } else {
+ if ((*match) (aNode->data, cdata)) {
+ return aNode;
+ }
+ }
+
+ if (aNode->leaves) {
+ WMTreeNode *leaf;
+ int i;
+
+ for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
+ leaf = findNodeInTree(WMGetFromArray(aNode->leaves, i), match, cdata);
+ if (leaf) {
+ return leaf;
+ }
+ }
+ }
+
+ return NULL;
+}
+
+WMTreeNode *WMFindInTree(WMTreeNode * aTree, WMMatchDataProc * match, void *cdata)
+{
+ wassertrv(aTree != NULL, NULL);
+
+ return findNodeInTree(aTree, match, cdata);
+}
--
1.7.0.4
From 39530d4c44744d07495e2d5f9402848e72303037 Mon Sep 17 00:00:00 2001
From: Tamas TEVESZ <[email protected]>
Date: Thu, 7 Oct 2010 23:46:43 +0200
Subject: [PATCH] WINGs: tree enhancements
- add WMFindInTreeWithDepthLimit, which is like WMFindInTree, but
does not descend down more than a set limit.
- add WMTreeWalk, which will walk a WMTreeNode, running a callback
function on each node.
Signed-off-by: Tamas TEVESZ <[email protected]>
---
WINGs/WINGs/WUtil.h | 8 +++++++
WINGs/tree.c | 55 +++++++++++++++++++++++++++++++++++++-------------
2 files changed, 48 insertions(+), 15 deletions(-)
diff --git a/WINGs/WINGs/WUtil.h b/WINGs/WINGs/WUtil.h
index 5e68105..9f0c2a3 100644
--- a/WINGs/WINGs/WUtil.h
+++ b/WINGs/WINGs/WUtil.h
@@ -117,6 +117,7 @@ typedef void WMInputProc(int fd, int mask, void *clientData);
typedef int WMCompareDataProc(const void *item1, const void *item2);
+typedef void WMTreeWalkProc(WMTreeNode *aNode, void *data);
typedef void WMFreeDataProc(void *data);
@@ -642,9 +643,16 @@ void WMSortTree(WMTreeNode *aNode, WMCompareDataProc *comparer);
/* Returns the first node which matches node's data with cdata by 'match' */
WMTreeNode* WMFindInTree(WMTreeNode *aTree, WMMatchDataProc *match, void *cdata);
+/* Returns the first node where node's data matches cdata by 'match' and node is
+ * at most `limit' depths down from `aTree'. */
+WMTreeNode *WMFindInTreeWithDepthLimit(WMTreeNode * aTree, WMMatchDataProc * match, void *cdata, int limit);
+
/* Returns first tree node that has data == cdata */
#define WMGetFirstInTree(aTree, cdata) WMFindInTree(aTree, NULL, cdata)
+/* Walk every node of aNode with `walk' */
+void WMTreeWalk(WMTreeNode *aNode, WMTreeWalkProc * walk, void *data, Bool DepthFirst);
+
/* ---[ WINGs/data.c ]---------------------------------------------------- */
diff --git a/WINGs/tree.c b/WINGs/tree.c
index 875d46d..b8ae731 100644
--- a/WINGs/tree.c
+++ b/WINGs/tree.c
@@ -196,27 +196,22 @@ void WMSortTree(WMTreeNode * aNode, WMCompareDataProc * comparer)
sortLeavesForNode(aNode, comparer);
}
-static WMTreeNode *findNodeInTree(WMTreeNode * aNode, WMMatchDataProc * match, void *cdata)
+static WMTreeNode *findNodeInTree(WMTreeNode * aNode, WMMatchDataProc * match, void *cdata, int limit)
{
- if (match == NULL) {
- if (aNode->data == cdata) {
- return aNode;
- }
- } else {
- if ((*match) (aNode->data, cdata)) {
- return aNode;
- }
- }
+ if (match == NULL && aNode->data == cdata)
+ return aNode;
+ else if ((*match) (aNode->data, cdata))
+ return aNode;
- if (aNode->leaves) {
+ if (aNode->leaves && limit != 0) {
WMTreeNode *leaf;
int i;
for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
- leaf = findNodeInTree(WMGetFromArray(aNode->leaves, i), match, cdata);
- if (leaf) {
+ leaf = findNodeInTree(WMGetFromArray(aNode->leaves, i),
+ match, cdata, limit > 0 ? limit - 1 : limit);
+ if (leaf)
return leaf;
- }
}
}
@@ -227,5 +222,35 @@ WMTreeNode *WMFindInTree(WMTreeNode * aTree, WMMatchDataProc * match, void *cdat
{
wassertrv(aTree != NULL, NULL);
- return findNodeInTree(aTree, match, cdata);
+ return findNodeInTree(aTree, match, cdata, -1);
+}
+
+WMTreeNode *WMFindInTreeWithDepthLimit(WMTreeNode * aTree, WMMatchDataProc * match, void *cdata, int limit)
+{
+ wassertrv(aTree != NULL, NULL);
+ wassertrv(limit >= 0, NULL);
+
+ return findNodeInTree(aTree, match, cdata, limit);
+}
+
+void WMTreeWalk(WMTreeNode * aNode, WMTreeWalkProc * walk, void *data, Bool DepthFirst)
+{
+ int i;
+ WMTreeNode *leaf;
+
+ wassertr(aNode != NULL);
+
+ if (DepthFirst)
+ (*walk)(aNode, data);
+
+ if (aNode->leaves) {
+ for (i = 0; i < WMGetArrayItemCount(aNode->leaves); i++) {
+ leaf = (WMTreeNode *)WMGetFromArray(aNode->leaves, i);
+ WMTreeWalk(leaf, walk, data, DepthFirst);
+ }
+ }
+
+ if (!DepthFirst)
+ (*walk)(aNode, data);
}
+
--
1.7.0.4
