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