riedl@cs.purdue.EDU (John T Riedl) (09/28/89)
A couple of minor bugs/questions: o In the documentation each of the Set class names ends with an 's' (e.g., CHSets). This does not agree with the implementation. o The hash function should probably expect an unsigned int. In CHSet it expects a signed int, and breaks if it gets a negative number. o Why can't I put () in a constructor if no arguments are expected? (Probably a g++ feature, not a libg++ bug.) o Why is ent.defs.h not included in ent.SLList.h automatically by genclass? It was needed every time I used SLList. o I was confused by the explanation of the use of odd pointers in CHSet. May I suggest that the old explanation: // The nodes are linked together serially via a version // of a trick used in some vtables: odd pointers are // actually links to the next table entry. // Not terrible, but not wonderful either be replaced with // A CHSet is implemented as an array (tab) of buckets, each of which // contains a pointer to a list of <T>CHNodes. Each node contains a // pointer to the next node in the list, and a pointer to the <T>. // The end of the list is marked by a next node pointer which is odd // when considered as an integer (least significant bit = 1). The // assumption is that CHNodes will all begin on even addresses. If // the odd pointer is right-shifted by one bit, it becomes the index // within the tab array of the next bucket (that is, bucket i has // next bucket pointer 2*(i+1)+1). // Currently the next bucket pointers are not used, though they are // initialized by the constructor and checked by the OK method. // Traversal is done by looping through the bucket indexes // sequentially, and following CHNode pointers within a bucket. // This implementation is not portable to machines with different // pointer and integer sizes, or on which CHNodes might be aligned on // odd byte boundaries, but allows the same pointer to be used for // chaining within a bucket and to the next bucket. Thanks, John