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     ! 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.