Lines Matching refs:sp
146 static void init_state(struct encode_state *sp)
150 bzero(sp, sizeof(*sp));
153 sp->text_buf[i] = ' ';
155 sp->rchild[i] = NIL;
157 sp->parent[i] = NIL;
168 static void insert_node(struct encode_state *sp, int r)
174 key = &sp->text_buf[r];
176 sp->rchild[r] = sp->lchild[r] = NIL;
177 sp->match_length = 0;
180 if (sp->rchild[p] != NIL)
181 p = sp->rchild[p];
183 sp->rchild[p] = r;
184 sp->parent[r] = p;
188 if (sp->lchild[p] != NIL)
189 p = sp->lchild[p];
191 sp->lchild[p] = r;
192 sp->parent[r] = p;
197 if ((cmp = key[i] - sp->text_buf[p + i]) != 0)
200 if (i > sp->match_length) {
201 sp->match_position = p;
202 if ((sp->match_length = i) >= F)
206 sp->parent[r] = sp->parent[p];
207 sp->lchild[r] = sp->lchild[p];
208 sp->rchild[r] = sp->rchild[p];
209 sp->parent[sp->lchild[p]] = r;
210 sp->parent[sp->rchild[p]] = r;
211 if (sp->rchild[sp->parent[p]] == p)
212 sp->rchild[sp->parent[p]] = r;
214 sp->lchild[sp->parent[p]] = r;
215 sp->parent[p] = NIL; /* remove p */
219 static void delete_node(struct encode_state *sp, int p)
223 if (sp->parent[p] == NIL)
225 if (sp->rchild[p] == NIL)
226 q = sp->lchild[p];
227 else if (sp->lchild[p] == NIL)
228 q = sp->rchild[p];
230 q = sp->lchild[p];
231 if (sp->rchild[q] != NIL) {
233 q = sp->rchild[q];
234 } while (sp->rchild[q] != NIL);
235 sp->rchild[sp->parent[q]] = sp->lchild[q];
236 sp->parent[sp->lchild[q]] = sp->parent[q];
237 sp->lchild[q] = sp->lchild[p];
238 sp->parent[sp->lchild[p]] = q;
240 sp->rchild[q] = sp->rchild[p];
241 sp->parent[sp->rchild[p]] = q;
243 sp->parent[q] = sp->parent[p];
244 if (sp->rchild[sp->parent[p]] == p)
245 sp->rchild[sp->parent[p]] = q;
247 sp->lchild[sp->parent[p]] = q;
248 sp->parent[p] = NIL;
261 struct encode_state *sp;
269 sp = (struct encode_state *) malloc(sizeof(*sp));
270 if (!sp) goto finish;
272 init_state(sp);
288 sp->text_buf[r + len] = *src++;
298 insert_node(sp, r - i);
304 insert_node(sp, r);
307 if (sp->match_length > len)
308 sp->match_length = len;
309 if (sp->match_length <= THRESHOLD) {
310 sp->match_length = 1; /* Not long enough match. Send one byte. */
312 code_buf[code_buf_ptr++] = sp->text_buf[r]; /* Send uncoded. */
315 code_buf[code_buf_ptr++] = (u_int8_t) sp->match_position;
317 ( ((sp->match_position >> 4) & 0xF0)
318 | (sp->match_length - (THRESHOLD + 1)) );
330 last_match_length = sp->match_length;
332 delete_node(sp, s); /* Delete old strings and */
334 sp->text_buf[s] = c; /* read new bytes */
341 sp->text_buf[s + N] = c;
348 insert_node(sp, r);
351 delete_node(sp, s);
358 insert_node(sp, r);
373 if (sp) free(sp);