src/tokens.c

   1 /*******************************************************************************
   2  * Reverse Polish Notation calculator.                                         *
   3  * Copyright (c) 2007-2008, Samuel Fredrickson <kinghajj@gmail.com>            *
   4  * All rights reserved.                                                        *
   5  *                                                                             *
   6  * Redistribution and use in source and binary forms, with or without          *
   7  * modification, are permitted provided that the following conditions are met: *
   8  *     * Redistributions of source code must retain the above copyright        *
   9  *       notice, this list of conditions and the following disclaimer.         *
  10  *     * Redistributions in binary form must reproduce the above copyright     *
  11  *       notice, this list of conditions and the following disclaimer in the   *
  12  *       documentation and/or other materials provided with the distribution.  *
  13  *                                                                             *
  14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER ``AS IS'' AND ANY EXPRESS *
  15  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED           *
  16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE      *
  17  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY        *
  18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES  *
  19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR          *
  20  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER  *
  21  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT          *
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY   *
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH *
  24  * DAMAGE.                                                                     *
  25  ******************************************************************************/
  26
  27 /*******************************************************************************
  28  * tokens.c -- splits a string into tokens.                                    *
  29  *                                                                             *
  30  * this doesn't use strtok(), which would work, because I personally dislike   *
  31  * it. however, the gettok() function is equivalent.                           *
  32  ******************************************************************************/
  33
  34 #include <ctype.h>
  35 #include "rpn.h"
  36 #include <stdlib.h>
  37 #include <string.h>
  38
  39 #ifndef DOXYGEN_SKIP
  40
  41 // returns true if c occurs in delims.
  42 static inline bool is_delim(char c, char *delims)
  43 {
  44         bool is = false;
  45
  46         if(delims)
  47                 while(*delims && !(is = (*delims++ == c)));
  48
  49         return is;
  50 }
  51
  52 #endif // DOXYGEN_SKIP
  53
  54 /**
  55  * @param start  A pointer to a string; keeps track of current position in
  56  *               original string.
  57  * @param delims Characters that will deliminate tokens.
  58  * @return A pointer to the first found token, or NULL if none found.
  59  *
  60  * gettok() works by taking in a pointer to a string, searching through that
  61  * string for deliminators, then updating that string so that on the next call,
  62  * it will return the next token.
  63  *
  64  * Like strtok(), gettok() modifies the original string by inserting NULs where
  65  * it finds deliminators.
  66  *
  67  * @code
  68  * void foo(char *str)
  69  * {
  70  *     char *start = str, *tok;
  71  *
  72  *     while((tok = gettok(&start, " ")))
  73  *         processToken(tok);
  74  * }
  75  * @endcode
  76  */
  77 char *gettok(char **start, char *delims)
  78 {
  79         char *search, *token;
  80
  81         if(start && *start && **start && delims) {
  82                 // start searching from the start, and assume the token will be here.
  83                 search = token = *start;
  84
  85                 // find first delim.
  86                 while(*search && !is_delim(*search, delims))
  87                         search++;
  88
  89                 // nullify all consecutive delims.
  90                 while(*search && is_delim(*search, delims))
  91                         *search++ = '\0';
  92
  93                 // the next token is right after the end of the delims.
  94                 *start = search;
  95         }
  96         else token = NULL;
  97
  98         // if token is NULL, let it pass. if token is not NULL but points to a '\0',
  99         // then the token hasn't really been found, so recurse to find it.
 100         return (!token || *token) ? token : gettok(start, delims);
 101 }
 102
 103 /**
 104  * Creates a new tokens array with the default initial size.
 105  *
 106  * @returns The new tokens array structure.
 107  */
 108 static RPNTokens *newTokens()
 109 {
 110         RPNTokens *tokens = new(RPNTokens);
 111
 112         if(!tokens)
 113                 RPN_error("could not allocate memory for tokens");
 114
 115         tokens->alloc_size = RPN_TOKENS_ALLOC_SIZE;
 116         tokens->tokens = RPN_malloc(tokens->alloc_size * sizeof(char**));
 117
 118         if(!tokens->tokens)
 119                 RPN_error("could not allocate memory for tokens");
 120
 121         tokens->size = 0;
 122         tokens->pos = 0;
 123
 124         return tokens;
 125 }
 126
 127 /**
 128  * Adds a token to a tokens array structure. Automatically resizes the array if
 129  * needed.
 130  *
 131  * @param tokens The array to which to add the token.
 132  * @param token The token to add.
 133  */
 134 static void addToken(RPNTokens *tokens, char *token)
 135 {
 136         if(!tokens)
 137                 RPN_error("attempted to add token to a NULL token array.");
 138         if(!token)
 139                 RPN_error("attempted to add a NULL token to token array.");
 140
 141         // Check the tokens array for resizing.
 142         if(tokens->size >= tokens->alloc_size)
 143         {
 144                 RPN_dprintf("tokens->size: %u", tokens->size);
 145                 RPN_dprintf("tokens->alloc_size: %u", tokens->alloc_size);
 146                 RPN_dprintf("tokens->tokens: %p", tokens->tokens);
 147                 RPN_dprintf("token: \"%s\" (%u)", token, strlen(token));
 148
 149                 tokens->alloc_size += RPN_TOKENS_ALLOC_SIZE;
 150                 tokens->tokens = realloc(tokens->tokens,
 151                                          tokens->alloc_size * sizeof(char**));
 152                 if(!tokens->tokens)
 153                         RPN_error("could not resize tokens");
 154         }
 155
 156         // store token in token structure
 157         tokens->tokens[tokens->size++] = token;
 158 }
 159
 160 /**
 161  * Splits a string into tokens using whitespace as the delimeter.
 162  *
 163  * @param str The string to split.
 164  * @return A RPNTokens structure with the tokens.
 165  */
 166 RPNTokens *RPN_splitString(char *str)
 167 {
 168         char *start = str, *tok;
 169         RPNTokens *tokens;
 170
 171         if(!str)
 172                 RPN_error("tried to split a null string");
 173
 174         tokens = newTokens();
 175
 176         while((tok = gettok(&start, " \t\n")))
 177                 addToken(tokens, tok);
 178
 179         // don't try to resize the tokens to null.
 180         if(tokens->size)
 181                 tokens->tokens = realloc(tokens->tokens, tokens->size * sizeof(char**));
 182         if(!tokens->tokens)
 183                 RPN_error("could not resize tokens");
 184
 185         return tokens;
 186 }
 187
 188 /**
 189  * Frees tokens.
 190  *
 191  * @param tokens The tokens to free.
 192  */
 193 void RPN_freeTokens(RPNTokens *tokens)
 194 {
 195         if(!tokens || !tokens->tokens)
 196                 RPN_error("tried to free a null tokens structure");
 197
 198         RPN_free(tokens->tokens);
 199         RPN_free(tokens);
 200 }