1 /***********************************************************************
2 * *
3 * This software is part of the BSD package *
4 *Copyright (c) 1978-1996 The Regents of the University of California an*
5 * *
6 * Redistribution and use in source and binary forms, with or *
7 * without modification, are permitted provided that the following *
8 * conditions are met: *
9 * *
10 * 1. Redistributions of source code must retain the above *
11 * copyright notice, this list of conditions and the *
12 * following disclaimer. *
13 * *
14 * 2. Redistributions in binary form must reproduce the above *
15 * copyright notice, this list of conditions and the *
16 * following disclaimer in the documentation and/or other *
17 * materials provided with the distribution. *
18 * *
19 * 3. Neither the name of The Regents of the University of California*
20 * names of its contributors may be used to endorse or *
21 * promote products derived from this software without *
22 * specific prior written permission. *
23 * *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND *
25 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, *
26 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF *
27 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE *
28 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS *
29 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
30 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED *
31 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON *
33 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, *
34 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY *
35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE *
36 * POSSIBILITY OF SUCH DAMAGE. *
37 * *
38 * Redistribution and use in source and binary forms, with or without *
39 * modification, are permitted provided that the following conditions *
40 * are met: *
41 * 1. Redistributions of source code must retain the above copyright *
42 * notice, this list of conditions and the following disclaimer. *
43 * 2. Redistributions in binary form must reproduce the above copyright *
44 * notice, this list of conditions and the following disclaimer in *
45 * the documentation and/or other materials provided with the *
46 * distribution. *
47 * 3. Neither the name of the University nor the names of its *
48 * contributors may be used to endorse or promote products derived *
49 * from this software without specific prior written permission. *
50 * *
51 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" *
52 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
53 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
54 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS *
55 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, *
56 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
57 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF *
58 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND *
59 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, *
60 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT *
61 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF *
62 * SUCH DAMAGE. *
63 * *
64 * Kurt Shoens (UCB) *
65 * gsf *
66 * *
67 ***********************************************************************/
68 #include "dthdr.h"
69
70 /*
71 ** Change the discipline structure.
72 ** Duplicates caused by the new functions will be removed.
73 ** dt : dictionary
74 ** disc : discipline
75 **
76 ** Written by Kiem-Phong Vo (7/15/95)
77 */
78
79 #if __STD_C
dtmemory(Dt_t * dt,Void_t * addr,size_t size,Dtdisc_t * disc)80 static Void_t* dtmemory(Dt_t* dt,Void_t* addr,size_t size,Dtdisc_t* disc)
81 #else
82 static Void_t* dtmemory(dt, addr, size, disc)
83 Dt_t* dt; /* dictionary */
84 Void_t* addr; /* address to be manipulate */
85 size_t size; /* size to obtain */
86 Dtdisc_t* disc; /* discipline */
87 #endif
88 {
89 if(addr)
90 { free(addr);
91 return NIL(Void_t*);
92 }
93 else return size > 0 ? malloc(size) : NIL(Void_t*);
94 }
95
96 #if __STD_C
dtdisc(Dt_t * dt,Dtdisc_t * disc,int type)97 Dtdisc_t* dtdisc(Dt_t* dt, Dtdisc_t* disc, int type)
98 #else
99 Dtdisc_t* dtdisc(dt,disc,type)
100 Dt_t* dt;
101 Dtdisc_t* disc;
102 int type;
103 #endif
104 {
105 reg Dtsearch_f searchf;
106 reg Dtlink_t *root, *t, *next, **slot, **eslot;
107 reg char* k;
108 reg int rehash;
109 reg Dtdisc_t* old;
110
111 if(!(old = dt->disc) ) /* initialization call from dtopen() */
112 { dt->disc = disc;
113 if(!(dt->memoryf = disc->memoryf) )
114 dt->memoryf = dtmemory;
115 return disc;
116 }
117
118 if(!disc) /* only want to know current discipline */
119 return old;
120
121 searchf = dt->meth->searchf;
122
123 UNFLATTEN(dt);
124
125 if(old->eventf && (*old->eventf)(dt,DT_DISC,(Void_t*)disc,old) < 0)
126 return NIL(Dtdisc_t*);
127
128 dt->disc = disc;
129 if(!(dt->memoryf = disc->memoryf) )
130 dt->memoryf = dtmemory;
131
132 /* no need to do anything further */
133 if((dt->data->type&(DT_STACK|DT_QUEUE)) ||
134 (type&(DT_COMPARF|DT_HASHF)) == (DT_COMPARF|DT_HASHF) )
135 return old;
136
137 if(dt->data->type&DT_HASH)
138 { /* collect all elements into a list */
139 root = next = NIL(Dtlink_t*);
140 for(eslot = (slot = dt->data->htab)+dt->data->ntab; slot < eslot; ++slot)
141 { if(!(t = *slot) )
142 continue;
143 if(next)
144 next->right = t;
145 else root = next = t;
146 while((t = next->right) )
147 next = t;
148 *slot = NIL(Dtlink_t*);
149 }
150
151 /* reinsert them */
152 dt->data->size = 0;
153 dt->data->here = NIL(Dtlink_t*);
154 while(root)
155 { next = root->right;
156 if(!(type&DT_HASHF)) /* new hash value */
157 { k = (char*)OBJ(root,disc); k = KEY((Void_t*)k,disc);
158 root->hash = HASH(dt,k,disc);
159 }
160 (void)(*searchf)(dt,(Void_t*)root,DT_RENEW);
161 root = next;
162 }
163 }
164 else if(!(type&DT_COMPARF) )
165 { dt->data->size = 0;
166 if(dt->data->type&DT_TREE)
167 { root = dt->data->here;
168 dt->data->here = NIL(Dtlink_t*);
169 while(root)
170 { while((t = root->left) )
171 RROTATE(root,t);
172 next = root->right;
173 (void)(*searchf)(dt,(Void_t*)root,DT_RENEW);
174 root = next;
175 }
176 }
177 else /*if(dt->data->type&DT_LIST)*/
178 { root = dt->data->head;
179 dt->data->head = NIL(Dtlink_t*);
180 while(root)
181 { t = root->right;
182 (void)(*searchf)(dt,(Void_t*)root,DT_RENEW);
183 root = t;
184 }
185 }
186 }
187
188 return old;
189 }
190