From 2bfdf7e32fb4fb4b806264b323bac5237ed91705 Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Sat, 10 Jul 2010 22:19:57 +0200 Subject: New immutable list implementation --- src/List.vala | 145 +++++++++++++++++++++++++--------------------------------- src/Term.vala | 29 ++++++++---- src/Util.vala | 13 ++---- 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 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 list0 = new Gee.LinkedList(); - 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 vars, Gee.Map 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 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; } } -- cgit v1.2.3