BasicPackagesDoc.tioga
Copyright Ó 1985, 1987, 1991 by Xerox Corporation. All rights reserved.
Russ Atkinson (RRA) June 24, 1985 9:52:35 pm PDT
Doug Wyatt, January 8, 1987 11:04:55 am PST
Rick Beach, March 13, 1987 11:22:43 am PST
Willie-Sue, November 25, 1987 12:09:35 pm PST
Michael Plass, October 14, 1991 1:29 pm PDT
BASIC PACKAGES
CEDAR 10.0 — FOR INTERNAL XEROX USE ONLY
Basic Packages
-- a collection of useful packages
Russ Atkinson
© Copyright 1985, 1987, 1991 Xerox Corporation. All rights reserved.
Abstract: BasicPackages is a collection of useful small packages that is loaded in the default Cedar system. It exports the following interfaces: Commander, PriorityQueue, Random, RedBlackTree, RefTab, RopeFile, RopeList, SymTab. Sadly, the documentation for these interfaces is contained in the source code for the interfaces.
Created by: various artists
Maintained by: Russ Atkinson <Atkinson.pa>
Keywords: command registry, data structures, hash table, lists, queues, random numbers, REF, ROPE, symbol tables
XEROX  Xerox Corporation
   Palo Alto Research Center
   3333 Coyote Hill Road
   Palo Alto, California 94304

For Internal Xerox Use Only
1. Commander
Commander manages command interpreter handles, primarily used by the CommandTool. Access to the registry of commands is properly monitorized. Access to Commander objects is not monitorized (concurrency is the client's responsibility).
2. PriorityQueue
PriorityQueue manages priority queue objects, which support insertion of arbitrary objects, with fast removal of the "best" object (determined by user predicate). Access to PriorityQueue objects is monitorized for concurrent access.
3. Prop
Prop provides an immutable property-list abstraction.
4. Random (moved to BootPackages component)
Random manages simple random number generator streams. Access to Random streams is monitorized for concurrent access.
5. RedBlackTree
RedBlackTree manages ordered symbol tables, where the user provides the sorting predicates. It uses self-adjusting trees to keep the nodes, with expected time of log(N) for insertion or deletion operations (worst case time of N). Access to RedBlackTree tables is monitorized for concurrent access.
6. RefTab (moved to BootPackages component)
RefTab manages hash tables that map from from REFs to REFs based on address equality, or on client-supplied equality and hash functions. It is a reasonably fast method of maintaining associations between objects. Access to RefTab tables is monitorized for concurrent access. Tables will grow as necessary to keep the density limited; see HashTableDoc.tioga for a lengthy discussion of this implementation.
7. RopeFile
RopeFile provides a means of making files into ropes. It is used underneath large Tioga files, although it has no Tioga dependence. Access to RopeFile ropes is monitorized for concurrent access.
RopeFile registers two Commander commands, RopeFiles and RopeFileParam, for inquiring about the status of RopeFile objects and setting various global parameters.
8. RopeList
RopeList manipulates lists of ropes much in the same way as List manipulates lists of REFs. Access to RopeFile ropes is not monitorized, concurrency is the responsibility of the client.
9. Scaled
Scaled provides arithmetic on 32-bit quantities with 16 bits of fraction.
10. SymTab (moved to BootPackages component)
SymTab manages symbol table objects, each of which is a fast hash table mapping from ropes to REFs. The hash size can be given at symbol table creation time to allow for tuning to the expected contents; as with RefTab, the table will grow as necessary to keep the density limited. The symbol lookup can be either case dependent (as for Mesa identifiers) or case independent (as for file names). Access to SymTab tables is monitorized for concurrent access.