1: /***************************************************************************
2: * _ _ ____ _
3: * Project ___| | | | _ \| |
4: * / __| | | | |_) | |
5: * | (__| |_| | _ <| |___
6: * \___|\___/|_| \_\_____|
7: *
8: * Copyright (C) 1997 - 2019, Daniel Stenberg, <daniel@haxx.se>, et al.
9: *
10: * This software is licensed as described in the file COPYING, which
11: * you should have received as part of this distribution. The terms
12: * are also available at https://curl.haxx.se/docs/copyright.html.
13: *
14: * You may opt to use, copy, modify, merge, publish, distribute and/or sell
15: * copies of the Software, and permit persons to whom the Software is
16: * furnished to do so, under the terms of the COPYING file.
17: *
18: * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
19: * KIND, either express or implied.
20: *
21: ***************************************************************************/
22:
23: #include "curl_setup.h"
24:
25: #include "splay.h"
26:
27: /*
28: * This macro compares two node keys i and j and returns:
29: *
30: * negative value: when i is smaller than j
31: * zero : when i is equal to j
32: * positive when : when i is larger than j
33: */
34: #define compare(i,j) Curl_splaycomparekeys((i),(j))
35:
36: /*
37: * Splay using the key i (which may or may not be in the tree.) The starting
38: * root is t.
39: */
40: struct Curl_tree *Curl_splay(struct curltime i,
41: struct Curl_tree *t)
42: {
43: struct Curl_tree N, *l, *r, *y;
44:
45: if(t == NULL)
46: return t;
47: N.smaller = N.larger = NULL;
48: l = r = &N;
49:
50: for(;;) {
51: long comp = compare(i, t->key);
52: if(comp < 0) {
53: if(t->smaller == NULL)
54: break;
55: if(compare(i, t->smaller->key) < 0) {
56: y = t->smaller; /* rotate smaller */
57: t->smaller = y->larger;
58: y->larger = t;
59: t = y;
60: if(t->smaller == NULL)
61: break;
62: }
63: r->smaller = t; /* link smaller */
64: r = t;
65: t = t->smaller;
66: }
67: else if(comp > 0) {
68: if(t->larger == NULL)
69: break;
70: if(compare(i, t->larger->key) > 0) {
71: y = t->larger; /* rotate larger */
72: t->larger = y->smaller;
73: y->smaller = t;
74: t = y;
75: if(t->larger == NULL)
76: break;
77: }
78: l->larger = t; /* link larger */
79: l = t;
80: t = t->larger;
81: }
82: else
83: break;
84: }
85:
86: l->larger = t->smaller; /* assemble */
87: r->smaller = t->larger;
88: t->smaller = N.larger;
89: t->larger = N.smaller;
90:
91: return t;
92: }
93:
94: /* Insert key i into the tree t. Return a pointer to the resulting tree or
95: * NULL if something went wrong.
96: *
97: * @unittest: 1309
98: */
99: struct Curl_tree *Curl_splayinsert(struct curltime i,
100: struct Curl_tree *t,
101: struct Curl_tree *node)
102: {
103: static const struct curltime KEY_NOTUSED = {
104: (time_t)-1, (unsigned int)-1
105: }; /* will *NEVER* appear */
106:
107: if(node == NULL)
108: return t;
109:
110: if(t != NULL) {
111: t = Curl_splay(i, t);
112: if(compare(i, t->key) == 0) {
113: /* There already exists a node in the tree with the very same key. Build
114: a doubly-linked circular list of nodes. We add the new 'node' struct
115: to the end of this list. */
116:
117: node->key = KEY_NOTUSED; /* we set the key in the sub node to NOTUSED
118: to quickly identify this node as a subnode */
119: node->samen = t;
120: node->samep = t->samep;
121: t->samep->samen = node;
122: t->samep = node;
123:
124: return t; /* the root node always stays the same */
125: }
126: }
127:
128: if(t == NULL) {
129: node->smaller = node->larger = NULL;
130: }
131: else if(compare(i, t->key) < 0) {
132: node->smaller = t->smaller;
133: node->larger = t;
134: t->smaller = NULL;
135:
136: }
137: else {
138: node->larger = t->larger;
139: node->smaller = t;
140: t->larger = NULL;
141: }
142: node->key = i;
143:
144: /* no identical nodes (yet), we are the only one in the list of nodes */
145: node->samen = node;
146: node->samep = node;
147: return node;
148: }
149:
150: /* Finds and deletes the best-fit node from the tree. Return a pointer to the
151: resulting tree. best-fit means the smallest node if it is not larger than
152: the key */
153: struct Curl_tree *Curl_splaygetbest(struct curltime i,
154: struct Curl_tree *t,
155: struct Curl_tree **removed)
156: {
157: static struct curltime tv_zero = {0, 0};
158: struct Curl_tree *x;
159:
160: if(!t) {
161: *removed = NULL; /* none removed since there was no root */
162: return NULL;
163: }
164:
165: /* find smallest */
166: t = Curl_splay(tv_zero, t);
167: if(compare(i, t->key) < 0) {
168: /* even the smallest is too big */
169: *removed = NULL;
170: return t;
171: }
172:
173: /* FIRST! Check if there is a list with identical keys */
174: x = t->samen;
175: if(x != t) {
176: /* there is, pick one from the list */
177:
178: /* 'x' is the new root node */
179:
180: x->key = t->key;
181: x->larger = t->larger;
182: x->smaller = t->smaller;
183: x->samep = t->samep;
184: t->samep->samen = x;
185:
186: *removed = t;
187: return x; /* new root */
188: }
189:
190: /* we splayed the tree to the smallest element, there is no smaller */
191: x = t->larger;
192: *removed = t;
193:
194: return x;
195: }
196:
197:
198: /* Deletes the very node we point out from the tree if it's there. Stores a
199: * pointer to the new resulting tree in 'newroot'.
200: *
201: * Returns zero on success and non-zero on errors!
202: * When returning error, it does not touch the 'newroot' pointer.
203: *
204: * NOTE: when the last node of the tree is removed, there's no tree left so
205: * 'newroot' will be made to point to NULL.
206: *
207: * @unittest: 1309
208: */
209: int Curl_splayremovebyaddr(struct Curl_tree *t,
210: struct Curl_tree *removenode,
211: struct Curl_tree **newroot)
212: {
213: static const struct curltime KEY_NOTUSED = {
214: (time_t)-1, (unsigned int)-1
215: }; /* will *NEVER* appear */
216: struct Curl_tree *x;
217:
218: if(!t || !removenode)
219: return 1;
220:
221: if(compare(KEY_NOTUSED, removenode->key) == 0) {
222: /* Key set to NOTUSED means it is a subnode within a 'same' linked list
223: and thus we can unlink it easily. */
224: if(removenode->samen == removenode)
225: /* A non-subnode should never be set to KEY_NOTUSED */
226: return 3;
227:
228: removenode->samep->samen = removenode->samen;
229: removenode->samen->samep = removenode->samep;
230:
231: /* Ensures that double-remove gets caught. */
232: removenode->samen = removenode;
233:
234: *newroot = t; /* return the same root */
235: return 0;
236: }
237:
238: t = Curl_splay(removenode->key, t);
239:
240: /* First make sure that we got the same root node as the one we want
241: to remove, as otherwise we might be trying to remove a node that
242: isn't actually in the tree.
243:
244: We cannot just compare the keys here as a double remove in quick
245: succession of a node with key != KEY_NOTUSED && same != NULL
246: could return the same key but a different node. */
247: if(t != removenode)
248: return 2;
249:
250: /* Check if there is a list with identical sizes, as then we're trying to
251: remove the root node of a list of nodes with identical keys. */
252: x = t->samen;
253: if(x != t) {
254: /* 'x' is the new root node, we just make it use the root node's
255: smaller/larger links */
256:
257: x->key = t->key;
258: x->larger = t->larger;
259: x->smaller = t->smaller;
260: x->samep = t->samep;
261: t->samep->samen = x;
262: }
263: else {
264: /* Remove the root node */
265: if(t->smaller == NULL)
266: x = t->larger;
267: else {
268: x = Curl_splay(removenode->key, t->smaller);
269: x->larger = t->larger;
270: }
271: }
272:
273: *newroot = x; /* store new root pointer */
274:
275: return 0;
276: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to splay.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / curl / lib