Learn C the Hard Way Practical Exercises on the Computational Subjects You Keep Avoiding (Like C) (Zed A. Shaw) (Z-Library)

ptg16283740 From the Library of Pankaj R Doharey

ptg16283740 LEARN C THE HARD WAY From the Library of Pankaj R Doharey

ptg16283740 Zed Shaw’s Hard Way Series emphasizes instruction and making things as the best way to get started in many computer science topics. Each book in the series is designed around short, understandable exercises that take you through a course of instruction that creates working software. All exercises are thoroughly tested to verify they work with real students, thus increasing your chance of success. The accompanying video walks you through the code in each exercise. Zed adds a bit of humor and inside jokes to make you laugh while you’re learning. Visit informit.com/hardway for a complete list of available publications. Make sure to connect with us! informit .com/socialconnect Zed Shaw’s Hard Way Series From the Library of Pankaj R Doharey

ptg16283740 LEARN C THE HARD WAY Practical Exercises on the Computational Subjects You Keep Avoiding (Like C) Zed A. Shaw New York • Boston • Indianapolis • San Francisco Toronto • Montreal • London • Munich • Paris • Madrid Capetown • Sydney • Tokyo • Singapore • Mexico City From the Library of Pankaj R Doharey

ptg16283740 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 the publisher was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals. The author and publisher 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. For information about buying this title in bulk quantities, or for special sales opportunities (which may include electronic versions; custom cover designs; and content particular to your business, training goals, marketing focus, or branding interests), please contact our corporate sales department at corpsales@pearsoned.com or (800) 382-3419. For government sales inquiries, please contact governmentsales@pearsoned.com. For questions about sales outside the U.S., please contact international@pearsoned.com. Visit us on the Web: informit.com/aw Library of Congress Cataloging-in-Publication Data Shaw, Zed, author. Learn C the hard way : practical exercises on the computational subjects you keep avoiding (like C) / Zed A. Shaw. pages cm Includes index. ISBN 978-0-321-88492-3 (pbk. : alk. paper)—ISBN 0-321-88492-2 (pbk. : alk. paper) 1. C (Computer program language)—Problems, exercises, etc. I. Title. QA76.73.C15S473 2016 005.13’3—dc23 2015020858 Copyright © 2016 Zed A. Shaw All rights reserved. Printed in the United States of America. This publication is protected by copyright, and permission must be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, 200 Old Tappan Road, Old Tappan, New Jersey 07657, or you may fax your request to (201) 236-3290. ISBN-13: 978-0-321-88492-3 ISBN-10: 0-321-88492-2 Text printed in the United States on recycled paper at RR Donnelley in Crawfordsville, Indiana. First printing, August 2015 From the Library of Pankaj R Doharey

ptg16283740 v Contents Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiv This Book Is Not Really about C . . . . . . . . . . . . . . . . . . . . . . . xv The Undefined Behaviorists . . . . . . . . . . . . . . . . . . . . . . . xvi C Is a Pretty and Ugly Language . . . . . . . . . . . . . . . . . . . . . xvii What You Will Learn . . . . . . . . . . . . . . . . . . . . . . . . . . xviii How to Read This Book . . . . . . . . . . . . . . . . . . . . . . . . . xviii The Videos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix The Core Competencies . . . . . . . . . . . . . . . . . . . . . . . . . . xix Reading and Writing . . . . . . . . . . . . . . . . . . . . . . . . . xix Attention to Detail . . . . . . . . . . . . . . . . . . . . . . . . . . xx Spotting Differences . . . . . . . . . . . . . . . . . . . . . . . . . . xx Planning and Debugging . . . . . . . . . . . . . . . . . . . . . . . xx Exercise 0 The Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Mac OS X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Text Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Do Not Use an IDE . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Exercise 1 Dust Off That Compiler . . . . . . . . . . . . . . . . . . . . . 6 Breaking It Down . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Exercise 2 Using Makefiles to Build . . . . . . . . . . . . . . . . . . . 10 Using Make . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Exercise 3 Formatted Printing . . . . . . . . . . . . . . . . . . . . . . . 14 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 External Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 From the Library of Pankaj R Doharey

ptg16283740 vi CONTENTS How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Exercise 4 Using a Debugger . . . . . . . . . . . . . . . . . . . . . . . . 18 GDB Tricks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 GDB Quick Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 LLDB Quick Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Exercise 5 Memorizing C Operators . . . . . . . . . . . . . . . . . . . . 20 How to Memorize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 The List of Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Exercise 6 Memorizing C Syntax . . . . . . . . . . . . . . . . . . . . . . 26 The Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Syntax Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 A Word of Encouragement . . . . . . . . . . . . . . . . . . . . . . . . 30 A Word of Warning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Exercise 7 Variables and Types . . . . . . . . . . . . . . . . . . . . . . . 32 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Exercise 8 If, Else-If, Else . . . . . . . . . . . . . . . . . . . . . . . . 36 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Exercise 9 While-Loop and Boolean Expressions . . . . . . . . . . . . 40 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Exercise 10 Switch Statements . . . . . . . . . . . . . . . . . . . . . . . 42 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Exercise 11 Arrays and Strings . . . . . . . . . . . . . . . . . . . . . . . 46 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Exercise 12 Sizes and Arrays . . . . . . . . . . . . . . . . . . . . . . . . 50 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 From the Library of Pankaj R Doharey

ptg16283740 CONTENTS vii How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Exercise 13 For-Loops and Arrays of Strings . . . . . . . . . . . . . . 54 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Understanding Arrays of Strings . . . . . . . . . . . . . . . . . . . . . 56 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Exercise 14 Writing and Using Functions . . . . . . . . . . . . . . . . . 58 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Exercise 15 Pointers, Dreaded Pointers . . . . . . . . . . . . . . . . . . 62 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Explaining Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Practical Pointer Usage . . . . . . . . . . . . . . . . . . . . . . . . . . 66 The Pointer Lexicon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Pointers Aren’t Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Exercise 16 Structs and Pointers to Them . . . . . . . . . . . . . . . . . 68 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Explaining Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 Exercise 17 Heap and Stack Memory Allocation . . . . . . . . . . . . . 74 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 Heap versus Stack Allocation . . . . . . . . . . . . . . . . . . . . . . . 80 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Exercise 18 Pointers to Functions . . . . . . . . . . . . . . . . . . . . . 84 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 Exercise 19 Zed’s Awesome Debug Macros . . . . . . . . . . . . . . . . 90 The C Error-Handling Problem . . . . . . . . . . . . . . . . . . . . . . 90 The Debug Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Using dbg.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 From the Library of Pankaj R Doharey

ptg16283740 viii CONTENTS What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 How the CPP Expands Macros . . . . . . . . . . . . . . . . . . . . . . 96 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Exercise 20 Advanced Debugging Techniques . . . . . . . . . . . . . . 100 Debug Printing versus GDB . . . . . . . . . . . . . . . . . . . . . . . . 100 A Debugging Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Exercise 21 Advanced Data Types and Flow Control . . . . . . . . . . 104 Available Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Type Modifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 Type Qualifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Type Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 Type Sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 Available Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Math Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 Data Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Logic Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Bit Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 Boolean Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 Assignment Operators . . . . . . . . . . . . . . . . . . . . . . . . . 110 Available Control Structures . . . . . . . . . . . . . . . . . . . . . . . 110 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Exercise 22 The Stack, Scope, and Globals . . . . . . . . . . . . . . . . 112 ex22.h and ex22.c . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 ex22_main.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Scope, Stack, and Bugs . . . . . . . . . . . . . . . . . . . . . . . . . . 118 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Exercise 23 Meet Duff’s Device . . . . . . . . . . . . . . . . . . . . . . . 120 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Solving the Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Why Bother? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 From the Library of Pankaj R Doharey

ptg16283740 CONTENTS ix Exercise 24 Input, Output, Files . . . . . . . . . . . . . . . . . . . . . . 126 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 The I/O Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Exercise 25 Variable Argument Functions . . . . . . . . . . . . . . . . 132 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Exercise 26 Project logfind . . . . . . . . . . . . . . . . . . . . . . . . 138 The logfind Specification . . . . . . . . . . . . . . . . . . . . . . . . 138 Exercise 27 Creative and Defensive Programming . . . . . . . . . . . . 140 The Creative Programmer Mind-Set . . . . . . . . . . . . . . . . . . . 140 The Defensive Programmer Mind-Set . . . . . . . . . . . . . . . . . . 141 The Eight Defensive Programmer Strategies . . . . . . . . . . . . . . 141 Applying the Eight Strategies . . . . . . . . . . . . . . . . . . . . . . 142 Never Trust Input . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 Prevent Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Fail Early and Openly . . . . . . . . . . . . . . . . . . . . . . . . . 146 Document Assumptions . . . . . . . . . . . . . . . . . . . . . . . . 147 Prevention over Documentation . . . . . . . . . . . . . . . . . . . 147 Automate Everything . . . . . . . . . . . . . . . . . . . . . . . . . 148 Simplify and Clarify . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Question Authority . . . . . . . . . . . . . . . . . . . . . . . . . . 149 Order Is Not Important . . . . . . . . . . . . . . . . . . . . . . . . . . 149 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Exercise 28 Intermediate Makefiles . . . . . . . . . . . . . . . . . . . 152 The Basic Project Structure . . . . . . . . . . . . . . . . . . . . . . . . 152 Makefile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 The Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 The Target Build . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 The Unit Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 The Cleaner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 The Install . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 The Checker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 From the Library of Pankaj R Doharey

ptg16283740 x CONTENTS What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Exercise 29 Libraries and Linking . . . . . . . . . . . . . . . . . . . . . 160 Dynamically Loading a Shared Library . . . . . . . . . . . . . . . . . 161 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 Exercise 30 Automated Testing . . . . . . . . . . . . . . . . . . . . . . 166 Wiring Up the Test Framework . . . . . . . . . . . . . . . . . . . . . 167 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 Exercise 31 Common Undefined Behavior . . . . . . . . . . . . . . . . 172 UB 20 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Common UBs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Exercise 32 Double Linked Lists . . . . . . . . . . . . . . . . . . . . . . 174 What Are Data Structures . . . . . . . . . . . . . . . . . . . . . . . . 178 Making the Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Exercise 33 Linked List Algorithms . . . . . . . . . . . . . . . . . . . . . 190 Bubble and Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . 190 The Unit Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 The Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 193 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 Exercise 34 Dynamic Array . . . . . . . . . . . . . . . . . . . . . . . . . 198 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . 205 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 From the Library of Pankaj R Doharey

ptg16283740 CONTENTS xi Exercise 35 Sorting and Searching . . . . . . . . . . . . . . . . . . . . . 208 Radix Sort and Binary Search . . . . . . . . . . . . . . . . . . . . . . . 211 C Unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 The Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 213 RadixMap_find and Binary Search . . . . . . . . . . . . . . . . . 219 RadixMap_sort and radix_sort . . . . . . . . . . . . . . . . . 220 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 Exercise 36 Safer Strings . . . . . . . . . . . . . . . . . . . . . . . . . . 224 Why C Strings Were a Horrible Idea . . . . . . . . . . . . . . . . . . . 224 Using bstrlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 Learning the Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 Exercise 37 Hashmaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 The Unit Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 Exercise 38 Hashmap Algorithms . . . . . . . . . . . . . . . . . . . . . 240 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 Exercise 39 String Algorithms . . . . . . . . . . . . . . . . . . . . . . . 248 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 Analyzing the Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258 Exercise 40 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . 260 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 Exercise 41 Project devpkg . . . . . . . . . . . . . . . . . . . . . . . . . 274 What Is devpkg? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 What We Want to Make . . . . . . . . . . . . . . . . . . . . . . . 274 The Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 The Apache Portable Runtime . . . . . . . . . . . . . . . . . . . . 275 Project Layout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 Other Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . 277 From the Library of Pankaj R Doharey

ptg16283740 xii CONTENTS The Makefile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 The Source Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 The DB Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279 The Shell Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 283 The Command Functions . . . . . . . . . . . . . . . . . . . . . . . 287 The devpkgMain Function . . . . . . . . . . . . . . . . . . . . . . 292 The Final Challenge . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 Exercise 42 Stacks and Queues . . . . . . . . . . . . . . . . . . . . . . . 296 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 Exercise 43 A Simple Statistics Engine . . . . . . . . . . . . . . . . . . . 300 Rolling Standard Deviation and Mean . . . . . . . . . . . . . . . . . 300 Implemention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 How to Use It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 Exercise 44 Ring Buffer . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 The Unit Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314 Exercise 45 A Simple TCP/IP Client . . . . . . . . . . . . . . . . . . . . . 316 Augment the Makefile . . . . . . . . . . . . . . . . . . . . . . . . . 316 The netclient Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 316 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 How to Break It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 Exercise 46 Ternary Search Tree . . . . . . . . . . . . . . . . . . . . . . 322 Advantages and Disadvantages . . . . . . . . . . . . . . . . . . . . . 330 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 Exercise 47 A Fast URL Router . . . . . . . . . . . . . . . . . . . . . . . 332 What You Should See . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 How to Improve It . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 Extra Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336 From the Library of Pankaj R Doharey

ptg16283740 CONTENTS xiii Exercise 48 A Simple Network Server . . . . . . . . . . . . . . . . . . . 338 The Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 Exercise 49 A Statistics Server . . . . . . . . . . . . . . . . . . . . . . . 340 Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 Exercise 50 Routing the Statistics . . . . . . . . . . . . . . . . . . . . . 342 Exercise 51 Storing the Statistics . . . . . . . . . . . . . . . . . . . . . . 344 The Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 Exercise 52 Hacking and Improving Your Server . . . . . . . . . . . . . 346 Next Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 From the Library of Pankaj R Doharey

ptg16283740 xiv Acknowledgments Iwould like to thank three kinds of people who helped make this book what it is today: the haters, the helpers, and the painters. The haters helped make this book stronger and more solid through their inflexibility of mind, ir- rational hero worship of old C gods, and complete lack of pedagogical expertise. Without their shining example of what not to be, I would have never worked so hard to make this book a com- plete introduction to becoming a better programmer. The helpers are DebraWilliams Cauley, Vicki Rowland, Elizabeth Ryan, the whole team at Addison- Wesley, and everyone online who sent in fixes and suggestions. Their work producing, fixing, edit- ing, and improving this book has formed it into a more professional and better piece of writing. The painters, Brian, Arthur, Vesta, and Sarah, helped me find a new way to express myself and to distract me from deadlines that Deb and Vicki clearly set for me but that I kept missing. Without painting and the gift of art these artists gave me, I would have a less meaningful and rich life. Thank you to all of you for helping me write this book. It may not be perfect, because no book is perfect, but it’s at least as good as I can possibly make it. From the Library of Pankaj R Doharey

ptg16283740 xv This Book Is Not Really about C P lease don’t feel cheated, but this book is not about teaching you C programming. You’ll learn to write programs in C, but the most important lesson you’ll get from this book is rigorous defensive programming. Today, toomany programmers simply assume that what they write works, but one day it will fail catastrophically. This is especially true if you’re the kind of person who has learned mostly modern languages that solve many problems for you. By reading this book and following my exercises, you’ll learn how to create software that defends itself from malicious activity and defects. I’m using C for a very specific reason: C is broken. It is full of design choices that made sense in the 1970s but make zero sense now. Everything from its unrestricted, wild use of pointers to its severely broken NUL terminated strings are to blame for nearly all of the security defects that hit C. It’s my belief that C is so broken that, while it’s in wide use, it’s the most difficult language to write securely. I would fathom that Assembly is actually easier to write securely than C. To be honest, and you’ll find out that I’m very honest, I don’t think that anybody should be writing new C code. If that’s the case, then why am I teaching you C? Because I want you to become a better, stronger programmer, and there are two reasons why C is an excellent language to learn if you want to get better. First, C’s lack of nearly every modern safety feature means you have to be more vigilant and more aware of what’s going on. If you can write secure, solid C code, you can write secure, solid code in any programming language. The techniques you learn will translate to every language you use from now on. Second, learning C gives you direct access to a mountain of legacy code, and teaches you the base syntax of a large number of descendant languages. Once you learn C, you can more easily learn C++, Java, Objective-C, and JavaScript, and even other languages become easier to learn. I don’t want to scare you away by telling you this, because I plan to make this book incredibly fun, easy, and devious. I’ll make it fun to learn C by giving you projects that you might not have done in other programming languages. I’ll make this book easy by using my proven pattern of exercises that has you doing C programming and building your skills slowly. I’ll make it devious by teaching you how to break and then secure your code so you understand why these issues matter. You’ll learn how to cause stack overflows, illegal memory access, and other common flaws that plague C programs so that you know what you’re up against. Getting through this book will be challenging, like all of my books, but when you’re done you will be a far better and more confident programmer. From the Library of Pankaj R Doharey

ptg16283740 xvi LEARN C THE HARD WAY The Undefined Behaviorists By the time you’re donewith this book, you’ll be able to debug, read, and fix almost any C program you run into, and then write new, solid C code should you need to. However, I’m not really going to teach you official C. You’ll learn the language, and you’ll learn how to use it well, but official C isn’t very secure. The vast majority of C programmers out there simply don’t write solid code, and it’s because of something called Undefined Behavior (UB). UB is a part of the American National Standards Institute (ANSI) C standard that lists all of the ways that a C compiler can disregard what you’ve written. There’s actually a part of the standard that says if you write code like this, then all bets are off and the compiler doesn’t have to do anything consistently. UB occurs when a C program reads off the end of a string, which is an incredibly common programming error in C. For a bit of background, C defines strings as blocks of memory that end in a NUL byte, or a 0 byte (to simplify the definition). Since many strings come from outside the program, it’s common for a C program to receive a string without this NUL byte. When it does, the C program attempts to read past the end of this string and into the memory of the computer, causing your program to crash. Every other language developed after C attempts to prevent this, but not C. C does so little to prevent UB that every C programmer seems to think it means they don’t have to deal with it. They write code full of potential NUL byte overruns, and when you point them out to these programmers, they say, ”Well that’s UB, and I don’t have to prevent it.” This reliance on C’s large number of UBs is why most C code is so horribly insecure. I write C code to try to avoid UB by either writing code that doesn’t trigger it, or writing code that attempts to prevent it. This turns out to be an impossible task because there is so much UB that it becomes a Gordian knot of interconnected pitfalls in your C code. As you go through this book, I’ll point out ways you can trigger UB, how to avoid it if you can, and how to trigger it in other people’s code if possible. However, you should keep in mind that avoiding the nearly random nature of UB is almost impossible, and you’ll just have to do your best. WARNING! You’ll find that hardcore C fans frequently will try to beat you up about UB. There’s a class of C programmers who don’t write very much C code but have memorized all of the UB just so they could beat up a beginner intellectually. If you run into one of these abusive programmers, please ignore them. Often, they aren’t practicing C programmers, they are arrogant, abusive, and will only end up asking you endless questions in an attempt to prove their superiority rather than helping you with your code. Should you ever need help with your C code, simply email me at help@learncodethehardway.org, and I will gladly help you. From the Library of Pankaj R Doharey

ptg16283740 THIS BOOK IS NOT REALLY ABOUT C xvii C Is a Pretty and Ugly Language The presence of UB though is one more reason why learning C is a good move if you want to be a better programmer. If you can write good, solid C code in the way I teach you, then you can survive any language. On the positive side, C is a really elegant language in many ways. Its syntax is actually incredibly small given the power it has. There’s a reason why so many other languages have copied its syntax over the last 45 or so years. C also gives you quite a lot using very little technology. When you’re done learning C, you’ll have an appreciation for a something that is very elegant and beautiful but also a little ugly at the same time. C is old, so like a beautiful monument, it will look fantastic from about 20 feet away, but when you step up close, you’ll see all the cracks and flaws it has. Because of this, I’m going to teach you the most recent version of C that I can make work with recent compilers. It’s a practical, straightforward, simple, yet complete subset of C that works well, works everywhere, and avoids many pitfalls. This is the C that I use to get real work done, and not the encyclopedic version of C that hardcore fans try and fail to use. I know the C that I use is solid because I spent two decades writing clean, solid C code that pow- ered large operations without much failure at all. My C code has probably processed trillions of transactions because it powered the operations of companies like Twitter and airbnb. It rarely failed or had security attacks against it. In the many years that my code powered the Ruby on Rails Web world, it’s run beautifully and even prevented security attacks, while other Web servers fell repeatedly to the simplest of attacks. My style of writing C code is solid, but more importantly, my mind-set when writing C is one every programmer should have. I approach C, and any programming, with the idea of preventing errors as best I can and assuming that nothing will work right. Other programmers, even supposedly good C programmers, tend to write code and assume everything will work, but rely on UB or the operating system to save them, neither of which will work as a solution. Just remember that if people try to tell you that the code I teach in this book isn’t “real C.” If they don’t have the same track record as me, maybe you can use what I teach you to show them why their code isn’t very secure. Does that mean my code is perfect? No, not at all. This is C code. Writing perfect C code is im- possible, and in fact, writing perfect code in any language is impossible. That’s half the fun and frustration of programming. I could take someone else’s code and tear it apart, and someone could take my code and tear it apart. All code is flawed, but the difference is that I try to assume my code is always flawed and then prevent the flaws. My gift to you, should you complete this book, is to teach you the defensive programming mind-set that has served me well for two decades, and has helped me make high-quality, robust software. From the Library of Pankaj R Doharey

ptg16283740 xviii LEARN C THE HARD WAY What You Will Learn The purpose of this book is to get you strong enough in C that you’ll be able to write your own software with it or modify someone else’s C code. After this book, you should read Brian Kernighan and Dennis Ritchie’s The C Programming Language, Second Edition (Prentice Hall, 1988), a book by the creators of the C language, also called K&R C. What I’ll teach you is • The basics of C syntax and idioms • Compilation, make files, linkers • Finding bugs and preventing them • Defensive coding practices • Breaking C code • Writing basic UNIX systems software By the final exercise, youwill havemore than enough ammunition to tackle basic systems software, libraries, and other smaller projects. How to Read This Book This book is intended for programmers who have learned at least one other programming lan- guage. I refer you to my book Learn Python the Hard Way (Addison-Wesley, 2013) if you haven’t learned a programming language yet. It’s meant for beginners and works very well as a first book on programming. Once you’ve completed Learn Python the Hard Way, then you can come back and start this book. For those who’ve already learned to code, this book may seem strange at first. It’s not like other books where you read paragraph after paragraph of prose and then type in a bit of code here and there. Instead, there are videos of lectures for each exercise, you code right away, and then I explain what you just did. This works better because it’s easier for me to explain something you’ve already done than to speak in an abstract sense about something you aren’t familiar with at all. Because of this structure, there are a few rules that you must follow in this book: • Watch the lecture video first, unless the exercise says otherwise. • Type in all of the code. Don’t copy-paste! • Type in the code exactly as it appears, even the comments. • Get it to run and make sure it prints the same output. • If there are bugs, fix them. From the Library of Pankaj R Doharey

ptg16283740 THIS BOOK IS NOT REALLY ABOUT C xix • Do the Extra Credit, but it’s all right to skip anything you can’t figure out. • Always try to figure it out first before trying to get help. If you follow these rules, do everything in the book, and still can’t code C, then you at least tried. It’s not for everyone, but just trying will make you a better programmer. The Videos Included in this course are videos for every exercise, and in many cases, more than one video for an exercise. These videos should be considered essential to get the full impact of the book’s educa- tional method. The reason for this is thatmany of the problems with writing C code are interactive issues with failure, debugging, and commands. C requires much more interaction to get the code running and to fix problems, unlike languages like Python and Ruby where code just runs. It’s also much easier to show you a video lecture on a topic, such as pointers or memory management, where I can demonstrate how the machine is actually working. I recommend that as you go through the course, you plan to watch the videos first, and then do the exercises unless directed to do otherwise. In some of the exercises, I use one video to present a problem and then another to demonstrate the solution. In most of the other exercises, I use a video to present a lecture, and then you do the exercise and complete it to learn the topic. The Core Competencies I’m going to guess that you have experience using a lesser language. One of those usable languages that lets you get away with sloppy thinking and half-baked hackery like Python or Ruby. Or, maybe you use a language like LISP that pretends the computer is some purely functional fantasy landwith padded walls for little babies. Maybe you’ve learned Prolog, and you think the entire world should just be a database where you walk around in it looking for clues. Even worse, I’m betting you’ve been using an integrated development environment (IDE), so your brain is riddled with memory holes, and you can’t even type an entire function’s name without hitting CTRL-SPACE after every three characters. No matter what your background is, you could probably use some improvement in these areas: Reading and Writing This is especially true if you use an IDE, but generally I find programmers do too much skimming and have problems reading for comprehension. They’ll just skim code that they need to under- stand in detail without taking the time to understand it. Other languages provide tools that let programmers avoid actually writing any code, so when faced with a language like C, they break down. The simplest thing to do is just understand that everyone has this problem, and you can fix it by forcing yourself to slow down and be meticulous about your reading and writing. At first, it’ll feel painful and annoying, but take frequent breaks, and then eventually it’ll be easier to do. From the Library of Pankaj R Doharey