1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0
23e1bbdc3SArnaldo Carvalho de Melo /*
33e1bbdc3SArnaldo Carvalho de Melo * Simple pointer stack
43e1bbdc3SArnaldo Carvalho de Melo *
53e1bbdc3SArnaldo Carvalho de Melo * (c) 2010 Arnaldo Carvalho de Melo <acme@redhat.com>
63e1bbdc3SArnaldo Carvalho de Melo */
73e1bbdc3SArnaldo Carvalho de Melo
83e1bbdc3SArnaldo Carvalho de Melo #include "pstack.h"
984f5d36fSJiri Olsa #include "debug.h"
103e1bbdc3SArnaldo Carvalho de Melo #include <linux/kernel.h>
117f7c536fSArnaldo Carvalho de Melo #include <linux/zalloc.h>
123e1bbdc3SArnaldo Carvalho de Melo #include <stdlib.h>
138520a98dSArnaldo Carvalho de Melo #include <string.h>
143e1bbdc3SArnaldo Carvalho de Melo
153e1bbdc3SArnaldo Carvalho de Melo struct pstack {
163e1bbdc3SArnaldo Carvalho de Melo unsigned short top;
173e1bbdc3SArnaldo Carvalho de Melo unsigned short max_nr_entries;
18*6549a8c0SGustavo A. R. Silva void *entries[];
193e1bbdc3SArnaldo Carvalho de Melo };
203e1bbdc3SArnaldo Carvalho de Melo
pstack__new(unsigned short max_nr_entries)213e1bbdc3SArnaldo Carvalho de Melo struct pstack *pstack__new(unsigned short max_nr_entries)
223e1bbdc3SArnaldo Carvalho de Melo {
2361e94515SArnaldo Carvalho de Melo struct pstack *pstack = zalloc((sizeof(*pstack) +
243e1bbdc3SArnaldo Carvalho de Melo max_nr_entries * sizeof(void *)));
2561e94515SArnaldo Carvalho de Melo if (pstack != NULL)
2661e94515SArnaldo Carvalho de Melo pstack->max_nr_entries = max_nr_entries;
2761e94515SArnaldo Carvalho de Melo return pstack;
283e1bbdc3SArnaldo Carvalho de Melo }
293e1bbdc3SArnaldo Carvalho de Melo
pstack__delete(struct pstack * pstack)3061e94515SArnaldo Carvalho de Melo void pstack__delete(struct pstack *pstack)
313e1bbdc3SArnaldo Carvalho de Melo {
3261e94515SArnaldo Carvalho de Melo free(pstack);
333e1bbdc3SArnaldo Carvalho de Melo }
343e1bbdc3SArnaldo Carvalho de Melo
pstack__empty(const struct pstack * pstack)3561e94515SArnaldo Carvalho de Melo bool pstack__empty(const struct pstack *pstack)
363e1bbdc3SArnaldo Carvalho de Melo {
3761e94515SArnaldo Carvalho de Melo return pstack->top == 0;
383e1bbdc3SArnaldo Carvalho de Melo }
393e1bbdc3SArnaldo Carvalho de Melo
pstack__remove(struct pstack * pstack,void * key)4061e94515SArnaldo Carvalho de Melo void pstack__remove(struct pstack *pstack, void *key)
413e1bbdc3SArnaldo Carvalho de Melo {
4261e94515SArnaldo Carvalho de Melo unsigned short i = pstack->top, last_index = pstack->top - 1;
433e1bbdc3SArnaldo Carvalho de Melo
443e1bbdc3SArnaldo Carvalho de Melo while (i-- != 0) {
4561e94515SArnaldo Carvalho de Melo if (pstack->entries[i] == key) {
463e1bbdc3SArnaldo Carvalho de Melo if (i < last_index)
4761e94515SArnaldo Carvalho de Melo memmove(pstack->entries + i,
4861e94515SArnaldo Carvalho de Melo pstack->entries + i + 1,
493e1bbdc3SArnaldo Carvalho de Melo (last_index - i) * sizeof(void *));
5061e94515SArnaldo Carvalho de Melo --pstack->top;
513e1bbdc3SArnaldo Carvalho de Melo return;
523e1bbdc3SArnaldo Carvalho de Melo }
533e1bbdc3SArnaldo Carvalho de Melo }
543e1bbdc3SArnaldo Carvalho de Melo pr_err("%s: %p not on the pstack!\n", __func__, key);
553e1bbdc3SArnaldo Carvalho de Melo }
563e1bbdc3SArnaldo Carvalho de Melo
pstack__push(struct pstack * pstack,void * key)5761e94515SArnaldo Carvalho de Melo void pstack__push(struct pstack *pstack, void *key)
583e1bbdc3SArnaldo Carvalho de Melo {
5961e94515SArnaldo Carvalho de Melo if (pstack->top == pstack->max_nr_entries) {
6061e94515SArnaldo Carvalho de Melo pr_err("%s: top=%d, overflow!\n", __func__, pstack->top);
613e1bbdc3SArnaldo Carvalho de Melo return;
623e1bbdc3SArnaldo Carvalho de Melo }
6361e94515SArnaldo Carvalho de Melo pstack->entries[pstack->top++] = key;
643e1bbdc3SArnaldo Carvalho de Melo }
653e1bbdc3SArnaldo Carvalho de Melo
pstack__pop(struct pstack * pstack)6661e94515SArnaldo Carvalho de Melo void *pstack__pop(struct pstack *pstack)
673e1bbdc3SArnaldo Carvalho de Melo {
683e1bbdc3SArnaldo Carvalho de Melo void *ret;
693e1bbdc3SArnaldo Carvalho de Melo
7061e94515SArnaldo Carvalho de Melo if (pstack->top == 0) {
713e1bbdc3SArnaldo Carvalho de Melo pr_err("%s: underflow!\n", __func__);
723e1bbdc3SArnaldo Carvalho de Melo return NULL;
733e1bbdc3SArnaldo Carvalho de Melo }
743e1bbdc3SArnaldo Carvalho de Melo
7561e94515SArnaldo Carvalho de Melo ret = pstack->entries[--pstack->top];
7661e94515SArnaldo Carvalho de Melo pstack->entries[pstack->top] = NULL;
773e1bbdc3SArnaldo Carvalho de Melo return ret;
783e1bbdc3SArnaldo Carvalho de Melo }
79c8539e3fSNamhyung Kim
pstack__peek(struct pstack * pstack)80c8539e3fSNamhyung Kim void *pstack__peek(struct pstack *pstack)
81c8539e3fSNamhyung Kim {
82c8539e3fSNamhyung Kim if (pstack->top == 0)
83c8539e3fSNamhyung Kim return NULL;
84c8539e3fSNamhyung Kim return pstack->entries[pstack->top - 1];
85c8539e3fSNamhyung Kim }
86