ArchWizard

DGD/

source navigation ]
diff markup ]
identifier search ]
file search ]
Version: [ 1.0.a0 ] [ 1.1 ] [ 1.2 ] [ 1.2p1 ] [ 1.2p2 ] [ 1.2p3 ] [ 1.2p4 ] [ 1.2.151 ]

  1 # include "dgd.h"
  2 # include "hash.h"
  3 # include "str.h"
  4 # include "array.h"
  5 # include "object.h"
  6 # include "data.h"
  7 
  8 # define STR_CHUNK      128
  9 
 10 typedef struct _strh_ {
 11     hte chain;                  /* hash table chain */
 12     string *str;                /* string entry */
 13     Uint index;                 /* building index */
 14     struct _strh_ **link;       /* next in list */
 15 } strh;
 16 
 17 typedef struct _strhchunk_ {
 18     struct _strhchunk_ *next;   /* next in list */
 19     strh sh[STR_CHUNK];         /* chunk of strh entries */
 20 } strhchunk;
 21 
 22 static hashtab *ht;             /* string merge table */
 23 static strh **slink;            /* linked list of merged strings */
 24 static strhchunk *shlist;       /* list of all strh chunks */
 25 static int strhchunksz;         /* size of current strh chunk */
 26 
 27 /*
 28  * NAME:        string->init()
 29  * DESCRIPTION: initialize string handling
 30  */
 31 void str_init()
 32 {
 33     ht = ht_new(STRMERGETABSZ, STRMERGEHASHSZ);
 34     strhchunksz = STR_CHUNK;
 35 }
 36 
 37 /*
 38  * NAME:        string->alloc()
 39  * DESCRIPTION: Create a new string. The text can be a NULL pointer, in which
 40  *              case it must be filled in later.
 41  */
 42 string *str_alloc(text, len)
 43 char *text;
 44 register long len;
 45 {
 46     register string *s;
 47     string dummy;
 48 
 49     /* allocate string struct & text in one block */
 50     s = (string *) ALLOC(char, dummy.text - (char *) &dummy + 1 + len);
 51     if (text != (char *) NULL && len > 0) {
 52         memcpy(s->text, text, (unsigned int) len);
 53     }
 54     s->text[s->len = len] = '\0';
 55     s->ref = 0;
 56     s->primary = (strref *) NULL;
 57 
 58     return s;
 59 }
 60 
 61 /*
 62  * NAME:        string->new()
 63  * DESCRIPTION: create a new string with size check
 64  */
 65 string *str_new(text, len)
 66 char *text;
 67 long len;
 68 {
 69     if (len > (unsigned long) MAX_STRLEN) {
 70         error("String too long");
 71     }
 72     return str_alloc(text, len);
 73 }
 74 
 75 /*
 76  * NAME:        string->del()
 77  * DESCRIPTION: remove a reference from a string. If there are none left, the
 78  *              string is removed.
 79  */
 80 void str_del(s)
 81 register string *s;
 82 {
 83     if (--(s->ref) == 0) {
 84         FREE(s);
 85     }
 86 }
 87 
 88 /*
 89  * NAME:        string->put()
 90  * DESCRIPTION: put a string in the string merge table
 91  */
 92 Uint str_put(str, n)
 93 register string *str;
 94 register Uint n;
 95 {
 96     register strh **h;
 97 
 98     h = (strh **) ht_lookup(ht, str->text, FALSE);
 99     for (;;) {
100         /*
101          * The hasher doesn't handle \0 in strings, and so may not have
102          * found the proper string. Follow the hash table chain until
103          * the end is reached, or until a match is found using str_cmp().
104          */
105         if (*h == (strh *) NULL) {
106             register strh *s;
107 
108             /*
109              * Not in the hash table. Make a new entry.
110              */
111             if (strhchunksz == STR_CHUNK) {
112                 register strhchunk *l;
113 
114                 l = ALLOC(strhchunk, 1);
115                 l->next = shlist;
116                 shlist = l;
117                 strhchunksz = 0;
118             }
119             s = *h = &shlist->sh[strhchunksz++];
120             s->chain.next = (hte *) NULL;
121             s->chain.name = str->text;
122             s->str = str;
123             s->index = n;
124             s->link = slink;
125             slink = h;
126 
127             return n;
128         } else if (str_cmp(str, (*h)->str) == 0) {
129             /* already in the hash table */
130             return (*h)->index;
131         }
132         h = (strh **) &(*h)->chain.next;
133     }
134 }
135 
136 /*
137  * NAME:        string->clear()
138  * DESCRIPTION: clear the string merge table. All entries are in a separate
139  *              linked list so this is simple. Note that this routine makes
140  *              assumptions about how the hash table is constructed.
141  */
142 void str_clear()
143 {
144     register strh **h;
145     register strhchunk *l;
146 
147     for (h = slink; h != (strh **) NULL; ) {
148         register strh *f;
149 
150         f = *h;
151         *h = (strh *) NULL;
152         h = f->link;
153     }
154     slink = (strh **) NULL;
155 
156     for (l = shlist; l != (strhchunk *) NULL; ) {
157         register strhchunk *f;
158 
159         f = l;
160         l = l->next;
161         FREE(f);
162     }
163     shlist = (strhchunk *) NULL;
164     strhchunksz = STR_CHUNK;
165 }
166 
167 
168 /*
169  * NAME:        string->cmp()
170  * DESCRIPTION: compare two strings
171  */
172 int str_cmp(s1, s2)
173 string *s1, *s2;
174 {
175     if (s1 == s2) {
176         return 0;
177     } else {
178         register ssizet len;
179         register char *p, *q;
180         long cmplen;
181         int cmp;
182 
183         cmplen = (long) s1->len - s2->len;
184         if (cmplen > 0) {
185             /* s1 longer */
186             cmplen = 1;
187             len = s2->len;
188         } else {
189             /* s2 longer or equally long */
190             if (cmplen < 0) {
191                 cmplen = -1;
192             }
193             len = s1->len;
194         }
195         for (p = s1->text, q = s2->text; len > 0 && *p == *q; p++, q++, --len) ;
196         cmp = UCHAR(*p) - UCHAR(*q);
197         return (cmp != 0) ? cmp : cmplen;
198     }
199 }
200 
201 /*
202  * NAME:        string->add()
203  * DESCRIPTION: add two strings
204  */
205 string *str_add(s1, s2)
206 register string *s1, *s2;
207 {
208     register string *s;
209 
210     s = str_new((char *) NULL, (long) s1->len + s2->len);
211     memcpy(s->text, s1->text, s1->len);
212     memcpy(s->text + s1->len, s2->text, s2->len);
213 
214     return s;
215 }
216 
217 /*
218  * NAME:        string->index()
219  * DESCRIPTION: index a string
220  */
221 ssizet str_index(s, l)
222 string *s;
223 register long l;
224 {
225     if (l < 0 || l >= (long) s->len) {
226         error("String index out of range");
227     }
228 
229     return l;
230 }
231 
232 /*
233  * NAME:        string->ckrange()
234  * DESCRIPTION: check a string subrange
235  */
236 void str_ckrange(s, l1, l2)
237 string *s;
238 register long l1, l2;
239 {
240     if (l1 < 0 || l1 > l2 + 1 || l2 >= (long) s->len) {
241         error("Invalid string range");
242     }
243 }
244 
245 /*
246  * NAME:        string->range()
247  * DESCRIPTION: return a subrange of a string
248  */
249 string *str_range(s, l1, l2)
250 register string *s;
251 register long l1, l2;
252 {
253     if (l1 < 0 || l1 > l2 + 1 || l2 >= (long) s->len) {
254         error("Invalid string range");
255     }
256 
257     return str_new(s->text + l1, l2 - l1 + 1);
258 }
259 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.