src/scratch.c

   1 /*
   2  * Copyright (C) 2013-2014 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                                 } else
 183                                         instr++;
 184                         }
 185                 } else {
 186                         c = *instr;
 187                         if (c == 0)
 188                                 continue;
 189                         instr++;
 190                 }
 191
 192                 /* extend the scratch area if needed */
 193                 if (length == capacity) {
 194                         capacity = 2 * capacity;
 195                         p = realloc(scratch, capacity + sizeof(size_t));
 196                         if (p == NULL)
 197                                 return NULL;
 198                         *((size_t*)p) = capacity;
 199                         if (p != scratch) {
 200                                 scratch = p;
 201                                 global_scratch = p;
 202                                 result = (char*)(1+((size_t*)p));
 203                         }
 204                 }
 205
 206                 /* append the char */
 207                 pc = result[length++] = c;
 208 #if INSTANCIATE
 209                 hashcode = HASHCODE_NEXT(hashcode, (size_t)c);
 210 #endif
 211         }
 212
 213 #if INSTANCIATE
 214         return instantiate(result, length, hashcode);
 215 #else
 216         return result;
 217 #endif
 218 }
 219
 220
 221 #ifdef TEST_SCRATCH
 222 #include <stdio.h>
 223 int main(int argc, const char**argv)
 224 {
 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