Return to table.sml CVS log

Up to [Research Unix] / researchv10no / cmd / sml / src / basics

Annotation of researchv10no/cmd/sml/src/basics/table.sml, revision 1.1.1.1

1.1       root        1: (* Copyright 1989 by AT&T Bell Laboratories *)
                      2: (* table.sml *)
                      3: 
                      4: structure Table =
                      5: struct
                      6:   datatype name = NIL | Name of string
                      7:   datatype 'a table = Hashed of {table : (Symbol.symbol * 'a) list array ref,
                      8:                                  elems : int ref, exn : exn, name : name}
                      9: 
                     10:   fun namednew(name, size, exn) =
                     11:       Hashed {table=ref(array(size,nil)),elems=ref 0, exn = exn, name = Name name}
                     12: 
                     13:   fun new(size, exn) =
                     14:       Hashed {table=ref(array(size,nil)),elems=ref 0, exn = exn, name = NIL}
                     15: 
                     16:   fun map (Hashed{table=ref a,exn,...}) (s: Symbol.symbol) =
                     17:       let fun find ((s',x)::r) = if s' = s then x else find r
                     18:             | find nil = raise exn
                     19:        in find (a sub Bits.andb(Symbol.number s, (length a)-1))
                     20:       end
                     21: 
                     22:   fun rem (Hashed{table=ref a,elems,...}) (s: Symbol.symbol) =
                     23:       let fun f ((b as (s',_))::r) =
                     24:                if s' = s then (dec elems; r) else b :: f r
                     25:            | f nil = nil
                     26:          val index = Bits.andb(Symbol.number s, (length a)-1)
                     27:        in update(a, index, f(a sub index))
                     28:       end
                     29: 
                     30:   fun app f (Hashed{table=ref a,...}) =
                     31:       let fun zap 0 = ()
                     32:            | zap n = let val m = n-1 in List.app f (a sub m); zap m end
                     33:        in zap(length a)
                     34:       end
                     35: 
                     36:   fun add (m as Hashed{table as ref a, elems, name, ...})
                     37:          (v as (s: Symbol.symbol,j)) =
                     38:       let val size = length a
                     39:          val i = Symbol.number s
                     40:        in if !elems <> size
                     41:          then let val index = Bits.andb(i, size-1)
                     42:                   fun f nil = (inc elems; [v])
                     43:                     | f ((a as (s',j))::b) = if s=s' then v::b else a::f b
                     44:                in update(a,index,f(a sub index))
                     45:               end
                     46:          else let val newsize = size+size
                     47:                   val newsize1 = newsize-1
                     48:                   val new = array(newsize,nil)
                     49:                   fun bucket n =
                     50:                       let fun add'(a,b,(v as (s,j))::rest) =
                     51:                               if Bits.andb(Symbol.number s, newsize1) = n
                     52:                               then add'(v::a,b,rest)
                     53:                               else add'(a,v::b,rest)
                     54:                             | add'(a,b,nil) = 
                     55:                               (update(new,n,a);
                     56:                                update(new,n+size,b);
                     57:                                bucket(n+1))
                     58:                       in add'(nil,nil,a sub n)
                     59:                       end
                     60:                in (case name
                     61:                      of NIL => ()
                     62:                       | Name name =>
                     63:                           (print("\nIncreasing size of table " ^ name ^ " to: ");
                     64:                            print newsize; print "\n"));
                     65:                   bucket 0 handle Subscript => ();
                     66:                   table := new;
                     67:                   add m v
                     68:               end
                     69:       end
                     70: 
                     71:   fun tableToList(Hashed{table,...})=
                     72:       let val a = ! table;
                     73:          val last = length a - 1
                     74:          fun loop (0, [], acc) = acc
                     75:          |   loop (n, first::rest, acc) = loop(n, rest, first::acc)
                     76:          |   loop (n,[], acc) = loop(n-1, a sub (n-1), acc)
                     77:        in loop(last,a sub last,[])
                     78:       end
                     79: 
                     80: end  (* structure Table *)

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.