summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMatthias Schiffer <mschiffer@universe-factory.net>2010-07-10 22:19:57 +0200
committerMatthias Schiffer <mschiffer@universe-factory.net>2010-07-10 22:19:57 +0200
commit2bfdf7e32fb4fb4b806264b323bac5237ed91705 (patch)
treedcf1c37042b96c06d196d9d249332aa2262b63f8
parente65240c658ac1d43c5e2c1dcffd83d15605dc0f4 (diff)
downloadeva-2bfdf7e32fb4fb4b806264b323bac5237ed91705.tar
eva-2bfdf7e32fb4fb4b806264b323bac5237ed91705.zip
New immutable list implementation
-rw-r--r--src/List.vala145
-rw-r--r--src/Term.vala29
-rw-r--r--src/Util.vala13
3 files changed, 86 insertions, 101 deletions
diff --git a/src/List.vala b/src/List.vala
index e215db4..7637998 100644
--- a/src/List.vala
+++ b/src/List.vala
@@ -1,31 +1,56 @@
namespace Eva {
public class List : Object, Term {
+ private static List _empty;
+
+ private Term? _head;
private Term? _tail;
- public Gee.List<Term?> list {get; construct;}
- public Term? tail {
+ public static List empty {
+ get {
+ if(_empty == null)
+ _empty = new List.create_empty();
+
+ return _empty;
+ }
+ }
+
+ public Term head {
get {
+ assert(!is_empty);
+ return _head;
+ }
+ }
+ public Term tail {
+ get {
+ assert(!is_empty);
return _tail;
}
- set {
- if(value is List) {
- List l = value as List;
-
- list.add_all(l.list);
- _tail = l._tail;
+ }
+
+ public bool is_empty {
+ get {
+ if(this == _empty) {
+ assert(_head == null && _tail == null);
+ return true;
}
else {
- _tail = value;
+ assert(_head != null && _tail != null);
+ return false;
}
}
}
- public List() {
- Gee.List<Term?> list0 = new Gee.LinkedList<Term?>();
- Object(list: list0);
- tail = null;
+ public List(Term head0, Term tail0 = empty) {
+ _head = head0;
+ _tail = tail0;
+ }
+
+ private List.create_empty() {
+ _head = null;
+ _tail = null;
}
+
protected bool do_match(Term o, Gee.Map<string, Term> vars, Gee.Map<string, string> aliases) {
if(o is Var) {
return o.do_match(this, vars, aliases);
@@ -33,59 +58,19 @@ namespace Eva {
if(o is List) {
List l = o as List;
+ if(is_empty && l.is_empty)
+ return true;
- if(list.size != l.list.size)
- return false;
- if((tail == null) != (l.tail == null))
- return false;
- if(tail != null && !tail.do_match(l.tail, vars, aliases))
+ if(is_empty && !l.is_empty)
return false;
- Gee.Iterator<Term> lt = l.list.iterator();
- lt.first();
- foreach(Term t in list) {
- if(!t.do_match(lt.get(), vars, aliases))
- return false;
-
- lt.next();
- }
+ if(!is_empty && l.is_empty)
+ return false;
- return true;
+ return (_head.do_match(l.head, vars, aliases) && _tail.do_match(l.tail, vars, aliases));
}
else if(o is String) {
- if(tail != null)
- return false;
-
- string s = "";
-
- foreach(Term t in list) {
- unichar c;
-
- if(t is Int) {
- Int i = t as Int;
- if(i.value < 0 || i.value > 255)
- return false;
-
- c = (unichar)i.value;
- }
- else if(t is UInt) {
- UInt i = t as UInt;
- if(i.value > 255)
- return false;
-
- c = (unichar)i.value;
- }
- else {
- return false;
- }
-
- string buf = string.nfill(6, 0);
- c.to_utf8(buf);
-
- s += buf;
- }
-
- return (s == (o as String).value);
+ return do_match(string_to_list((o as String).value), vars, aliases);
}
else {
return false;
@@ -93,38 +78,32 @@ namespace Eva {
}
public string to_string() {
- string ret = "[";
- bool first = true;
+ if(is_empty)
+ return "[]";
- foreach(Term term in list) {
- if(first) {
- first = false;
- ret += term.to_string();
- }
- else {
- ret += "," + term.to_string();
- }
+ string ret = "[" + _head.to_string();
+
+ Term rest = _tail;
+ for(rest = _tail; rest is List && rest != List.empty; rest = (rest as List)._tail) {
+ ret += "," + (rest as List)._head.to_string();
}
- if(tail != null)
- ret += "|" + tail.to_string();
+ if(rest != List.empty) {
+ ret += "|" + rest.to_string();
+ }
return ret + "]";
}
public void encode(Erl.Buffer buffer) {
- if(!list.is_empty) {
- buffer.encode_list_header(list.size);
-
- foreach(Term term in list) {
- term.encode(buffer);
- }
- }
-
- if(tail == null)
+ if(is_empty) {
buffer.encode_empty_list();
- else
- tail.encode(buffer);
+ }
+ else {
+ buffer.encode_list_header(1);
+ _head.encode(buffer);
+ _tail.encode(buffer);
+ }
}
}
}
diff --git a/src/Term.vala b/src/Term.vala
index 6b08730..698bfc2 100644
--- a/src/Term.vala
+++ b/src/Term.vala
@@ -75,18 +75,14 @@ namespace Eva {
case Erl.TermType.NIL:
case Erl.TermType.LIST:
- List term = new List();
-
assert(Erl.decode_list_header(buffer, ref index, out size) == 0);
- if(size != 0) {
- for(int i = 0; i < size; ++i) {
- term.list.add(do_decode(buffer, ref index));
- }
- term.tail = do_decode(buffer, ref index);
+ if(size == 0) {
+ return List.empty;
+ }
+ else {
+ return decode_list(buffer, ref index, size);
}
-
- return term;
case Erl.TermType.STRING:
char[] value = new char[size+1];
@@ -119,6 +115,19 @@ namespace Eva {
assert_not_reached();
}
}
+
+ private static List decode_list(void *buffer, ref int index, int n) {
+ Term head = do_decode(buffer, ref index);
+ Term tail;
+
+ if(n > 1) {
+ tail = decode_list(buffer, ref index, n-1);
+ }
+ else {
+ tail = do_decode(buffer, ref index);
+ }
+
+ return new List(head, tail);
+ }
}
-
}
diff --git a/src/Util.vala b/src/Util.vala
index 3666f96..7c704fb 100644
--- a/src/Util.vala
+++ b/src/Util.vala
@@ -32,14 +32,11 @@ namespace Eva {
}
private List string_to_list(string str) {
- List ret = new List();
-
- for(unowned string rest = str; rest.length > 0; rest = rest.next_char()) {
- unichar c = rest.get_char();
-
- ret.list.add(new UInt(c));
+ if(str.length == 0) {
+ return List.empty;
+ }
+ else {
+ return new List(new UInt(str.get_char()), string_to_list(str.next_char()));
}
-
- return ret;
}
}