2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
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)
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
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
23 /* $XConsortium: strtab.c /main/4 1996/05/09 04:23:54 drk $ */
25 routines to implement a string -> unique ptr table & access functions
26 suitable for use with shared memory
33 #include <sys/types.h>
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 */
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 */
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 */
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 */
66 #define NOT_AN_INDEX ((unsigned short) 0xffff)
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 *);
76 returns offset in string table where string is found,
77 else -1 if string is not found.
80 const char * _DtShmBosonToString(DtShmStrtab strtab, int boson)
82 const char * s = (const char *) strtab + ((strtab_t *) strtab)->st_stroffset;
87 DtShmBoson _DtShmStringToBoson(DtShmStrtab strtab, const char * string)
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);
99 s = (unsigned const char *) string;
104 i = j % ((strtab_t *) strtab)->st_count;
107 check bucket first pointer....
110 if((i=(ptr+i)->first) == NOT_AN_INDEX)
114 loop through other buckets on hash table, looking for
115 our string. Note that we reused s.
118 s = (unsigned const char *) strtab + ((strtab_t *) strtab)->st_stroffset;
120 while(strcmp( (char *) (s + ptr[i].key), string))
121 if((i= ptr[i].next) == NOT_AN_INDEX)
130 _DtShmProtoInitStrtab(int sizeguess)
132 strlist_t * ptr = (strlist_t *) malloc(sizeof(*ptr));
136 if(!(ptr->sl_hash = _DtUtilMakeHash(sizeguess))) {
141 if(!(ptr->sl_bosons = _DtUtilMakeIHash(sizeguess))) {
142 (void)_DtUtilDestroyHash(ptr->sl_hash, NULL, NULL);
147 ptr->sl_charcount = 1;
148 return((DtShmProtoStrtab) ptr);
152 _DtShmProtoDestroyStrtab(DtShmProtoStrtab strlist)
154 strlist_t * ptr = (strlist_t *) strlist;
156 _DtUtilDestroyHash(ptr->sl_hash, NULL, NULL);
157 _DtUtilDestroyHash(ptr->sl_bosons, (des_func)free, NULL);
163 _DtShmProtoAddStrtab(DtShmProtoStrtab strlist, const char * string, int * isnew)
165 strlist_t * ptr = (strlist_t *) strlist;
167 int * bucket = (int *) _DtUtilGetHash(ptr->sl_hash, (const unsigned char *)string);
171 if(*bucket == NULL) /* new */ {
172 unsigned char ** sptr;
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;
185 return((DtShmBoson)ret);
189 _DtShmProtoLookUpStrtab (DtShmProtoStrtab prototab, DtShmBoson boson)
191 strlist_t * ptr = (strlist_t *) prototab;
192 unsigned char ** sptr;
194 sptr = (unsigned char **) _DtUtilFindHash(ptr->sl_bosons, (const unsigned char *) boson);
196 return(sptr?((const char *)*sptr):NULL);
201 _DtShmProtoSizeStrtab(DtShmProtoStrtab strlist)
205 strlist_t * ptr = (strlist_t * ) strlist;
209 _DtUtilOperateHash(ptr->sl_hash, inc_it, &foo);
211 size = sizeof(strtab_t) + (foo[0]) * sizeof(strtab_entry_t) + foo[0] + foo[1] + 3 ;
212 /* header */ /* table */ /* for string + terminator */ /* padding */
215 fix size so that it is always a multiple of 4 for ease of programming
217 size = (~3) & (size+3);
224 _DtShmProtoCopyStrtab(DtShmProtoStrtab in, void * destination)
226 strlist_t * strlist = (strlist_t *) in;
227 strtab_t * ptr = (strtab_t *) destination;
231 struct strtab_build building;
236 _DtUtilOperateHash(strlist->sl_hash, inc_it, &foo);
238 size = sizeof(strtab_t) + (foo[0]) * sizeof(strtab_entry_t) + (foo[0] + foo[1] + 3) & ~3 ;
239 /* header */ /* table */ /* for string + terminator */
241 memset((char *) ptr, 255, 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 */
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;
254 _DtUtilOperateHash(strlist->sl_hash, build_it, & building);
255 return((DtShmStrtab) destination);
258 static void build_it(int a, struct strtab_build * ptr, unsigned char * key)
260 register unsigned int i,j;
261 register unsigned char * s;
262 register strtab_entry_t * e;
263 register unsigned short * add_ptr;
265 strcpy((char *) ptr->strstart + a, (const char *)key);
274 i = j % ((strtab_t *) ptr->strtab)->st_count;
276 e = ptr->tabstart + ptr->index;
278 e -> key = a; /* save key value in our block */
279 e -> next = NOT_AN_INDEX;
281 e = ptr->tabstart + i;
283 if(e->first == NOT_AN_INDEX)
284 add_ptr = & e->first;
286 e = ptr->tabstart + e->first;
287 while( e->next != NOT_AN_INDEX)
288 e = ptr->tabstart + e->next;
292 *add_ptr = ptr->index++;
297 static void inc_it(int * a, int * b, unsigned char * key)
300 b[1] += strlen((const char *)key) + 1;