Home | History | Annotate | Download | only in util 
      1 /*
      2  * Simple pointer stack
      3  *
      4  * (c) 2010 Arnaldo Carvalho de Melo <acme (at) redhat.com>
      5  */
      6 
      7 #include "util.h"
      8 #include "pstack.h"
      9 #include <linux/kernel.h>
     10 #include <stdlib.h>
     11 
     12 struct pstack {
     13 	unsigned short	top;
     14 	unsigned short	max_nr_entries;
     15 	void		*entries[0];
     16 };
     17 
     18 struct pstack *pstack__new(unsigned short max_nr_entries)
     19 {
     20 	struct pstack *pstack = zalloc((sizeof(*pstack) +
     21 				       max_nr_entries * sizeof(void *)));
     22 	if (pstack != NULL)
     23 		pstack->max_nr_entries = max_nr_entries;
     24 	return pstack;
     25 }
     26 
     27 void pstack__delete(struct pstack *pstack)
     28 {
     29 	free(pstack);
     30 }
     31 
     32 bool pstack__empty(const struct pstack *pstack)
     33 {
     34 	return pstack->top == 0;
     35 }
     36 
     37 void pstack__remove(struct pstack *pstack, void *key)
     38 {
     39 	unsigned short i = pstack->top, last_index = pstack->top - 1;
     40 
     41 	while (i-- != 0) {
     42 		if (pstack->entries[i] == key) {
     43 			if (i < last_index)
     44 				memmove(pstack->entries + i,
     45 					pstack->entries + i + 1,
     46 					(last_index - i) * sizeof(void *));
     47 			--pstack->top;
     48 			return;
     49 		}
     50 	}
     51 	pr_err("%s: %p not on the pstack!\n", __func__, key);
     52 }
     53 
     54 void pstack__push(struct pstack *pstack, void *key)
     55 {
     56 	if (pstack->top == pstack->max_nr_entries) {
     57 		pr_err("%s: top=%d, overflow!\n", __func__, pstack->top);
     58 		return;
     59 	}
     60 	pstack->entries[pstack->top++] = key;
     61 }
     62 
     63 void *pstack__pop(struct pstack *pstack)
     64 {
     65 	void *ret;
     66 
     67 	if (pstack->top == 0) {
     68 		pr_err("%s: underflow!\n", __func__);
     69 		return NULL;
     70 	}
     71 
     72 	ret = pstack->entries[--pstack->top];
     73 	pstack->entries[pstack->top] = NULL;
     74 	return ret;
     75 }
     76