cde/lib/DtSvc/DtUtil1/strtab.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: strtab.c /main/4 1996/05/09 04:23:54 drk $ */
  24 /*
  25   routines to implement a string -> unique ptr table & access functions
  26   suitable for use with shared memory
  27   */
  28
  29 #include <stdio.h>
  30 #include <string.h>
  31 #include <unistd.h>
  32 #include <stdlib.h>
  33 #include <sys/types.h>
  34 #include <sys/stat.h>
  35 #include <sys/mman.h>
  36
  37 #include "DtHash.h"
  38 #include "DtShmDb.h"
  39
  40 typedef struct strtab {
  41   unsigned int st_size;         /* size in bytes                                                */
  42   unsigned int st_stroffset;    /* offset (bytes) from this structure to contained strings      */
  43   unsigned int st_taboffset;    /* offset (bytes) from this structure to table offset           */
  44   unsigned int st_count;        /* number of elements in this string table                      */
  45 } strtab_t;
  46
  47 typedef struct strtab_entry {
  48   unsigned int key;             /* offset into contained strings                                */
  49   unsigned short first;         /* offset in table to first string to hash to this spot         */
  50   unsigned short next;          /* offset in table to next item to hash to this spot            */
  51 } strtab_entry_t;
  52
  53 typedef struct strlist {
  54   DtHashTbl             sl_hash;        /* hash table to hold strings during definition         */
  55   DtHashTbl             sl_bosons;      /* reverse hash table for Nolan's lookup function       */
  56   unsigned int          sl_charcount;   /* count of current bytes of strings                    */
  57 } strlist_t;
  58
  59 struct strtab_build {
  60   unsigned int          index;                  /* iteration                    */
  61   unsigned char *       strstart;               /* start of strings             */
  62   strtab_entry_t *      tabstart;               /* start of table               */
  63   strtab_t *            strtab;                 /* pointer to head              */
  64 };
  65
  66 #define NOT_AN_INDEX ((unsigned short) 0xffff)
  67
  68 static void inc_it  (int * a, int * b, unsigned char * key);
  69 static void build_it(int a, struct strtab_build * ptr, unsigned char * key);
  70 extern char * strdup(const char *);
  71 typedef int (*des_func)(void *);
  72
  73 /*
  74   client routine
  75
  76   returns offset in string table where string is found,
  77   else -1 if string is not found.
  78   */
  79
  80 const char *    _DtShmBosonToString(DtShmStrtab strtab, int boson)
  81 {
  82   const char * s = (const char *) strtab + ((strtab_t *) strtab)->st_stroffset;
  83   return(s+boson);
  84 }
  85
  86
  87 DtShmBoson _DtShmStringToBoson(DtShmStrtab strtab, const char * string)
  88 {
  89   register unsigned int i,j;
  90   register unsigned const char * s;
  91   register strtab_entry_t * ptr = (strtab_entry_t *) ((unsigned char *) strtab  +
  92                                                       ((strtab_t *) strtab) -> st_taboffset);
  93
  94   /*
  95     hash the input string
  96     */
  97   i = 1;
  98   j = 0;
  99   s = (unsigned const char *) string;
 100
 101   while(*s!=0)
 102     j += (*s++ << i++);
 103
 104   i = j % ((strtab_t *) strtab)->st_count;
 105
 106   /*
 107     check bucket first pointer....
 108     */
 109
 110   if((i=(ptr+i)->first) == NOT_AN_INDEX)
 111     return(-1);
 112
 113   /*
 114     loop through other buckets on hash table, looking for
 115     our string.  Note that we reused s.
 116     */
 117
 118   s = (unsigned const char *) strtab + ((strtab_t *) strtab)->st_stroffset;
 119
 120   while(strcmp( (char *) (s +  ptr[i].key), string))
 121     if((i= ptr[i].next) == NOT_AN_INDEX)
 122       return(-1);
 123
 124   return(ptr[i].key);
 125 }
 126
 127
 128
 129 DtShmProtoStrtab
 130 _DtShmProtoInitStrtab(int sizeguess)
 131 {
 132   strlist_t * ptr = (strlist_t *) malloc(sizeof(*ptr));
 133   if(!ptr)
 134     return(NULL);
 135
 136   if(!(ptr->sl_hash =  _DtUtilMakeHash(sizeguess))) {
 137     free(ptr);
 138     return(NULL);
 139   }
 140
 141   if(!(ptr->sl_bosons =  _DtUtilMakeIHash(sizeguess))) {
 142     (void)_DtUtilDestroyHash(ptr->sl_hash, NULL, NULL);
 143     free(ptr);
 144     return(NULL);
 145   }
 146
 147   ptr->sl_charcount = 1;
 148   return((DtShmProtoStrtab) ptr);
 149 }
 150
 151 int
 152 _DtShmProtoDestroyStrtab(DtShmProtoStrtab strlist)
 153 {
 154   strlist_t * ptr = (strlist_t *) strlist;
 155
 156   _DtUtilDestroyHash(ptr->sl_hash, NULL, NULL);
 157   _DtUtilDestroyHash(ptr->sl_bosons, (des_func)free, NULL);
 158   free(ptr);
 159   return(0);
 160 }
 161
 162 DtShmBoson
 163 _DtShmProtoAddStrtab(DtShmProtoStrtab strlist, const char * string, int * isnew)
 164 {
 165   strlist_t * ptr = (strlist_t *) strlist;
 166
 167   int * bucket = (int *) _DtUtilGetHash(ptr->sl_hash, (const unsigned char *)string);
 168
 169   int ret = *bucket;
 170
 171   if(*bucket == NULL) /* new */ {
 172     unsigned char ** sptr;
 173     *isnew = 1;
 174     *bucket = ret = ptr->sl_charcount;
 175     sptr = (unsigned char**)_DtUtilGetHash(ptr->sl_bosons, (const unsigned char *)ret);
 176     *sptr = (unsigned char*)strdup(string);
 177     ptr->sl_charcount += strlen(string) + 1;
 178   }
 179
 180   else {
 181     *isnew = 0;
 182   }
 183
 184
 185   return((DtShmBoson)ret);
 186 }
 187
 188 const char *
 189 _DtShmProtoLookUpStrtab (DtShmProtoStrtab prototab, DtShmBoson boson)
 190 {
 191   strlist_t * ptr = (strlist_t *) prototab;
 192   unsigned char ** sptr;
 193
 194   sptr = (unsigned char **) _DtUtilFindHash(ptr->sl_bosons, (const unsigned char *) boson);
 195
 196   return(sptr?((const char *)*sptr):NULL);
 197 }
 198
 199
 200 int
 201 _DtShmProtoSizeStrtab(DtShmProtoStrtab strlist)
 202 {
 203   int foo[2];
 204   int size;
 205   strlist_t * ptr = (strlist_t * ) strlist;
 206
 207   foo[1] = foo[0] = 0;
 208
 209   _DtUtilOperateHash(ptr->sl_hash, inc_it, &foo);
 210
 211   size = sizeof(strtab_t) + (foo[0]) * sizeof(strtab_entry_t) + foo[0] + foo[1] + 3 ;
 212          /* header */      /* table */  /* for string + terminator */        /* padding */
 213
 214   /*
 215     fix size so that it is always a multiple of 4 for ease of programming
 216     */
 217   size = (~3) & (size+3);
 218
 219   return(size);
 220
 221 }
 222
 223 DtShmStrtab
 224 _DtShmProtoCopyStrtab(DtShmProtoStrtab in, void * destination)
 225 {
 226   strlist_t *   strlist = (strlist_t *) in;
 227   strtab_t *    ptr = (strtab_t *) destination;
 228
 229   int foo[2];
 230   int size;
 231   struct strtab_build building;
 232
 233
 234   foo[0] = foo[1] = 0;
 235
 236   _DtUtilOperateHash(strlist->sl_hash, inc_it, &foo);
 237
 238   size = sizeof(strtab_t) + (foo[0]) * sizeof(strtab_entry_t) + (foo[0] + foo[1] + 3) & ~3 ;
 239          /* header */      /* table */  /* for string + terminator */
 240
 241   memset((char *) ptr, 255, size);
 242
 243
 244   ptr-> st_size= size;
 245   ptr-> st_stroffset = sizeof(*ptr);
 246   ptr-> st_taboffset = sizeof(*ptr) + (foo[0] + foo[1] + 3) & ~3;
 247   ptr-> st_count = foo[0];                      /* patch alignment */
 248
 249   building.index = 0;
 250   building.strstart = (unsigned char *) ptr  + ptr->st_stroffset;
 251   building.tabstart = (strtab_entry_t *) ((unsigned char *) ptr  + ptr->st_taboffset);
 252   building.strtab = ptr;
 253
 254   _DtUtilOperateHash(strlist->sl_hash, build_it, & building);
 255   return((DtShmStrtab) destination);
 256 }
 257
 258 static void build_it(int a, struct strtab_build * ptr, unsigned char * key)
 259 {
 260   register unsigned int i,j;
 261   register unsigned char * s;
 262   register strtab_entry_t * e;
 263   register unsigned short * add_ptr;
 264
 265   strcpy((char *) ptr->strstart + a, (const char *)key);
 266
 267   i = 1;
 268   j = 0;
 269   s = key;
 270
 271   while(*s!=0)
 272     j += (*s++ << i++);
 273
 274   i = j % ((strtab_t *) ptr->strtab)->st_count;
 275
 276   e = ptr->tabstart + ptr->index;
 277
 278   e -> key = a; /* save key value in our block */
 279   e -> next = NOT_AN_INDEX;
 280
 281   e = ptr->tabstart + i;
 282
 283   if(e->first == NOT_AN_INDEX)
 284     add_ptr = & e->first;
 285   else {
 286     e = ptr->tabstart + e->first;
 287     while( e->next != NOT_AN_INDEX)
 288       e = ptr->tabstart + e->next;
 289     add_ptr = & e->next;
 290   }
 291
 292   *add_ptr = ptr->index++;
 293
 294 }
 295
 296 /* ARGSUSED */
 297 static void inc_it(int * a, int * b, unsigned char * key)
 298 {
 299   b[0]++;
 300   b[1] += strlen((const char *)key) + 1;
 301 }
 302