Mercurial > hg > Members > nobuyasu > CbC

changeset 22:13a2c13bbd0b draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add unbalance_binary_tree.cbc
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 13 Aug 2012 03:49:55 +0900
parents 42f3a796c0be
children 72b74b3466f9
files DPP/memory.c Huffman/test-huffman.c compare/tree/unbalance_binary_tree.cbc
diffstat 3 files changed, 190 insertions(+), 82 deletions(-) [+]
line wrap: on
line diff
--- a/DPP/memory.c	Tue Aug 07 19:13:10 2012 +0900
+++ b/DPP/memory.c	Mon Aug 13 03:49:55 2012 +0900
@@ -1,21 +1,21 @@
 /*
 
-    memory fragment management library
+  memory fragment management library
 
-    Shinji Kono (2006)
+  Shinji Kono (2006)
 
-    usage:
+  usage:
 
-    MemoryPtr db = 0;
-    add_memory(address,length,&db);
+  MemoryPtr db = 0;
+  add_memory(address,length,&db);
 
-	memory pattern is copyied and stored in a binary tree in db.
-	All patterns are shared.
+  memory pattern is copyied and stored in a binary tree in db.
+  All patterns are shared.
 
-    memory pattern database (binary tree by pattern)
+  memory pattern database (binary tree by pattern)
 
 
- */
+*/
 
 #include <stdio.h>
 #include <stdlib.h>
@@ -49,9 +49,9 @@
 
 /*
 
-    make memory fragment as a part of the program state
+  make memory fragment as a part of the program state
 
- */
+*/
 
 MemoryPtr
 create_memory(void *adr, int length)
@@ -69,9 +69,9 @@
 
 /*
 
-    Compute hash value of a memory fragment
+  Compute hash value of a memory fragment
 
- */
+*/
 
 void
 compute_memory_hash1(MemoryPtr m)
@@ -89,25 +89,25 @@
 
 /*
 
-   Compare memory contents ( doesn't care about its address )
+  Compare memory contents ( doesn't care about its address )
 
- */
+*/
 
 int
 cmp_content(MemoryPtr a,MemoryPtr b)
 {
     if (a->length != b->length) {
-	if (a->length > b->length) {
-	    return 1;
-	} else {
-	    return -1;
-	}
+		if (a->length > b->length) {
+			return 1;
+		} else {
+			return -1;
+		}
     }
     if (a->hash == b->hash) {
 #if MEMORY_REPORT
-    memcmp_count ++;
+		memcmp_count ++;
 #endif
-	return memcmp(a->body,b->body,a->length);
+		return memcmp(a->body,b->body,a->length);
     } else if (a->hash > b->hash) {
         return 1;
     } else {
@@ -117,9 +117,9 @@
 
 /*
 
-   Compare entire memory contents ( doesn't care about its address )
+  Compare entire memory contents ( doesn't care about its address )
 
- */
+*/
 
 static int
 cmp_memory1(MemoryPtr a,MemoryPtr b)
@@ -128,7 +128,7 @@
     if ((r=cmp_content(a,b))) return r;
 
     if (a->adr==b->adr) {
-	return 0;
+		return 0;
     } 
     return (a->adr > b->adr) ? 1 : -1;
 }
@@ -138,26 +138,26 @@
 {
     int r;
     while(1) {
-	if ((r=cmp_memory1(a,b))) return r;
-	if (a->left && b->left) {
-	    if ((r=cmp_memory(a->left,b->left))) return r;
-	} else if (a->left || b->left) {
-	    return (a->left > b->left)? 1 : -1;
-	}
-	if (a->right && b->right) {
-	    a = a->right; b = b->right;
-	    // recursive loop
-	} else if (a->right || b->right) {
-	    return (a->right > b->right)? 1 : -1;
-	} else {
-	    return 0;  // singleton
-	}
+		if ((r=cmp_memory1(a,b))) return r;
+		if (a->left && b->left) {
+			if ((r=cmp_memory(a->left,b->left))) return r;
+		} else if (a->left || b->left) {
+			return (a->left > b->left)? 1 : -1;
+		}
+		if (a->right && b->right) {
+			a = a->right; b = b->right;
+			// recursive loop
+		} else if (a->right || b->right) {
+			return (a->right > b->right)? 1 : -1;
+		} else {
+			return 0;  // singleton
+		}
     }
 }
 
 /*
-    Make a copy of real memory fragments
- */
+  Make a copy of real memory fragments
+*/
 
 MemoryPtr 
 copy_memory1(MemoryPtr m)
@@ -165,8 +165,8 @@
     MemoryPtr new = create_memory(m->adr,m->length);
     void *p = (void *)malloc(m->length);
     if (!p) {
-	die_exit("can't alloc memory body");
-	return 0;
+		die_exit("can't alloc memory body");
+		return 0;
     }
 #if MEMORY_REPORT
     memory_body += m->length;
@@ -192,28 +192,28 @@
 }
 
 /*
-    restore copied memory save to the original addresses
- */
+  restore copied memory save to the original addresses
+*/
 
 void
 restore_memory(MemoryPtr m)
 {
     while (m) {
-	memcpy(m->adr,m->body,m->length);
+		memcpy(m->adr,m->body,m->length);
 #if MEMORY_REPORT
-    restore_count ++;
-    restore_size += m->length;
+		restore_count ++;
+		restore_size += m->length;
 #endif
-	if (m->left)  restore_memory(m->left);
-	m = m->right;
+		if (m->left)  restore_memory(m->left);
+		m = m->right;
     }
 }
 
 
 /*
-    get hash for all memeory fragments
-	initial value of hash should be zero
- */
+  get hash for all memeory fragments
+  initial value of hash should be zero
+*/
 
 int
 get_memory_hash(MemoryPtr m, int hash)
@@ -226,8 +226,8 @@
 }
 
 /*
-    add modified memory fragments to the pattern database
- */
+  add modified memory fragments to the pattern database
+*/
 
 MemoryPtr
 add_memory(void *ptr,int length, MemoryPtr *parent)
@@ -244,7 +244,7 @@
 
 int
 memory_lookup(MemoryPtr m, MemoryPtr *parent, 
-		    MemoryPtr (*new_memory)(MemoryPtr), MemoryPtr *out)
+			  MemoryPtr (*new_memory)(MemoryPtr), MemoryPtr *out)
 {
     MemoryPtr db;
     int r;
@@ -252,19 +252,19 @@
     while(1) {
         db = *parent;
         if (!db) {
-	    /* not found */
-	    if (new_memory && out) {
-		db = new_memory(m);
-		db->left = db->right = 0;
-		*out = *parent = db;
-	    }
+			/* not found */
+			if (new_memory && out) {
+				db = new_memory(m);
+				db->left = db->right = 0;
+				*out = *parent = db;
+			}
             return 0;
         }
         if(!(r = cmp_memory1(m,db))) {
             /* bingo */
-	    if (out) {
-		*out = db;
-	    }
+			if (out) {
+				*out = db;
+			}
             return 1;
         } else if (r>0) {
             parent = &db->left;
@@ -276,9 +276,9 @@
 }
 
 /*
-    memory range list management for state registration
-	this list points the real memory
- */
+  memory range list management for state registration
+  this list points the real memory
+*/
 
 MemoryPtr
 add_memory_range(void *ptr,int length, MemoryPtr *parent)
@@ -296,9 +296,9 @@
 cmp_range(MemoryPtr a,MemoryPtr b)
 {
     if (a->adr==b->adr) {
-	if (a->length != b->length) 
-	    die_exit("memory range inconsitency");
-	return 0;
+		if (a->length != b->length) 
+			die_exit("memory range inconsitency");
+		return 0;
     }
     return (a->adr > b->adr) ? 1 : -1;
 }
@@ -312,22 +312,22 @@
     while(1) {
         db = *parent;
         if (!db) {
-	    /* not found */
-	    if (out) {
-		db = create_memory(m->adr, m->length);
-		*out = *parent = db;
-	    }
+			/* not found */
+			if (out) {
+				db = create_memory(m->adr, m->length);
+				*out = *parent = db;
+			}
 #if MEMORY_REPORT
-	    range_count++;
-	    range_size+=m->length;
+			range_count++;
+			range_size+=m->length;
 #endif
             return 0;
         }
         if(!(r = cmp_range(m,db))) {
             /* bingo (actually an error) */
-	    if (out) {
-		*out = db;
-	    }
+			if (out) {
+				*out = db;
+			}
             return 1;
         } else if (r>0) {
             parent = &db->left;
--- a/Huffman/test-huffman.c	Tue Aug 07 19:13:10 2012 +0900
+++ b/Huffman/test-huffman.c	Mon Aug 13 03:49:55 2012 +0900
@@ -95,7 +95,7 @@
 	for (i=0; i<N; i++ ) {
 		if (*numbers[i] == 0) continue;
 		
-		nodes[node_count] = ;
+		nodes[node_count] =  ;
 		node_count++;
 
 	}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/compare/tree/unbalance_binary_tree.cbc	Mon Aug 13 03:49:55 2012 +0900
@@ -0,0 +1,108 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef struct Node Node;
+struct Node {
+	int num;
+	Node *left;
+	Node *right;
+};
+
+typedef struct Ds Ds;
+struct Ds {
+	Node *root;
+	int *numbers;
+	int size;
+	int i;
+	__code (*next)(Ds *ds);
+};
+
+
+Node *make_node();
+__code loop(Ds *ds);
+__code insert(Ds *ds, Node* p);
+__code create_nodes(Ds *ds);
+void print_nodes(Node *p);
+void free_nodes(Node *p);
+
+Node *make_node()
+{
+	Node *n = (Node *)malloc(sizeof(Node));
+	n->num = -1;
+	n->left = NULL;
+	n->right = NULL;
+	return n;
+}
+
+__code loop(Ds *ds)
+{
+	if (ds->i < ds->size) {
+		goto insert(ds, ds->root);
+	}
+
+	print_nodes(ds->root);
+	exit(0);
+}
+
+__code insert(Ds *ds, Node *p)
+{
+	if (p->num == -1) {
+		p->num = ds->numbers[ds->i];
+		ds->i++;
+
+		p->left = make_node();
+		p->right = make_node();
+		goto loop(ds);
+	}
+	if (p->num < ds->numbers[ds->i]) {
+		goto insert(ds,p->left);
+	} else {
+ 		goto insert(ds,p->right);
+	}
+}
+
+__code create_nodes(Ds *ds)
+{
+	Node *root = make_node();
+	root->num = ds->numbers[ds->i];
+	ds->i++;
+
+	root->left = make_node();
+	root->right = make_node();
+
+	ds->root = root;
+	goto insert(ds, root);
+}
+
+void print_nodes(Node *p)
+{
+	if (p->left != NULL) print_nodes(p->left);
+	if (p->num != -1) printf("%d \n",p->num);
+	if (p->right != NULL) print_nodes(p->right);
+}
+
+void free_nodes(Node *p)
+{
+	if (p->left != NULL) free_nodes(p->left);
+	if (p->right != NULL) free_nodes(p->right);
+	free(p);
+}
+
+void main1(Ds *ds)
+{
+	goto create_nodes(ds);
+}
+
+int main()
+{
+	int numbers[] = {3,5,10,2,65,23,19,42,50,29,32,67,33,31,99};
+	int size = sizeof(numbers)/sizeof(int);
+
+	Ds *ds = (Ds *)malloc(sizeof(Ds));
+	ds->numbers = numbers;
+	ds->size = size;
+	ds->i = 0;
+	goto main1(ds);
+
+	return 0;
+}