Line data    Source code

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