Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2017 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #include "patricia_map.h"
       6             : #ifdef __cplusplus
       7             : extern "C" {
       8             : #endif
       9             : #include "patricia_api.h"
      10             : #ifdef __cplusplus
      11             : }
      12             : #endif
      13             : 
      14        6473 : patroot *patricia_root_init(patroot *root, boolean key_is_ptr, uint16_t klen,
      15             :                         uint8_t koffset)
      16             : {
      17        6473 :     patroot *pat_root = NULL;
      18             : 
      19        6473 :     pat_root = (patroot *)malloc(sizeof(patroot));
      20        6473 :     if (!pat_root) {
      21           0 :         return NULL;
      22             :     }
      23             : 
      24        6473 :     PatriciaMapTable *agent_patroot = new PatriciaMapTable(klen, koffset);
      25        6473 :     if (!agent_patroot) {
      26           0 :         free(pat_root);
      27           0 :         return NULL;
      28             :     }
      29             : 
      30        6473 :     pat_root->agent_patroot = agent_patroot;
      31             : 
      32        6473 :     return pat_root;
      33             : }
      34             : 
      35        6179 : void patricia_root_delete(patroot *root)
      36             : {
      37        6179 :     if (!root) {
      38          81 :         return;
      39             :     }
      40             : 
      41        6098 :     PatriciaMapTable *agent_patroot = (PatriciaMapTable *)root->agent_patroot;
      42        6098 :     delete agent_patroot;
      43             : 
      44        6098 :     free(root);
      45             : 
      46        6098 :     return;
      47             : }
      48             : 
      49        4291 : boolean patricia_add(patroot *root, patnode *node)
      50             : {
      51        4291 :     PatriciaMapTable *agent_patroot = (PatriciaMapTable *)root->agent_patroot;
      52             : 
      53        4291 :     PatriciaNode *agent_patnode = new PatriciaNode(agent_patroot->klen_,
      54        4291 :                                         agent_patroot->koffset_, node, node);
      55             : 
      56        4291 :     bool ret = agent_patroot->Insert(agent_patnode);
      57        4291 :     if (!ret) {
      58           0 :         delete agent_patnode;
      59           0 :         return FALSE;
      60             :     }
      61             : 
      62        4291 :     node->agent_patnode = agent_patnode;
      63        4291 :     return TRUE;
      64             : }
      65             : 
      66        4291 : boolean patricia_delete(patroot *root, patnode *node)
      67             : {
      68        4291 :     PatriciaMapTable *agent_patroot = (PatriciaMapTable *)root->agent_patroot;
      69             : 
      70        4291 :     PatriciaNode *agent_patnode = (PatriciaNode *)node->agent_patnode;
      71             : 
      72        4291 :     bool ret = agent_patroot->Remove(agent_patnode);
      73        4291 :     if (!ret) {
      74           0 :         return FALSE;
      75             :     }
      76             : 
      77        4291 :     delete (PatriciaNode *)node->agent_patnode;
      78             : 
      79        4291 :     return TRUE;
      80             : }
      81             : 
      82       17679 : patnode *patricia_lookup(patroot *root, const void *key)
      83             : {
      84       17679 :     PatriciaMapTable *agent_patroot = (PatriciaMapTable *)root->agent_patroot;
      85             : 
      86       17679 :     PatriciaNode *agent_patnode = new PatriciaNode(agent_patroot->klen_,
      87       17679 :                                         0, NULL, key);
      88       17679 :     if (!agent_patnode) {
      89           0 :         return NULL;
      90             :     }
      91             : 
      92       17679 :     PatriciaNode *found = agent_patroot->Find(agent_patnode);
      93             : 
      94       17679 :     delete agent_patnode;
      95       17679 :     if (!found) {
      96        4655 :         return NULL;
      97             :     }
      98             : 
      99       13024 :     patnode *node = (patnode *)found->knode_;
     100       13024 :     return node;
     101             : }
     102             : 
     103       17235 : patnode *patricia_lookup_least(patroot *root)
     104             : {
     105       17235 :     PatriciaMapTable *agent_patroot = (PatriciaMapTable *)root->agent_patroot;
     106             : 
     107       17235 :     PatriciaNode *agent_patnode = NULL;
     108       17235 :     agent_patnode = agent_patroot->GetNext(agent_patnode);
     109       17235 :     if (!agent_patnode) {
     110       16772 :         return NULL;
     111             :     }
     112             : 
     113         463 :     patnode *node = (patnode *)agent_patnode->knode_;
     114             : 
     115         463 :     return node;
     116             : }
     117             : 
     118           0 : patnode *patricia_lookup_greatest(patroot *root)
     119             : {
     120           0 :     PatriciaMapTable *agent_patroot = (PatriciaMapTable *)root->agent_patroot;
     121             : 
     122           0 :     PatriciaNode *agent_patnode = agent_patroot->GetLast();
     123           0 :     if (!agent_patnode) {
     124           0 :         return NULL;
     125             :     }
     126             : 
     127           0 :     patnode *node = (patnode *)agent_patnode->knode_;
     128             : 
     129           0 :     return node;
     130             : }
     131             : 
     132         651 : patnode *patricia_get_next(patroot *root, patnode *node)
     133             : {
     134         651 :     PatriciaMapTable *agent_patroot = (PatriciaMapTable *)root->agent_patroot;
     135             : 
     136         651 :     PatriciaNode *agent_patnode = node ? (PatriciaNode *)node->agent_patnode : NULL;
     137         651 :     agent_patnode = agent_patroot->GetNext(agent_patnode);
     138         651 :     if (!agent_patnode) {
     139         649 :         return NULL;
     140             :     }
     141             : 
     142           2 :     return (patnode *)agent_patnode->knode_;
     143             : }
     144             : 
     145           0 : patnode *patricia_get_previous(patroot *root, patnode *node)
     146             : {
     147           0 :     PatriciaMapTable *agent_patroot = (PatriciaMapTable *)root->agent_patroot;
     148             : 
     149           0 :     PatriciaNode *agent_patnode = (PatriciaNode *)node->agent_patnode;
     150           0 :     agent_patnode = agent_patroot->GetPrev(agent_patnode);
     151           0 :     if (!agent_patnode) {
     152           0 :         return NULL;
     153             :     }
     154             : 
     155           0 :     return (patnode *)agent_patnode->knode_;
     156             : }
     157             : 
     158           0 : patnode *patricia_lookup_geq(patroot *root, patnode *node)
     159             : {
     160           0 :     PatriciaMapTable *agent_patroot = (PatriciaMapTable *)root->agent_patroot;
     161             : 
     162           0 :     PatriciaNode *agent_patnode = new PatriciaNode(agent_patroot->klen_,
     163           0 :                                         agent_patroot->koffset_, node, node);
     164           0 :     if (!agent_patnode) {
     165           0 :         return NULL;
     166             :     }
     167             : 
     168           0 :     PatriciaNode *found = agent_patroot->Find(agent_patnode);
     169             : 
     170           0 :     if (found) {
     171           0 :         delete agent_patnode;
     172           0 :         return (patnode *)found->knode_;
     173             :     }
     174             : 
     175           0 :     found = agent_patroot->GetNext(agent_patnode);
     176             : 
     177           0 :     delete agent_patnode;
     178           0 :     if (!found) {
     179           0 :         return NULL;
     180             :     }
     181             : 
     182           0 :     return (patnode *)found->knode_;
     183             : }
     184             :