/src/freeradius-server/src/lib/util/rb_expire.c
Line | Count | Source |
1 | | /* |
2 | | * This program is free software; you can redistribute it and/or modify |
3 | | * it under the terms of the GNU General Public License as published by |
4 | | * the Free Software Foundation; either version 2 of the License, or |
5 | | * (at your option) any later version. |
6 | | * |
7 | | * This program is distributed in the hope that it will be useful, |
8 | | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
9 | | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
10 | | * GNU General Public License for more details. |
11 | | * |
12 | | * You should have received a copy of the GNU General Public License |
13 | | * along with this program; if not, write to the Free Software |
14 | | * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA |
15 | | */ |
16 | | |
17 | | /** Red/black expiry tree implementation |
18 | | * |
19 | | * @file src/lib/util/rb_expire.c |
20 | | * |
21 | | * @copyright 2024 Network RADIUS SAS (legal@networkradius.com) |
22 | | */ |
23 | | RCSID("$Id: 2ce557540ad045d8fa5cc25c5b7c163e8d4c702c $") |
24 | | |
25 | | #include <freeradius-devel/util/rb_expire.h> |
26 | | |
27 | | /** Attempt to find current data in the tree, if it does not exist insert it |
28 | | * |
29 | | * Any used node will be inserted into the tail of the expire list, |
30 | | * and will expire at "now + expire->lifetime". |
31 | | * |
32 | | * @param[in] expire to search/insert into. |
33 | | * @param[in] data to find. |
34 | | * @param[in] now the current time |
35 | | * @return |
36 | | * - true if data was inserted. |
37 | | * - false if we can't insert it. |
38 | | */ |
39 | | bool fr_rb_expire_insert(fr_rb_expire_t *expire, void *data, fr_time_t now) |
40 | 0 | { |
41 | 0 | fr_dlist_t *entry = fr_dlist_item_to_entry(expire->head.offset, data); |
42 | 0 | fr_rb_expire_node_t *re = (fr_rb_expire_node_t *) (((uintptr_t) entry) - offsetof(fr_rb_expire_node_t, entry)); |
43 | |
|
44 | 0 | fr_assert(!fr_rb_node_inline_in_tree(&re->node)); |
45 | |
|
46 | 0 | if (!fr_rb_insert(&expire->tree, data)) { |
47 | 0 | return false; |
48 | 0 | } |
49 | | |
50 | 0 | fr_dlist_insert_tail(&expire->head, data); |
51 | |
|
52 | 0 | re->when = fr_time_add_time_delta(now, expire->lifetime); |
53 | |
|
54 | 0 | return true; |
55 | 0 | } |
56 | | |
57 | | void fr_rb_expire_update(fr_rb_expire_t *expire, void *data, fr_time_t now) |
58 | 0 | { |
59 | 0 | fr_dlist_t *entry = fr_dlist_item_to_entry(expire->head.offset, data); |
60 | 0 | fr_rb_expire_node_t *re = (fr_rb_expire_node_t *) (((uintptr_t) entry) - offsetof(fr_rb_expire_node_t, entry)); |
61 | |
|
62 | 0 | fr_assert(fr_rb_node_inline_in_tree(&re->node)); |
63 | |
|
64 | 0 | fr_dlist_remove(&expire->head, data); |
65 | |
|
66 | 0 | fr_dlist_insert_tail(&expire->head, data); |
67 | 0 | re->when = fr_time_add_time_delta(now, expire->lifetime); |
68 | |
|
69 | | #if 0 |
70 | | /* |
71 | | * Expire old entries. |
72 | | */ |
73 | | fr_dlist_foreach(&expire->head, fr_rb_expire_node_t, old) {{ |
74 | | re = (fr_rb_expire_node_t *) (((uintptr_t) old) - offsetof(fr_rb_expire_node_t, entry)); |
75 | | |
76 | | if (old->when > now) break; |
77 | | |
78 | | fr_dlist_remove(&expire->head, &old->entry); |
79 | | |
80 | | fr_rb_delete(&expire->tree, re); |
81 | | } |
82 | | #endif |
83 | 0 | } |