"Fossies" - the Fresh Open Source Software Archive

Member "mlr-5.6.2/c/parsing/lemon_string.c" (25 Aug 2019, 3642 Bytes) of package /linux/misc/mlr-5.6.2.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "lemon_string.c" see the Fossies "Dox" file reference documentation.

    1 #include <stdio.h>
    2 #include <stdlib.h>
    3 #include <string.h>
    4 #include "lemon_memory.h"
    5 #include "lemon_string.h"
    6 
    7 int strhash(char *x) {
    8     unsigned h = 0;
    9     while (*x) h = h*13 + *(x++);
   10     return (int)h;
   11 }
   12 
   13 // ================================================================
   14 /* There is one instance of the following structure for each
   15 ** associative array of type "x1".
   16 */
   17 struct s_x1 {
   18     int size;               /* The number of available slots. Must be a power of 2, >= 1. */
   19     int count;              /* Number of currently slots filled */
   20     struct s_x1node *tbl;  /* The data stored here */
   21     struct s_x1node **ht;  /* Hash table for lookups */
   22 };
   23 
   24 /* There is one instance of this structure for every data element
   25 ** in an associative array of type "x1".
   26 */
   27 typedef struct s_x1node {
   28     char *data;                  /* The data */
   29     struct s_x1node *next;   /* Next entry with the same hash */
   30     struct s_x1node **from;  /* Previous link */
   31 } x1node;
   32 
   33 /* There is only one instance of the array, which is the following */
   34 static struct s_x1 *x1a;
   35 
   36 // ================================================================
   37 /* Works like strdup, sort of.  Save a string in malloced memory, but
   38 ** keep strings in a table so that the same string is not in more
   39 ** than one place.
   40 */
   41 char *Strsafe(char *y) {
   42     char *z;
   43 
   44     z = Strsafe_find(y);
   45     if (z==0 && (z=malloc (strlen(y)+1) )!=0) {
   46         strcpy(z,y);
   47         Strsafe_insert(z);
   48     }
   49     MemoryCheck(z);
   50     return z;
   51 }
   52 
   53 /* Allocate a new associative array */
   54 void Strsafe_init(){
   55     if (x1a)  return;
   56     x1a = (struct s_x1*)malloc (sizeof(struct s_x1)) ;
   57     if (x1a) {
   58         x1a->size = 1024;
   59         x1a->count = 0;
   60         x1a->tbl = (x1node*)malloc (
   61             (sizeof(x1node) + sizeof(x1node*))*1024) ;
   62         if (x1a->tbl==0) {
   63             free(x1a);
   64             x1a = 0;
   65         } else {
   66             int i;
   67             x1a->ht = (x1node**)&(x1a->tbl[1024]);
   68             for(i=0; i<1024; i++) x1a->ht[i] = 0;
   69         }
   70     }
   71 }
   72 
   73 /* Insert a new record into the array.  Return TRUE if successful.
   74 ** Prior data with the same key is NOT overwritten */
   75 int Strsafe_insert(char *data)
   76 {
   77     x1node *np;
   78     int h;
   79     int ph;
   80 
   81     if (x1a==0)  return 0;
   82     ph = strhash(data);
   83     h = ph & (x1a->size-1);
   84     np = x1a->ht[h];
   85     while (np) {
   86         if (strcmp(np->data,data)==0) {
   87             /* An existing entry with the same key is found. */
   88             /* Fail because overwrite is not allows. */
   89             return 0;
   90         }
   91         np = np->next;
   92     }
   93     if (x1a->count>=x1a->size) {
   94         /* Need to make the hash table bigger */
   95         int i,size;
   96         struct s_x1 array;
   97         array.size = size = x1a->size*2;
   98         array.count = x1a->count;
   99         array.tbl = (x1node*)malloc(
  100             (sizeof(x1node) + sizeof(x1node*))*size) ;
  101         if (array.tbl==0)  return 0;  /* Fail due to malloc failure */
  102         array.ht = (x1node**)&(array.tbl[size]);
  103         for(i=0; i<size; i++) array.ht[i] = 0;
  104         for(i=0; i<x1a->count; i++){
  105             x1node *oldnp, *newnp;
  106             oldnp = &(x1a->tbl[i]);
  107             h = strhash(oldnp->data) & (size-1);
  108             newnp = &(array.tbl[i]);
  109             if (array.ht[h])  array.ht[h]->from = &(newnp->next);
  110             newnp->next = array.ht[h];
  111             newnp->data = oldnp->data;
  112             newnp->from = &(array.ht[h]);
  113             array.ht[h] = newnp;
  114         }
  115         free(x1a->tbl);
  116         *x1a = array;
  117     }
  118     /* Insert the new data */
  119     h = ph & (x1a->size-1);
  120     np = &(x1a->tbl[x1a->count++]);
  121     np->data = data;
  122     if (x1a->ht[h])  x1a->ht[h]->from = &(np->next);
  123     np->next = x1a->ht[h];
  124     x1a->ht[h] = np;
  125     np->from = &(x1a->ht[h]);
  126     return 1;
  127 }
  128 
  129 /* Return a pointer to data assigned to the given key.  Return NULL
  130 ** if no such key. */
  131 char *Strsafe_find(char *key)
  132 {
  133     int h;
  134     x1node *np;
  135 
  136     if (x1a==0)  return 0;
  137     h = strhash(key) & (x1a->size-1);
  138     np = x1a->ht[h];
  139     while (np) {
  140         if (strcmp(np->data,key)==0)  break;
  141         np = np->next;
  142     }
  143     return np ? np->data : 0;
  144 }