Files in this item



application/pdf9512576.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


Title:Categorization and analyzing linked structures
Author(s):Tsai, Mei-Chin
Doctoral Committee Chair(s):Harrison, Williams Ludwell, III,
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
Abstract:In this thesis, we categorize linked structures and linked substructures each into four groups based on two attributes, sharing and cycles. We show that these two attributes can be determined at compile-time by augmenting any store-based analysis with heap reference counts and the missing link property. An analysis, which has the form of an abstract interpretation, is defined and implemented with the program generator Z1. The language analyzed is a low-level intermediate form in which there is no user-level type information. This fact makes the analysis applicable to languages like C and C++, for which type casting and type violations are frequent.
A set of programs that create and manipulate linked structures is analyzed. The results show that the analysis is able to correctly recognize a variety of linked data structures, such as radix trees and binary search trees, and substructures, such as those defined by down and next pointer fields in meshes.
Issue Date:1994
Rights Information:Copyright 1994 Tsai, Mei-Chin
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9512576
OCLC Identifier:(UMI)AAI9512576

This item appears in the following Collection(s)

Item Statistics