xnu/libkern/mkext.c

181 static void init_state(struct encode_state *sp)
185     bzero(sp, sizeof(*sp));
188         sp->text_buf[i] = ' ';
190         sp->rchild[i] = NIL;
192         sp->parent[i] = NIL;
203 static void insert_node(struct encode_state *sp, int r)
209     key = &sp->text_buf[r];
211     sp->rchild[r] = sp->lchild[r] = NIL;
212     sp->match_length = 0;
215             if (sp->rchild[p] != NIL)
216                 p = sp->rchild[p];
218                 sp->rchild[p] = r;
219                 sp->parent[r] = p;
223             if (sp->lchild[p] != NIL)
224                 p = sp->lchild[p];
226                 sp->lchild[p] = r;
227                 sp->parent[r] = p;
232             if ((cmp = key[i] - sp->text_buf[p + i]) != 0)
235         if (i > sp->match_length) {
236             sp->match_position = p;
237             if ((sp->match_length = i) >= F)
241     sp->parent[r] = sp->parent[p];
242     sp->lchild[r] = sp->lchild[p];
243     sp->rchild[r] = sp->rchild[p];
244     sp->parent[sp->lchild[p]] = r;
245     sp->parent[sp->rchild[p]] = r;
246     if (sp->rchild[sp->parent[p]] == p)
247         sp->rchild[sp->parent[p]] = r;
249         sp->lchild[sp->parent[p]] = r;
250     sp->parent[p] = NIL;  /* remove p */
254 static void delete_node(struct encode_state *sp, int p)
258     if (sp->parent[p] == NIL)
260     if (sp->rchild[p] == NIL)
261         q = sp->lchild[p];
262     else if (sp->lchild[p] == NIL)
263         q = sp->rchild[p];
265         q = sp->lchild[p];
266         if (sp->rchild[q] != NIL) {
268                 q = sp->rchild[q];
269             } while (sp->rchild[q] != NIL);
270             sp->rchild[sp->parent[q]] = sp->lchild[q];
271             sp->parent[sp->lchild[q]] = sp->parent[q];
272             sp->lchild[q] = sp->lchild[p];
273             sp->parent[sp->lchild[p]] = q;
275         sp->rchild[q] = sp->rchild[p];
276         sp->parent[sp->rchild[p]] = q;
278     sp->parent[q] = sp->parent[p];
279     if (sp->rchild[sp->parent[p]] == p)
280         sp->rchild[sp->parent[p]] = q;
282         sp->lchild[sp->parent[p]] = q;
283     sp->parent[p] = NIL;