vnet/vnet/vcgn/index_list.h

   1 /*
   2  *------------------------------------------------------------------
   3  * index_list.h - vector-index-based doubly-linked lists
   4  *
   5  * Copyright (c) 2008-2009 Cisco and/or its affiliates.
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with the License.
   8  * You may obtain a copy of the License at:
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  *------------------------------------------------------------------
  18  */
  19
  20 #ifndef _INDEX_LIST_H_
  21 #define _INDEX_LIST_H_ 1
  22
  23 /* An index we can't possibly see in practice... */
  24 #define EMPTY ((u32)~0)
  25
  26 typedef struct index_slist_ {
  27     u32 next;
  28 } index_slist_t;
  29
  30 /*
  31  * index_slist_addhead
  32  *
  33  * args:  headp -- pointer to e.g. a hash bucket
  34  *       vector -- vector containing the list
  35  *       elsize -- size of an element in this vector
  36  *       offset -- offset in each vector element of this list thread
  37  * index_to_add -- index in the vector to add to the list
  38  *
  39  * Adds new items to the head of the list. Try not to screw up the args!
  40  */
  41 static inline void
  42               index_slist_addhead_inline (index_slist_t *headp,
  43                                           u8 *vector, u32 elsize,
  44                                           u32 offset, u32 index_to_add)
  45 {
  46     index_slist_t *addme;
  47
  48     addme = (index_slist_t *)(vector + offset + elsize*index_to_add);
  49     addme->next = EMPTY;
  50
  51     if (headp->next == EMPTY) {
  52         headp->next = index_to_add;
  53         return;
  54     } else {
  55         addme->next = headp->next;
  56         headp->next = index_to_add;
  57     }
  58 }
  59
  60 /*
  61  * index_slist_remelem
  62  *
  63  * args:  headp -- pointer to e.g. a hash bucket
  64  *       vector -- vector containing the list
  65  *       elsize -- size of an element in this vector
  66  *       offset -- offset in each vector element of this list thread
  67  * index_to_del -- index in the vector to delete from the list
  68  *
  69  * Try not to screw up the args!
  70  */
  71
  72 static inline int
  73               index_slist_remelem_inline (index_slist_t *headp,
  74                                               u8 *vector, u32 elsize,
  75                                               u32 offset, u32 index_to_delete)
  76 {
  77     index_slist_t *findme;
  78     index_slist_t *prev;
  79     index_slist_t *cur;
  80
  81     findme = (index_slist_t *)(vector + offset + elsize*index_to_delete);
  82
  83     if (headp->next == index_to_delete) {
  84         headp->next = findme->next;
  85         findme->next = EMPTY;
  86         return 0;
  87     }
  88
  89     prev = (index_slist_t *)(vector + offset + elsize*headp->next);
  90     cur = (index_slist_t *)(vector + offset + elsize*prev->next);
  91     while (cur != findme) {
  92         if (cur->next == EMPTY)
  93             return (1);
  94         prev = cur;
  95         cur = (index_slist_t *)(vector + offset + elsize*cur->next);
  96     }
  97     prev->next = findme->next;
  98     findme->next = EMPTY;
  99     return 0;
 100 }
 101
 102 void index_slist_addhead (index_slist_t *headp,
 103                           u8 *vector, u32 elsize, u32 offset, u32 index);
 104 int index_slist_remelem (index_slist_t *headp,
 105                          u8 *vector, u32 elsize, u32 offset, u32 index);
 106
 107 typedef struct index_dlist_ {
 108     u32 next;
 109     u32 prev;
 110 } index_dlist_t;
 111
 112 void index_dlist_addtail (u32 head_index, u8 *vector, u32 elsize,
 113                           u32 offset, u32 index_to_add);
 114
 115 u32 index_dlist_remelem (u32 head_index,
 116                          u8 *vector, u32 elsize, u32 offset,
 117                          u32 index_to_delete);
 118 #endif /* _INDEX_LIST_H_ */