Practical C — Giulio Zambon Practical C Giulio Zambon Practical C Giulio Zambon Harrison, Aust Capital Terr Australia ISBN-13 (pbk): 978-1-4842-1768-9 ISBN-13 (electronic): 978-1-4842-1769-6 DOI 10.1007/978-1-4842-1769-6 Library of Congress Control Number: 2016959617 Copyright © 2016 by Giulio Zambon This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Trademarked names, logos, and images may appear in this book. Rather than use a trademark symbol with every occurrence of a trademarked name, logo, or image we use the names, logos, and images only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. While the advice and information in this book are believed to be true and accurate at the date of publication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. Managing Director: Welmoed Spahr Lead Editor: Steve Anglin Technical Reviewer: Rohan Walia Editorial Board: Steve Anglin, Pramila Balan, Laura Berendson, Aaron Black, Louise Corrigan, Jonathan Gennick, Robert Hutchinson, Celestin Suresh John, Nikhil Karkal, James Markham, Susan McDermott, Matthew Moodie, Natalie Pao, Gwenan Spearing Coordinating Editor: Mark Powers Copy Editor: Kezia Endsley Compositor: SPi Global Indexer: SPi Global Artist: SPi Global Distributed to the book trade worldwide by Springer Science+Business Media New York, 233 Spring Street, 6th Floor, New York, NY 10013. Phone 1-800-SPRINGER, fax (201) 348-4505, e-mail o rders-ny@springer- sbm.com , or visit w ww.springeronline.com . Apress Media, LLC is a California LLC and the sole member (owner) is Springer Science + Business Media Finance Inc (SSBM Finance Inc). SSBM Finance Inc is a Delaware corporation. For information on translations, please e-mail [email protected] , or visit w ww.apress.com . Apress and friends of ED books may be purchased in bulk for academic, corporate, or promotional use. eBook versions and licenses are also available for most titles. For more information, reference our Special Bulk Sales–eBook Licensing web page at w ww.apress.com/bulk-sales . Any source code or other supplementary materials referenced by the author in this text are available to readers at www.apress.com/9781484217689 . For detailed information about how to locate your book’s source code, go to www.apress.com/source-code/ . Readers can also access source code at SpringerLink in the Supplementary Material section for each chapter. Printed on acid-free paper Contents at a Glance About the Author ...................................................................................................xiii About the Technical Reviewer .................................................................................xv ■ Chapter 1: Introduction .........................................................................................1 ■ Chapter 2: Tricky Bits ............................................................................................9 ■ Chapter 3: Iteration, Recursion, and Binary Trees ...............................................47 ■ Chapter 4: Lists, Stacks, and Queues ..................................................................85 ■ Chapter 5: Exception Handling ..........................................................................119 ■ Chapter 6: String Utilities ..................................................................................137 ■ Chapter 7: Dynamic Arrays ................................................................................185 ■ Chapter 8: Searching .........................................................................................207 ■ Chapter 9: Sorting .............................................................................................253 ■ Chapter 10: Numerical Integration ....................................................................275 ■ Chapter 11: Embedded Software .......................................................................315 ■ Chapter 12: Databases ......................................................................................337 ■ Chapter 13: Web Server Using Mongoose .........................................................375 ■ Chapter 14: Game Application: MathSearch ......................................................395 ■ Appendix A: Abbreviations and Acronyms ........................................................435 ■ Appendix B: Introduction to SQL ........................................................................439 Index .....................................................................................................................465 iii Contents About the Author ...................................................................................................xiii About the Technical Reviewer .................................................................................xv ■ Chapter 1: Introduction .........................................................................................1 Coding Style .....................................................................................................................1 Indentation ..............................................................................................................................................1 Naming and Other Conventions ..............................................................................................................4 The Use of goto .......................................................................................................................................5 How to Read This Book ....................................................................................................7 ■ Chapter 2: Tricky Bits ............................................................................................9 The Scope and Life of Variables .......................................................................................9 Local Variables ........................................................................................................................................9 Global Variables ....................................................................................................................................12 Functions ..............................................................................................................................................13 Call by Value ...................................................................................................................13 Preprocessor Macros .....................................................................................................16 Booleans .........................................................................................................................18 Structure Packing ...........................................................................................................20 Characters and Locales ..................................................................................................21 Normal and Wide Characters ..........................................................................................24 Dealing with Numbers ....................................................................................................28 Integers.................................................................................................................................................29 Floating-Point Numbers ........................................................................................................................30 Summary ........................................................................................................................46 v ■ CONTENTS ■ Chapter 3: Iteration, Recursion, and Binary Trees ...............................................47 Iteration ..........................................................................................................................47 Recursion .......................................................................................................................48 A Simple Example .................................................................................................................................49 Binary Trees ....................................................................................................................50 Displaying a Tree Graphically ................................................................................................................57 Generating a Random Tree ...................................................................................................................73 Traversing a Tree ..................................................................................................................................77 More Binary Trees .................................................................................................................................81 Summary ........................................................................................................................83 ■ Chapter 4: Lists, Stacks, and Queues ..................................................................85 There Are Lists and Lists ................................................................................................85 Stacks ............................................................................................................................86 Array-Based Stacks ..............................................................................................................................87 Linked-List Stacks ................................................................................................................................96 Queues .........................................................................................................................100 Array-Based Queues ...........................................................................................................................100 Linked-List Queues .............................................................................................................................113 Summary ......................................................................................................................117 ■ Chapter 5: Exception Handling ..........................................................................119 Long Jumps ..................................................................................................................120 Throw ...........................................................................................................................121 Try and Catch ...............................................................................................................122 Multiple Catches ...........................................................................................................128 Multiple Tries ................................................................................................................130 Examples ......................................................................................................................133 Summary ......................................................................................................................136 vi ■ CONTENTS ■ Chapter 6: String Utilities ..................................................................................137 String Allocation and Release ......................................................................................137 str_new() ............................................................................................................................................139 str_release() .......................................................................................................................................142 str_release_all() .................................................................................................................................144 str_list() ..............................................................................................................................................145 Some Examples ..................................................................................................................................146 Multiple Stacks ...................................................................................................................................149 String Formatting .........................................................................................................151 String Info .....................................................................................................................153 String Update ...............................................................................................................155 String Copy .........................................................................................................................................156 String Conversion ...............................................................................................................................158 String Clean Up ...................................................................................................................................159 String Remove ....................................................................................................................................161 Searches ......................................................................................................................163 Find a Character .................................................................................................................................163 Find a Substring .................................................................................................................................168 Replace ........................................................................................................................170 Replace a Character ...........................................................................................................................170 Replace a Substring ...........................................................................................................................172 Extract a Substring .......................................................................................................175 Concatenate Strings .....................................................................................................177 More Functionality? ......................................................................................................182 Summary ......................................................................................................................182 ■ Chapter 7: Dynamic Arrays ................................................................................185 Array Allocation and Release ........................................................................................185 Allocating an Array .............................................................................................................................186 Releasing an Array ..............................................................................................................................188 Multiple Stacks ...................................................................................................................................192 vii ■ CONTENTS Changing the Size of an Array ......................................................................................195 Array Copy and Duplication ..........................................................................................198 Select Array Elements ..................................................................................................201 Summary ......................................................................................................................205 ■ Chapter 8: Searching .........................................................................................207 Comparisons ................................................................................................................207 C Standard Comparison Functions .....................................................................................................207 Comparing Structures .........................................................................................................................210 Comparing Arrays ...............................................................................................................................211 Fuzziness ............................................................................................................................................211 Searches ......................................................................................................................216 Unordered Arrays of Integers ..............................................................................................................216 Unordered Arrays of Pointers ..............................................................................................................224 Ordered Arrays ....................................................................................................................................228 Linked Lists and Binary Search Trees .................................................................................................234 Summary ......................................................................................................................252 ■ Chapter 9: Sorting .............................................................................................253 Insertion Sort ................................................................................................................253 Shell Sort ......................................................................................................................254 Bubble Sort ...................................................................................................................259 Quicksort ......................................................................................................................260 Integer Arrays ...............................................................................................................268 The Standard C Function ..............................................................................................271 Summary ......................................................................................................................274 ■ Chapter 10: Numerical Integration ....................................................................275 Getting Started with One-Variable Functions ...............................................................275 The Trapezoidal Rule ....................................................................................................278 The Simpson’s Rule ......................................................................................................284 viii ■ CONTENTS The Newton-Cotes Formulas ........................................................................................286 Deciding When to Stop .................................................................................................289 Singularities .................................................................................................................293 Maximum and Minimum .....................................................................................................................294 Monte Carlo ..................................................................................................................296 3D Integration ...............................................................................................................300 Integration Domains ...........................................................................................................................301 From Trapezoid in 2D to Prism in 3D ..................................................................................................303 Improving the Prism Rule ...................................................................................................................307 Converting the Rectangular Rule to 3D ..............................................................................................311 Final Considerations on Multiple Integrals ...................................................................313 Summary ......................................................................................................................314 ■ Chapter 11: Embedded Software .......................................................................315 Bit Operations ...............................................................................................................315 Endianness ...................................................................................................................319 Embedded Environments .............................................................................................320 Naked Boards .....................................................................................................................................320 Real-Time OSs (RTOSs) .......................................................................................................................321 High-Level OSs ...................................................................................................................................321 Signals and Interrupts ..................................................................................................322 Concurrency .................................................................................................................332 Summary ......................................................................................................................336 ■ Chapter 12: Databases ......................................................................................337 MySQL ..........................................................................................................................337 Using the CLI to Create and Populate a Database ..............................................................................338 The MySQL Workbench .......................................................................................................................345 Using MySQL from a C Program .........................................................................................................347 ix ■ CONTENTS SQLite ...........................................................................................................................360 Using SQLite from the CLI ...................................................................................................................364 Using SQLite from C ............................................................................................................................365 Using Dynamic Strings and Arrays .....................................................................................................369 Summary ......................................................................................................................374 ■ Chapter 13: Web Server Using Mongoose .........................................................375 Web Pages and Protocols .............................................................................................375 Dynamic Web Pages .....................................................................................................378 The Simplest Application with a Web Server ................................................................378 Event Handler .....................................................................................................................................380 Main ....................................................................................................................................................381 An Application with a Web Server ................................................................................381 Static Variables ...................................................................................................................................384 main() .................................................................................................................................................384 e_handler(), get_x(), and send_response() .........................................................................................385 index.html ...........................................................................................................................................387 Tailoring Mongoose ......................................................................................................391 Summary ......................................................................................................................394 ■ Chapter 14: Game Application: MathSearch ......................................................395 MathSearch Specifi cation and Design .........................................................................396 MathSearch Specs ..............................................................................................................................397 MathSearch Design ............................................................................................................................397 Implementing MathSearch ...........................................................................................399 Module: main ......................................................................................................................................399 Module: count ...............................................................................................................416 Module: display ............................................................................................................417 Module: save_html .......................................................................................................424 Module: save_images ..................................................................................................430 Summary ......................................................................................................................434 x