C Interfaces and Implementations Techniques for Creating Reusable Software (David R. Hanson) (Z-Library)

Table of Contents Copyright................................................................................................................................ 1 Addison-Wesley Professional Computing Series..................................................................... 1 Preface................................................................................................................................... 4 Acknowledgments................................................................................................................. 10 Chapter 1. Introduction......................................................................................................... 12 Section 1.1. Literate Programs....................................................................................................................................................................................................... 13 Section 1.2. Programming Style..................................................................................................................................................................................................... 19 Section 1.3. Efficiency.................................................................................................................................................................................................................... 22 Further Reading............................................................................................................................................................................................................................ 23 Exercises........................................................................................................................................................................................................................................ 24 Chapter 2. Interfaces and Implementations.......................................................................... 26 Section 2.1. Interfaces.................................................................................................................................................................................................................... 26 Section 2.2. Implementations....................................................................................................................................................................................................... 29 Section 2.3. Abstract Data Types.................................................................................................................................................................................................. 32 Section 2.4. Client Responsibilities............................................................................................................................................................................................... 35 Section 2.5. Efficiency.................................................................................................................................................................................................................... 41 Further Reading............................................................................................................................................................................................................................. 41 Exercises........................................................................................................................................................................................................................................ 42 Chapter 3. Atoms.................................................................................................................. 44 Section 3.1. Interface..................................................................................................................................................................................................................... 44 Section 3.2. Implementation......................................................................................................................................................................................................... 45 Further Reading............................................................................................................................................................................................................................. 53 Exercises........................................................................................................................................................................................................................................ 53 Chapter 4. Exceptions and Assertions................................................................................... 56 Section 4.1. Interface..................................................................................................................................................................................................................... 58 Section 4.2. Implementation......................................................................................................................................................................................................... 64 Section 4.3. Assertions.................................................................................................................................................................................................................. 70 Further Reading............................................................................................................................................................................................................................. 74 Exercises........................................................................................................................................................................................................................................ 75 Chapter 5. Memory Management.......................................................................................... 78 Section 5.1. Interface..................................................................................................................................................................................................................... 80 Section 5.2. Production Implementation...................................................................................................................................................................................... 84 Section 5.3. Checking Implementation......................................................................................................................................................................................... 87 Further Reading............................................................................................................................................................................................................................ 96 Exercises........................................................................................................................................................................................................................................ 97 Chapter 6. More Memory Management............................................................................... 100 Section 6.1. Interface.................................................................................................................................................................................................................... 101 Section 6.2. Implementation....................................................................................................................................................................................................... 103 Further Reading........................................................................................................................................................................................................................... 109 Exercises....................................................................................................................................................................................................................................... 111 Chapter 7. Lists.................................................................................................................... 114 Section 7.1. Interface.................................................................................................................................................................................................................... 114 Section 7.2. Implementation........................................................................................................................................................................................................ 119 Further Reading........................................................................................................................................................................................................................... 124 Exercises....................................................................................................................................................................................................................................... 125 Chapter 8. Tables................................................................................................................ 126 Section 8.1. Interface................................................................................................................................................................................................................... 126 Section 8.2. Example: Word Frequencies................................................................................................................................................................................... 129 Section 8.3. Implementation....................................................................................................................................................................................................... 136 Further Reading........................................................................................................................................................................................................................... 143 Exercises...................................................................................................................................................................................................................................... 144 Chapter 9. Sets.................................................................................................................... 148 Section 9.1. Interface................................................................................................................................................................................................................... 149 Section 9.2. Example: Cross-Reference Listings......................................................................................................................................................................... 151 Section 9.3. Implementation....................................................................................................................................................................................................... 159 Further Reading........................................................................................................................................................................................................................... 169 Exercises...................................................................................................................................................................................................................................... 169 Chapter 10. Dynamic Arrays................................................................................................ 172 Section 10.1. Interfaces................................................................................................................................................................................................................ 173 Section 10.2. Implementation...................................................................................................................................................................................................... 176 Further Reading.......................................................................................................................................................................................................................... 180 Exercises...................................................................................................................................................................................................................................... 180 Chapter 11. Sequences......................................................................................................... 182 Section 11.1. Interface.................................................................................................................................................................................................................. 182 Section 11.2. Implementation...................................................................................................................................................................................................... 185 C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

Further Reading........................................................................................................................................................................................................................... 191 Exercises....................................................................................................................................................................................................................................... 191 Chapter 12. Rings................................................................................................................ 194 Section 12.1. Interface.................................................................................................................................................................................................................. 194 Section 12.2. Implementation..................................................................................................................................................................................................... 198 Further Reading.......................................................................................................................................................................................................................... 207 Exercises...................................................................................................................................................................................................................................... 208 Chapter 13. Bit Vectors........................................................................................................ 210 Section 13.1. Interface.................................................................................................................................................................................................................. 210 Section 13.2. Implementation...................................................................................................................................................................................................... 213 Further Reading.......................................................................................................................................................................................................................... 224 Exercises...................................................................................................................................................................................................................................... 224 Chapter 14. Formatting....................................................................................................... 226 Section 14.1. Interface.................................................................................................................................................................................................................. 227 Section 14.2. Implementation..................................................................................................................................................................................................... 235 Further Reading.......................................................................................................................................................................................................................... 249 Exercises...................................................................................................................................................................................................................................... 250 Chapter 15. Low-Level Strings............................................................................................. 252 Section 15.1. Interface.................................................................................................................................................................................................................. 254 Section 15.2. Example: Printing Identifiers................................................................................................................................................................................ 260 Section 15.3. Implementation..................................................................................................................................................................................................... 262 Further Reading........................................................................................................................................................................................................................... 275 Exercises...................................................................................................................................................................................................................................... 276 Chapter 16. High-Level Strings........................................................................................... 280 Section 16.1. Interface................................................................................................................................................................................................................. 280 Section 16.2. Implementation..................................................................................................................................................................................................... 287 Further Reading.......................................................................................................................................................................................................................... 304 Exercises...................................................................................................................................................................................................................................... 305 Chapter 17. Extended-Precision Arithmetic........................................................................ 308 Section 17.1. Interface................................................................................................................................................................................................................. 308 Section 17.2. Implementation...................................................................................................................................................................................................... 314 Further Reading.......................................................................................................................................................................................................................... 332 Exercises...................................................................................................................................................................................................................................... 333 Chapter 18. Arbitrary-Precision Arithmetic........................................................................ 334 Section 18.1. Interface................................................................................................................................................................................................................. 334 Section 18.2. Example: A Calculator........................................................................................................................................................................................... 338 Section 18.3. Implementation..................................................................................................................................................................................................... 345 Further Reading.......................................................................................................................................................................................................................... 364 Exercises...................................................................................................................................................................................................................................... 365 Chapter 19. Multiple-Precision Arithmetic.......................................................................... 368 Section 19.1. Interface................................................................................................................................................................................................................. 369 Section 19.2. Example: Another Calculator................................................................................................................................................................................ 376 Section 19.3. Implementation..................................................................................................................................................................................................... 384 Further Reading........................................................................................................................................................................................................................... 413 Exercises....................................................................................................................................................................................................................................... 413 Chapter 20. Threads............................................................................................................ 416 Section 20.1. Interfaces................................................................................................................................................................................................................ 419 Section 20.2. Examples............................................................................................................................................................................................................... 429 Section 20.3. Implementations................................................................................................................................................................................................... 442 Further Reading........................................................................................................................................................................................................................... 474 Exercises...................................................................................................................................................................................................................................... 476 Interface Summary............................................................................................................. 480 AP................................................................................................................................................................................................................................................. 481 Arena........................................................................................................................................................................................................................................... 482 Arith............................................................................................................................................................................................................................................. 483 Array............................................................................................................................................................................................................................................ 483 ArrayRep...................................................................................................................................................................................................................................... 484 Assert........................................................................................................................................................................................................................................... 485 Atom............................................................................................................................................................................................................................................ 485 Bit................................................................................................................................................................................................................................................. 485 Chan............................................................................................................................................................................................................................................. 487 Except.......................................................................................................................................................................................................................................... 487 Fmt.............................................................................................................................................................................................................................................. 488 List............................................................................................................................................................................................................................................... 489 Mem............................................................................................................................................................................................................................................. 490 MP................................................................................................................................................................................................................................................ 491 Ring.............................................................................................................................................................................................................................................. 494 Sem.............................................................................................................................................................................................................................................. 495 Seq............................................................................................................................................................................................................................................... 496 Set................................................................................................................................................................................................................................................ 497 C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

Stack............................................................................................................................................................................................................................................ 498 Str................................................................................................................................................................................................................................................ 498 Table............................................................................................................................................................................................................................................. 501 Text.............................................................................................................................................................................................................................................. 502 Thread.......................................................................................................................................................................................................................................... 504 XP................................................................................................................................................................................................................................................. 505 Bibliography....................................................................................................................... 508 ...................................................................................................................................................................................................................................................... 515 bvdindexIndex..................................................................................................................... 515 C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

Addison-Wesley Professional Computing Series Brian W. Kernighan, Consulting Editor Ken Arnold/John Peyton, A C User’s Guide to ANSI C Tom Cargill, C++ Programming Style William R. Cheswick/Steven M. Bellovin, Firewalls and Internet Security: Repelling the Wily Hacker David A. Curry, UNIX® System Security: A Guide for Users and System Administrators Erich Gamma/Richard Helm/Ralph Johnson/John Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software David R. Hanson, C Interfaces and Implementations: Techniques for Creating Reusable Software John Lakos, Large Scale C++ Software Design Scott Meyers, Effective C++: 50 Specific Ways to Improve Your Programs and Designs Scott Meyers, More Effective C++: 35 New Ways to Improve Your Programs and Designs Robert B. Murray, C++ Strategies and Tactics David R. Musser/Atul Saini, STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library John K. Ousterhout, Tcl and the Tk Toolkit Craig Partridge, Gigabit Networking J. Stephen Pendergrast Jr., Desktop KornShell Graphical Programming Radia Perlman, Interconnections: Bridges and Routers David M. Piscitello/A. Lyman Chapin, Open Systems Networking: TCP/IP and OSI Stephen A. Rago, UNIX® System V Network Programming Curt Schimmel, UNIX® Systems for Modern Architectures: Symmetric Multiprocessing and Caching for Kernel Programmers W. Richard Stevens, Advanced Programming in the UNIX® Environment W. Richard Stevens, TCP/IP Illustrated, Volume 1: The Protocols W. Richard Stevens, TCP/IP Illustrated, Volume 3: TCP for Transactions, HTTP, NNTP, and the UNIX Domain Protocols Gary R. Wright/W. Richard Stevens, TCP/IP Illustrated, Volume 2: The Implementation C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

David R. Hanson Princeton University ▲ ▼▼ ADDISON-WESLEY An imprint of Addison Wesley Longman, Inc. Reading, Massachusetts • Harlow, England • Menlo Park, California Berkeley, California • Don Mills, Ontario • Sydney Bonn • Amsterdam • Tokyo • Mexico City IMPLEMENTATIONS INTERFACESC AND Techniques for Creating Reusable Software C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved. Licensed by Frank Liu 1740749

This book was prepared from camera-ready copy supplied by the author. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book and Addison Wesley Longman, Inc. was aware of a trademark claim, the designations have been printed in initial caps or all caps. The authors and publishers have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibility for errors or omissions. No liability is assumed for incidental or consequential damages in connection with or arising out of the use of the information or programs contained herein. The publisher offers discounts on this book when ordered in quantity for special sales. For more information, please contact: Corporate & Professional Publishing Group Addison Wesley Longman, Inc. One Jacob Way Reading, Massachusetts 01867 Library of Congress Cataloging-in-Publication Data Hanson, David R. C interfaces and implementations : techniques for creating reusable software / David R. Hanson. p. cm. –– (Addison-Wesley professional computing series) Includes bibliographical references and index. ISBN 0-201-49841-3 (pbk.) 1. C (Computer program language) 2. Computer software– –Reusability I. Title. II. Series. QA76.73.C15H37 1996 005.13'3––dc20 96-28817 CIP Copyright © 1997 by David R. Hanson. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form, or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. Published simultaneously in Canada. Text design by Wilson Graphics & Design (Kenneth J. Wilson). Text printed on recycled and acid-free paper. ISBN 0-201-49841-3 2 3 4 5 6 7 8 9 10-MA-00999897 Second printing, January 1997 C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

xi PREFACE rogrammers are inundated with information about application pro- gramming interfaces, or APIs. Yet, while most programmers use APIs and the libraries that implement them in almost every appli- cation they write, relatively few create and disseminate new, widely applicable, APIs. Indeed, programmers seem to prefer to “roll their own” instead of searching for a library that might meet their needs, perhaps because it is easier to write application-specific code than to craft well- designed APIs. I’m as guilty as the next programmer: lcc, a compiler for ANSI/ISO C written by Chris Fraser and myself, was built from the ground up. (lcc is described in A Retargetable C Compiler: Design and Implementation, Addison-Wesley, 1995.) A compiler exemplifies the kind of application for which it is possible to use standard interfaces and to create inter- faces that are useful elsewhere. Examples include interfaces for memory management, string and symbol tables, and list manipulation. But lcc uses only a few routines from the standard C library, and almost none of its code can be used directly in other applications. This book advocates a design methodology based on interfaces and their implementations, and it illustrates this methodology by describing 24 interfaces and their implementations in detail. These interfaces span a large part of the computing spectrum and include data structures, arithmetic, string processing, and concurrent programming. The imple- mentations aren’t toys — they’re designed for use in production code. As described below, the source code is freely available. There’s little support in the C programming language for the interface- based design methodology. Object-oriented languages, like C++ and Modula-3, have language features that encourage the separation of an interface from its implementation. Interface-based design is independent of any particular language, but it does require more programmer will- power and vigilance in languages like C, because it’s too easy to pollute an interface with implicit knowledge of its implementation and vice versa. P C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

xii PREFACE Once mastered, however, interface-based design can speed develop- ment time by building upon a foundation of general-purpose interfaces that can serve many applications. The foundation class libraries in some C++ environments are examples of this effect. Increased reuse of existing software — libraries of interface implementations — reduces initial development costs. It also reduces maintenance costs, because more of an application rests on well-tested implementations of general-purpose interfaces. The 24 interfaces come from several sources, and all have been revised for this book. Some of the interfaces for data structures — abstract data types — originated in lcc code, and in implementations of the Icon programming language done in the late 1970s and early 1980s (see R. E. Griswold and M. T. Griswold, The Icon Programming Language, Prentice Hall, 1990). Others come from the published work of other pro- grammers; the “Further Reading” sections at the end of each chapter give the details. Some of the interfaces are for data structures, but this is not a data structures book, per se. The emphasis is more on algorithm engineering — packaging data structures for general use in applications — than on data-structure algorithms. Good interface design does rely on appropri- ate data structures and efficient algorithms, however, so this book com- plements traditional data structure and algorithms texts like Robert Sedgewick’s Algorithms in C (Addison-Wesley, 1990). Most chapters describe one interface and its implementation; a few describe related interfaces. The “Interface” section in each chapter gives a concise, detailed description of the interface alone. For programmers interested only in the interfaces, these sections form a reference manual. A few chapters include “Example” sections, which illustrate the use of one or more interfaces in simple applications. The “Implementation” section in each chapter is a detailed tour of the code that implements the chapter’s interface. In a few cases, more than one implementation for the same interface is described, which illustrates an advantage of interface-based design. These sections are most useful for those modifying or extending an interface or designing related inter- faces. Many of the exercises explore design and implementation alterna- tives. It should not be necessary to read an “Implementation” section in order to understand how to use an interface. The interfaces, examples, and implementations are presented as liter- ate programs; that is, the source code is interleaved with its explanation in an order that best suits understanding the code. The code is extracted automatically from the text files for this book and assembled into the C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

ORGANIZATION xiii order dictated by the C programming language. Other book-length exam- ples of literate programming in C include A Retargetable C Compiler and The Stanford GraphBase: A Platform for Combinatorial Computing by D. E. Knuth (Addison-Wesley, 1993). Organization The material in this book falls into the following broad categories: Most readers will benefit from reading all of Chapters 1 through 4, because these chapters form the framework for the rest of the book. The remaining chapters can be read in any order, although some of the later chapters refer to their predecessors. Chapter 1 covers literate programming and issues of programming style and efficiency. Chapter 2 motivates and describes the interface- based design methodology, defines the relevant terminology, and tours two simple interfaces and their implementations. Chapter 3 describes Foundations 1. Introduction 2. Interfaces and Implementations 4. Exceptions and Assertions 5. Memory Management 6. More Memory Management Data Structures 7. Lists 8. Tables 9. Sets 10. Dynamic Arrays 11. Sequences 12. Rings 13. Bit Vectors Strings 3. Atoms 14. Formatting 15. Low-Level Strings 16. High-Level Strings Arithmetic 17. Extended-Precision Arithmetic 18. Arbitrary-Precision Arithmetic 19. Multiple-Precision Arithmetic Threads 20. Threads C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

xiv PREFACE the prototypical Atom interface, which is the simplest production-quality interface in this book. Chapter 4 introduces exceptions and assertions, which are used in every interface. Chapters 5 and 6 describe the memory management interfaces used by almost all the implementations. The rest of the chapters each describe an interface and its implementation. Instructional Use I assume that readers understand C at the level covered in undergradu- ate introductory programming courses, and have a working understand- ing of fundamental data structures at the level presented in texts like Algorithms in C. At Princeton, the material in this book is used in sys- tems programming courses from the sophomore to first-year graduate levels. Many of the interfaces use advanced C programming techniques, such as opaque pointers and pointers to pointers, and thus serve as non- trivial examples of those techniques, which are useful in systems pro- gramming and data structure courses. This book can be used for courses in several ways, the simplest being in project-oriented courses. In a compiler course, for example, students often build a compiler for a toy language. Substantial projects are com- mon in graphics courses as well. Many of the interfaces can simplify the projects in these kinds of courses by eliminating some of the grunt pro- gramming needed to get such projects off the ground. This usage helps students realize the enormous savings that reuse can bring to a project, and it often induces them to try interface-based design for their own parts of the project. This latter effect is particularly valuable in team projects, because that’s a way of life in the “real world.” Interfaces and implementations are the focus of Princeton’s sopho- more-level systems programming course. Assignments require students to be interface clients, implementors, and designers. In one assignment, for example, I distribute Section 8.1’s Table interface, the object code for its implementation, and the specifications for Section 8.2’s word fre- quency program, wf. The students must implement wf using only my object code for Table. In the next assignment, they get the object code for wf, and they must implement Table. Sometimes, I reverse these assignments, but both orders are eye-openers for most students. They are unaccustomed to having only object code for major parts of their program, and these assignments are usually their first exposure to the semiformal notation used in interfaces and program specification. C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

INSTRUCTIONAL USE xv Initial assignments also introduce checked runtime errors and asser- tions as integral parts of interface specifications. Again, it takes a few assignments before students begin to appreciate the value of these con- cepts. I forbid “unannounced” crashes; that is, crashes that are not announced by an assertion failure diagnostic. Programs that crash get a grade of zero. This penalty may seem unduly harsh, but it gets the stu- dents’ attention. They also gain an appreciation of the advantages of safe languages, like ML and Modula-3, in which unannounced crashes are impossible. (This grading policy is less harsh than it sounds, because in multipart assignments, only the offending part is penalized, and differ- ent assignments have different weights. I’ve given many zeros, but none has ever caused a course grade to shift by a whole point.) Once students have a few interfaces under their belts, later assign- ments ask them to design new interfaces and to live with their design choices. For example, one of Andrew Appel’s favorite assignments is a primality testing program. Students work in groups to design the inter- faces for the arbitrary-precision arithmetic that is needed for this assign- ment. The results are similar to the interfaces described in Chapters 17 through 19. Different groups design interfaces, and a postassignment comparison of these interfaces, in which the groups critique one anothers’ work, is always quite revealing. Kai Li accomplishes similar goals with a semester-long project that builds an X-based editor using the Tcl/Tk system (J. K. Ousterhout, Tcl and the Tk Toolkit, Addison- Wesley, 1994) and editor-specific interfaces designed and implemented by the students. Tk itself provides another good example of interface- based design. In advanced courses, I usually package assignments as interfaces and give the students free rein to revise and improve on them, and even to change the goals of the assignment. Giving them a starting point reduces the time required for assignment, and allowing substantial changes encourages creative students to explore alternatives. The unsuccessful alternatives are often more educational than the successful ones. Stu- dents invariably go down the wrong road, and they pay for it with greatly increased development time. When, in hindsight, they understand their mistakes, they come to appreciate that designing good interfaces is hard, but worth the effort, and they almost always become converts to interface-based design. C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

xvi PREFACE How to Get the Software The software in this book has been tested on the following platforms: A few of the implementations are machine-specific; they assume that the machine has two’s-complement integer and IEEE floating-point arith- metic, and that unsigned longs can hold object pointers. The source code for everything in this book is available for anony- mous ftp at ftp.cs.princeton.edu in pub/packages/cii. Use an ftp client to connect to ftp.cs.princeton.edu, change to the directory pub/packages/cii, and download the file README, which describes the contents of the directory and how to download the distribution. The most recent distributions are usually in files with names like ciixy.tar.gz or ciixy.zip, where xy is the version number; for exam- ple, 10 is version 1.0. ciixy.tar.gz is a UNIX tar file compressed with gzip, and ciixy.zip is a ZIP file compatible with PKZIP version 2.04g. The files in ciixy.zip are DOS/Windows text files; that is, their lines end with carriage returns and linefeeds. ciixy.zip may also be available on America Online, CompuServe, and other online services. Information is also available on the World Wide Web at the URL http://www.cs.princeton.edu/software/cii/. This page includes instructions on reporting bugs. processor operating systems compilers SPARC SunOS 4.1 lcc 3.5 gcc 2.7.2 Alpha OSF/1 3.2A lcc 4.0 gcc 2.6.3 cc MIPS R3000 IRIX 5.3 lcc 3.5 gcc 2.6.3 cc MIPS R3000 Ultrix 4.3 lcc 3.5 gcc 2.5.7 Pentium Windows 95 Windows NT 3.51 Microsoft Visual C/C++ 4.0 C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

ACKNOWLEDGMENTS xvii Acknowledgments I have been using some of the interfaces in this book for my own research projects and in courses at the University of Arizona and Prince- ton University since the late 1970s. Students in these courses have been guinea pigs for my drafts of these interfaces. Their feedback over the years has been an important contribution to both the code in this book and its explanation. The Princeton students in several offerings of COS 217 and COS 596 deserve special thanks, because they suffered unknow- ingly through the drafts of most of what’s in this book. Interfaces are a way of life at Digital’s System Research Center (SRC), and my 1992 and 1993 summers at SRC working on the Modula-3 project erased any doubts I may have harbored about the efficacy of this approach. My thanks to SRC for supporting my visits, and to Bill Kalsow, Eric Muller, and Greg Nelson for many illuminating discussions. My thanks to IDA’s Centers for Communications Research in Princeton and La Jolla for their support during the summer of 1994 and during my 1995–96 sabbatical. The CCRs provided ideal hideouts at which to plan and complete this book. Technical interactions with colleagues and students have contributed to this book in many ways. Even seemingly unrelated discussions have provoked improvements in my code and in its explanation. Thanks to Andrew Appel, Greg Astfalk, Jack Davidson, John Ellis, Mary Fernández, Chris Fraser, Alex Gounares, Kai Li, Jacob Navia, Maylee Noah, Rob Pike, Bill Plauger, John Reppy, Anne Rogers, and Richard Stevens. Careful readings of my code and prose by Rex Jaeschke, Brian Kernighan, Taj Khattra, Richard O’Keefe, Norman Ramsey, and David Spuler made a sig- nificant contribution to the quality of both. David R. Hanson C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved. Licensed by Frank Liu 1740749

C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

1 1 INTRODUCTION big program is made up of many small modules. These modules provide the functions, procedures, and data structures used in the program. Ideally, most of these modules are ready-made and come from libraries; only those that are specific to the application at hand need to be written from scratch. Assuming that library code has been tested thoroughly, only the application-specific code will contain bugs, and debugging can be confined to just that code. Unfortunately, this theoretical ideal rarely occurs in practice. Most programs are written from scratch, and they use libraries only for the lowest level facilities, such as I/O and memory management. Program- mers often write application-specific code for even these kinds of low- level components; it’s common, for example, to find applications in which the C library functions malloc and free have been replaced by custom memory-management functions. There are undoubtedly many reasons for this situation; one of them is that widely available libraries of robust, well designed modules are rare. Some of the libraries that are available are mediocre and lack standards. The C library has been standardized since 1989, and is only now appear- ing on most platforms. Another reason is size: Some libraries are so big that mastering them is a major undertaking. If this effort even appears to be close to the effort required to write the application, programmers may simply reim- plement the parts of the library they need. User-interface libraries, which have proliferated recently, often exhibit this problem. Library design and implementation are difficult. Designers must tread carefully between generality, simplicity, and efficiency. If the routines and data structures in a library are too general, they may be too hard to A C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

2 INTRODUCTION use or inefficient for their intended purposes. If they’re too simple, they run the risk of not satisfying the demands of applications that might use them. If they’re too confusing, programmers won’t use them. The C library itself provides a few examples; its realloc function, for instance, is a marvel of confusion. Library implementors face similar hurdles. Even if the design is done well, a poor implementation will scare off users. If an implementation is too slow or too big — or just perceived to be so — programmers will design their own replacements. Worst of all, if an implementation has bugs, it shatters the ideal outlined above and renders the library useless. This book describes the design and implementation of a library that is suitable for a wide range of applications written in the C programming language. The library exports a set of modules that provide functions and data structures for “programming-in-the-small.” These modules are suitable for use as “piece parts” in applications or application compo- nents that are a few thousand lines long. Most of the facilities described in the subsequent chapters are those covered in undergraduate courses on data structures and algorithms. But here, more attention is paid to how they are packaged and to making them robust. Each module is presented as an interface and its implemen- tation. This design methodology, explained in Chapter 2, separates mod- ule specifications from their implementations, promotes clarity and precision in those specifications, and helps provide robust imple- mentations. 1.1 Literate Programs This book describes modules not by prescription, but by example. Each chapter describes one or two interfaces and their implementations in full. These descriptions are presented as literate programs. The code for an interface and its implementation is intertwined with prose that explains it. More important, each chapter is the source code for the inter- faces and implementations it describes. The code is extracted automati- cally from the source text for this book; what you see is what you get. A literate program is composed of English prose and labeled chunks of program code. For example, compute x • y≡ sum = 0; C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

LITERATE PROGRAMS 3 for (i = 0; i < n; i++) sum += x[i]*y[i]; defines a chunk named compute x • y; its code computes the dot prod- uct of the arrays x and y. This chunk is used by referring to it in another chunk: function dotproduct≡ int dotProduct(int x[], int y[], int n) { int i, sum; compute x • y return sum; } When the chunk function dotproduct is extracted from the file that holds this chapter, its code is copied verbatim, uses of chunks are replaced by their code, and so on. The result of extracting function dot- product is a file that holds just the code: int dotProduct(int x[], int y[], int n) { int i, sum; sum = 0; for (i = 0; i < n; i++) sum += x[i]*y[i]; return sum; } A literate program can be presented in small pieces and documented thoroughly. English prose subsumes traditional program comments, and isn’t limited by the comment conventions of the programming language. The chunk facility frees literate programs from the ordering con- straints imposed by programming languages. The code can be revealed in whatever order is best for understanding it, not in the order dictated by rules that insist, for example, that definitions of program entities pre- cede their uses. The literate-programming system used in this book has a few more features that help describe programs piecemeal. To illustrate these fea- tures and to provide a complete example of a literate C program, the rest C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

4 INTRODUCTION of this section describes double, a program that detects adjacent identi- cal words in its input, such as “the the.” For example, the UNIX command % double intro.txt inter.txt intro.txt:10: the inter.txt:110: interface inter.txt:410: type inter.txt:611: if shows that “the” occurs twice in the file intro.txt; the second occur- rence appears on line 10; and double occurrences of “interface,” “type,” and “if” appear in inter.txt at the lines shown. If double is invoked with no arguments, it reads its standard input and omits the file names from its output. For example: % cat intro.txt inter.txt | double 10: the 143: interface 343: type 544: if In these and other displays, commands typed by the user are shown in a slanted typewriter font, and the output is shown in a regular type- writer font. Let’s start double by defining a root chunk that uses other chunks for each of the program’s components: double.c 4≡ includes 5 data 6 prototypes 6 functions 5 By convention, the root chunk is labeled with the program’s file name; extracting the chunk double.c 4 extracts the program. The other chunks are labeled with double’s top-level components. These components are listed in the order dictated by the C programming language, but they can be presented in any order. The 4 in double.c 4 is the page number on which the definition of the chunk begins. The numbers in the chunks used in double.c 4 are the C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.

LITERATE PROGRAMS 5 page numbers on which their definitions begin. These page numbers help readers navigate the code. The main function handles double’s arguments. It opens each file and calls doubleword to scan the file: functions 5≡ int main(int argc, char *argv[]) { int i; for (i = 1; i < argc; i++) { FILE *fp = fopen(argv[i], "r"); if (fp == NULL) { fprintf(stderr, "%s: can't open '%s' (%s)\n", argv[0], argv[i], strerror(errno)); return EXIT_FAILURE; } else { doubleword(argv[i], fp); fclose(fp); } } if (argc == 1) doubleword(NULL, stdin); return EXIT_SUCCESS; } includes 5≡ #include <stdio.h> #include <stdlib.h> #include <errno.h> The function doubleword needs to read words from a file. For the pur- poses of this program, a word is one or more nonspace characters, and case doesn’t matter. getword reads the next word from an opened file into buf[0..size-1] and returns one; it returns zero when it reaches the end of file. functions 5+≡ int getword(FILE *fp, char *buf, int size) { int c; c = getc(fp); scan forward to a nonspace character or EOF 6 C Interfaces and Implementations: Techniques for Creating Reusable Software. C Interfaces and Implementations: Techniques for Creating Reusable Software, ISBN: 9780321562807 Prepared for frliu@microsoft.com, Frank Liu Copyright © 1997 by David R. Hanson.. This download file is made available for personal use only and is subject to the Terms of Service. Any other use requires prior written consent from the copyright owner. Unauthorized use, reproduction and/or distribution are strictly prohibited and violate applicable laws. All rights reserved.