C Interfaces and Implementations: Techniques for Creating Reusable Software

Every programmer and software project manager must master the art of creating reusable software modules; they are the building blocks of large, reliable applications. Unlike some modern object-oriented languages, C provides little linguistic support or motivation for creating reusable application programming interfaces (APIs). While most C programmers use APIs and the libraries that implement them in almost every application they write, relatively few programmers create and disseminate new, widely applicable APIs. C Interfaces and Implementations shows how to create reusable APIs using interface-based design, a language-independent methodology that separates interfaces from their implementations. This methodology is explained by example. The author describes in detail 24 interfaces and their implementations, providing the reader with a thorough understanding of this design approach. Features of C Interfaces and Implementations: *Concise interface descriptions that comprise a reference manual for programmers interested in using the interfaces.* A guided tour of the code that implements each chapter's interface tp help those modifying or extending an interface or designing related interfaces. *In-depth focus on "algorithm engineering:" how to package data structures and related algorithms into reusable modules. *Source code for 24 APIs and 8 sample applications is examined, with each presented as a "literate program" in which a thorough explanation is interleaved with the source code. *Rarely documented C programming tricks-of-the-trade. *Convenient access to all source code in the book via the World Wide Web at http://www.cs.princeton.edu/software/cii/ 0201498413B04062001

Table of Contents:
Preface xi Organization xiii Instructional Use xiv How to Get the Software xvi Acknowledgments xvii Chapter 1: Introduction 1 1.1 Literate Programs 2 1.2 Programming Style 8 1.3 Efficiency 11 Further Reading 12 Exercises 13 Chapter 2: Interfaces and Implementations 15 2.1 Interfaces 15 2.2 Implementations 18 2.3 Abstract Data Types 21 2.4 Client Responsibilities 24 2.5 Efficiency 30 Further Reading 30 Exercises 31 Chapter 3: Atoms 33 3.1 Interface 33 3.2 Implementation 34 Further Reading 42 Exercises 42 Chapter 4: Exceptions and Assertions 45 4.1 Interface 47 4.2 Implementation 53 4.3 Assertions 59 Further Reading 63 Exercises 64 Chapter 5: Memory Management 67 5.1 Interface 69 5.2 Production Implementation 73 5.3 Checking Implementation 76 Further Reading 85 Exercises 86 Chapter 6: More Memory Management 89 6.1 Interface 90 6.2 Implementation 92 Further Reading 98 Exercises 100 Chapter 7: Lists 103 7.1 Interface 103 7.2 Implementation 108 Further Reading 113 Exercises 114 Chapter 8: Tables 115 8.1 Interface 115 8.2 Example: Word Frequencies 118 8.3 Implementation 125 Further Reading 132 Exercises 133 Chapter 9: Sets 137 9.1 Interface 138 9.2 Example: Cross-Reference Listings 140 9.3 Implementation 148 Further Reading 158 Exercises 158 Chapter 10: Dynamic Arrays 161 10.1 Interfaces 162 10.2 Implementation 165 Further Reading 169 Exercises 169 Chapter 11: Sequences 171 11.1 Interface 171 11.2 Implementation 174 Further Reading 180 Exercises 180 Chapter 12: Rings 183 12.1 Interface 183 12.2 Implementation 187 Further Reading 196 Exercises 197 Chapter 13: Bit Vectors 199 13.1 Interface 199 13.2 Implementation 202 Further Reading 213 Exercises 213 Chapter 14: Formatting 215 14.1 Interface 216 14.2 Implementation 224 Further Reading 238 Exercises 239 Chapter 15: Low-Level Strings 241 15.1 Interface 243 15.2 Example: Printing Identifiers 249 15.3 Implementation 251 Further Reading 264 Exercises 265 Chapter 16: High-Level Strings 269 16.1 Interface 269 16.2 Implementation 276 Further Reading 293 Exercises 294 Chapter 17. Extended-Precision Arithmetic 297 17.1 Interface 297 17.2 Implementation 303 Further Reading 321 Exercises 322 Chapter 18: Arbitrary-Precision Arithmetic 323 18.1 Interface 323 18.2 Example: A Calculator 327 18.3 Implementation 334 Further Reading 353 Exercises 354 Chapter 19: Multiple-Precision Arithmetic 357 19.1 Interface 358 19.2 Example: Another Calculator 365 19.3 Implementation 373 Further Reading 402 Exercises 402 Chapter 20: Threads 405 20.1 Interfaces 408 20.2 Examples 418 20.3 Implementations 431 Further Reading 463 Exercises 465 Appendix: Interface Summary 469 Bibliography 497 Index 505