lang/C/the.ansi.c.programming.language/c.programming.notes.int/sx8.html

   1 <!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
   2 <!-- This collection of hypertext pages is Copyright 1995-7 by Steve Summit. -->
   3 <!-- This material may be freely redistributed and used -->
   4 <!-- but may not be republished or sold without permission. -->
   5 <html>
   6 <head>
   7 <link rev="owner" href="mailto:scs@eskimo.com">
   8 <link rev="made" href="mailto:scs@eskimo.com">
   9 <title>Chapter 22: Pointers to Pointers</title>
  10 <link href="sx7.html" rev=precedes>
  11 <link href="sx9.html" rel=precedes>
  12 <link href="top.html" rev=subdocument>
  13 </head>
  14 <body>
  15 <H1>Chapter 22: Pointers to Pointers</H1>
  16
  17 <p>Since we can have pointers to <TT>int</TT>,
  18 and pointers to <TT>char</TT>,
  19 and pointers to any structures we've defined,
  20 and in fact pointers to any type in C,
  21 it shouldn't come as too much of a surprise that we can have
  22 pointers to other pointers.
  23 If we're used to thinking about simple pointers,
  24 and to keeping clear in our minds the distinction between
  25 <I>the pointer itself</I> and <I>what it points to</I>,
  26 we should be able to think about pointers to pointers, too,
  27 although we'll now have to distinguish between the pointer,
  28 what it points to,
  29 and what the pointer that it points to points to.
  30 (And, of course, we might also end up with
  31 pointers to pointers to pointers,
  32 or pointers to pointers to pointers to pointers,
  33 although these rapidly become too esoteric to have any practical
  34 use.)
  35 </p><p>The declaration of a pointer-to-pointer looks like
  36 <pre>
  37         int **ipp;
  38 </pre>
  39 where the two asterisks indicate
  40 that two levels of pointers are involved.
  41 </p><p>Starting off with the familiar, uninspiring,
  42 kindergarten-style examples,
  43 we can demonstrate the use of <TT>ipp</TT>
  44 by declaring some pointers for it to point to and some
  45 <TT>int</TT>s for those pointers to point to:
  46 <pre>
  47         int i = 5, j = 6; k = 7;
  48         int *ip1 = &amp;i, *ip2 = &amp;j;
  49 </pre>
  50 Now we can set
  51 <pre>
  52         ipp = &amp;ip1;
  53 </pre>
  54 and <TT>ipp</TT> points to <TT>ip1</TT> which points to <TT>i</TT>.
  55 <TT>*ipp</TT> is <TT>ip1</TT>,
  56 and <TT>**ipp</TT> is <TT>i</TT>, or 5.
  57 We can illustrate the situation,
  58 with our familiar box-and-arrow notation, like this:
  59 <br>
  60 <center><img src="fig22.1.gif"></center>
  61 <br>
  62 If we say
  63 <pre>
  64         *ipp = ip2;
  65 </pre>
  66 we've changed the pointer pointed to by <TT>ipp</TT>
  67 (that is, <TT>ip1</TT>)
  68 to contain a copy of <TT>ip2</TT>,
  69 so that it (<TT>ip1</TT>)
  70 now points at <TT>j</TT>:
  71 <br>
  72 <center><img src="fig22.2.gif"></center>
  73 <br>
  74 If we say
  75 <pre>
  76         *ipp = &amp;k;
  77 </pre>
  78 we've changed the pointer pointed to by <TT>ipp</TT>
  79 (that is, <TT>ip1</TT> again)
  80 to point to <TT>k</TT>:
  81 <br>
  82 <center><img src="fig22.3.gif"></center>
  83 <br>
  84 </p><p>What are pointers to pointers good for, in practice?
  85 One use is returning pointers from functions,
  86 via pointer arguments rather than as the formal return value.
  87 To explain this, let's first step back and consider the case of
  88 returning a simple type, such as <TT>int</TT>, from a function via
  89 a pointer argument.
  90 If we write the function
  91 <pre>
  92         f(int *ip)
  93         {
  94                 *ip = 5;
  95         }
  96 </pre>
  97 and then call it like this:
  98 <pre>
  99         int i;
 100         f(&amp;i);
 101 </pre>
 102 then <TT>f</TT> will ``return'' the value 5 by writing
 103 it to the location specified by the pointer passed by the caller;
 104 in this case, to the caller's variable <TT>i</TT>.
 105 A function might ``return'' values in this way if it
 106 had multiple things to return,
 107 since a function can only have one formal return value
 108 (that is, it can only return one value via the <TT>return</TT>
 109 statement.)
 110 The important thing to notice is that for the function to return
 111 a value of type <TT>int</TT>,
 112 it used a parameter of type pointer-to-<TT>int</TT>.
 113 </p><p>Now, suppose that a function wants to return a <em>pointer</em> in this way.
 114 The corresponding parameter will then have to be a pointer to a pointer.
 115 For example, here is a little function which tries to allocate
 116 memory for a string of length <TT>n</TT>,
 117 and which returns zero (``false'') if it fails and 1
 118 (nonzero, or ``true'') if it succeeds, returning the
 119 actual pointer to the allocated memory via a pointer:
 120 <pre>
 121         #include &lt;stdlib.h&gt;
 122
 123         int allocstr(int len, char **retptr)
 124         {
 125                 char *p = malloc(len + 1);      /* +1 for \0 */
 126                 if(p == NULL)
 127                         return 0;
 128                 *retptr = p;
 129                 return 1;
 130         }
 131 </pre>
 132 The caller can then do something like
 133 <pre>
 134         char *string = "Hello, world!";
 135         char *copystr;
 136         if(allocstr(strlen(string), &amp;copystr))
 137                 strcpy(copystr, string);
 138         else    fprintf(stderr, "out of memory\n");
 139 </pre>
 140 (This is a fairly crude example;
 141 the <TT>allocstr</TT> function is not terribly useful.
 142 It would have been just about as easy for the caller to call
 143 <TT>malloc</TT> directly.
 144 A different,
 145 and more useful,
 146 approach to writing a ``wrapper'' function around <TT>malloc</TT>
 147 is exemplified by the <TT>chkmalloc</TT> function we've been using.)
 148 </p><p>One side point about pointers to pointers and memory allocation:
 149 although the <TT>void *</TT> type,
 150 as returned by <TT>malloc</TT>,
 151 is a ``generic pointer,''
 152 suitable for assigning to or from pointers of any type,
 153 the hypothetical type <TT>void **</TT> is <em>not</em>
 154 a ``generic pointer to pointer.''
 155 Our <TT>allocstr</TT> example can only be used for allocating
 156 pointers to <TT>char</TT>.
 157 It would not be possible to use a function which returned generic
 158 pointers indirectly via a <TT>void **</TT> pointer,
 159 because when you tried to use it, for example by declaring and
 160 calling
 161 <pre>
 162         double *dptr;
 163         if(!hypotheticalwrapperfunc(100, sizeof(double), &amp;dptr))
 164                 fprintf(stderr, "out of memory\n");
 165 </pre>
 166 you would not be passing a <TT>void **</TT>,
 167 but rather a <TT>double **</TT>.
 168 </p><p>Another good use for pointers to pointers is in dynamically allocated,
 169 simulated multidimensional arrays,
 170 which we'll discuss in the next chapter.
 171 </p><p>As a final example,
 172 let's look at how pointers to pointers can be used to eliminate a
 173 nuisance we've had when trying to insert and delete items in
 174 linked lists.
 175 For simplicity, we'll consider lists of integers,
 176 built using this structure:
 177 <pre>
 178         struct list
 179                 {
 180                 int item;
 181                 struct list *next;
 182                 };
 183 </pre>
 184 Suppose we're trying to write
 185 some code
 186 to delete a given integer from a list.
 187 The straightforward solution looks like this:
 188 <pre>
 189         /* delete node containing i from list pointed to by lp */
 190
 191         struct list *lp, *prevlp;
 192         for(lp = list; lp != NULL; lp = lp-&gt;next)
 193                 {
 194                 if(lp-&gt;item == i)
 195                         {
 196                         if(lp == list)
 197                                 list = lp-&gt;next;
 198                         else    prevlp-&gt;next = lp-&gt;next;
 199                         break;
 200                         }
 201                 prevlp = lp;
 202                 }
 203         }
 204 </pre>
 205 This code works, but it has two blemishes.
 206 One is that it has to use an extra variable to keep track of the
 207 node one behind the one it's looking at,
 208 and the other is that it has to use an extra test to special-case the
 209 situation in which the node being deleted is at the head of the
 210 list.
 211 Both of these problems arise because the deletion of a node from
 212 the list involves modifying the previous pointer to point to the next node
 213 (that is, the node before the deleted node to point to the one
 214 following).
 215 But, depending on whether the node being deleted is the first
 216 node in the list or not,
 217 the pointer that needs modifying is either the pointer that
 218 points to the head of the list,
 219 or the <TT>next</TT> pointer in the previous node.
 220 </p><p>To illustrate this, suppose that we have the list (1, 2, 3)
 221 and we're trying to delete the element 1.
 222 After we've found the element 1,
 223 <TT>lp</TT> points to its node,
 224 which just happens to be the same node
 225 that the main <TT>list</TT> pointer points to,
 226 as illustrated in (a) below:
 227 <br>
 228 <center><img src="fig22.4.gif"></center>
 229 <br>
 230 To remove element 1 from the list,
 231 then,
 232 we must adjust the main <TT>list</TT> pointer
 233 so that it points to 2's node,
 234 the new head of the list
 235 (as shown in (b)).
 236 If we were trying to delete node 2, on the other hand
 237 (as illustrated in (c) above),
 238 we'd have to adjust node 1's <TT>next</TT> pointer to point to 3.
 239 The <TT>prevlp</TT> pointer keeps track of
 240 the previous node we were looking at,
 241 since
 242 (at other than the first node in the list)
 243 that's the node whose <TT>next</TT> pointer will need adjusting.
 244 (Notice that if we were to delete node 3,
 245 we would copy its <TT>next</TT> pointer over to 2,
 246 but since 3's <TT>next</TT> pointer is the null pointer,
 247 copying it to node 2
 248 would make node 2 the end of the list,
 249
 250 as desired.)
 251 </p><p>We can write another version of the list-deletion code,
 252 which is (in some ways, at least)
 253 much cleaner,
 254 by using a
 255 <em>pointer to a pointer</em>
 256 to a
 257 <TT>struct list</TT>.
 258 This pointer will point at the pointer which points at the node
 259 we're looking at;
 260 it will either point at the head pointer or at the <TT>next</TT>
 261 pointer of the node we looked at last time.
 262 Since this pointer points at the pointer that points at the node
 263 we're looking at (got that?),
 264 it points at the pointer which we need to modify if the node
 265 we're looking at is the node we're deleting.
 266 Let's see how the code looks:
 267 <pre>
 268         struct list **lpp;
 269         for(lpp = &amp;list; *lpp != NULL; lpp = &amp;(*lpp)-&gt;next)
 270                 {
 271                 if((*lpp)-&gt;item == i)
 272                         {
 273                         *lpp = (*lpp)-&gt;next;
 274                         break;
 275                         }
 276                 }
 277         }
 278 </pre>
 279 That single line
 280 <pre>
 281         *lpp = (*lpp)-&gt;next;
 282 </pre>
 283 updates the correct pointer,
 284 to splice the node
 285 it refers to
 286 out of the list,
 287 regardless of whether
 288 the pointer being updated is
 289 the head pointer
 290 or one of the <TT>next</TT> pointers.
 291 (Of course, the payoff is not absolute,
 292 because
 293 the use of a pointer to a pointer to a <TT>struct list</TT> leads
 294 to an algorithm which might not be nearly as obvious at first glance.)
 295 </p><p>To illustrate
 296 the use of the pointer-to-pointer <TT>lpp</TT>
 297 graphically,
 298 here are two more figures illustrating
 299 the situation just before deleting node 1
 300 (on the left)
 301 or node 2
 302 (on the right).
 303 <br>
 304 <center><img src="fig22.5.gif"></center>
 305 <br>
 306 In both cases,
 307 <TT>lpp</TT> points at a <TT>struct node</TT> pointer
 308 which points at the node to be deleted.
 309 In both cases,
 310 the pointer pointed to by <TT>lpp</TT>
 311 (that is, the pointer <TT>*lpp</TT>)
 312 is the pointer that needs to be updated.
 313 In both cases, the new pointer
 314 (the pointer that <TT>*lpp</TT> is to be updated <em>to</em>)
 315 is the <TT>next</TT> pointer of the node being deleted,
 316 which is always <TT>(*lpp)-&gt;next</TT>.
 317 </p><p>One other aspect of the code deserves mention.
 318 The expression
 319 <pre>
 320         (*lpp)-&gt;next
 321 </pre>
 322 describes the <TT>next</TT> pointer of the <TT>struct node</TT>
 323 which is pointed to by <TT>*lpp</TT>,
 324 that is,
 325 which is pointed to by the pointer
 326 which is pointed to by <TT>lpp</TT>.
 327 The expression
 328 <pre>
 329         lpp = &amp;(*lpp)-&gt;next
 330 </pre>
 331 sets <TT>lpp</TT> to point to the <TT>next</TT> field
 332 of the <TT>struct list</TT>
 333 pointed to by <TT>*lpp</TT>.
 334 In both cases,
 335 the parentheses
 336 around <TT>*lpp</TT>
 337 are needed because the precedence of <TT>*</TT> is
 338 lower than <TT>-&gt;</TT>.
 339 </p><p>As a second,
 340 related example,
 341 here is a piece of code for <em>inserting</em> a new node into a list,
 342 in its proper order.
 343 This code uses a pointer-to-pointer-to-<TT>struct list</TT>
 344 for the same reason,
 345 namely,
 346 so that it doesn't have to worry about treating the beginning of
 347 the list specially.
 348 <pre>
 349         /* insert node newlp into list */
 350
 351         struct list **lpp;
 352         for(lpp = &amp;list; *lpp != NULL; lpp = &amp;(*lpp)-&gt;next)
 353                 {
 354                 struct list *lp = *lpp;
 355                 if(newlp-&gt;item &lt; lp-&gt;item)
 356                         {
 357                         newlp-&gt;next = lp;
 358                         *lpp = newlp;
 359                         break;
 360                         }
 361                 }
 362         }
 363 </pre>
 364 </p><hr>
 365 <p>
 366 Read sequentially:
 367 <a href="sx7.html" rev=precedes>prev</a>
 368 <a href="sx9.html" rel=precedes>next</a>
 369 <a href="top.html" rev=subdocument>up</a>
 370 <a href="top.html">top</a>
 371 </p>
 372 <p>
 373 This page by <a href="http://www.eskimo.com/~scs/">Steve Summit</a>
 374 // <a href="copyright.html">Copyright</a> 1996-1999
 375 // <a href="mailto:scs@eskimo.com">mail feedback</a>
 376 </p>
 377 </body>
 378 </html>