src/scratch.c

   1 /*
   2  * Copyright (C) 2013 Intel Corporation.
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  17  *
  18  * Authors:
  19  *   José Bollo <jose.bollo@open.eurogiciel.org>
  20  *   Stéphane Desneux <stephane.desneux@open.eurogiciel.org>
  21  *   Jean-Benoit Martin <jean-benoit.martin@open.eurogiciel.org>
  22  *
  23  */
  24 #define _GNU_SOURCE
  25
  26 #ifdef HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include <stdlib.h>
  31 #include <memory.h>
  32
  33 #ifndef INITIAL_SCRATCH_CAPACITY
  34 #define INITIAL_SCRATCH_CAPACITY  240
  35 #endif
  36
  37 #if INITIAL_SCRATCH_CAPACITY <= 0
  38 #error "bad value for INITIAL_SCRATCH_CAPACITY"
  39 #endif
  40
  41 #define INSTANCIATE 1
  42 #if INSTANCIATE
  43 #define SET_CAPACITY            97
  44 #define HASHCODE_INIT       5381
  45 #define HASHCODE_NEXT(H,C)  (((H) << 5) + (H) + (C))
  46 #ifndef NOT_MULTI_THREAD_SAFE
  47 #define NOT_MULTI_THREAD_SAFE
  48 #endif
  49 #endif
  50
  51 #ifndef NOT_MULTI_THREAD_SAFE
  52 #include <pthread.h>
  53 static pthread_key_t tlskey;
  54 static int key_initialized = 0;
  55 #else
  56 static void *global_scratch = NULL;
  57 #endif
  58
  59 #if INSTANCIATE
  60 /* structure for recording items in the hash map */
  61 struct set_item {
  62         struct set_item *next;  /* chain to next item */
  63         size_t hashcode;                /* hash of the string */
  64         size_t length;                  /* length of the string including null */
  65 };
  66
  67 /* the array of recorded strings */
  68 static struct set_item *global_path_set[SET_CAPACITY]; /* initialized to  zeros */
  69
  70 /* instanciate (or retrieve an instance) of the 'string' that
  71 is granted to have the 'length' including terminating null and a
  72 hash code 'hashcode' */
  73 static const char *instantiate(const char *string, size_t length, size_t hashcode)
  74 {
  75         struct set_item **pp, *item;
  76         char *result;
  77
  78         /* get first item in the table */
  79         pp = &global_path_set[hashcode % SET_CAPACITY];
  80         result = 0;
  81         do {
  82                 /* inspect the item */
  83                 item = *pp;
  84                 if (!item) {
  85                         /* no item: create it */
  86                         item = malloc(length + sizeof * item);
  87                         if (!item)
  88                                 return NULL;
  89                         /* init it */
  90                         item->next = 0;
  91                         item->hashcode = hashcode;
  92                         item->length = length;
  93                         result = (char *)(item + 1);
  94                         memcpy(result, string, length);
  95                         /* record it */
  96                         *pp = item;
  97                 } else if (item->hashcode == hashcode
  98                         && item->length == length
  99                         && 0 == strcmp(string, (const char *)(item + 1))) {
 100                         /* item found */
 101                         result = (char *)(item + 1);
 102                 } else {
 103                         /* try the next */
 104                         pp = &item->next;
 105                 }
 106         } while (!result);
 107
 108         return result;
 109 }
 110 #endif
 111
 112 /* CAUTION: in a multitheaded context, it is expected that
 113 =========== the function scratchcat is call under a mutex.
 114 If it is not the case please check for initializing 'tlskey'
 115 only one time before use of it. */
 116
 117 const char *scratchcat( int ispath, const char **strings)
 118 {
 119     void *scratch, *p;
 120     char *result;
 121     size_t length, capacity;
 122     const char *instr;
 123     char c, pc;
 124 #if INSTANCIATE
 125         size_t hashcode = HASHCODE_INIT;
 126 #endif
 127
 128     /* get the recorded pointer on scrtch area */
 129 #ifndef NOT_MULTI_THREAD_SAFE
 130     if (!key_initialized) {
 131         key_initialized = 1;
 132         pthread_key_create( &tlskey, (void(*)(void*))free);
 133     }
 134     scratch = pthread_getspecific( tlskey);
 135 #else
 136     scratch = global_scratch;
 137 #endif
 138
 139     /* create the scratch area if needed */
 140     if (scratch == NULL) {
 141         capacity = INITIAL_SCRATCH_CAPACITY;
 142         p = malloc( capacity + sizeof(size_t));
 143         if (p == NULL)
 144             return NULL;
 145         *((size_t*)p) = capacity;
 146         scratch = p;
 147 #ifndef NOT_MULTI_THREAD_SAFE
 148         pthread_setspecific( tlskey, p);
 149 #else
 150         global_scratch = p;
 151 #endif
 152     }
 153
 154     /* set local data for scratch area */
 155     capacity = *((size_t*)scratch);
 156     result = (char*)(1+((size_t*)scratch));
 157     length = 0;
 158
 159     /* copy the strings */
 160     c = 0;
 161     pc = 1;
 162     while(pc) {
 163
 164         if (c == 0) {
 165             instr = *strings++;
 166             if (instr != NULL) {
 167                 c = *instr;
 168                 if (c == 0)
 169                     continue;
 170                 if (!ispath)
 171                     instr++;
 172                 else if(c != '/' && pc != '/')
 173                     c = '/';
 174                 else if(c == '/' && pc == '/') {
 175                     instr++;
 176                     continue;
 177                 }
 178                 else
 179                     instr++;
 180             }
 181         }
 182         else {
 183             c = *instr;
 184             if (c == 0)
 185                 continue;
 186             instr++;
 187         }
 188
 189         /* extend the scratch area if needed */
 190         if (length == capacity) {
 191             capacity = 2 * capacity;
 192             p = realloc( scratch, capacity + sizeof(size_t));
 193             if (p == NULL)
 194                 return NULL;
 195             *((size_t*)p) = capacity;
 196             if (p != scratch) {
 197                 scratch = p;
 198 #ifndef NOT_MULTI_THREAD_SAFE
 199                 pthread_setspecific( tlskey, p);
 200 #else
 201                 global_scratch = p;
 202 #endif
 203                 result = (char*)(1+((size_t*)p));
 204             }
 205         }
 206
 207         /* append the char */
 208         pc = result[length++] = c;
 209 #if INSTANCIATE
 210                 hashcode = HASHCODE_NEXT(hashcode, (size_t)c);
 211 #endif
 212     }
 213
 214 #if INSTANCIATE
 215         return instantiate(result, length, hashcode);
 216 #else
 217     return result;
 218 #endif
 219 }
 220
 221
 222 #ifdef TEST_SCRATCH
 223 #include <stdio.h>
 224 int main(int argc, const char**argv) {
 225     int ispath, iter, i;
 226     argv++;
 227     ispath = argv[0] && argv[0][0] == '-' && argv[0][1] == 'p';
 228         for (i = 0 ; i < 2 ; i++) {
 229                 iter = ispath;
 230                 while (iter < argc) {
 231                 const char *p = scratchcat(ispath,argv+iter++);
 232                 printf("%p: %s\n",p,p);
 233                 }
 234         }
 235     return 0;
 236 }
 237 #endif