Software 1 - Red-Black Tree & Preprocessor (7)

administrivia

Web Page - http://www.cs.tau.ac.il/~efif/courses/Software1_Summer_03

The C Preprocessor

• a translation applied before the compiler
  • preprocessor, compiler, linker
• textual substitution
  • file inclusion - inserting the contents of another file into your source file, as if you had typed it all in there
  • macro substitution - replacing instances of one piece of text with another.
  • conditional compilation - depending on various circumstances, certain parts of your source code are seen or not seen by the compiler

The C Preprocessor syntax

• line based - must begin at the beginning of a line, and each ends at the end of the line
  • you can break long lines with the '\' character at the end of the line
    • useful especially for text substitution directives
• begin with the # character
• knows nothing about C statements or expressions
  • playing tricky and outrageous games with the preprocessor is considered sporting in some circles

File inclusion

• a line of the form

  #include <filename.h>

  or

  #include "filename.h"

• the contents of the file filename.h is read, parsed, and compiled at that point.
• after filename.h is processed, compilation continues on the line following the #include line
• example
  place the prototypes of several related function in a header file myio.h

  extern int getline(char [], int);

  
  at the top of each source file add the line

  #include "myio.h"

• stdio.h - a collection of declarations (including external function prototype declarations)

the difference between the <> and ""

• where the preprocessor searches for filename.h?
  • files enclosed in <> - in central, standard directories
  • files enclosed in "" - in the current directory or the directory containing the including source file
• what do they contain?
  • "" - usually used for header files you've written,
  • <> - usually used for headers which are provided for you

what should you put in header files?

• external declarations of global variables and functions commonly used
• a global variable
  • must have exactly one defining instance,
  • can have external declarations in many places
• common declarations and definitions
  • if they ever change, they only have to be changed in one place
  • it is an error to declare a variable of one type externaly in one place and define its instance with another type
    • if the two places are two source files, separately compiled, only the linker will catch the discrepancy
  • ensures consistent declarations.
    • include the header in the source file where the defining instance appears, too
      • the compiler can check that the declaration and definition match

what should you put in header files?

• common declarations and definitions
  • preprocessor macro definitions
  • structure definitions (which we haven't seen yet)
  • typedef declarations (which we have hardly seen).
• however, there are a few things not to put in header files:
  • defining instances of global variables.
  • function bodies (which are also defining instances)
    • it's much better to learn how to use your compiler or linker to combine together separately-compiled object files

using a third-party library

• two-step process
  • you must #include the header in the files where you call the library functions,
  • you must tell the linker to read in the functions from the library itself

macro definition and substitution

• K&R Sec. 4.11.2
• a preprocessor line of the form

  #define name text

  • name - the given macro name
  • text - the given replacement text.
• name is replaced with text
  • after that for the rest of the current source file, or
  • until name is undefined

    #undef name

macro name and replacement text

• follows the same rules as ordinary identifiers
  • can contain only letters, digits, and underscores
  • may not begin with a digit
• since macros behave quite differently from normal variables (or functions), it is customary to give them names which are all capital letters
• the replacement text can be absolutely anything

macro use

• propagate constants around
• make them more self-documenting.
• example

  char line[100]; ... getline(line, 100);

  if we ever decide that 100 is too smal, we'll have to remember to change the number in two (or more) places.

  #define MAXLINE 100 char line[MAXLINE]; ... getline(line, MAXLINE);

macro definition and substitution syntax

• there does not have to be (and in fact there usually is not) a semicolon at the end of a #define line
• if you accidentally type

  #define MAXLINE 100; /* WRONG */

  then when you later declare

  char line[MAXLINE];

  the preprocessor will expand it to

  char line[100;]; /* WRONG */

macro evaluation

• evaluation not performed when the macro is defined
• suppose that you write something meaningless like

  #define A 2 #define B 3 #define C A + B int x = C * 2;

  you'd expect x to end up with the value 10, but
  • the preprocessor substitutes text for macros exactly as you have written it,
  • first, C is substituted

    int x = A + B * 2;

  • then, the macros A and B are substituted

    int x = 2 + 3 * 2;

  • using the normal precedence of multiplication over addition x is intialized with the value 8
• it is always a good idea to include explicit parentheses

  #define C (A + B)

macros which look like little functions

• macros like MAXLINE act like constant expressions
• macros can look like little functions
  • they expand to replacement text which is a function of the actual arguments they are invoked with
  • this is as far as we go here

conditional compilation

• K&R Sec. 4.11.3
• controls which parts of your program get compiled

  #ifdef name program text #else more program text #endif

• if name is defined, "program text" is compiled and "more program text" is ignored. Otherwise, the opposite
• different then if statement
  • controls which statements are executed at run time
• the #else is optional

other directives

• #ifndef name - compiles code if the macro is not defined
• #if expresion - compiles code if expression is true

  #if 0 program text #endif

• #if defined(name) - like #ifdef name, but can be augmented
  • #if defined(name1) && defined(name2)

conditional compilation is useful

• you are writing a portable program that depends on
  • compiler
  • operating system
  • computer
• different versions of code, one for each situation, between suitable #ifdef directives
• compilers have ways of letting you define macros from
  • the invocation command line

    cl.exe -Dname

  • in a configuration file
  • many predefine certain macro names related to the operating system, processor, or compiler in use.

example

• in ANSI C, the function to delete a file is remove
• on older Unix systems, the function was called unlink

  #ifdef unix unlink(filename); #else remove(filename); #endif

• you could place the line

  #define unix

  at the top of the file when compiling under an old Unix system
  • no need to give it any replacement text
  • any definition for a macro, even if the replacement text is empty, causes an #ifdef to succeed
• C compilers on old Unix systems tend to predefine it for you
  • no need to define the macro unix at all

conditional compilation is useful

• building different versions from the same source code
• compiling different versions with different features present in the different versions
• turn debugging statements on or off

  #ifdef DEBUG printf("x is %d\n", x); #endif

• define the macro DEBUG from the compiler invocatin line
  • use a compiler flag such as -DDEBUG

Red-black Binary Tree

• A binary tree that satisfies the following properties:
  • Each node has a color, which is either red or black.
  • A red node cannot have a red parent.
  • The number of black nodes from every path from the tree root to a leaf is the same for all tree leaves (it is called the 'black depth' of the tree).
  Propeties 2-3 guaranty that the depth of a red-black tree containing n nodes is bounded by 2*log₂(n).
• Code
  • rbtree.c
  • Red_black_tree.h
  • Red_black_tree.c
  • makefile
  • makefile_simple
  • html