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 #endif
  47
  48 #ifndef NOT_MULTI_THREAD_SAFE
  49 #include <pthread.h>
  50 #endif
  51
  52 #if !(defined(NOT_MULTI_THREAD_SAFE) || INSTANCIATE)
  53 static __thread void *global_scratch = NULL;
  54 #else
  55 static void *global_scratch = NULL;
  56 #endif
  57 #if INSTANCIATE && !defined(NOT_MULTI_THREAD_SAFE)
  58 static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
  59 #endif
  60
  61 #if INSTANCIATE
  62 /* structure for recording items in the hash map */
  63 struct set_item {
  64     struct set_item *next;        /* chain to next item */
  65     size_t hashcode;                /* hash of the string */
  66     size_t length;                /* length of the string including null */
  67 };
  68
  69 /* the array of recorded strings */
  70 static struct set_item *global_path_set[SET_CAPACITY]; /* initialized to  zeros */
  71
  72 /* instanciate (or retrieve an instance) of the 'string' that
  73 is granted to have the 'length' including terminating null and a
  74 hash code 'hashcode' */
  75 static const char *instantiate(const char *string, size_t length, size_t hashcode)
  76 {
  77     struct set_item **pp, *item;
  78     char *result;
  79
  80     /* get first item in the table */
  81     pp = &global_path_set[hashcode % SET_CAPACITY];
  82     result = 0;
  83     do {
  84         /* inspect the item */
  85         item = *pp;
  86         if (!item) {
  87             /* no item: create it */
  88             item = malloc(length + sizeof * item);
  89             if (!item)
  90                 return NULL;
  91             /* init it */
  92             item->next = 0;
  93             item->hashcode = hashcode;
  94             item->length = length;
  95             result = (char *)(item + 1);
  96             memcpy(result, string, length);
  97             /* record it */
  98             *pp = item;
  99         } else if (item->hashcode == hashcode
 100                 && item->length == length
 101                 && 0 == strcmp(string, (const char *)(item + 1))) {
 102             /* item found */
 103             result = (char *)(item + 1);
 104         } else {
 105             /* try the next */
 106             pp = &item->next;
 107         }
 108     } while (!result);
 109
 110     return result;
 111 }
 112 #endif
 113
 114 /* CAUTION: in a multitheaded context, it is expected that
 115 =========== the function scratchcat is call under a mutex.
 116 If it is not the case please check for initializing 'tlskey'
 117 only one time before use of it. */
 118
 119 #if INSTANCIATE && !defined(NOT_MULTI_THREAD_SAFE)
 120 static const char *_scratchcat( int ispath, const char **strings);
 121
 122 const char *scratchcat( int ispath, const char **strings)
 123 {
 124     const char *result;
 125     pthread_mutex_lock(&mutex);
 126     result = _scratchcat( ispath, strings);
 127     pthread_mutex_unlock(&mutex);
 128     return result;
 129 }
 130
 131 static const char *_scratchcat( int ispath, const char **strings)
 132 #else
 133 const char *scratchcat( int ispath, const char **strings)
 134 #endif
 135 {
 136     void *scratch, *p;
 137     char *result;
 138     size_t length, capacity;
 139     const char *instr;
 140     char c, pc;
 141 #if INSTANCIATE
 142     size_t hashcode = HASHCODE_INIT;
 143 #endif
 144
 145     /* get the recorded pointer on scrtch area */
 146     scratch = global_scratch;
 147
 148     /* create the scratch area if needed */
 149     if (scratch == NULL) {
 150         capacity = INITIAL_SCRATCH_CAPACITY;
 151         p = malloc( capacity + sizeof(size_t));
 152         if (p == NULL)
 153             return NULL;
 154         *((size_t*)p) = capacity;
 155         scratch = p;
 156         global_scratch = p;
 157     }
 158
 159     /* set local data for scratch area */
 160     capacity = *((size_t*)scratch);
 161     result = (char*)(1+((size_t*)scratch));
 162     length = 0;
 163
 164     /* copy the strings */
 165     c = 0;
 166     pc = 1;
 167     while(pc) {
 168
 169         if (c == 0) {
 170             instr = *strings++;
 171             if (instr != NULL) {
 172                 c = *instr;
 173                 if (c == 0)
 174                     continue;
 175                 if (!ispath)
 176                     instr++;
 177                 else if(c != '/' && pc != '/')
 178                     c = '/';
 179                 else if(c == '/' && pc == '/') {
 180                     instr++;
 181                     continue;
 182                 }
 183                 else
 184                     instr++;
 185             }
 186         }
 187         else {
 188             c = *instr;
 189             if (c == 0)
 190                 continue;
 191             instr++;
 192         }
 193
 194         /* extend the scratch area if needed */
 195         if (length == capacity) {
 196             capacity = 2 * capacity;
 197             p = realloc( scratch, capacity + sizeof(size_t));
 198             if (p == NULL)
 199                 return NULL;
 200             *((size_t*)p) = capacity;
 201             if (p != scratch) {
 202                 scratch = p;
 203                 global_scratch = p;
 204                 result = (char*)(1+((size_t*)p));
 205             }
 206         }
 207
 208         /* append the char */
 209         pc = result[length++] = c;
 210 #if INSTANCIATE
 211         hashcode = HASHCODE_NEXT(hashcode, (size_t)c);
 212 #endif
 213     }
 214
 215 #if INSTANCIATE
 216     return instantiate(result, length, hashcode);
 217 #else
 218     return result;
 219 #endif
 220 }
 221
 222
 223 #ifdef TEST_SCRATCH
 224 #include <stdio.h>
 225 int main(int argc, const char**argv) {
 226     int ispath, iter, i;
 227     argv++;
 228     ispath = argv[0] && argv[0][0] == '-' && argv[0][1] == 'p';
 229     for (i = 0 ; i < 2 ; i++) {
 230         iter = ispath;
 231         while (iter < argc) {
 232             const char *p = scratchcat(ispath,argv+iter++);
 233             printf("%p: %s\n",p,p);
 234         }
 235     }
 236     return 0;
 237 }
 238 #endif